techmore.in

C++ Unordered Sets and Maps

In C++, std::unordered_set and std::unordered_map are associative containers provided by the Standard Template Library (STL) that store elements based on hash tables. These containers allow for average constant-time complexity for insertions, deletions, and lookups, making them suitable for scenarios where fast access is required and ordering is not important.

std::unordered_set

std::unordered_set is similar to std::set but uses a hash table for storage. Elements are stored based on their hash values rather than a strict order.

Basic Operations with std::unordered_set

  1. Include the Necessary Header:

    cpp
    #include 
#include

  2. Declare an Unordered Set:

    cpp
    std::unordered_set<int> mySet;

  3. Add Elements:

    cpp
    mySet.insert(5);
mySet.insert(10);
mySet.insert(3);

  4. Check for Presence of an Element:

    cpp
    if (mySet.find(10) != mySet.end()) {
    std::cout << "10 is in the unordered set." << std::endl;
}

  5. Remove Elements:

    cpp
    mySet.erase(5);  // Removes the element with value 5

  6. Iterate Through the Unordered Set:

    cpp
    for (const auto& elem : mySet) {
    std::cout << elem << " ";
}
std::cout << std::endl;

  7. Get the Size of the Unordered Set:

    cpp
    std::cout << "Size of the unordered set: " << mySet.size() << std::endl;

  8. Check if the Unordered Set is Empty:

    cpp
    if (mySet.empty()) {
    std::cout << "Unordered set is empty." << std::endl;
}

std::unordered_map

std::unordered_map is similar to std::map but uses a hash table for storage. It stores key-value pairs, with keys being unique.

Basic Operations with std::unordered_map

  1. Include the Necessary Header:

    cpp
    #include 
#include

  2. Declare an Unordered Map:

    cpp
    std::unordered_map<int, std::string> myMap;

  3. Add Elements:

    cpp
    myMap[1] = "one";
myMap[2] = "two";
myMap[3] = "three";

  4. Access Elements:

    cpp
    std::cout << "Value associated with key 2: " << myMap[2] << std::endl;

    You can also use the at method:

    cpp
    try {
    std::cout << "Value associated with key 4: " << myMap.at(4) << std::endl;
} catch (const std::out_of_range& e) {
    std::cout << "Key 4 does not exist." << std::endl;
}

  5. Check for Presence of a Key:

    cpp
    if (myMap.find(3) != myMap.end()) {
    std::cout << "Key 3 exists in the unordered map." << std::endl;
}

  6. Remove Elements:

    cpp
    myMap.erase(2);  // Removes the element with key 2

  7. Iterate Through the Unordered Map:

    cpp
    for (const auto& pair : myMap) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

  8. Get the Size of the Unordered Map:

    cpp
    std::cout << "Size of the unordered map: " << myMap.size() << std::endl;

  9. Check if the Unordered Map is Empty:

    cpp
    if (myMap.empty()) {
    std::cout << "Unordered map is empty." << std::endl;
}

Custom Hash Functions

You can define custom hash functions and equality predicates if you need special handling for the keys in your unordered containers.

  1. Define a Custom Hash Function:

    cpp
    struct CustomHash {
    std::size_t operator()(int key) const {
        return std::hash<int>{}(key) ^ 0x12345678;  // Example custom hash function
    }
};

  2. Define a Custom Equality Predicate:

    cpp
    struct CustomEqual {
    bool operator()(int lhs, int rhs) const {
        return lhs % 10 == rhs % 10;  // Example custom equality function
    }
};

  3. Use Custom Hash Function and Equality Predicate:

    cpp
    std::unordered_set<int, CustomHash, CustomEqual> customSet;

Example Code

Here’s a complete example demonstrating basic operations for both std::unordered_set and std::unordered_map:

cpp
#include 
#include 
#include 
#include 

// Custom hash function
struct CustomHash {
    std::size_t operator()(int key) const {
        return std::hash<int>{}(key) ^ 0x12345678;
    }
};

// Custom equality predicate
struct CustomEqual {
    bool operator()(int lhs, int rhs) const {
        return lhs % 10 == rhs % 10;
    }
};

int main() {
    // Unordered set
    std::unordered_set<int> mySet = {5, 10, 3, 7};

    std::cout << "Unordered set:" << std::endl;
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Unordered map
    std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    std::cout << "Unordered map:" << std::endl;
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // Custom unordered set
    std::unordered_set<int, CustomHash, CustomEqual> customSet = {5, 15, 25};  // Example with custom hash and equality
    std::cout << "Custom unordered set:" << std::endl;
    for (const auto& elem : customSet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output

yaml
Unordered set:
5 10 3 7
Unordered map:
1: one
2: two
3: three
Custom unordered set:
5 15 25

This example demonstrates basic usage and custom configuration of unordered associative containers.