std::vector 如何访问元素之间有巨大差距的元素？

Question

有这个代码：

template <class IIt, class OIt>
OIt copy2(IIt begin, IIt end, OIt dest)
{
   while (begin != end)
   {
      //make gap between element addresses
      for (int i = 0; i < 99999999; i++)
      {
         dest++;
      }
      *dest++ = *begin++;
   }
   return dest;
}

int main(int argc, char** argv)
{
   vector<int> vec({ 1, 2, 3 });
   vector<int> vec2;
   copy2(vec.begin(), vec.end(), back_inserter(vec2));
   for (int i : vec2)
   {
      cout << i << endl;
   }
}

编译需要很长时间，但最终会得到正确的输出

1
2
3

问题是（不知道std::vector的内部实现，是c-style数组？还是更复杂的结构？），怎么办正确地找到 for(int i:vec2) 中的那些元素，当那些元素的地址（指针）是 而不是 顺序？（即 因为 iterator/pointer 移动了 99999999）。

我认为 OutputIterator 需要属性，只能对其执行一次访问，一次轮班。但是当你在访问它们之间不止一次地移动（添加）它时，就会有一个差距，这对我来说是相当大的。那么它是如何编译的呢？

Answer 1

你被骗了

std::back_inserter返回的迭代器有it++ as a no-op。所以那些 'gaps' 你正在创造？是的，这就是什么都不做。

Answer 2

std::vector, is it c-style array?

不完全是，但它创建的缓冲区在结构上是相同的。

when the address (pointers) of those element are not sequential?

前提错误。向量元素的内存地址是连续的。一个对象紧接着另一个对象开始。

此外，它们是否连续并不重要。即使这些元素在内存中不连续，您也可以同样很好地遍历链表。

OutputIterator ... But when you shift(add) it more then once between accessing them, then there is a gap

这个假设是不正确的。

在 std::back_insert_iterator 的特殊情况下，文档说：

std::back_insert_iterator<Container>::operator++

Does nothing.

Answer 3

你的 for 循环

for (int i = 0; i < 99999999; i++)
{
    dest++;
}

没有按照你的想法去做。除了从 0 迭代到 99999999.

之外，它在那里没有任何影响

当您查看 std::back_insert_iterator 时，它显示

[...]. Incrementing the std::back_insert_iterator is a no-op.

或如 23.5.2.1.1 中所述，它只是 returns back_insert_iterator，没有对其进行任何操作。

constexpr back_insert_iterator& operator++();
constexpr back_insert_iterator  operator++(int);

#Returns: *this.

意思是dest++;没有作用。这使得您所做的整个假设完全无效。该程序执行时间很长，只是因为从 0 到 99999999.

的迭代

它提出了一个问题：那么为什么会有 std::back_insert_iterator<Container>::operator++ 过载呢？

来自 cpprefereence std::back_insert_iterator<Container>::operator++:

Does nothing. These operator overloads are provided to satisfy the requirements of LegacyOutputIterator. They make it possible for the expressions *iter++=value and *++iter=value to be used to output (insert) a value into the underlying container.

std::vector 如何访问元素之间有巨大差距的元素？

How can std::vector access elements with huge gaps between them?

c++

algorithm

templates

iterator

stdvector