unordered_map Standard Template Library (STL) - GitMasterNikanjam/C_WiKi GitHub Wiki

std::unordered_map is a container in C++ from the Standard Template Library (STL) that stores key-value pairs, similar to a hash table or dictionary in other programming languages. It provides an efficient way to access, insert, and remove elements based on keys. Unlike std::map, which stores elements in a sorted order (typically using a balanced binary tree), std::unordered_map stores elements in an arbitrary order determined by a hash function, which provides average constant-time complexity for insertions, deletions, and lookups.

1. Unordered Storage: Elements are not stored in any particular order. The order of elements depends on the hash function and the internal bucket organization.
2. Constant-Time Operations: Average time complexity for lookups, insertions, and deletions is O(1), making it faster than std::map for these operations in most cases.
3. Hashing: Uses a hash function to map keys to buckets, which is the basis for the fast access times.
4. Unique Keys: Each key must be unique within the map; inserting a duplicate key will overwrite the existing value associated with that key.
5. Custom Hash and Equality Functions: You can provide custom hash functions and comparison (equality) functions if needed.

Here is a simple example of how to use std::unordered_map:

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // Creating an unordered_map with string keys and int values
    std::unordered_map<std::string, int> umap;

    // Inserting elements into the unordered_map
    umap["apple"] = 5;
    umap["banana"] = 10;
    umap["orange"] = 8;

    // Accessing elements
    std::cout << "Apple count: " << umap["apple"] << std::endl;

    // Iterating over the unordered_map
    for (const auto& pair : umap) {
        std::cout << "Fruit: " << pair.first << ", Count: " << pair.second << std::endl;
    }

    // Checking if a key exists
    if (umap.find("banana") != umap.end()) {
        std::cout << "Banana is present in the map." << std::endl;
    }

    // Erasing an element
    umap.erase("orange");

    return 0;
}

• Insertion and Access: Elements are inserted using the [] operator or the insert() method. Elements can be accessed with the [] operator.
• Iteration: Iterating over an unordered_map does not guarantee any particular order.
• Finding Elements: The find() function returns an iterator to the element if the key exists, otherwise it returns end().
• Deletion: Elements can be removed using the erase() method.

• Use std::unordered_map when you need fast lookups, insertions, and deletions without caring about the order of elements.
• Avoid using it when you need sorted elements; in such cases, consider std::map instead.

This container is highly useful for scenarios where performance is critical and order does not matter.

To use std::unordered_map with struct variables, you can store either the struct itself as the key or the value, depending on your needs. A common scenario is using a struct as the key or the value type in the map. When using a struct as a key, you need to provide a custom hash function and an equality function since std::unordered_map relies on hashing and comparing keys.

In this example, we'll create a struct called Person, which will be used as the value type in the unordered_map. The key will be a string representing the person's name.

#include <iostream>
#include <unordered_map>
#include <string>

// Define a struct to store person information
struct Person {
    int age;
    std::string address;

    // Optional: A constructor for convenience
    Person(int a, const std::string& addr) : age(a), address(addr) {}
};

int main() {
    // Create an unordered_map with string keys and Person struct as values
    std::unordered_map<std::string, Person> people;

    // Insert elements into the unordered_map
    people["John"] = Person(30, "123 Maple Street");
    people["Jane"] = Person(25, "456 Oak Avenue");
    people["Doe"] = Person(40, "789 Pine Road");

    // Access and print the elements
    for (const auto& pair : people) {
        std::cout << "Name: " << pair.first 
                  << ", Age: " << pair.second.age 
                  << ", Address: " << pair.second.address 
                  << std::endl;
    }

    // Check if a key exists
    if (people.find("Jane") != people.end()) {
        std::cout << "Jane's age: " << people["Jane"].age << std::endl;
    }

    // Erase an element
    people.erase("Doe");

    return 0;
}

When using a struct as a key, you must define a custom hash function and an equality function since std::unordered_map needs these to work correctly with user-defined types.

Here's an example of using a struct as a key:

#include <iostream>
#include <unordered_map>
#include <string>

// Define a struct to be used as a key
struct PersonKey {
    std::string firstName;
    std::string lastName;

    // Constructor
    PersonKey(const std::string& first, const std::string& last) 
        : firstName(first), lastName(last) {}

    // Equality operator for comparing keys
    bool operator==(const PersonKey& other) const {
        return (firstName == other.firstName && lastName == other.lastName);
    }
};

// Custom hash function for PersonKey
struct PersonKeyHash {
    std::size_t operator()(const PersonKey& key) const {
        // Simple hash combination of first and last names
        return std::hash<std::string>()(key.firstName) ^ std::hash<std::string>()(key.lastName);
    }
};

