Iterators

[kyrresc]

I have just started working on iterators, and I assume this is very basic...
why does not the following code work? It does compile, but I get a bad access error when I run it.

void replace(vector<string> &stringvec, string old, string replacement) {
    
    for (vector<string>::iterator it = stringvec.begin(); it != stringvec.end(); it++) {
        if (*it == old) {
            stringvec.insert(it,replacement);
            
            
        }
    }

[Repeater]

When you change the vector, the iterator you have becomes invalid.

http://www.cplusplus.com/reference/vector/vector/insert/ ( "those pointing to position and beyond are invalidated" and preceding text)

vector::insert returns a valid iterator. That should become your iterator when you do an insert operation.

[kyrresc]

How do I change that?

[Repeater]

You can set an iterator using the = operator.

For example,

it = stringvec.insert(it,replacement);

[nuderobmonkey]

If you want to replace an element, you could do this:

#include <iostream>
#include <vector>

using namespace std;

void replace(vector<string> &stringvec, string old, string replacement) {
    
    for (vector<string>::iterator it = stringvec.begin(); it != stringvec.end(); ++it) {
        if (*it == old) {
            it = stringvec.erase(it);  // it points now to the next element
            it = stringvec.insert(it,replacement); // insert before it
        }
    }
}

int main()
{
    vector<string> vec { "apple", "banana", "cherry" };   
    for ( auto item : vec ) cout << item << " ";
    
    replace( vec, "banana", "hammer");
    
    cout << std::endl;
    for (auto item : vec ) cout << item << " ";
}

output:

apple banana cherry 
apple hammer cherry 

But these operations are very 'expensive', because at erase and insert operations all subsequentially elements will get resorted.

better/cheaper:

void replace(vector<string> &stringvec, string old, string replacement) {
    
    for (vector<string>::iterator it = stringvec.begin(); it != stringvec.end(); ++it) {
        if (*it == old) {
            *it = replacement;
        }
    }
}

[dhayden]

Your code inserts a new element. If you want to replace the existing element, do it in place:

void replace(vector<string> &stringvec, string old, string replacement) {
    
    for (vector<string>::iterator it = stringvec.begin(); it != stringvec.end(); it++) {
        if (*it == old) {
            *it = replacement;
        }
    }
}

You should also familiarize yourself with range-based for loops, which make this sort of thing much easier and less error prone:

for (string &str : stringvec) {
    if (str == old) {
        str = replacement;
    }
}

[kyrresc]

Thanks, I am familiar with range-based for loops. I posted this example to increase my understanding of how iterators work.

Is it some way I can fix my code so you are able to insert elements at a given position in the vector, using insert? I do not want to erase any elements, just insert additional elements using insert.

[nuderobmonkey]

Using like this?

    size_t index = some_index_val;
    stringvec.insert( stringvec.begin()+index, item );

[kyrresc]

Thx, but I am still not 100% certain why

it = stringvec.insert(it,replacement);

doesn't work, while:

it = stringvec.erase(it);  // it points now to the next element
            it = stringvec.insert(it,replacement); // insert before it 

works. Anyone?

[nuderobmonkey]

That's because if you add an item before the iterator, and now you merely increase the iterator by one, the iterator points again to your old element, and thus your comparison at the next iteration of your loop will again be evaluated to 'true'. To break this endless recurrence, you need to increase the iterator after the insert operation by two positions.

void insert_before(vector<string> &stringvec, string item, string to_insert) {
    
    for (vector<string>::iterator it = stringvec.begin(); it != stringvec.end(); ++it) {
        if (*it == item) {
            it = stringvec.insert( it, to_insert );
            ++it;  // Here the Iterator will increased again after insert operation
        }
    }
}

*edited

[kyrresc]

Thank you a lot, that was what I was wondering!!

[kyrresc]

Follow-up: would this be any different if we were working with a list and not a vector? With regards to iterators.

[Peter87]

The same will work for std::list::iterator too.

[Duthomhas]

There’s a lot of messed-up info here.

An iterator is a thinly-veiled pointer. That is why it looks like a pointer and acts like a pointer.

Every container class implements an iterator in the simplest way possible. For example:

  • For a vector, an iterator can’t get any simpler: just be a pointer.
  • For a deque, it gets more complicated because the iterator class must know how to jump from block to block.
  • For a list, the iterator just has to know how to get from one node to the next, and to dereference as the node’s data object.

All this means is that there have to be strict considerations about when an iterator becomes invalid.

  • For a vector, any modification to the vector invalidates all iterators into the vector. This is because a vector resize may move the data() to another spot in memory.
  • For a deque, we can limit the potential damage to only invalidating iterators after the modification point.
  • For a list, we can have the nice property that no iterators are invalidated.

Always, always, refer to the documentation. Repeater only quoted part of the documentation. The full text is:

vector::insert says:

Iterator validity
If a reallocation happens, all iterators, pointers and references related to the container are invalidated.
Otherwise, only those pointing to position and beyond are invalidated, with all iterators, pointers and references to elements before position guaranteed to keep referring to the same elements they were referring to before the call.

Emphasis added

In practice, this means you either need to test for reallocation, or simply assume that any iterators you have are all invalid.


If you are only looking to replace an element, you can do that without invalidating iterators:

for (auto iter = v.begin(); iter != v.end(); ++iter)
  if (*iter = element_to_replace)
    *iter = new_element_value;

If you are looking to insert elements, that takes a little more work. An unoptimized loop might look like this:

auto iter = v.begin();
while ((iter = std::find( v.begin(), v.end(), some_element )) != v.end())
  v.insert( iter, new_element );

Hope this helps.

[edit] friggin bbcode

[dhayden]

If you are looking to insert elements, that takes a little more work.

Another option is to use an index into the array:

for (size_t i=0; i<v.size(); ++i) {
    if (v[i] == some_element) {
       v.insert(v.begin()+i, new_element);
       ++i;  // skip the new element
    }
}