How C++ Iterator is Really Affected by erase(): vector vs list

Overview

This is an experiment to test the difference between C++ iterator of STL vector and list affected by erase operation and list performs like real linked list.

How C++ Iterator is Really Affected by erase(): vector vs list

The official saying or description about C++ iterators of vector and list are listed as follows:

for list erase:
Data races
The container is modified.
The elements removed are modified. Concurrently accessing or modifying other elements is safe,
although iterating ranges that include the removed elements is not.

for vector erase:
Data races
The container is modified.
None of the elements before position (or first) is accessed, and concurrently accessing or modifying them is safe.
iterator validity
Iterators, pointers and references pointing to position (or first) and beyond are invalidated, with all iterators,
pointers and references to elements before position (or first) are guaranteed to keep referring to the same elements
they were referring to before the call.

So by the above description, I want to confirm:

  1. is the erased iterator indeed invalidated? What exactly does invalidate mean? Can we access that iterator after erasing it?
  2. does the list iterator performs really like the pointer? And the iterators for each entry in the list does not affect each other, by erasing an iterator from a list, will all the other iterators not be affected?
  3. for list iterator, Is it  just like memory address which will not be changed like in a real double linked list? What is exactly the internal structure of this list?

And the following code answers the above questions and I will give my own conclusion after:

#include <vector>
#include <list>
#include <map>
#include <iostream>

using namespace std;

int main() {
    int sz = 6;
    int testcase[] = {0, 1, 2, 3, 4, 5};
    vector<int> vec(testcase, testcase + sz);
    list<int>   dlist(testcase, testcase + sz);

    map<int, vector<int>::iterator> mapForVec;
    map<int, list<int>::iterator> mapForList;

    for (auto it = vec.begin(); it != vec.end(); ++it)     mapForVec[*it] = it;
    for (auto it = dlist.begin(); it != dlist.end(); ++it) mapForList[*it] = it;

    cout << "-------------  after erase for *vec*:" << endl;
    auto itr = mapForVec.find(3);
    mapForVec.erase(itr);
    vec.erase(itr->second);
    cout << "map(3): key = " << itr->first << ", value = " << *(itr->second) << endl;

    cout << (mapForVec[4] == vec.end() - 1 ?
            "The old iterator for element 4 is point to the last element of the newly vector!" :
            "You are wrong!") << endl;

    for (auto it = mapForVec.begin(); it != mapForVec.end(); ++it)
        cout << "key = " << it->first << ", value = " << *(it->second) << endl;

    cout << "-------------  after erase for *list*:" << endl;
    auto itr2 = mapForList.find(3);
    mapForList.erase(itr2);
    dlist.erase(itr2->second);
    cout << "map(3): key = " << itr2->first << ", value = " << *(itr2->second) << endl;
    for (auto it = mapForList.begin(); it != mapForList.end(); ++it)
        cout << "key = " << it->first << ", value = " << *(it->second) << endl;

    return 0;
}

And the following is the output:

-------------  after erase for *vec*:
map(3): key = 3, value = 4
The old iterator for element 4 is point to the last element of the newly vector!
key = 0, value = 0
key = 1, value = 1
key = 2, value = 2
key = 4, value = 5
key = 5, value = 5
-------------  after erase for *list*:
map(3): key = 3, value = 3
key = 0, value = 0
key = 1, value = 1
key = 2, value = 2
key = 4, value = 4
key = 5, value = 5

Well based on the output, my conclusion is that:

  1. the erased iterator could still access the old value although it is not safe to do so, my feeling is that, it is just by chance that we got the correct value in the second list case and the iterator actually is not valid anymore.
  2. the iterator works pretty much like the pointer storing the memory address
  3. for vector, the erase() works by moving all the remaining part of the vector after the erased number forward by one step. But the iterator itself actually do not change, so that is why we see, the old iterator which pointer to 3 now actually point to 4 and the old pointer to 4 actually point to the last position of the newly vector after erase()
  4. for list, the erase() works exactly as the double linked list, the memory address are not necessary continuous, and erase() is just like remove a linked list node in constant time.
  5. By conclusion 3 and 4, the iterator itself does not change value, just like the memory address stored in the iterator is not changed at all.

Summary

This is an experiment to test the difference between C++ iterator of STL vector and list affected by erase operation and list performs like real linked list.

Written on December 15, 2014