int main() {
    // Create an unordered_map with PersonKey as keys and int as values
    std::unordered_map<PersonKey, int, PersonKeyHash> personScores;

    // Insert elements into the unordered_map
    personScores[PersonKey("John", "Doe")] = 85;
    personScores[PersonKey("Jane", "Smith")] = 92;
    personScores[PersonKey("Alice", "Johnson")] = 78;

    // Access and print the elements
    for (const auto& pair : personScores) {
        std::cout << "Name: " << pair.first.firstName << " " << pair.first.lastName 
                  << ", Score: " << pair.second << std::endl;
    }

    // Check if a key exists
    if (personScores.find(PersonKey("Jane", "Smith")) != personScores.end()) {
        std::cout << "Jane Smith's score: " << personScores[PersonKey("Jane", "Smith")] << std::endl;
    }

    // Erase an element
    personScores.erase(PersonKey("Alice", "Johnson"));

    return 0;
}

1. Custom Hash Function: PersonKeyHash is a functor that defines how to hash the PersonKey struct. This is necessary because std::unordered_map requires a hash function to handle custom types.

2. Equality Operator: The operator== is overloaded in PersonKey to ensure that two keys are considered equal if their firstName and lastName match.

3. Insertion and Access: Elements are inserted into the map using the custom struct as the key. Accessing elements is done using the key, just like any other map.

This pattern is commonly used when you need to associate complex keys (like combinations of multiple fields) with values in a map, especially when order does not matter, but quick access time is critical.

Here's an example of using std::unordered_map with classes instead of structs. The principle is similar: you can use class objects as either keys or values in the unordered_map. When using class objects as keys, you'll still need custom hash and equality functions.

This example demonstrates how to use a class as the value in an unordered_map. The class will encapsulate information about a person, such as age and address.

#include <iostream>
#include <unordered_map>
#include <string>

// Define a class to store person information
class Person {
private:
    int age;
    std::string address;

public:
    // Constructor
    Person(int a, const std::string& addr) : age(a), address(addr) {}

    // Getters
    int getAge() const { return age; }
    std::string getAddress() const { return address; }

    // Setters
    void setAge(int a) { age = a; }
    void setAddress(const std::string& addr) { address = addr; }
};

int main() {
    // Create an unordered_map with string keys and Person class objects as values
    std::unordered_map<std::string, Person> people;

    // Insert elements into the unordered_map
    people.emplace("John", Person(30, "123 Maple Street"));
    people.emplace("Jane", Person(25, "456 Oak Avenue"));
    people.emplace("Doe", Person(40, "789 Pine Road"));

    // Access and print the elements
    for (const auto& pair : people) {
        std::cout << "Name: " << pair.first 
                  << ", Age: " << pair.second.getAge() 
                  << ", Address: " << pair.second.getAddress() 
                  << std::endl;
    }

    // Check if a key exists
    if (people.find("Jane") != people.end()) {
        std::cout << "Jane's age: " << people["Jane"].getAge() << std::endl;
    }

    // Erase an element
    people.erase("Doe");

    return 0;
}

When using a class as a key, you must define custom hash and equality functions, as the unordered map needs these to manage custom types.

#include <iostream>
#include <unordered_map>
#include <string>

// Define a class to be used as a key
class PersonKey {
private:
    std::string firstName;
    std::string lastName;

public:
    // Constructor
    PersonKey(const std::string& first, const std::string& last) 
        : firstName(first), lastName(last) {}

    // Getters
    std::string getFirstName() const { return firstName; }
    std::string getLastName() const { return lastName; }

    // Equality operator for comparing keys
    bool operator==(const PersonKey& other) const {
        return (firstName == other.firstName && lastName == other.lastName);
    }
};

// Custom hash function for PersonKey
class PersonKeyHash {
public:
    std::size_t operator()(const PersonKey& key) const {
        // Simple hash combination of first and last names
        return std::hash<std::string>()(key.getFirstName()) ^ std::hash<std::string>()(key.getLastName());
    }
};

int main() {
    // Create an unordered_map with PersonKey as keys and int as values
    std::unordered_map<PersonKey, int, PersonKeyHash> personScores;

    // Insert elements into the unordered_map
    personScores.emplace(PersonKey("John", "Doe"), 85);
    personScores.emplace(PersonKey("Jane", "Smith"), 92);
    personScores.emplace(PersonKey("Alice", "Johnson"), 78);

    // Access and print the elements
    for (const auto& pair : personScores) {
        std::cout << "Name: " << pair.first.getFirstName() << " " << pair.first.getLastName()
                  << ", Score: " << pair.second << std::endl;
    }

    // Check if a key exists
    if (personScores.find(PersonKey("Jane", "Smith")) != personScores.end()) {
        std::cout << "Jane Smith's score: " << personScores[PersonKey("Jane", "Smith")] << std::endl;
    }

    // Erase an element
    personScores.erase(PersonKey("Alice", "Johnson"));

    return 0;
}

