Unordered Map/Set in VC++/Boost?
Hello, I wanted to use hash maps in VC++, but it seems that they have only an old implementation, but not the tr1 unordered_map type. Actually the hash_map would have been fine if I could use it with the boost "hash" class. Anyway, after searching a bit on google, I've found a page where is mentioned something about boost having an implementation of the unordered_map. So my question is: does boost or does it not contain the unordered_map, and if not, then anyone has any idea how I could use the boost hash class with the VC++ (2005) hash_map class? Thx in advance, Peter
On Sunday 20 May 2007 17:52:36 Péter Szilágyi wrote:
I wanted to use hash maps in VC++
VC++ is not a compiler. At the very least, this needs a version, after all there are ages between VC6 and VC8 and both are still in use!
but it seems that they have only an old implementation, but not the tr1 unordered_map type.
My guess is that they have the hash containers from the STL.
Actually the hash_map would have been fine if I could use it with the boost "hash" class. Anyway, after searching a bit on google, I've found a page where is mentioned something about boost having an implementation of the unordered_map.
Boost has a TR1 implementation and it documents pretty well which parts thereof are implemented and which aren't. Specifically that would be http://boost.org/doc/html/boost_tr1.html and it says that it is _not_ included.
[...] anyone has any idea how I could use the boost hash class with the VC++ (2005) hash_map class?
Sorry, can't help with that. If you dearly need TR1's unordered containers, you could license a TR1 implementation from Dinkumware though. Other than that, what exactly is it that you want to achieve? Knowing that could help giving better advise... Uli
I wanted to use hash maps in VC++ but it seems that they have only an old implementation, but not the tr1 unordered_map type.
STLPort has unordered_* containers. I'm not sure how they are compliant with TR1, but since initially SGI's hash containers were close to it, I'd expect this implementation to be good. -- Best regards, Andrey mailto:andysem@mail.ru
VC++ is not a compiler. At the very least, this needs a version, after all there are ages between VC6 and VC8 and both are still in use!
Yes... that's why I wrote 2005 in parenthesis. Sorry, can't help with that. If you dearly need TR1's unordered containers,
you could license a TR1 implementation from Dinkumware though.
Not really the answer I was looking for. Other than that, what exactly is it that you want to achieve? Knowing that
could help giving better advise...
Actually what I need is a container to associate an ID with an object and to enable very fast lookups to see if the item I'm looking for does already exist (has an ID) or not. My current implementation uses the STL map, but as far as I know, a hash map would be a far better choice for consequent lookups and as my object (currently 4-tuple unsigned int) count in the map could potentially reach one to two million. Here speed is everything. STLPort has unordered_* containers. I'm not sure how they are
compliant with TR1, but since initially SGI's hash containers were close to it, I'd expect this implementation to be good.
I don't really want to add additional libraries, that aren't needed. I'd rather solve it with the already available tools. Here's a sketch of how this
might be done - although, completely untested, as I'm using Linux at the moment.
Thx for the example and the explanation, I'll try it out. Peter
Actually what I need is a container to associate an ID with an object
and
to enable very fast lookups to see if the item I'm looking for does already exist (has an ID) or not.
With the most recent versions of VC++ they ship a hash_map in the stdext namespace. I would look at that first. joe
----- Mensaje original ----- De: Péter Szilágyi <peterke@gmail.com> Fecha: Martes, Mayo 22, 2007 9:39 pm Asunto: Re: [boost] Unordered Map/Set in VC++/Boost? Para: boost@lists.boost.org [...]
I don't really want to add additional libraries, that aren't needed. I'd rather solve it with the already available tools.
Boost.MultiIndex provides hashed indices, so you can emulate an unordered_set with a single-index multi_index_container. For instance, a TR1-compatible unordered set of ints would be defined as: #include <boost/multi_index_container.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/identity.hpp> typedef boost::multi_index_container< int, boost::multi_index::indexed_by< boost::multi_index::hashed_unique< boost::multi_index::identity<int> > >
int_unordered_set;
An emulation of an unordered map is a little more tricky and the result won't be TR1-compatible, but might be close enough for your needs, take for instance an unordered_map of ints to std::strings: #include <boost/multi_index_container.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/member.hpp> struct istr_pair { istr_pair(int i,const std::string& str): first(i),second(str){} int first; mutable std::string second; }; typedef boost::multi_index_container< istr_pair, boost::multi_index::indexed_by< boost::multi_index::hashed_unique< boost::multi_index::member< istr_pair,int,&istr_pair::first > > >
istr_unordered_map;
(Note that the second member of istr_pair is mutable so that we can freely modify it in elements of istr_unordered_map, which are treated as const, that's why we can use std::pair instead.) Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On 5/22/07, "JOAQUIN LOPEZ MU?Z" <joaquin@tid.es> wrote:
De: Péter Szilágyi <peterke@gmail.com>
I don't really want to add additional libraries, that aren't needed. I'd rather solve it with the already available tools.
Boost.MultiIndex provides hashed indices, so you can emulate an unordered_set with a single-index multi_index_container. [snip] An emulation of an unordered map is a little more tricky and the result won't be TR1-compatible, but might be close enough for your needs
You can use Boost.Bimap. #include <boost/bimap/bimap.hpp> #include <boost/bimap/unordered_set_of.hpp> #include <boost/bimap/unconstrained_set_of.hpp> using boost::bimaps; typedef bimap< unordered_set_of<std::string>, unconstrained_set_of<int> > bm_type; typedef bm_type::left_map map_type; bm_type bm; map_type & m = bm.left; // Use map as a std::unordered_map m["one"] = 1; m["two"] = 2; assert( m.find("one") != m.end() ); m.insert( map_type::value_type("three",3) ); assert( m.size() == 3 ); If you need unordered_multimap use unordered_multiset_of. You can read more about Boost.Bimap here: http://tinyurl.com/22sja5 Best regards Matias
Péter Szilágyi wrote:
does boost or does it not contain the unordered_map,
Boost doesn't currently have unordered containers. I'm going to ask for a review soon, but given the amount of time it's taken libraries to get into boost recently, don't hold your breath. The review won't be for a while and, if it's accepted, it'll have to wait for an appropriate release to be included. For now, you can get the work in progress from: http://boost-consulting.com/vault/index.php?directory=Containers It's called 'unordered.tar.gz'. It should be pretty reliable.
then anyone has any idea how I could use the boost hash class with the VC++ (2005) hash_map class?
Looking at the MSDN documentation, boost::hash will have a couple of issues with Visual C++'s hash_map. One is that Visual C++'s hash_map uses power of 2 sized buckets - while boost::hash is really designed to work with a container that uses a prime number of buckets. So if your key's hash values don't vary much in the lower bits you'll get a lot of collisions. Whether this is likely depends on your data, but you'll need to be careful. The other issue is that while unordered_map uses an equality predicate to compare elements, Visual C++'s hash_map uses a 'less' predicate. Although, as long as the comparison is consistent with the hash value I think it should be okay. But if you do want to use Boost.Hash, then you'll need to implement your own hash_compare which uses boost::hash. Here's a sketch of how this might be done - although, completely untested, as I'm using Linux at the moment. template<class Key> class my_hash_compare { boost::hash<Key> hasher_; public: const std::size_t bucket_size = 4; const std::size_t min_buckets = 8; hash_compare() : hasher_() {} std::size_t operator()(const Key& k) const { return hasher_(k); } bool operator()(const Key& k1, const Key& k2) const { return k1 < k2; } }; stdext::hash_map<std::string, int, my_hash_compare<std::string> > map; For more info on hash_compare see: http://msdn2.microsoft.com/en-us/library/8zz3703d(VS.80).aspx Hope that helps, Daniel
Daniel James wrote:
Péter Szilágyi wrote:
does boost or does it not contain the unordered_map,
Boost doesn't currently have unordered containers. I'm going to ask for a review soon, but given the amount of time it's taken libraries to get into boost recently, don't hold your breath.
While "don't hold your breath" is certainly good advice, there is general agreement that we need to fix the release procedure so we can release on a much more reliable schedule. At BoostCon last week there was a lot of background discussion about the details of objectives and how to achieve them. I'm writing a proposal now and should be ready to post for comments sometime this coming week. --Beman
participants (8)
-
"JOAQUIN LOPEZ MU?Z" -
Andrey Semashev -
Beman Dawes -
Daniel James -
Greer, Joe -
Matias Capeletto -
Péter Szilágyi -
Ulrich Eckhardt