8

Following code snippet provides a very weird output. I was expecting an overflow( Python gives a MemoryError)

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> a{1,2,3};

    for( auto const & item : a)
        a.push_back(item);


    for( auto const & item : a)
        std::cout<<item<<',';

    return 0;
}

Output: 1,2,3,1,0,3,

How do I interpret this result?

If you do a similar thing in Python, it gives a memory error.

>>> a = range(0,20)
>>> for i in a:
    a.append(i)



Traceback (most recent call last):
  File "<pyshell#3>", line 2, in <module>
    a.append(i)
MemoryError

>>>

This question came to my mind, because above way of writing code is considered to be bound-safe. And for bound safety container should not grow/shrink during foreach type iteration. So, this is a leaky abstraction.

Is there a way one can wrap this foreach loop so that any operation causing size-modification/reallocation is not allowed in the loop body.

g-217
  • 2,069
  • 18
  • 33

2 Answers2

18

In C++ adding elements to a vector may cause reallocation of the contained data, which will invalidate all iterators. That means you can't loop over the vector using iterators (which is what the range-based for loop does) while also inserting new elements.

You can however iterate using indexes and use the vector size as condition, since indexes will always be the same.

Some programmer dude
  • 400,186
  • 35
  • 402
  • 621
  • This question came to my mind, because above way of writing code is considered to be bound-safe. Isn't it a leaky abstraction – g-217 Mar 11 '16 at 11:34
  • Everyone in C++ committee advocates these loops and vouches for bound-safety. Without size of container being constant we can't achieve bound safety. – g-217 Mar 11 '16 at 11:46
  • This answer is gold. I teared my hears because of this problem. – Nurbol Alpysbayev Sep 29 '19 at 08:58
5

If the vector is resized, the iterator will become invalid.

You could do it if you reserve in advance.

Keep in mind that for range will operate on the iterator bounds defined before any changes are made. So will only get a copy of your list appended.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> a{1,2,3};

    a.reserve(10);           // 10 should be enough to get a copy without reallocating
    for( auto const & item : a)
        a.push_back(item);

    for( auto const & item : a)
        std::cout<<item<<',';

    return 0;
}

Output:

1,2,3,1,2,3,

I would not recommend an approach like this because I don't consider it clean or clear. However, if you refer to the standard, this behaviour is expected:

23.3.6.5 vector modifiers

With respect to the use of insert,emplace,emplace_back, push_back.

Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

That is, if no reallocation happens, you can trust your iterators before the insertion point. So as long as the capacity of your vector is high enough, you can append with no problems.

Juan Leni
  • 6,982
  • 5
  • 55
  • 87
  • why doesn't C++ makes the size of std::vector constant i.e. no reallocation. because above code does not make any sense. – g-217 Mar 11 '16 at 11:30
  • `std::vector` is able to grow. If you want the size to be constant you should `use std::array` – Juan Leni Mar 11 '16 at 11:31
  • This question came to my mind, because above way of writing code is considered to be bound-safe. Isn't it a leaky abstraction – g-217 Mar 11 '16 at 11:35
  • @mtk99 There is a nother crucial difference between `std::vector` and `std::array` though, that may make `std::array` unisable: The vector allocate memory on the heap, while the array is allocated on the stack (if defined as a local variable) by the compiler at the time of compilation. – Some programmer dude Mar 11 '16 at 11:36
  • @GautamJha. I appended some information with respect to the C++ standard – Juan Leni Mar 11 '16 at 11:45