1. Custom Hash and Equality Functions: When using a class as a key, you must define custom hash and equality functions. The PersonKeyHash class implements the hash function, and the operator== is defined inside PersonKey to compare two keys correctly.

2. Encapsulation: Classes allow you to encapsulate data and provide access through public methods (getters and setters), which is useful for more complex logic that might be required in a real-world application.

3. Emplace for Efficiency: The emplace() method is used to insert elements directly by constructing them in place, which can be more efficient than first creating the object and then inserting it.

Using classes instead of structs provides more flexibility and encapsulation, making your code cleaner and easier to maintain, especially when dealing with more complex objects in your unordered_map.

std::unordered_map has been a part of the C++ Standard Library since C++11. Both the examples provided use features that are consistent with the C++11 standard and later standards.

1. C++11:

   • std::unordered_map: Introduced in C++11, it provides average constant-time complexity for insertions, deletions, and lookups.
   • Emplace Method: The emplace method was introduced in C++11 to construct elements in place, avoiding the need for additional copy or move operations.
   • Custom Hash and Equality Functions: Using custom hash functions and equality operators for user-defined types is supported in C++11 and beyond.

2. C++14 and Later:

   • std::unordered_map Enhancements: The standard library saw additional improvements in later versions of C++. For instance, C++14 made various minor improvements and bug fixes, while C++17 introduced features such as std::optional and std::variant that complement container usage but don't directly affect std::unordered_map.

3. C++20 and C++23:

   • No Major Changes to std::unordered_map: While these standards introduce new features and enhancements to the language, the core functionality of std::unordered_map remains consistent with C++11. However, features like constexpr and improved support for multi-threaded programming can be useful in the context of unordered containers.

The examples provided are compatible with C++11 and later standards. If you use a compiler with support for C++11 or newer, such as GCC 4.8 and later, Clang 3.3 and later, or MSVC 2015 and later, you will be able to compile and run the examples without modifications.

To ensure that your code is compiled with the C++11 standard or later, you may need to specify the appropriate flag for your compiler:

• GCC and Clang:

  g++ -std=c++11 your_code.cpp -o your_program

• MSVC: By default, MSVC supports C++11 and later, but you can specify the standard version with the /std:c++14, /std:c++17, or /std:c++20 flag.

In summary, the examples provided use features available from C++11 onwards. If you use a C++11 or later compliant compiler, you should have no issues with these examples.

std::unordered_map is a powerful and versatile container in C++ that is particularly useful in scenarios where you need fast access to elements based on unique keys. Here are some typical applications and situations where std::unordered_map is particularly useful:

1. Fast Lookup Operations:

   • Caching and Memoization: Use std::unordered_map to cache results of expensive computations to avoid redundant calculations. For example, memoization of recursive functions where results are stored based on input parameters.
   • Symbol Tables: In compilers or interpreters, std::unordered_map can store identifiers (such as variable names) and their associated information (e.g., type, value) for quick lookup and modification.

2. Associative Data Storage:

   • Dictionary Implementation: When you need to map keys to values, such as storing word definitions in a dictionary or user settings/preferences.
   • Configuration Management: Storing application configurations where keys are configuration names and values are configuration details.

3. Unique Key Constraints:

   • Tracking Unique Items: When you need to ensure that items are unique, such as tracking user IDs, product codes, or other identifiers where duplicates are not allowed.
   • Event Handling: Mapping events (identified by unique event IDs) to their handlers for fast retrieval and execution.

4. Counting and Frequency Analysis:

   • Frequency Counting: Counting occurrences of items, such as the frequency of words in a text or the number of times a specific event occurs.
   • Histogram Representation: Storing and quickly accessing frequency counts of various categories or ranges.

5. Dynamic and Sparse Data:

   • Sparse Data Representations: Storing large, sparse data sets where the keys represent the positions or indices and the values represent the data at those positions.
   • Dynamic Data Structures: Managing dynamic collections where elements are frequently added and removed, and fast access to elements is crucial.

1. When Fast Access is Critical:

   • Performance: std::unordered_map provides average O(1) time complexity for access, insertion, and deletion operations, making it suitable for performance-critical applications where quick lookups are necessary.

