学ぶアンオーダードコンテナ：unordered_set、unordered_map

メニューを表示するにはスワイプしてください

定義

C++の非順序コンテナは、ハッシュテーブルを使用して要素を格納および取得し、挿入や検索において平均して定数時間のパフォーマンスを提供。

std::setやstd::mapのような順序付きコンテナとは異なり、std::unordered_setやstd::unordered_mapなどの非順序コンテナは要素をソートしない。代わりにハッシュ化を利用し、キーのハッシュ値によって格納バケットが決まり、多くの場合で高速なアクセスが可能。

最も一般的に使用される非順序コンテナはstd::unordered_setとstd::unordered_map：

挿入や検索で高速な平均定数時間を実現；
要素の順序は保持しない；
ハッシュ衝突により最悪の場合は線形時間になる可能性がある；
要素の順序よりもキーによる操作の速度を重視する場合に最適。

順序付きコンテナと非順序コンテナの選択は、要素の順序を重視するか、キー操作の平均速度を重視するかによって決定。

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";
}

アンオーダードコンテナは、ハッシュ関数を使用して要素を内部バケットに効率的に分散します。C++ では標準型に対して組み込みのハッシュ関数が提供されていますが、カスタム型の場合は均等な分布と衝突の最小化を確保するために独自のハッシュ関数を定義する必要があります。

衝突は、異なるキーが同じハッシュ値を生成した場合に発生します。コンテナはこれらを同じバケットにグループ化し、多くの場合リンクリストを使用して管理します。定数時間のパフォーマンスを維持するためには、設計の良いハッシュ関数を使用し、ユーザー定義キー型の場合はカスタムハッシュと等価関数の両方を提供することが重要です。

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';
}

すべて明確でしたか？

フィードバックありがとうございます！

セクション 1. 章 4

AIに質問する

何でも質問するか、提案された質問の1つを試してチャットを始めてください

セクション 1. 章 4