Sign in to follow this  
_Sigma

std::map of iterators?

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this