C++プログラマへの道 #10 - 連想コンテナ

C++DSA

Last Edited: 10/1/2024

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

C++ Set Map

前回の記事では、要素が順序通りに保存されるシーケンスコンテナについて説明しました。 今回の記事では、キーに基づいて効率的に要素を取得できる連想コンテナについて説明します。

セット

他のコンテナが重複する要素を許すのに対し、セットは要素をユニークかつ（デフォルトでは昇順に）ソートされた状態で保持します。

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

セットは、イテレータを含む標準的なコンテナ操作もサポートしています。

マップ

マップはユニークなキーを保持するだけでなく、キーに関連付けられた値（キー-値ペア）を保存します。セットと同様に、マップのキーもデフォルトでは昇順で保存されます。

#include <map>
 
int main () {
    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;
}

マップ内では、キーと値のペアは pair オブジェクトとして保存され、first はキーを、second は対応する値を表します。マップは、イテレータを含む標準的なコンテナ操作もサポートしています。

二分探索木

set と map コンテナは、要素のソートや検索を効率的に行うためのデータ構造であり、 これらは二分探索木（BST） を使用して実装されています。二分探索木は、各ノードが最大で2つの子ノードを持ち、 左のノードはルートノードよりも小さく、右のノードはルートノードよりも大きいという構造を持つ木です。

BST

上記は、二分探索木の例です。要素の検索は木の高さに依存し（平衡木ではO(log2n)O(log_2 n)）、 ルートノードから比較することで半分ずつ要素を除外していくことができるため、効率的です。 要素の挿入も効率的に行われ（平衡木ではO(log2n)O(log_2 n)）、各レベルでノードを比較しながら適切な挿入場所を検索します。 以下は、BSTのC++の部分的な実装です。

#include <iostream>
using namespace std;
 
template <typename T>
class Node {
public:
    T data;
    Node* left;
    Node* right;
 
    // Constructor to initialize the node with data and null left and right pointers
    Node(T data) : data(data), left(nullptr), right(nullptr) {};
};
 
template <typename T>
class BST {
public:
    Node<T>* root;
 
    // Constructor initializes the root as nullptr (empty tree)
    BST() : root(nullptr) {};
 
    void insert(T data) {
        root = insertion(root, new Node<T>(data));
    }
 
    void print() {
        display(root);
        cout << endl;
    };
 
private:
    Node<T>* insertion(Node<T>* root, Node<T>* node) {
        if (root == nullptr) {
            return node;
        }
 
        if (node->data < root->data) {
            root->left = insertion(root->left, node);
        } else if (node->data > root->data) {
            root->right = insertion(root->right, node);
        }
        return root;
    };
 
    void display(Node<T>* root) {
        if (root != nullptr) {
            display(root->left);
            cout << root->data << " ";
            display(root->right);
        }
    };
};

上記の実装は、挿入と印刷の機能のみを実装しています。チャレンジとして、検索や削除を実装することをお勧めします。 （ノードの削除は、ノードの移動が必要になることがあり、少し複雑です。） このように、set は一意の要素をソートされた順序で効率的に検索・挿入できるようにBSTを使用して実装されています。 map も、キーと値を保持するノードを持つBSTで構築できます。

結論

この記事では、C++標準ライブラリで利用可能な連想コンテナについて紹介し、これらがBSTを使用して効率的な挿入と検索を実現していることを説明しました。 次回の記事では、別の種類のコンテナである順序なし連想コンテナについて探求します。

リソース

TOPに戻る↑