2. When Order of Elements Does Not Matter:

   • No Sorting Requirement: If you do not need to maintain elements in a sorted order, std::unordered_map is more efficient than std::map due to its hashing mechanism.

3. When Keys Are Well-Defined:

   • Hashable Keys: Ensure that the keys used are hashable and have a well-defined equality operator. If you need custom hashing or comparison logic, you can provide it with std::unordered_map.

4. When Memory Usage is Manageable:

   • Memory Overhead: Be aware that std::unordered_map may have higher memory overhead due to its internal hash table structure and potential collisions. This might be a consideration if you have very large datasets or limited memory resources.

• Cache Implementation:

  #include <unordered_map>
  #include <iostream>
  
  int expensiveComputation(int x) {
      // Simulate an expensive computation
      return x * x;
  }
  
  int main() {
      std::unordered_map<int, int> cache;
      int input = 5;
  
      // Check if result is already in cache
      if (cache.find(input) == cache.end()) {
          // Perform computation and store result in cache
          cache[input] = expensiveComputation(input);
      }
  
      // Retrieve result from cache
      std::cout << "Result: " << cache[input] << std::endl;
      return 0;
  }

• Word Frequency Count:

  #include <unordered_map>
  #include <string>
  #include <iostream>
  
  int main() {
      std::unordered_map<std::string, int> wordCount;
      std::string words[] = {"apple", "banana", "apple", "orange", "banana", "banana"};
  
      // Count frequency of each word
      for (const std::string& word : words) {
          ++wordCount[word];
      }
  
      // Print word frequencies
      for (const auto& pair : wordCount) {
          std::cout << pair.first << ": " << pair.second << std::endl;
      }
  
      return 0;
  }

In summary, std::unordered_map is best used when you need fast access to data via unique keys and don't require the elements to be stored in any specific order. It is particularly effective for scenarios involving caching, fast lookups, counting, and associative data storage.

Using std::unordered_map on microcontrollers like the STM32, particularly in environments such as the Keil IDE, presents some challenges due to the constraints and characteristics of embedded systems. Here’s a breakdown of considerations and feasibility:

1. Memory Constraints:

   • Dynamic Memory: std::unordered_map relies on dynamic memory allocation (using new and delete), which can be problematic on microcontrollers with limited RAM. Microcontrollers often have constrained memory, and dynamic memory allocation can lead to fragmentation or insufficient memory issues.
   • Memory Overhead: The internal data structures of std::unordered_map (hash tables, buckets) can have significant memory overhead, which might not be acceptable on systems with limited RAM.

2. Standard Library Support:

   • Library Support: The availability of std::unordered_map depends on the C++ Standard Library implementation provided by the compiler and IDE. For embedded systems like STM32, not all libraries or compilers include full support for C++11 or later features by default. Ensure that the C++ standard library you are using supports std::unordered_map.

3. Performance Considerations:

   • Hash Functions and Collisions: std::unordered_map uses hash functions, which may not be optimized for all microcontroller environments. Performance issues could arise if the hash function is not well-suited for the available hardware.

4. Embedded Development Environment:

   • Keil IDE: Keil MDK (Microcontroller Development Kit) includes ARM's CMSIS and the Keil C++ library, but the full support for modern C++ features might be limited or require configuration. Verify whether your specific version of Keil MDK and its associated C++ runtime library support std::unordered_map.

1. Verify Compiler and Library Support:

   • Check the documentation for your compiler and standard library to confirm support for std::unordered_map. Ensure you are using a version of the library that includes this feature.

2. Consider Alternatives:

   • If memory constraints or library support issues arise, consider alternatives such as:
     • Fixed-size Arrays: For simple use cases, fixed-size arrays or lookup tables may suffice.
     • Other Containers: Depending on your needs, containers like std::map or custom data structures might be more appropriate.
     • Lightweight Hash Maps: Some specialized libraries or implementations are designed for embedded systems and might offer hash map functionality with reduced overhead.

3. Testing and Optimization:

   • Memory Usage: Carefully monitor and optimize memory usage. Ensure that your application does not run out of memory or experience fragmentation.
   • Performance Testing: Test the performance of std::unordered_map in your specific embedded environment to ensure it meets the requirements.

If your Keil IDE setup and library support std::unordered_map, you can use it as follows:

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Example of using std::unordered_map
    std::unordered_map<std::string, int> dataMap;

    // Insert some data
    dataMap["temperature"] = 23;
    dataMap["humidity"] = 45;

    // Access data
    std::cout << "Temperature: " << dataMap["temperature"] << std::endl;
    std::cout << "Humidity: " << dataMap["humidity"] << std::endl;

    return 0;
}

