C++ 順序付集合 std::set とは

C++ の std::set とは順序付けされたデータを複数保持することができる順序付集合のコンテナクラスだぞ。
データを順不同に順序付集合に追加すると、その値をキーにし自動的にソートして内部に格納してくれるぞ。
つまり、要素が常にソートされた状態の配列のようなものだ。
内部的にはツリーを使用するので、ix 番目の要素を高速に取り出すことは出来ないけどね。
なお、multiset とは違い、重複するデータを保持することはできないぞ。

set はデータの追加・削除・検索の処理速度が O(log N) と高速だ。
vector に入っているデータを単純に検索すると処理速度は O(N) だが、あらかじめ O(N * log N) の時間をかけてデータをソートし、 lower_bound 等の二分探索を行うと O(log N) となる。
なので、データが動的に追加されないような場合は、vector を用いた方がメモリ効率がよく、速度差も無い。
しかし、ランダム・アクセスが必要なくて、データ追加が動的に何度も行われ、平行して検索するような場合は vector よりも set を用いた方がいいぞ。

データ構造

std::set のデータ構造の例を下図に示す。通常は赤黒木が用いられる。

これはデータ構造の一例であり、あなたの環境の実際のデータ構造とは少し違うかもしれない。

重要なことは、以下の３点である。

• 各ノードには値が入っていて、左右の子供ノードへのポインタを持つ
• 左の子供の値 ＜ 値 ＜ 右の子供の値 という条件が成立している（set は重複を許さないので「≦」でなく「＜」）
• ノードの深さは概ね同じで、ツリーはバランスしている

準備：インクルード

set は C++標準のライブラリであり、「#include <set>」を記述することで利用可能になる。

名前空間は「std」なので、使用の度に「std::」を前置するか、または「using namespace std;」を記述しておく。

#include <set>       // ヘッダファイルインクルード
int main()
{
    std::set<int> st;       // ローカル変数として、st を生成
    .....
}

#include <set>       // ヘッダファイルインクルード
using namespace std;         //  名前空間指定
int main()
{
    set<int> st;       // ローカル変数として、st を生成
    .....
}

宣言・初期化

単純な宣言

std::set オブジェクトを生成するには「std::set<型> オブジェクト名;」 と記述する。
オブジェクト名とは、宣言する順序付集合を識別するための名前のことだ。変数名と言ってもよい。 set はクラスなので、それを実体化したものはオブジェクトまたはインスタンスと呼ばれる。
下記は、int 型の順序付集合 st を宣言している例だ。

    std::set<int> st;  //  int 型の順序付集合 st の宣言

型はたいてい何でも指定可能なのだが、set は順序付集合なので、大小比較が可能であることが必須である。つまり operator<() が定義済みでないといけない。 int などのPODや string はデフォルトで大小比較可能であるが、vector や自分で定義した型は大小比較が出来ないかもしれない。
そのような型を順序付集合に格納するには、operator<() を自分で定義するといいぞ。

struct Person {
    string m_name;
    int    m_height;
};
// 比較演算子の定義
bool operator<(const Person &lhs, const Person &rhs)
{
    return lhs.m_name < rhs.m_name;
}
std::set<Person> st;       // 比較演算子を定義しておけばOK

データを指定して初期化

C++11 以上であれば初期化リストを利用して、要素の初期化が可能。

    std::set<int> st{3, 1, 4};

上記の様に記述すると、3, 1, 4 が要素として格納される。set は順序付集合なので、格納されるときに自動的にソートされ、内部では {1, 3, 4} の順序となる。

    std::set<int> st{3, 1, 4, 1};

set は重複を許さない順序付集合なので、上記のように重複データがある場合は、重複データは自動的に削除され、{1, 3, 4} だけが格納される。
ちなみに、重複を許す順序付集合 multiset であれば {1, 1, 3, 4} が格納される。

コピーコンストラクタ

コピーコンストラクタとは、同じ型のオブジェクトを渡され、それと同じ内容のオブジェクトを生成するコンストラクタのことである。
「std::set<型> オブジェクト名(コピー元オブジェクト名);」と記述する。
当然ながら、コピー元オブジェクトと生成するオブジェクトは通常同じ型である。

    std::set<int> org{3, 1, 4};
    std::set<int> x(org);      // コピーコンストラクタ

上記のコードは org をコピーするので {1, 3, 4} という値をもつ動的配列 x を生成する。

演習問題：

1. int 型の順序付集合を {3, 1, 4} で初期化するコードを書き、ビルド、デバッガで実行し、中身を確認しなさい。 show

    std::set<int> st{3, 1, 4};

2. int 型の順序付集合を {3, 1, 4, 1} で初期化するコードを書き、ビルド、デバッガで実行し、中身を確認しなさい。 show

    std::set<int> st{3, 1, 4, 1};

3. コピーコンストラクタの例をビルドし、デバッガで実行して正しくコピーされていることを確認しなさい。
4. class Person { string m_name; int m_height; }; を順序付集合に格納できるよう、名前のみで順序を決める比較関数を定義しなさい。 show

class Person { string m_name; int m_height; };
bool operator<(const Person &lhs, const Person &rhs)
{
    return lhs.m_name < rhs.m_name;
}
std::set<Preson> st;

まとめ

• std::set<型> 変数名; で、型の順序付集合を生成できるぞ
• 型は < 演算子が定義されていないとだめだぞ
• std::set<型> 変数名{値, 値, ... 値}; で、順序付集合を初期化できるぞ
• std::set<型> x(org); で、順序付集合をコピーできるぞ

値の参照

set の内部構造は配列ではなく、二分木になっているので、[] 演算子（operator[](size_t)）で、指定番目の要素を取り出すことは出来ない。
したがって、イテレータ を使って各要素にアクセスする必要がある。

