Menu
I was reading over my text book Data Structures and Algorithms: By Mark Allen Weiss and it says that the standard library does not contain hash table implementations of a set or map, but rather compilers can provide hash_set and hash_map with same member functions of the set and map class. Why not just include hash implementations in the standard library? The book was published in 2006, have there been any revisions of C++ since to add these implementations to the standard library?
496
A Hash Table in C/C++ (Associative array) is a data structure that maps keys to values. This uses a hash function to compute indexes for a key. Based on the Hash Table index, we can store the value at the appropriate location.
There are some operations which are not efficiently supported by hash tables, such as iterating over all the elements whose keys are within a certain range, finding the element with the largest key or smallest key, and so on. The O(n) complexity is on average.
Implementation of a hash table. The basic idea behind hashing is to distribute key/value pairs across an array of placeholders or "buckets" in the hash table. A hash table is typically an array of linked lists.
The idea of a hash table is to provide a direct access to its items. So that is why the it calculates the "hash code" of the key and uses it to store the item, insted of the key itself. The idea is to have only one hash code per key.
What you're looking for are called std::unordered_set/map. These are part of C++11, the next version of the C++ standard (due to be finalized in a few months). They were also made available in Technical Report 1 in 2005, which was a list of additions to the C++ standard library between the first standard and the next one. In TR1, they were in the std::tr1 namespace.
Boost actually ships an implementation of TR1 (though you shouldn't use the std::tr1::shared_ptr version, as the regular boost::shared_ptr and std::shared_ptr in C++11 are much, much better).
If I recall, the reason why hash tables were not initially introduced in C++98 was simply a lack of time for the C++ standards committee. They basically had a cut-off date in order to ship the thing, and hash tables didn't make it.
125
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
