Can we insert into a stl list while traversing

Question

I have a list of items which I am traversing. While traversing new items get created and they should be inserted at different appropriate positions of the same list.

I am using std::list as its insertion time (ordered) is log(N).

Can this cause any issues as I am using an iterator to the container while inserting into the same? Note that insertion can happen just next to current iterator position too.

If this does not work, what are the other options that I have? Do we have a design pattern or a best practice for this kind of activity?

Answer 1

Yes, you can insert into a given position in a list given its iterator, using list::insert.

The following will insert the value 3 as the second item in the list:

list<int> stuff(/*...*/);
auto it = stuff.begin();
++it;
stuff.insert (it,3);

Specifically, the list::insert function inserts an item just before the iterator that's passed to it. This is the most common way to insert into a list.

Note, however, that std::list's insertion time is not O(log(n)). The complexity of inserting one element into a std::list, at any position (given an iterator), is O(1).

Answer 2

No iterators or references to items in the list are invalidated when something is inserted. So in general what you're asking about is OK.

Answer 3

Inserting into a std::list doesn't invalidate any iterator or reference.

In C++'s STL, when an operation is said to don't invalidate any iterator or reference, means that it is safe to continue working with the same iterator after the operation, or any copy of previous or next iterators of the same container.

Answer 4

Many thanks all.

Just adding a sample code for completion. It does not do exactly what I said but it covers my question.

This runs fine so far.

Answer 5

 


time_t t;
srand((unsigned) time(&t));

list<int> mylist;
mylist.push_back(5);
mylist.push_back(2);
mylist.push_back(1);

for (int& i : mylist) {
    int temp = rand() % mylist.size();
    int j;
    std::list<int>::iterator it1;
    for (it1 = mylist.begin(), j = 0; it1 != mylist.end() && i != j; it1++, j++);
    mylist.insert(it1, temp);

    cout << mylist.size() << ": " << endl;
    for (int& k : mylist) {
        cout << k << " ";
    }
    cout << endl;
}