Iterating, inserting and removing?

Dream output:

 /* DREAM OUTPUT:
 INT: 1
 TESTINT: 1
 TESTINT: 2
 TESTINT: 23
 TESTINT: 24
 TESTINT: 25
 TESTINT: 3
 TESTINT: 4
 TESTINT: 5
 TESTINT: 6
 INT: 23
 INT: 24
 INT: 25
 INT: 3
 INT: 4
 INT: 5
 INT: 6

Problem

 ERROR 1: Not erasing the '2' causes a bizzare effect.
 ERROR 2: Erasing the '2' causes memory corruption.

Code

 #include <cstdlib>
 #include <iostream>
 #include <vector>

 int main(int argc, char* argv[])
 {
    std::vector<int> someInts;

    someInts.push_back(1);
    someInts.push_back(2);
    someInts.push_back(3);
    someInts.push_back(4);
    someInts.push_back(5);
    someInts.push_back(6);

    for(std::vector<int>::iterator currentInt = someInts.begin();
        currentInt != 开发者_运维技巧someInts.end(); ++currentInt)
     if(*currentInt == 2)
     {
        std::vector<int> someNewInts;

        someNewInts.push_back(23);
        someNewInts.push_back(24);
        someNewInts.push_back(25);

        someInts.insert(currentInt + 1, someNewInts.begin(), someNewInts.end());
        //someInts.erase(currentInt);

        for(std::vector<int>::iterator testInt = someInts.begin();
            testInt != someInts.end(); ++testInt)
         std::cout << "TESTINT: " << *testInt << '\n';
     }
     else
        std::cout << "INT: " << *currentInt << '\n';

    return 0;
 }

The code is pretty self-explanatory, but I'd like to know what's going on here. This is a replica using ints of what's happening in a much larger project. It baffles me.

Inserting elements into a vector causes the iterators asociated with it to be invalid, since the vector can grow and thus it reallocates its internal storage space.

As someInts.erase(currentInt); invalidates currentInt you can't use it until you set it right.

It so happens that erase() returns a valid iterator in the list to continue with.

An iterator that designates the first element remaining beyond any elements removed, or a pointer to the end of the vector if no such element exists.

Try

currentInt = someInts.erase(currentInt);

which would put the outer loop at '23' the start of your test data and step to '24' for the next loop.

You need to understand the differences between the stl collections.

A Vector is a continuous (usually) block of memory. Whem you insert into the middle, it tries to be helpful by re-allocating enough memory for the existing data plus the new, then copying it all to the right places and letting you continue as if nothing had happened. However, as you're finding - something has happened. Your iterators that used to refer to the old memory block, are still pointing there - but the data has been moved. You get memory errors if you try to use them.

One answer is to determine where the iterator used to point, and update it to point to the new location. Typically, people use the [] operator for this, but you can use begin() + x (where x is the index into the vector).

Alternatively, use a collection whose iterators are not invalidated by inserting. The best one for this is the list. Lists are constructed from little blocks of memory (1 per item) with a pointer to the next block along. This makes insertion very quick and easy as no memory needs to be modified, just the pointers to the blocks either side of the new item. Your iterator will still be valid too!

Erasing is just the same, except once you delete the item your iterator refers to, its invalid (obviously) so you cannot make any operation on it. Even ++ operator will not work as the memory might have changed in a vector, or the list pointers be different. So, you can first get an iterator to the next element, store it and then use that once you've deleted an item, or use the return value from the erase() method.

If you were to use list as the collection instead of vector, you would not get random-access and it might use more memory but you would have constant-time insertion in the middle of the collection and doing so would not invalidate your iterators.

The exception would be the one you were erasing, so you would not be able to ++ it at the end of the loop. You would have to handle this situation by storing a copy of its next element.