Hashing and std::hash

std::unordered_map vs std::map

What are the differences between std::unordered_map and std::map in C++?

Abstract art representing computer programming

std::unordered_map and std::map are both associative containers in C++ that store key-value pairs, but they have some key differences:

Ordering:

  • std::unordered_map¬†does not maintain any particular order of elements. The elements are organized into buckets based on their hash values.
  • std::map¬†is an ordered associative container. It stores elements in sorted order based on the keys. By default, the keys are sorted in ascending order.

Underlying Data Structure:

  • std::unordered_map¬†is implemented using a hash table. It uses a hash function to compute the hash value of the keys and distributes the elements into buckets accordingly.
  • std::map¬†is typically implemented as a self-balancing binary search tree, such as a red-black tree. The elements are arranged in a hierarchical structure based on the key values.

Lookup and Insertion Complexity:

  • std::unordered_map¬†provides average constant-time O(1) complexity for lookup, insertion, and deletion operations. However, in the worst case (e.g., when all elements have the same hash value), the complexity can degrade to linear time O(n).
  • std::map¬†guarantees logarithmic time O(log n) complexity for lookup, insertion, and deletion operations. The self-balancing property of the underlying binary search tree ensures efficient operations.

Key Requirements:

  • In¬†std::unordered_map, the key type must have a hash function and an equality comparison operator. The hash function is used to distribute the elements into buckets, and the equality operator is used to resolve collisions.
  • In¬†std::map, the key type must have a strict weak ordering (e.g.,¬†operator<¬†or a custom comparator). The keys are compared using the¬†operator<¬†or the provided comparator function.

Here's an example to illustrate the differences:

#include <iostream>
#include <map>
#include <unordered_map>

int main() {
  std::unordered_map<std::string, int> umap = {
      {"apple", 5}, {"banana", 3}, {"orange", 2}};

  std::map<std::string, int> map = {
    {"apple", 5}, {"banana", 3}, {"orange", 2}};

  // Iterating over unordered_map
  // (no specific order)
  std::cout << "Unordered Map:" << '\n';
  for (const auto& pair : umap) {
    std::cout << pair.first << ": "
      << pair.second << '\n';
  }

  // Iterating over map (sorted order)
  std::cout << "\nMap:" << '\n';
  for (const auto& pair : map) {
    std::cout << pair.first << ": "
      << pair.second << '\n';
  }
}
Unordered Map:
orange: 2
apple: 5
banana: 3

Map:
apple: 5
banana: 3
orange: 2

In general, if you need fast lookup, insertion, and deletion operations and don't care about the order of elements, std::unordered_map is a good choice. If you require the elements to be sorted based on keys or need logarithmic time complexity guarantees, std::map is a suitable option.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved