モーダルを閉じる工作HardwareHub ロゴ画像

工作HardwareHubは、ロボット工作や電子工作に関する情報やモノが行き交うコミュニティサイトです。さらに詳しく

利用規約プライバシーポリシー に同意したうえでログインしてください。

工作HardwareHub ロゴ画像 (Laptop端末利用時)
工作HardwareHub ロゴ画像 (Mobile端末利用時)

STL/集合と連想配列 (C++をもう一度)

モーダルを閉じる

ステッカーを選択してください

モーダルを閉じる

お支払い内容をご確認ください

購入商品
」ステッカーの表示権
メッセージ
料金
(税込)
決済方法
GooglePayマーク
決済プラットフォーム
確認事項

利用規約をご確認のうえお支払いください

※カード情報はGoogleアカウント内に保存されます。本サイトやStripeには保存されません

※記事の執筆者は購入者のユーザー名を知ることができます

※購入後のキャンセルはできません

作成日作成日
2014/12/28
最終更新最終更新
2017/05/04
記事区分記事区分
一般公開

目次

    低レイヤーのプログラミングとOS開発が趣味。C言語を使っています。

    0
    ステッカーを贈るとは?

    ツリーはデータを階層的に扱うデータ構造です。各ノードの子ノードが最大二つしか存在しないことが保証されているツリーを特に二分木とよびます。データ構造である二分木に新たな要素ノードを追加する際の規則を工夫することで、要素の検索を二分探索で実行できるようになります。この場合の二分木を特に二分探索木とよびます。二分探索木に対し、ソートされた要素を順番に追加すると性能が極端に悪くなってしまいます。これは二分探索木の中でも特殊な平衡二分探索木を使用することで回避できます。

    二分探索木の要素ノードには key と value の二つの属性を備えることができます。key のみが備えられた二分探索木を集合 set とよびます。key と value の両方が備えられた二分探索木を連想配列 map とよびます。

    連想配列 map

    #include <iostream>
    #include <map>
    using namespace std;
    
    int main() {
        map<string, int> m;
        multimap<string, int> mm; // キーの重複が許される連想配列
    
        // 値の追加
        m["one"] = 1;
        m["two"] = 2;
        m.insert( map<string, int>::value_type("two", 2) ); // としても同じ
        cout << m.size() << endl; //=> 2 (キーの重複が許されなかったため 3 とはならない)
    
        // multimap の場合は重複可能性があるため [] 演算子は使用できません
        mm.insert( multimap<string, int>::value_type("one", 1) );
        mm.insert( multimap<string, int>::value_type("one", -1) );
        cout << mm.size() << endl; //=> 2
    
    
        // 値の参照
        cout << m["one"] << endl; //=> 1
        for(map<string, int>::iterator it = m.begin(), end = m.end(); it != end; ++it) {
            cout << it->first << ": " << it->second << endl; //=> one: 1
        }                                                    //   two: 2
    
        for(multimap<string, int>::iterator it = mm.begin(), end = mm.end(); it != end; ++it) {
            cout << it->first << ": " << it->second << endl; //=> one: 1
        }                                                    //   one: -1
    
        // 該当キーの要素数
        cout << m.count("one") << endl; //=> 1
        cout << mm.count("one") << endl; //=> 2
    
    
        // 値の検索
        map<string, int>::iterator it = m.find("one");
        if ( it != m.end() ) { // 見つからなければ m.end() が返されます
            cout << "found: (" << it->first << ", " << it->second << ")" << endl; //=> found: (one, 1)
        }
    
        multimap<string, int>::iterator it_ = mm.find("one");
        if ( it_ != mm.end() ) {
            cout << "found" << endl; //=> found
        }
    
        // 値の削除
        cout << m.erase("one") << endl; //=> 1 (削除された要素数)
        cout << m.erase("not_exist") << endl; //=> 0 (存在しない要素の場合)
        cout << m.size() << endl; //=> 1
    
        cout << mm.erase("one") << endl; //=> 2
        cout << mm.size() << endl; //=> 0
    
        // 全削除
        m.clear();
        mm.clear();
        cout << boolalpha
             << m.empty() << endl //=> true
             << mm.empty() << endl; //=> true
    
        return 0;
    }
    

    集合 set

    #include <iostream>
    #include <set>
    using namespace std;
    
    int main() {
        set<int> s;
        multiset<int> ms; // 重複が許される集合
    
        // 要素の追加
        s.insert( set<int>::value_type(0) );
        s.insert( set<int>::value_type(0) );
        cout << s.size() << endl; //=> 1 (キーの重複が許されなかったため 2 とはならない)
    
        ms.insert( multiset<int>::value_type(0) );
        ms.insert( multiset<int>::value_type(0) );
        cout << ms.size() << endl; //=> 2
    
        // 要素の列挙
        for(set<int>::iterator it = s.begin(), end = s.end(); it != end; ++it) {
            cout << *it << endl; //=> 0
        }
    
        for(multiset<int>::iterator it = ms.begin(), end = ms.end(); it != end; ++it) {
            cout << *it << endl; //=> 0
        }                       //    0
    
        // 該当キーの要素数
        cout << s.count(0) << endl; //=> 1
        cout << ms.count(0) << endl; //=> 2
    
        // 値の検索
        set<int>::iterator it = s.find(0);
        if ( it != s.end() ) { // 見つからなければ s.end() が返されます
            cout << "found: " << *it << endl; //=> found: 0
        }
        multiset<int>::iterator it_ = ms.find(0);
        if ( it_ != ms.end() ) {
            cout << "found: " << *it_ << endl; //=> found: 0
        }
    
        // 値の削除
        cout << s.erase(0) << endl; //=> 1 (削除された要素数)
        cout << s.erase(-1) << endl; //=> 0 (存在しない要素の場合)
        cout << s.size() << endl; //=> 0
    
        cout << ms.erase(0) << endl; //=> 2
        cout << ms.size() << endl; //=> 0
    
        // 全削除
        s.clear();
        ms.clear();
        cout << boolalpha
             << s.empty() << endl //=> true
             << ms.empty() << endl; //=> true
    
        return 0;
    }
    
    0
    詳細設定を開く/閉じる
    アカウント プロフィール画像 (本文下)

    低レイヤーのプログラミングとOS開発が趣味。C言語を使っています。

    記事の執筆者にステッカーを贈る

    有益な情報に対するお礼として、またはコメント欄における質問への返答に対するお礼として、 記事の読者は、執筆者に有料のステッカーを贈ることができます。

    さらに詳しく →
    ステッカーを贈る コンセプト画像

    Feedbacks

    Feedbacks コンセプト画像

      ログインするとコメントを投稿できます。

      関連記事