🔒 Locked 🎮 Unity

std::map iterator increment issue

Started by gcooper Nov 17, 2014 at 12:34 AM 7 replies 3.6k views

Original Post

Nov 17, 2014 at 12:34 AM

Suppose I have a class AS, and I make a map that contains pointers of that type, and uses as keys, the addresses of AS objects, so:

std::map mymap;

Suppose I add 2 items. And execute the following loop.

typedef std::map>::iterator it_type;

for(it_type iterator = mymap.begin(); iterator != mymap.end(); iterator++) {

iterator->first->update().

}

I all works fine. Then,suppose I delete one item.

And execute the loop again.

That loop raises an error saying that it cannot increment the iterator.

What could be the problem?

alvaro

Nov 17, 2014 at 12:48 AM

Maybe you can post exact code. Ideally you would post a tiny program that shows the odd behavior you are describing.

One note, though: Unless all the pointers you are using as keys are taken from the same array, chances are you are invoking undefined behavior.

ApochPiQ

Nov 17, 2014 at 1:56 AM

This is a common and trivial issue. Look up iterator invalidation and something like "remove element from map while iterating." There are dozens of places that have good answers.

gcooper

Nov 17, 2014 at 12:42 PM

One note, though: Unless all the pointers you are using as keys are taken from the same array, chances are you are invoking undefined behavior.

Yes, the pointer keys I am using are not from the same array. Can you explain a bit, how this generates undefined behavior? I mean, since they're pointers, to compare the keys, the addresses are the only thing that is compared, right?

This is a common and trivial issue. Look up iterator invalidation and something like "remove element from map while iterating." There are dozens of places that have good answers.

Well, I'm not sure if I explained correctly, but I delete the item from the map, before actually creating an iterator and looping through it(so I'm not deleting anything while iterating it).

As for the code, I'll try to get access to it as soon as possible(I don't work alone on it, and I currently don't have access at this time).

alvaro

Nov 17, 2014 at 1:20 PM

[background=#fafbfc]One note, though: Unless all the pointers you are using as keys are taken from the same array, chances are you are invoking undefined behavior. [/background]

Yes, the pointer keys I am using are not from the same array. Can you explain a bit, how this generates undefined behavior? I mean, since they're pointers, to compare the keys, the addresses are the only thing that is compared, right?

That's only one possible implementation. The language says what happens if you compare pointers within the same array, or within a struct. But in general the result is unspecified. That means that pointers are not guaranteed to satisfy the "strict weak ordering" requirement for keys in a map, which in turn probably results in undefined behavior.

http://en.cppreference.com/w/cpp/language/operator_comparison#Pointer_comparison_operators

https://www.sgi.com/tech/stl/StrictWeakOrdering.html

NightCreature83

Nov 17, 2014 at 1:23 PM

Ok tip one when working with multiple people on a project setup a source control solution so that you both can access the source files at the same time. There is SVN, Mercurial, Git, Perforce and even Team Foundation, some of these will have free online depots like github or similar.

rozz666

Nov 17, 2014 at 7:12 PM

That means that pointers are not guaranteed to satisfy the "strict weak ordering" requirement for keys in a map, which in turn probably results in undefined behavior.

While this is true for operator<, std::less for pointer guarantees correct ordering (source: http://en.cppreference.com/w/cpp/utility/functional/less).

alvaro

Nov 17, 2014 at 7:46 PM

That means that pointers are not guaranteed to satisfy the "strict weak ordering" requirement for keys in a map, which in turn probably results in undefined behavior.

While this is true for operator<, std::less for pointer guarantees correct ordering (source: http://en.cppreference.com/w/cpp/utility/functional/less).

I did not know that. Thanks!

Zipster

Nov 17, 2014 at 8:00 PM

Can the update() method cause the map to be modified in any way, perhaps indirectly at some point down the call chain?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.