Is Hash_Map Part of the Stl

Is hash_map part of the STL?

The STL has hash_map, but the C++ Standard Library does not.

Due to a common misconception, you may think of the C++ Standard Library as "the STL", or of parts of your toolchain's implementation of the C++ Standard Library as "an STL implementation".

It is not.

It is also a great shame that both MSVC++ and GCC (which implement hash_map as a compiler-specific extension), place it in the std namespace, which is not only highly misleading, but also illegal per the standard. *sigh*

C++11 has introduced std::unordered_map, which is not dissimilar.

does STL has hashmap data structure?

Standard C++98 does not have a hash map, but many implementation of the STL, like the original SGI implementation, do have a hash_map class.

map vs. hash_map in C++

They are implemented in very different ways.

hash_map (unordered_map in TR1 and Boost; use those instead) use a hash table where the key is hashed to a slot in the table and the value is stored in a list tied to that key.

map is implemented as a balanced binary search tree (usually a red/black tree).

An unordered_map should give slightly better performance for accessing known elements of the collection, but a map will have additional useful characteristics (e.g. it is stored in sorted order, which allows traversal from start to finish). unordered_map will be faster on insert and delete than a map.

What's the scenario difference between hash_map and map in STL?

hash_map is useful if you are only looking elements by their key. A possible use-case for a hash_map would be a dictionary. If the elements need to be in order map is the container for that.

And just for clarification (because of the usage of the word "STL"): hash_map isn't yet part of the C++ Standard Library, but it has been implemented in several C++ compilers. unordered_map was proposed in the C++ Technical Report 1, and it will be defined in the next edition of the standard, C++0x.

c++: The order of iterating through std::hash_map

No, hash_map or the standard equivalent std::unordered_map is an unordered container.

What is the best way to use a HashMap in C++?

The standard library includes the ordered and the unordered map (std::map and std::unordered_map) containers. In an ordered map the elements are sorted by the key, insert and access is in O(log n). Usually the standard library internally uses red black trees for ordered maps. But this is just an implementation detail. In an unordered map insert and access is in O(1). It is just another name for a hashtable.

An example with (ordered) std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

Output:

23
Key: hello Value: 23

If you need ordering in your container and are fine with the O(log n) runtime then just use std::map.

Otherwise, if you really need a hash-table (O(1) insert/access), check out std::unordered_map, which has a similar to std::map API (e.g. in the above example you just have to search and replace map with unordered_map).

The unordered_map container was introduced with the C++11 standard revision. Thus, depending on your compiler, you have to enable C++11 features (e.g. when using GCC 4.8 you have to add -std=c++11 to the CXXFLAGS).

Even before the C++11 release GCC supported unordered_map - in the namespace std::tr1. Thus, for old GCC compilers you can try to use it like this:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

It is also part of boost, i.e. you can use the corresponding boost-header for better portability.

---

Related Topics