Back to General and Gameplay Programming

std::map of iterators?

General and Gameplay Programming Programming

Started by _Sigma March 03, 2008 11:56 AM

7 comments, last by _Sigma 16 years, 1 month ago

_Sigma

792

Author

March 03, 2008 11:56 AM

I have a std::map like thus:


std::map<std::string,myclass *> myMap;

However, there are some items in myMap which I require access to, however these items change. So I was thinking of doing something like:


std::map<std::string, myclass *> myMAP;
std::map<std::string, myclass *>::iterator it = ... ;
std::map<std::string, std::map<std::string, myclass *>::iterator> myIterators;

myIterators would store iterators into myMap for simple access. That is, I don't have to iterate throughout myMap to find the items that I'm interested in, I can just use ptrs to myMap; Is there a reason this is a bad idea? Is there a better way of handling this?

iMalc

2,466

March 03, 2008 12:25 PM

I'd say its probably asking for trouble.
The thing is, you don't have to "iterate throughout myMap" to find each item. Searches in a map are O(log n) if you do it properly using 'find'. Don't use for_each!
So find operations probably aren't slow enough to justify what you've suggested doing.

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

_Sigma

792

Author

March 03, 2008 01:50 PM

I am aware that search as O(logn) - that is why I am using it. However, there are times when I need to iterate through the whole container. When I iterate through the whole container, I'm not checking the key, rather a bool value in MyClass.

Why do you say this is asking for trouble?

Zakwayda

2,389

March 03, 2008 02:20 PM

Quote:Original post by _Sigma
I am aware that search as O(logn) - that is why I am using it. However, there are times when I need to iterate through the whole container. When I iterate through the whole container, I'm not checking the key, rather a bool value in MyClass.

Why do you say this is asking for trouble?

Assuming that you can store iterators in a map as in your example (I don't see why you wouldn't be able to, but I've never tried it), the (potential) problem I see is that the iterators are 'dumb'; that is, if the target map does happen to be modified in some way, the iterators referencing it may become invalid.

As an alternative, how about storing smart pointers rather than raw pointers in your map? That way, you could pass out references (strong or weak, whichever is appropriate) to the stored items, and bypass the iterator business entirely. (Plus, this would offer the added benefit of automatic cleanup.)

_Sigma

792

Author

March 03, 2008 03:23 PM

Hmm...I didn't think of smart pointers...

Quote:
the (potential) problem I see is that the iterators are 'dumb'; that is, if the target map does happen to be modified in some way, the iterators referencing it may become invalid.

According to here,

Quote:
Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

So the iterators should always remain valid. I don't ever remove individual elements, so deletion is not an issue.

swiftcoder

18,997

March 03, 2008 03:32 PM

Quote:Original post by _Sigma
I am aware that search as O(logn) - that is why I am using it. However, there are times when I need to iterate through the whole container. When I iterate through the whole container, I'm not checking the key, rather a bool value in MyClass.

My intuition is that you should be maintaining a separate map, but that it should hold a pointer to the object itself, rather than an iterator.

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

Zakwayda

2,389

March 03, 2008 03:46 PM

Quote:According to here,
Quote:
Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

So the iterators should always remain valid. I don't ever remove individual elements, so deletion is not an issue.

Sure - as you note, a map iterator will remain valid unless that specific element is destroyed.

However, that doesn't protect you from inadvertently erasing that element yourself, from the entire map getting cleared, or from the map going out of scope.

Sure, you're not planning on letting any of these things happen, but that's the problem with C++: we're all quite certain that we won't shoot ourselves in the foot - but eventually, we do :)

Anyway, here's the way I look at it. The iterator issue aside, it would be wise to handle ownership of the pointed-at objects via RAII. This basically means either boost::ptr_map (or something like it), or boost::shared_ptr (or something like it).

In the former case (boost::ptr_map), handing out the pointer itself would be no more or less dangerous than handing out an iterator (or so it seems to me at the moment - there might be more to it than that, but I'm not going to give it much more thought right now), so you might as well just hand out the pointer. In the latter case (boost::shared_ptr), you're golden no matter what; whether you hand out a strong or weak reference, you're (practically) guaranteed a valid pointer to dereference.

In other words, I don't think you have anything to lose by handing out a pointer of some sort rather than an iterator (IMO, of course).

Zahlman

1,682

March 03, 2008 05:54 PM

Quote:Original post by _Sigma
I have a std::map like thus:
std::map<std::string,myclass *> myMap;
However, there are some items in myMap which I require access to, however these items change.

Then just use the string to look up the thing you need access to. If the item "changed" in the mean time, the map will have reflected that, and you'll get the updated pointer to the new instance. What's the problem?

_Sigma

792

Author

March 03, 2008 10:43 PM

I think I'm overthinking this:
I'll just store all the keys of the items that change...Since they are just std::strings. That would work well I think...

std::map of iterators?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

std::map of iterators?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines