tags:

views:

392

answers:

3

I'll keep this brief.

I am trying to keep a map between strings and object pointers, and as such, I use std::map. I have a manager that's a global class that keeps track of the map, and whenever an object's destructor is called, it tells the manager that it has been deleted.

The only way I can think of is to search through the map for the object. Is there an efficient STL solution to this problem? Does a map that is efficient at searching by key as well exist?

+6  A: 

No there is not an efficient way of doing this with std::map other than iterating through comparing the values.

However most of the time the key for a value is computable from the value itself. For example using the Name property of a Person object as the key. Is it possible for the manager to store a list of key / value pairs as opposed to the value itself. This would solve your problem without having to rewrite a new algorithm.

Or alternatively you could keep a reverse map on the manager class. Essentially value to key. That way you could use it to compute the key to remove later on.

JaredPar
Thanks! I didn't even think of having the object store the key itself. Definitely a better solution than having a second map.
Andrei Krotkov
+1, I will remove my answer as it sounds same as yours.
aJ
+1  A: 

Take a look at Boost Multi-Index Containers library.

Nikolai N Fetissov
Note that you need both keys and values to be unique in order to use a bidirectional map. std::map only requires unique keys.
Kristo
+3  A: 

Looking at SGI's documentation for the STL,

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 you can store an iterator into the map inside your object, and use that as a constant-time lookup key when you need to go delete its entry.

Crashworks