C++プログラマへの道 #11 - 無順序連想コンテナ

C++DSA

Last Edited: 10/8/2024

このブログ記事では、C++における無順序セットやマップなどの無順序連想コンテナを紹介します。

C++ Set Map

前回の記事では、要素が順序通りに格納されるシーケンスコンテナについて取り上げました。今回の記事では、要素が従来の連想コンテナのようにソートされない、無順序連想コンテナについて説明します。

無順序セット

名前が示すように、無順序セットはデフォルトで順序を保持せず、しかし一意性を強制します。つまり、すべての要素は一意でなければなりません。

#include <unordered_set>
 
int main() {
    
    unordered_set<int> s;
    s.insert(1);
    s.insert(3);
    s.insert(2);
    s.insert(2);
 
    cout << "s:";
    for (auto i: s) {
        cout << " " << i;
    }
    cout << endl;
    // => s: 1 3 2
 
    return 0;
}

見てわかるように、setとインターフェースは非常に似ていますが、要素の順序は保持されません。 順序を犠牲にすることで、無順序セットは挿入をより高速に行うことができます。

無順序マップ

無順序マップは、名前の通りキーに対するデフォルトの順序付けがないマップです。

#include <unordered_map>
 
int main () {
    unordered_map<string, int> m;
    m["a"] = 1;
    m["b"] = 2;
    m.insert(pair<string, int>("c", 3)); // "pair" is an object for key-value pair
 
    cout << "m:" << endl;
    for (auto i: s) {
        cout << " " << i.first << ": " << i.second << endl;
    }
    // => m: 
    //    a: 1
    //    b: 2
    //    c: 3
 
    return 0;
}

mapとインターフェースはほぼ同じですが、要素の順序は保持されません。このトレードオフにより、挿入と検索がより高速になります。

ハッシュテーブル

二分探索木（BST）は、要素の順序を維持することに重点を置いているため、無順序セットや無順序マップを実装するには最適ではありません。 そこで、順序を犠牲にしても高速な検索を可能にする別のデータ構造であるハッシュテーブルがあります。 配列の特定のインデックスへのアクセスはO(1)O(1)ですが、どのインデックスに要素があるかは通常わかりません。 ハッシュテーブルは、キーを数値に変換し、その数値に対してモジュロ演算を行うハッシュ関数を使用して、要素のインデックスを決定します。

C++ Hashing

上記の例は、ハッシュテーブルの例です。ハッシュ関数はASCIIテーブルを使用して文字列を数値に変換し、その数値に対して11でモジュロ演算を行い、文字列を格納するインデックスを決定します。 このようにして、キーを検索する際には同じハッシュ関数を使用してキーが格納されているインデックスを特定できます。無順序セットではキーのみを格納し、無順序マップではキーと値のペアを格納します。

衝突

理想的には、各キーがユニークなインデックスにマップされますが、実際には2つのキーが同じインデックスにマップされることがよくあります。 これを 衝突（コリジョン） と呼びます。衝突を処理する方法はいくつかありますが、簡単な方法の一つは、各インデックスにリンクリストを作成することです。 キーを検索する際には、ハッシュ関数でインデックスを特定し、そのインデックスが指すリンクリストをたどって要素を見つけます。 この場合ハッシュテーブルで要素を検索する最悪のケースの時間計算量はO(n)O(n)になってしまいますが、これを回避するために、より良いハッシュ関数と大きな除数を使用することができます。

#include <iostream>
using namespace std;
 
class Node {
    public:
        int data;
        Node* next;
 
    Node(int data): data(data), next(nullptr) {};
};
 
class HashTable {
    public:
        Node* table[11];
 
        int insert(int data) {
            Node* new_node = new Node(data);
            int index = hash(data);
 
            if (table[index] == nullptr) {
                table[index] = new_node;
                return 1;
            };
 
            Node* p_current = table[index];
            while (p_current != nullptr) {
                if (p_current->data == data) {
                    return 0;
                }
                if (p_current->next == nullptr) {
                    p_current->next = new_node;
                    return 1;
                }
                p_current = p_current->next;
            }
            
            return 0;
        };
 
        void print() {
            for (int i = 0; i < 11; i++) {
                Node* p_current = table[i];
                if (p_current == nullptr) {
                    continue;
                }
                cout << "Index: " << i << ", Value: ";
                while (p_current != nullptr) {
                    cout << " -> " << p_current->data;
                    p_current = p_current->next;
                }
                cout << endl;
            }
        };
 
    HashTable() : divisor(11) {
        for (int i = 0; i < 11; i++) {
                table[i] = nullptr;
            }
    };
 
    ~HashTable() {
        for (int i = 0; i < 11; i++) {
            Node* p_current = table[i];
            while (p_current != nullptr) {
                Node* next_node = p_current->next;
                delete p_current;
                p_current = next_node;
            }
        }
    };
 
    private:
        int divisor;
 
        int hash(int data) {
            return data % divisor;
        };
};
 
int main () {
 
    HashTable ht;
    ht.insert(5);
    ht.insert(10);
    ht.insert(16);
    ht.insert(121);
    ht.print();
    // =>
    // Index: 0, Value:  -> 121
    // Index: 5, Value:  -> 5 -> 16
    // Index: 10, Value:  -> 10
 
    return 0;
}

上記の例は、C++で部分的に実装されたハッシュテーブルの例です。簡易化のためにキーは整数に限定されており、ハッシュ関数は単にキーに対して直接モジュロ演算を行い、除数として11を使用しています。 この例から、無順序セットや無順序マップがハッシュテーブルでどのように構築されるかがわかります。チャレンジとして、検索や削除の実装、または異なるハッシュ関数や衝突処理方法を使用したクラステンプレートを実装してみることをお勧めします。

結論

この記事では、C++標準ライブラリで利用可能な無順序連想コンテナについて紹介しました。連想コンテナはBSTで実装されているため、デフォルトでキーを昇順に並べますが、 無順序連想コンテナは、ハッシュテーブルで実装されているため、順序がない代わりにパフォーマンスの向上が見られます。しかし、 実装によっては多くの衝突が起こり、パフォーマンスが著しく低下してしまう可能性があることに留意が必要です。

リソース

TOPに戻る↑