STL Iterators

[ironic]

Hi!

I'm experiencing some difficulties with my iterator I am using in a loop...
Let's assume the following code:

multimap<string, string> testMap;
for (multimap<string, string>::iterator iter=testMap.begin(); iter!=testMap.end(); iter++) {
// inside the for loop, testMap-items are accessible by (*iter).first (key) or (*iter).second (value)
...
}

If I call another function inside this for-loop that inserts a new item to my testMap (lets assume its global and there is already an item in the map because the code above would not be working this way though there's no element in it), then it happens that the iterator doesn't loop through all the newely inserted items. The problem is that SOME newely inserted elements are actually looped!!!

Is there any possibility to solve this problem, meaning to loop through all items that are newely inserted? I thought that if the method 'insert()' of a map is called, then the map's 'end()' function would point to the last inserted object.
Maybe if i use a linked list? Like 'list'?

By the way, I'm using Ubuntu 8.04 (Hardy) and the compiler is GNU G++.

ironic

[bnbertha]

You have to be really careful inserting or deleting elements in a container in the middle of cycling through it with iterators. You cannot rely on what the iterators point to after such an operation so you have to explicitly point it where you want it.

std maps order the data so what you insert won't necessarily be put where your iterator is currently pointing, and it could argued that it is dangerous to try and second guess where the entry will be inserted. The testMap.end() is evaluated each time you loop so that should cope with the changes you make to the maps' contents. It's difficult to be more specific with knowing why you are inserting elements, what conditions you are looking for etc.

If you need to do an operation on a newly inserted element, I would do a find to get an iterator to it after the insert. It's the only guaranteed way after you change the contents of the map.

You could do it with a linked list but you'll have a lot more code to write.

[Duthomhas]

Exactly. You cannot both iterate through a multimap (or any other associative container) and insert items at the same time. You must do them separately.

I recommend that you simply build a temporary multimap then join it after you have iterated through the first.

void quux( multimap <string, string> &testMap )
  {
  multimap <string, string> toAdd;

  // Play with my multimap
  for ( multimap <string, string> ::iterator iter = testMap.begin(); iter != testMap.end(); iter++)
    {
    ...
    // I found a reason to add elements to testMap
    // But I can't do it yet, so I'll save it for later
    toAdd.insert( something );
    ...
    }

  // OK, it is later :-)
  testMap.insert( toAdd.begin(), toAdd.end() );
  }

Hope this helps.

[ironic]

Hi bnbertha and Duoas.
First of all I'd like to thank you for your answers, I did not know that you can't rely on where the items are being inserted (I thought thats what iteraters are for...).

The problem with your code, Duoas, is, that you won't cycle through newely inserted items, so this loop would exactely cycle testMap.size() times. But I need a way to cycle new items as well because I'm doing other things with these new elements inside the loop. And unfortunately I cannot use find() because I don't know what the associative container of the specific next object is called.

By the way there is no way to find() elements through values instead of keys right?

But thanks for your help mates! :D

[bnbertha]

Would it be possible to manipulate what you put in the container, before you put it in? It wold save you a lot of grief.

Or in the example Duoas provided, cycle through the temporary container to make your changes before adding it to the main container

You can do find on 'second' but you need to use functors or function objects to do it.

[ironic]

Hi bnbertha

Would it be possible to manipulate what you put in the container, before you put it in? It would save you a lot of grief.

I'm not sure what you exactely mean, but yes I am inserting an item like Duoas did, so I could manipulate the key and the value (Are you thinking about returning the key?).

Or in the example Duoas provided, cycle through the temporary container to make your changes before adding it to the main container

The problem is that i have to cycle through n new items, so if i just cycle again through the whole map like you think, it could be that i even add more items in this loop because i call the same function... So it has to be sumething more dynamic...

thanks for helping!

[Duthomhas]

Perhaps if you could give us a better idea of exactly what you are trying to accomplish (in other words, what is your data and what are you trying to do with it), we might be able to better help.

Cycling through a container and modifying it at the same time are conceptually incompatible.

There is nothing particularly oddball about the problem. A container:
a c q r v z
Let's iterate. We read a, then c, then q, and now we are looking at r:
a c q r v z . . . ^ . .
Now to insert a bunch of stuff:
a b c h j n q r t u v z
The question now is, where do we continue?
If we were indexing by position (0, 1, 2, ...) we have:
a b c h j n q r t u v z . . . ^ . . . . . . . .
which is wrong.
If we are iterating by key, we have:
a b c h j n q r t u v z . . . . . . . ^ . . . .
which is also probably wrong.
But there is one other consideration. By inserting, existing elements may have been moved in memory. So we might have:
a b c h j n q r t u v z . . . . . . . . . . . . . . . . . . . ^
which is definitely wrong.


There are really only two answers:
1) insert and iterate separately
2) tag visited elements, and after inserting reset to the beginning of the container

Let us know what you want to do.

[ironic]

Ok Duos, thank you for your very detailed description. I already knew that you can't rely on which element has already been cycled and which not.
So I'm more and more considering using a self-made double linked list (next and previous pointer), so i always now which is the next element. In the for loop i then check if the pointer is invalid (null because i default-set it to null). What do you think of that?

[Duthomhas]

Well, I can't comment intelligently on that because I still don't know exactly what you are trying to accomplish. If you just want a generic data structure, that would certainly work. It just might not be the best choice for your problem.