Talk:C plus plus:Modern C plus plus:Containers

From GPWiki

Umm, i'm a bit confused by the "std::map<K,D> is essentially just a nice interface to std::set< std::pair<K,D> >" part. Because you can't explicitly search for the K part in a set, unless you want to do it linearly by iterating through it (in O(N) time). That's probably not the way std::map does it when you use the operator[] (not sure though, better to say: I hope not..). So I think it's a little more elaborate than "just a nice interface". If I'm incorrect in any way, please let me know =).

Seniltai

You're right. I should say that it "can be thought of as", rather than "is essentially". There are a number of issues about constness, the searching you mentioned, and some other things that keep it from really even being conveniently implemented with a set of pairs.

On the other hand, you can make a std::set< std::pair<K,D>, first_comparator >, where first_comparator is a struct whose operator() does the same thing as K's operator>, and then you have logarithmic search for a key, and prevention of duplicate equivalent keys, just like a map. Add in some const_casting (which would even be legal since none of the nodes could have been created const, since they come from std::allocator) and you have all the functionality of a map.

As for map's operator[], it's really quite simple. It calls insert( pair<K,D>(k, D()) ) to create the node (the call changes nothing if the key already exists), and returns the ->second of the iterator returned, which is a reference to the data associated with the key.

Thanks for the comments,

--me22 22:39, 4 January 2008 (EST)