Criteria, don't want creating copies of objects all over the place. Should be fast, memory efficient and should not create leaks. Should be threadsafe.
Ideally I would want to store pointers to vectors in the HashMap, but I am worried about memory leaks that way.
Is this the best way?
std::map<std::string, std::auto_ptr<std::vector<std::string> > > adjacencyMap;
You're prohibited from storing an auto_ptr in any standard container. §23.1/3: "The type of objects stored in these components must meet the requirements of CopyConstructible
types (20.1.3), and the additional requirements of Assignable types." std::auto_ptr doesn't meet that requirement.
A std::map<> is not implemented as a hash_map, but as a red-black tree (see http://en.wikipedia.org/wiki/Map_(C%2B%2B))
You can use std::unordered_map<> for c++0x compilers or std::tr1::unordered_map<> for non c++0x compilers.
Boost also has its version.
That's pretty smart way of doing it.
Only suggestion I can offer is to refrain from putting auto_ptr's into STL containers. http://www.devx.com/tips/Tip/13606
If you use shared_ptr instead everything should work fine. http://beta.boost.org/doc/libs/1_40_0/libs/smart_ptr/shared_ptr.htm
How about...
map<string, vector<string> >
Please note that map is pretty special in that unlike say vector the elements are never copied during map resizing, or when other elements are inserted or deleted. For this reason, there is no need to use pointers to protect against unnecessary deep copies.
From http://www.sgi.com/tech/stl/Map.html:
"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."
Of course, there may be a deep copy in copying a value into the map if you don't construct it in-place, and if you for some reason need to copy it out, but it's often easy to do everything in-place, perhaps with the helper ala:
vector<string>& this_one = my_map[my_key];
// work on this_one
So many questions bundled...
std::unordered_map, std::tr1::unordered_map or boost::unordered_map are hash maps. They are reliable, but not thread safe (see that later)vector, you'll avoid memory leaks, with the upcoming C++0x it's likely that they'll be moved around instead of copied and thus you'll have both performance and safety... in the meantime, don't worry about performance until profiling tells you where bottlenecks are.Explaining the latter point: suppose I have a magnificent tbb::concurrent_hash_map named container.
if (!container.empty())container.clear(){ value = container.front(); } // Undefined behaviorThe issue is that a thread-safe container doesn't guarantee thread correctness. You'll still need to explicitly lock the container for your operations, and therefore it would be pointless for the container to lock within your lock.
So don't worry so much about finding thread-safe containers, the very reason the STL does not have any is that it's pretty much useless anyway since most of the operations you want are composite and require the lock to be held for the entire suite, not released between each of them.
On your thread safety criterion: None of the STL containers are guaranteed threadsafe in non-trivial cases. In some cases you can get away with certain concurrent access patterns, but I doubt you will be able to make that work with a hash map.
If this is really what you require, then you will need a threadsafe hash map class. Intel's Threading Building Blocks has a concurrent_hash_map class IIRC, which seems like the most obvious option to me, although I'm sure there are others.
Although note that this will of course not make your vectors threadsafe, only the containing hashmap; TBB has a concurrent_vector as well if you need that too.
