Lernen Unordered Containers: unordered_set, unordered_map

Definition

Unordered containers in C++ store and retrieve elements using hash tables, offering average constant-time performance for insertions and lookups.

Unlike ordered containers like std::set and std::map, unordered containers such as std::unordered_set and std::unordered_map do not keep elements sorted. Instead, they rely on hashing, where a key’s hash value determines its storage bucket, enabling faster access in most cases.

The most commonly used unordered containers are std::unordered_set and std::unordered_map:

Offer fast, average-case constant time insertions and lookups;
Do not maintain any particular order of elements;
May degrade to linear time in the worst case due to hash collisions;
Are ideal when you prioritize speed for key-based operations over element ordering.

Choosing between ordered and unordered containers depends on whether you prioritize element ordering or average-case speed for key-based operations.

main.cpp


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

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

    std::string query = "banana";
    
    if (wordCounts.find(query) != wordCounts.end())
        std::cout << query << ": " << wordCounts[query] << '\n';
    else
        std::cout << query << " not found.\n";
}

Unordered containers use hash functions to distribute elements efficiently across internal buckets. C++ provides built-in hash functions for standard types, but for custom types, you may need to define your own to ensure even distribution and minimize collisions.

Collisions occur when different keys produce the same hash value. The container handles them by grouping elements in the same bucket, often using linked lists. To maintain constant-time performance, use a well-designed hash function and provide both a custom hash and an equality function when working with user-defined key types.

main.cpp


              123456789101112131415161718192021
            
#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& other) const { return x == other.x && y == other.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const { return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1); }
};

int main()
{
    std::unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2}); // Duplicate, will not be inserted

    std::cout << "Number of unique points: " << points.size() << '\n';
}

War alles klar?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 4

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Suggested prompts:

Can you explain how to write a custom hash function for my own type?

What happens if my hash function causes too many collisions?

How do I choose between ordered and unordered containers in practice?

Awesome!

Completion rate improved to 6.67

Swipe um das Menü anzuzeigen

Definition

Unordered containers in C++ store and retrieve elements using hash tables, offering average constant-time performance for insertions and lookups.

The most commonly used unordered containers are std::unordered_set and std::unordered_map:

Offer fast, average-case constant time insertions and lookups;
Do not maintain any particular order of elements;
May degrade to linear time in the worst case due to hash collisions;
Are ideal when you prioritize speed for key-based operations over element ordering.

Choosing between ordered and unordered containers depends on whether you prioritize element ordering or average-case speed for key-based operations.

main.cpp


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

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

    std::string query = "banana";
    
    if (wordCounts.find(query) != wordCounts.end())
        std::cout << query << ": " << wordCounts[query] << '\n';
    else
        std::cout << query << " not found.\n";
}

main.cpp


              123456789101112131415161718192021
            
#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& other) const { return x == other.x && y == other.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const { return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1); }
};

int main()
{
    std::unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2}); // Duplicate, will not be inserted

    std::cout << "Number of unique points: " << points.size() << '\n';
}

War alles klar?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 4