Using std::unordered_map in embedded systems like STM32 with Keil IDE is possible but depends on several factors including compiler support, memory constraints, and performance considerations. Ensure that your development environment supports the necessary C++ features and be mindful of the resource limitations typical in embedded systems. If std::unordered_map is not feasible, consider using alternative data structures or libraries better suited for embedded development.

When working with microcontrollers, especially in resource-constrained environments, using std::unordered_map may not always be the best choice due to its memory overhead and reliance on dynamic memory allocation. Instead, consider these alternative approaches and libraries that are often better suited for embedded systems:

1. Fixed-size Arrays or Lookup Tables:

   • Use Case: When you know the maximum number of entries and can allocate a fixed-size array.
   • Advantages: Minimal memory overhead, deterministic performance.
   • Example: If you need to map a limited set of keys to values and the keys are integer indices or known values, a simple array can be efficient.

   #include <array>
   #include <iostream>
   
   constexpr size_t SIZE = 10;
   std::array<int, SIZE> lookupTable = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
   
   int main() {
       int index = 5;
       std::cout << "Value at index " << index << " is " << lookupTable[index] << std::endl;
       return 0;
   }

2. std::map:

   • Use Case: When you need ordered key-value pairs and can tolerate the additional memory overhead of a balanced tree (e.g., Red-Black Tree).
   • Advantages: Provides ordered traversal, no need for custom hash functions.
   • Disadvantages: Generally has higher memory and time overhead compared to std::unordered_map for lookups.

3. Custom Hash Maps:

   • Use Case: When you need a hash map but with more control over memory usage and performance.
   • Advantages: You can design it to be more memory-efficient and better suited to the specific constraints of your application.
   • Libraries:
     • ****NuttX**: A real-time operating system (RTOS) that provides its own set of lightweight containers and utilities that might be suitable for embedded systems.
     • UTL (Ultra Lightweight Templates): A lightweight C++ template library designed for embedded systems.

4. Third-Party Lightweight Hash Maps:

   • ****Open Addressing Hash Maps**: Libraries specifically designed for embedded systems can be more memory-efficient than std::unordered_map.
   • ****Klaus Tschira's hash_map**: A minimalistic hash map implementation suitable for embedded systems.

5. STL Compatible Embedded Libraries:

   • ****EASTL (EA Standard Template Library)**: Provides STL-like containers optimized for performance and lower memory overhead, suitable for game development and embedded systems.
   • ****Arduino’s Standard Library**: For Arduino, libraries like ArduinoSTL offer STL-like containers optimized for the Arduino environment.

6. Custom Fixed-Size Hash Maps:

   • Use Case: When you need hash-based access but want to manage memory and performance more tightly.
   • Advantages: Customizable for your specific constraints and use cases.
   • Example: Implement a simple hash table with fixed-size buckets and linear probing for collision resolution.

Here’s an example of a simple hash map with fixed size and linear probing, suitable for embedded systems:

#include <iostream>
#include <string>
#include <vector>
#include <optional>

template<size_t SIZE>
class FixedHashMap {
public:
    FixedHashMap() : table(SIZE, std::nullopt) {}

    void insert(const std::string& key, int value) {
        size_t index = hash(key) % SIZE;
        while (table[index].has_value() && table[index]->first != key) {
            index = (index + 1) % SIZE;  // Linear probing
        }
        table[index] = {key, value};
    }

    std::optional<int> find(const std::string& key) const {
        size_t index = hash(key) % SIZE;
        while (table[index].has_value()) {
            if (table[index]->first == key) {
                return table[index]->second;
            }
            index = (index + 1) % SIZE;  // Linear probing
        }
        return std::nullopt;
    }

private:
    std::vector<std::optional<std::pair<std::string, int>>> table;

    size_t hash(const std::string& key) const {
        size_t hash = 0;
        for (char c : key) {
            hash = hash * 31 + c;
        }
        return hash;
    }
};

int main() {
    FixedHashMap<10> map;
    map.insert("apple", 1);
    map.insert("banana", 2);
    map.insert("cherry", 3);

    auto result = map.find("banana");
    if (result.has_value()) {
        std::cout << "Found value: " << result.value() << std::endl;
    } else {
        std::cout << "Key not found" << std::endl;
    }

    return 0;
}

When working with microcontrollers, it’s often best to use data structures and libraries that are tailored to the constraints of embedded systems. Consider using fixed-size arrays, custom hash maps, or lightweight third-party libraries designed for embedded environments. Ensure that whatever solution you choose is compatible with your microcontroller’s memory limitations and performance requirements.