Exercise 9.22

[lafener]

除了iter的值没有改变以外，是否还有迭代器失效的问题？毕竟发生了insert操作。

表9.5中说，向一个vector、string或者deque中插入元素会使得所有指向容器的迭代器、引用和指针失效。

[pezy]

Adding elements to a vector, string, or deque potentially invalidates all existing iterators, references, and pointers into the container.

这个问题会在 9.3.6. Container Operations May Invalidate Iterators 里详细讲解。

那里就会有一个使用 insert 也不会让迭代器失效的例子：

std::vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin();
while (iter != vi.end()) {
    if (*iter % 2) {
        iter = vi.insert(iter, *iter);  // duplicate the current element
        iter += 2; // advance past this element and the one inserted before it
    } else
        iter = vi.erase(iter);
}

[Mooophy]

Agree @pezy
The code in ex9.22 lacks enough detail to tell whether iterators or pointer etc become invalidated or not.

The specific rule goes like this:

vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) [23.3.6.5/1]

from SO

[Mooophy]

Code for ex9.22 :

vector<int>::iterator iter = iv.begin(), mid = iv.begin() + iv.size()/2;
while (iter != mid)
    if (*iter == some_val)
        iv.insert(iter, 2 * some_val);

In this code, we have have no way to see what capacity it has.. No clue to tell if invalidation would happen or not.

[lafener]

@Mooophy 我的意思是：mid位于插入点之后，所以会受到影响而失效。

@pezy 这个例子不太好吧，因为iter在insert之后被重新赋值了。

[pezy]

mid位于插入点之后，所以会受到影响而失效。

这个很好验证。我就针对这句话举例子吧：

std::vector<int> iv = {0,1,2,3,4,5,6,7,8,9};
std::vector<int>::iterator iter = iv.begin(), mid = iv.begin() + iv.size()/2; // refer to 5
iv.insert(iter, -1);
std::cout << *mid << std::endl; // print 5.

显然这里的 mid 是没有失效的。 我是错的。

[Mooophy]

@pezy I think @lafener is right, I didn't notice mid's position.
Try this code:

#include <iostream>
#include <vector>
int main()
{
    std::vector<int> iv = {0,1,2,3,4,5,6,7,8,9};
    auto iter = iv.begin(), mid = iv.begin() + iv.size()/2;
    for(int count = 50; count;   --count )
    {
        iv.insert(iter, -1);
        std::cout << "capacity = " << iv.capacity() << " *mid = " << *mid << std::endl;
    }
    return 0;
}

output on Ubuntu 14.04 LTS ,using GCC 4.8.2:

capacity = 20 *mid = 5
capacity = 20 *mid = 4
capacity = 20 *mid = 3
capacity = 20 *mid = 2
capacity = 20 *mid = 0
capacity = 20 *mid = 0
capacity = 20 *mid = -1
capacity = 20 *mid = -1
capacity = 20 *mid = -1
capacity = 20 *mid = -1
Press to close this window...

[Mooophy]

The key point is reallocation. The runtime should be something like this:

The code above is supposed to print 50 times. But as shown above it only printed 10 times and crashed. That's when iv's size() reached its capacity() i.e. 20. At this point iv performed a reallocation and therefore iterator mid was totally invalidated. The dereferencing operation in expression *mid caused this program crash.

[pezy]

@lafener 的确是对的。

比较新的标准里(草稿 N3690)，对此是如此规定的：

§ 23.3.7.5 / 1
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.

这里要注意的是，before the insertion point.

所以 @Mooophy 的验证代码还没有给出问题的本质，根本不需要50次或是10次，一次就已经失效了。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> iv = {0,1,2,3,4,5,6,7,8,9};
    auto iter = iv.begin(), mid = iv.begin() + iv.size()/2;
    iv.insert(iter, -1);
    std::cout << "capacity = " << iv.capacity() << std::endl;
    std::cout << "iter's pos: " << iter - iv.begin() << std::endl;  // -12
    std::cout << "mid's pos: " << mid - iv.begin() << std::endl;  // -7

    return 0;
}

GCC 4.9.1

这里我自己打自己脸了，上面说“显然”有效，其实一点都不“显然”，上面的代码，可以看到，不仅 mid, 连就在后面一步之遥的 iter 都已经失效了。(想了一下，说失效不准确，应该是未定义行为了)

[Mooophy]

Awesome.
I bet this discussion made everyone here understand this pitfall better.Nothing about face punching.

[Mooophy]

Thx @lafener for issue reporting.

[frank67]

@pezy , @Mooophy
I apologize for the necrobump, your code:
https://github.com/Mooophy/Cpp-Primer/blob/master/ch09/ex9_22.cpp
with these input: vector<int> iv={1, 2, 1, 2, 2, 1, 1, 1, 1, 1}; ... insertDoubleValue(iv, 1);
return: 25 1 2 2 1 2 2 2 1 1 1 1 1
instead of: 2 1 2 2 1 2 2 1 1 1 1 1
The code I wrote is:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
        vector<int> iv={1, 2, 1, 2, 2, 1, 1, 1, 1, 1};
        vector<int>::iterator   iter = iv.begin();
        vector<int>::size_type  mid = iv.size()/2;
        int some_val=1;

        // see chapter §9.3.1:
        // Adding elements to a sequential container will invalidate iterator thus we cannot rely on
        // these for equality: while(iter != mid)
        while (mid)     {
                if (*iter == some_val)  {
                        iter=iv.insert(iter, 2 * some_val);     // handling the return iterator makes it valid
                        ++iter; // now "iter" points to the element matched in the if(...) condition
                }
                ++iter; // advance to next element 
                --mid;  // decrement middle value
        }

        for(const auto& i : iv)
                cout << i << " " << flush;
        cout << endl;

        return EXIT_SUCCESS;
}