イテレータとは抽象化されたポインタのことだ。begin() で最初の要素への、end() で最後の要素の次へのイテレータを取得することが出来る。

    std::set<int> st{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    auto itr = st.begin();       // 最初の要素へのイテレータを取得
    std::cout << *itr << "\n";      // イテレータの指す先のデータを表示

イテレータの型は std::set<型>::iterator であるが、タイプが大変なので、通常は上記のように auto を使用する。
set のイテレータはランダム・アクセス不可で、前後にのみ移動出来る。
ix 番目の要素に無理やりアクセスしたい場合は、begin() で取ってきたイテレータを ix 回インクリメントする。

    auto itr = st.begin();
    for(int i = 0; i < ix; ++i)
        ++itr;

*itr で、イテレータの指す先の要素の値を取得できる。

全ての要素を表示するときは、以下のように記述する。イテレータのお決まりの書き方だ。

    std::set<int> st{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    for(auto itr = st.begin(); itr != st.end(); ++itr) {
        std::cout << *itr << "\n";      // イテレータの指す先のデータを表示
    }

ちなみに、C++11で導入された範囲forを使うことも出来る。

    std::set<int> st{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    for(auto x : st) {
        std::cout << x << "\n";     // 要素を順に表示
    }

通常、非const なイテレータは *itr = 値; で、イテレータが指す先の要素の値を上書きすることができるが、 VC++ では 非const なイテレータでも中身の上書きは不可のようだ。

    std::set<int> st{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    std::set<int>::iterator itr = st.begin();       // 最初の要素へのイテレータを取得
    *itr = 123;    //  コンパイルエラーとなる

演習問題：

1. int 型、順序付集合を、{8, 1, 4} で初期化し、最初の要素を表示してみなさい。show

    std::set<int> st{8, 1, 4};
    auto itr = st.begin();
    std::cout << *itr << "\n";

2. int 型、順序付集合を、{8, 1, 4} で初期化し、最後の要素を表示してみなさい。show

    std::set<int> st{8, 1, 4};
    auto itr = st.end();
    --itr;
    std::cout << *itr << "\n";

3. int 型、順序付集合を、{8, 1, 4} で初期化し、最初から最後まで、全ての要素を表示してみなさい。 show

    std::set<int> st{8, 1, 4};
    for(auto itr = st.begin(); itr != st.end(); ++itr {
        std::cout << *itr << "\n";
    }

まとめ

• 順序付集合要素の値を参照するときは、イテレータを作り、それ経由で参照する
• イテレータ経由で値を書き換えることはできない

データの追加

• insert(値) : pair<iterator, bool>

insert(値) : pair<iterator, bool>

順序付集合にデータを追加するときは insert(値) を使用する。
値は、ソートされた位置に挿入される。
なので、push_back(値) や push_front(値) は無い。挿入する位置を指定するのは無意味だからだ。

    std::set<int> st{3, 1, 4};
    st.insert(2);   //  値 2 を追加

既に格納されているデータと同じものを追加しても無視される。

    std::set<int> st{3, 1, 4};
    st.insert(3);   //  値 3 は既に格納されているので、無視される

insert(値) は pair<iterator, bool> を返す。ペアの最初（first）は、挿入した値へのイテレータで、2番め（second）は挿入が実際に行われたかどうかを表す。

    std::set<int> st{3, 1, 4};
    auto r = st.insert(2);
    std::cout << r.second << "\n";       // r.second は true
    r = st.insert(2);
    std::cout << r.second << "\n";       // r.second は false

データ追加の処理速度は O(log N)

演習問題：

1. int 型の順序付集合 st を作り、そこに [0, 10000) の範囲のランダムな要素を1万回格納しなさい。 デバッガで、実際に格納された要素数を確認しなさい。show

    const int N = 10000;
    const int RAND_UPPER = 10000;       // 乱数値上限
    set<int> st;
    for (int i = 0; i < N; ++i) {
        st.insert(rand() % RAND_UPPER);       // [0, 9999]
    }

2. 上記の処理速度を計測しなさい。同じことを10万回、100万回行った場合の処理速度も計測してみなさい。show

#include <iostream>
#include <set>
#include <chrono>
void measure(int N)
{
    std::cout << N << ":";
    const int RAND_UPPER = 10000;       // 乱数値上限
    set<int> st;
    auto start = std::chrono::system_clock::now();      // 計測スタート時刻を保存
    for (int i = 0; i < N; ++i) {
        st.insert(rand() % RAND_UPPER);       // [0, 9999]
    }
    auto end = std::chrono::system_clock::now();       // 計測終了時刻を保存
    auto dur = end - start;        // 要した時間を計算
    // 要した時間をミリ秒（1/1000秒）に変換して表示
    std::cout << std::chrono::duration_cast(dur).count() << " milli sec \n";
}

int main()
{
    measure(10000);
    measure(100000);
    measure(1000000);
    return 0;
}

まとめ

• insert(値) で指定値を順序付集合に追加できるぞ
• 上記は pair<iterator, bool> を返す。２番めの値は、実際に値を追加したかどうかだ

データの削除

• erase(値) : size_t
• erase(イテレータ) : iterator
• erase(first, last) : iterator

erase(値) : size_t

erase(値) で値が格納されていれば、それを削除する。リターン値として削除したデータの個数（1 or 0）を返す。

    std::set<int> st{3, 1, 4};
    auto c = st.erase(3);      //  3 を削除、1 が返ってくる
    c = st.erase(3);      // 再度 3 を削除、既に削除済みなので 0 が返ってくる

削除処理に要する時間は O(log N) である。

erase(イテレータ) : iterator

引数にイテレータを指定することも出来る。リターン値として、削除した要素の次の要素へのイテレータを返す。

以下は、偶数の要素を全て削除する例。

    set<int> st{1, 2, 3, 4, 5, 6};
    for(auto itr = st.begin(); itr != st.end();) {
        if( *itr % 2 == 0 )      // 偶数ならば
            itr = st.erase(itr);       //  削除
        else
            ++itr;
    }

イテレータを指定した場合は、削除処理に要する時間は O(1) である。

erase(first, last) : iterator

範囲指定して複数の要素を一度に削除することもできる。first は削除する先頭要素へのイテレータ、last は削除する最後の要素の次の要素へのイテレータ。

    set<int> st{1, 2, 3, 4, 5, 6};
    auto first = st.find(2);
    auto last = st.find(4);
    st.erase(first, last);       // 要素 2, 3 を削除

演習問題：

1. int 型の順序付集合を {3, 1, 4, 5} で初期化し、要素 3 を削除するコードを書き、動作確認しなさい。show

    std::set<int> st{3, 1, 4, 5};
    st.erase(3);

2. int 型の順序付集合を {1, 3, 4} で初期化し、最初の要素を削除するコードを書き、動作確認しなさい。show

    std::set<int> st{1, 3, 4};
    st.erase(st.begin());

まとめ

• erase(値) で、順序付集合に格納されている値を削除できるぞ
• erase(イテレータ) で、イテレータが指す要素を削除できるぞ

データの検索

• find(値) : iterator
• count(値) : size_t

find(値) : iterator

find(値) は、引数で指定された値を検索し、それへのイテレータを返す。
値が順序付集合に含まれない場合は end() を返す。

処理時間は O(log N) である。

    set<int> st{3, 1, 4};
    auto itr = st.find(4);   //  要素 4 を検索

count(値) : size_t

count(値) は、順序付集合に含まれる指定値の数を返す。set は重複を許さないので、0 または 1 を返す。
処理時間は O(log N) である。

    set<int> st{3, 1, 4, 3};
    cout << st.count(2) << "\n";   //  要素 2 の個数（0）を表示
    cout << st.count(3) << "\n";   //  要素 3 の個数（1）を表示

演習問題：

1. int 型の順序付集合を {3, 1, 4, 5} で初期化し、要素 4 を検索するコードを書き、正しく検索されていることを確認しなさい。 show

    std::set<int> st{3, 1, 4, 5};
    auto itr = st.find(4);
    if( itr != st.end() && *itr == 4 ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

2. int 型の順序付集合を {3, 1, 4, 5} で初期化し、要素 9 を検索するコードを書き、検索結果が正しいことを確認しなさい。 show

    std::set<int> st{3, 1, 4, 5};
    auto itr = st.find(9);
    if( itr == st.end() ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

3. int 型の順序付集合を {3, 1, 4, 5, 4} で初期化し、値が 4 の要素数を表示するコードを書き、動作確認しなさい show

    std::set<int> st{3, 1, 4, 5, 4};
    cout << "count(4) = " << st.count(4) << "\n";

4. int 型の順序付集合を {3, 1, 4, 5} で初期化し、値が 7 の要素数を表示するコードを書き、動作確認しなさい show

    std::set<int> st{3, 1, 4, 5};
    cout << "count(7) = " << st.count(7) << "\n";

まとめ

• find(値) で値を検索できるぞ。
• count(値) は順序付集合に含まれる指定値の個数（0 または 1）を返すぞ

その他のメンバ関数

順序付集合の状態を取得

• empty() : bool
• size() : size_t

empty() : bool

empty() は順序付集合が空かどうかを返すメンバ関数だ。

    std::set<int> st;
    if( st.empty() ) {
        cout << "empty.\n";
    } else {
        cout << "Not empty.\n";
    }
    st.insert(5);     //  5 を追加
    if( st.empty() ) {
        cout << "empty.\n";
    } else {
        cout << "Not empty.\n";
    }

size() : size_t

size() は順序付集合に格納されている要素の数を返す。

下記コードを実行すると、3 と 4 が表示される。

    std::set<int> st{3, 1, 4};
    cout << st.size() << "\n";
    std::set<int> st2{3, 1, 4, 1, 5};
    cout << st2.size() << "\n";

set の状態を変更

• clear() : void
• swap(std::set&) : void

clear() : void

clear() は要素を全て削除し、順序付集合を空にします。

    std::set<int> st{3, 1, 4};      // 要素数3の順序付集合を生成
    cout << st.size() << "\n";      // 要素数を表示
    st.clear();      // 要素を全て削除
    cout << st.size() << "\n";      // 要素数を表示

swap(std::set&) : void

x.swap(y) は、集合 x と y の中身を交換する関数だ。

    std::set<int> x{3, 1, 4, 1, 5}
    std::set<int> y{9, 8};
    x.swap(y);     // x, y の中身を入れ替え

イテレータ

• begin() : iterator
• end() : iterator

begin() : iterator

begin() は最初の要素への、end() は最後の要素の次へのイテレータを返す。

既に何度も出てきているが、下記は全ての要素を表示するコードである。

    std::set<int> st{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    for(auto itr = st.begin(); itr != st.end(); ++itr) {
        std::cout << *itr << "\n";      // イテレータの指す先のデータを表示
    }

演習問題：

1. empty() の動作確認を行うプログラムを書き、実行してみなさい。show

    std::set<int> st;
    if( st.empty() ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }
    std::set<int> st2{ 3, 1, 4};
    if( !st2.empty() ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

2. size() の動作確認を行うプログラムを書き、実行してみなさい。show

    std::set<int> st;
    if( st.size() == 0 ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }
    std::set<int> st2{ 3, 1, 4};
    if( st2.size() == 3) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }
    std::set<int> st3{ 3, 1, 4, 3, 1, 4};
    if( st3.size() == 3) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

3. clear() の動作確認を行うプログラムを書き、実行してみなさい。show

    std::set<int> st{3, 1, 4};
    st.clear();
    if( st.empty() && st.size() == 0 ) {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

4. swap() の動作確認を行うプログラムを書き、実行してみなさい。show

    std::set<int> st1, st2{3, 1, 4};
    st1.swap(st2);
    if( !st1.empty() && st1.size() == 3 &&
        st2.empty() && st2.size() == 0)
    {
        std::cout << "OK\n";
    } else {
        std::cout << "NG\n";
    }

まとめ：

• empty() : bool で集合が空かどうか判定可能だぞ
• size() : size_t で、集合に含まれる要素数を取得できるぞ
• clear() で、集合に含まれる要素を全て削除し、集合を空にすることが出来るぞ
• x.swap(y) で、x と y の中身を交換出来るぞ
• begin()、end() で最初、最後の次へのイテレータを取得出来るぞ
• set::iterator はイテレータが指す先の値を取れるだけで、書き換えは出来ないぞ

まとめ・参考

順序付集合 std::set は格納された要素を自動的にソートしてくれるコンテナクラスだぞ。
ランダム・アクセスは出来ないが、値をキーにした検索は O(log N) と高速だ。
要素の追加・削除も O(log N) と高速だ。

要素の追加を頻繁に行い、ランダム・アクセスが必要でなければ std::set はお薦めだ。
そうでなければ、std::vector を使い、要素をソートしておくという選択肢もあるぞ。

本稿では std::set のすべての機能・詳細を解説していない。詳しくは以下のサイトなどで勉強して欲しい。
参照：http://www.cplusplus.com/reference/set/set/

---

　

最近更新したページ

人気のページ

関連ページ

• C++ 動的配列クラス std::vector 入門
• C++ 双方向リストクラス std::list 入門
• C++ マップクラス std::map 入門
• C++ 文字列クラス std::string 入門
• C++ 乱数 std::random 入門
• C/C++ 処理時間計測 入門
• C/C++ static 修飾子 入門
• JavaScript 配列入門