📚🔢 Hashmaps in C++ STL: Ordered and Unordered 🗺️🧩

Hey there! 👋 Today, let's talk about two essential map containers provided by the standard library in C++. 📚✨ These containers are called ordered map (std::map) and unordered map (std::unordered_map). Let's explore their features and differences. 🤓🔍

🗺️🔢 Ordered Map (std::map): In an ordered map, the elements are sorted based on their keys. Inserting and accessing elements in an ordered map have a time complexity of O(log n), where n is the number of elements in the map. The standard library typically uses red-black trees internally to implement ordered maps. However, remember that this is just an implementation detail! 🌳

Here's an example using an ordered map:

#include <map>
#include <iostream>
#include <cassert>
using namespace std;

int main(int argc, char **argv) {
  map<string, int> m;
  m["hello"] = 23;

  // Check if key is present
  if (m.find("world") != m.end())
    cout << "The map contains the key 'world'!\n";

  // Retrieve the value
  cout << m["hello"] << '\n';

  map<string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  cout << "Key: " << i->first << " Value: " << i->second << '\n';

  return 0;
}

Output:

23
Key: hello Value: 23

If you require ordering in your container and are okay with the O(log n) runtime, then std::map is a great choice! 😊👍

🔍🔢 Unordered Map (std::unordered_map): On the other hand, if you need a hash table with constant-time insertions and access (O(1)), you should consider using an unordered map. It behaves like a hashtable and provides faster lookup times compared to an ordered map. 🚀🔑

To use an unordered map, you can check out std::unordered_map, which has a similar API to std::map. In the example above, you would simply replace "map" with "unordered_map". 😉

The unordered_map container was introduced with the C++11 standard revision. Therefore, depending on your compiler, you might need to enable C++11 features. For instance, if you're using GCC 4.8, you can add "-std=c++11" to the CXXFLAGS.

If you're working with an older GCC compiler, fear not! 😄📅 unordered_map was already supported by GCC, but in the namespace std::tr1. So, for older GCC compilers, you can try using it like this:

#include <iostream>
#include <tr1/unordered_map>

using namespace std;
using namespace std::tr1;

int main(int argc, char** argv) {
  unordered_map<string, int> m;
  m["hello"] = 23;

  // Check if key is present
  if (m.find("world") != m.end())
    cout << "The unordered_map contains the key 'world'!\n";

  // Retrieve the value
  cout << m["hello"] << '\n';

  unordered_map<string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  cout << "Key: " << i->first << " Value: " << i->second << '\n';

  return 0;
}

Lastly, if you're looking for even better portability, unordered_map is also part of the Boost library. You can use the corresponding Boost header to ensure compatibility across different systems. 🌐🚀

That's it for today's exploration of ordered and unordered maps in C++! I hope you found this information helpful and that it guides you in choosing the right container for your needs. Happy coding! 💻✨