I think my code is right IMHO, please could you give me any hints?
Best regards.

[Mooophy]

Hi @frank67

I must admit that the code in repo looked a little bit misleading. I've updated it like below:

#include <iostream>
#include <vector>

void double_and_insert(std::vector<int>& v, int some_val)
{
    auto mid = [&]{ return v.begin() + v.size() / 2; };
    for (auto curr = v.begin(); curr != mid(); ++curr)
        if (*curr == some_val)
            ++(curr = v.insert(curr, 2 * some_val));
}

int main()
{
    std::vector<int> v{ 1, 9, 1, 9, 9, 9, 1, 1 };
    double_and_insert(v, 1);

    for (auto i : v) 
        std::cout << i << std::endl;
}

I think the point here is iterator invalidation. Your implementation has modified the original code from the exercise too much, such as mid became an unsigned.

[frank67]

@Mooophy sorry I cannot help you, I don't know what kind of object is mid now. There is a bug, it doesn't insert before the last element of the middle range. For sake of clarity I suggest to print the container's elements this way:

    for (auto i : v)
        std::cout << i << " " << std::flush;
    std::cout << std::endl;

given these value:

std::vector<int> v={1, 2, 1, 2, 2, 1, 1, 1, 1, 1};
//                              ^ last element, then five times 1
double_and_insert(v, 2);

your code returns:

1 4 2 1 4 2 2 1 1 1 1 1

mine instead:

1 4 2 1 4 2 4 2 1 1 1 1 1

I tried to increment mid changing your code this way:

auto mid = [&]{ return ++(v.begin() + v.size() / 2); };

but I got seg-fault at runtime, sorry again:confounded:
Best regards

[Mooophy]

It's not a bug..

[Mooophy]

@frank67
Basically, it's a little bit tricky to explain what's going on here.Let's go back to the exercise description:

Exercise 9.22: Assuming iv is a vector of ints, what is wrong with the following program? How might you correct the problem(s)?

    vector<int>::iterator iter = iv.begin(), mid = iv.begin() + iv.size() / 2;
    while (iter != mid)
        if (*iter == some_val)
            iv.insert(iter, 2 * some_val);

From the code above, we may interpret author's original abstraction intention in two different ways:

• mid refereed to the initial middle index permanently.
• mid refereed to the dynamic middle index that would change when a new item was inserted into first half of the container.

IMHO, your code was implementing the first interpretation, whereas mine the second. That's why I was using a function object for mid. It's hard to say which one is better.Besides, the key point here is iterator invalidation rules, rather than guessing what the author was thinking about. So can we forget it and move on to something more meaningful?

Thx for contribution.

[frank67]

Ok, you can also consider to change the Pezy code applying this 2 lines patch to the insertDoubleValue function (note also the mid decrement):

void insertDoubleValue(vector<int> &iv, int some_val)
{
    vector<int>::iterator iter = iv.begin(), mid = --(iv.begin() + iv.size()/2);
    while (iter != mid)
        if (*mid == some_val)
            mid = iv.insert(mid, 2 * some_val);
        else --mid;

     if (*mid == some_val)
        mid = iv.insert(mid, 2 * some_val);
}

In order to choice the first interpretation, otherwise if you prefer to recalculate the middle iterator each for-loop then your code will be fine. But it looks like to me that it isn't a required feature from the exercise.
I'm not an expert (as you have surely deduced) but to avoid iterators invalidation the strategy to decrement the mid iterator up to beginning it's safe IMHO.
I choose the first interpretation: the Pezy code with my change as above 😏
Thank you for your patience, best regards.

[LinyuWang]

I wanna ask everyone a question. Whether the iterator iter is changed. According to the problem9.22,the iter is not assigned after insertion operation, so i think iter is not changed, thus after the first insertion, the iter is invalidate.

[frank67]

"iter" doesn't appear in the provided exercise's solution https://github.com/Mooophy/Cpp-Primer/blob/master/ch09/ex9_22.cpp what code are you asking for comments?

[LinyuWang]

exercise 9.22 in 《c ++ primer》
vector::iterator iter = iv.begin(), mid = iv.begin() + iv.size()/2;
while (iter != mid)
if (*iter == some_val)
iv.insert(iter, 2 * some_val);

[frank67]

Yes, of course, you cannot test for equality iterators of a container that it grows (if you not previously reassigned these) because it could be reallocated.
Have you your own exercise's solution?

[l3518563]

awesome!!!I have learnt so much.

[Layty]

I think we can use the iv.end() is also ok

void insertDoubleValue2(vector<int>& iv, int some_val)
{
    auto cursor = iv.size() / 2;
    auto iter = iv.begin();
    while (iter != iv.end() - cursor) {
        if (*iter == some_val) {
            iter = iv.insert(iter, 2 * some_val);
            ++iter;
        }
        ++iter;
    }
}