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

user_13770014 0
Viewed 2175

Having this code:

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;
   }
}

Which takes quite a long to compile, but will finally do with the proper output

1
2
3

The problem is (without knowing the inner implementation of std::vector, is it c-style array? or more complex structure?), how can it properly find those elements in the for(int i:vec2), when the address (pointers) of those elements are not sequential? (i.e. because of the shifting of the iterator/pointer by 99999999).

I thought there was a requirement for OutputIterator to have that property, that only one-access, one-shift could be performed on it. But when you shift(add) it more than once between accessing them, then there is a gap, which is quite huge in my case. So how does it compile?

stdvector iterator templates algorithm c++
3 Answers

You've been fooled.

The iterator returned by std::back_inserter has it++ as a no-op. So those 'gaps' you are creating? Yeah that's all doing nothing.

user_5656350

Your for-loop

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

does not do what you think. It has no effect on there, other than iterating from 0 to 99999999.

When you look into the std::back_insert_iterator, it says

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

or as stated in 23.5.2.1.1 it simply returns the back_insert_iterator, without doing anything into it.

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

#Returns: *this.

Meaning dest++; has no effect. This makes entire assumptions you made, completely not valid. The program took long to execute only because of the iteration from 0 to 99999999.

It raises the question: Then why there is an std::back_insert_iterator<Container>::operator++ overload at all?

From 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.

user_96098400

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

Not quite, but the buffer that it creates is structurally identical.

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

The premise is faulty. The memory addresses of vector elements are contiguous. One object begins immediately after another.

Also, whether they are sequential or not doesn't matter. You can equally well iterate over a linked list even though those elements are not contiguous in memory.

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

This assumption is not true.

In particular case of std::back_insert_iterator, the documentation says:

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

Does nothing.

user_20793030
Related