C++ set: std::set で一意かつソート済みの要素を扱う

一意でソート済みの値の入れ物

unordered_map が、ハッシュベースの高速な検索でキーと値のペアを格納するのを見てきました。std::set はそのよりシンプルな仲間で、格納するのは値だけ（関連データは持ちません）であり、2 つのルールを自動的に適用します。すべての要素は一意であり（重複は静かに捨てられます）、要素は常にソートされた順序で保たれます。

そのため set は、「これは前に見たことがあるか？」や「重複のない要素をソートして返してほしい」といった問いに対する自然な選択肢になります。重複を気にせず挿入でき、先にソートしなくても反復できます。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // 重複 - 無視される

    for (int x : s) cout << x << " ";   // 10 30 40（ソート済み、重複なし）
}

10 を 2 回、しかも順不同で挿入したにもかかわらず、出力はソートされており 10 は 1 回だけ現れることに注目してください。set があなたの代わりに管理してくれたのです。

挿入と削除

insert は、値がまだ存在しなければそれを追加します。.second が bool の pair を返し、その値が挿入が実際に行われたかどうかを教えてくれます。値が新しいものだったかどうかを知りたいときに便利です。

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

値を削除するには、値そのものを渡して erase を呼びます。削除された要素の数（set では 0 か 1）を返します。存在しないものを削除しても無害で、エラーにはなりません。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // 3 を削除する
    s.erase(99);         // 何もせず、0 を返す

    for (int x : s) cout << x << " ";   // 1 2 4
}

メンバーシップの確認

set の最大の目的は、「これは含まれているか？」という高速な判定です。最も分かりやすい方法は、1 か 0 を返す count です。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

C++20 以降には、bool を直接返す、さらに読みやすい選択肢 contains があります。

if (primes.contains(7)) { /* ... */ }   // C++20

よくある間違いは、map でするように operator[] に手を伸ばすことです。set には operator[] がありません。取り出すべき値はなく、存在を判定するだけだからです。s[7] ではなく count や contains を使いましょう。

実際の位置が必要な場合（削除したり隣接要素を見たりするため）は、イテレータか end() を返す find を使います。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // イテレータで削除 - 二度目の検索は不要
    }
    cout << "size now " << s.size() << "\n";
}

順序どおりの反復と範囲クエリ

set はソートされているため、反復は常に要素を小さい順から大きい順に返し、ソート済みコンテナならではの技を無料で使えます。lower_bound(x) は x 以上の最初の要素を、upper_bound(x) は x より厳密に大きい最初の要素を返します。両者を組み合わせると、すべての要素を確認することなく数値の範囲を走査できます。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // [12, 31] の範囲にあるものをすべて出力する
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

細かいながら重要なルールがあります。set の要素は変更できません。イテレータは const 参照を渡すため、要素をその場で変更することはできません。変更すると、コンテナが頼りにしているソート順が壊れる恐れがあるからです。値を「変更」するには、古いものを削除して新しいものを挿入します。

デフォルトの順序は昇順（std::less）です。降順にするには、2 番目のテンプレート引数として別の比較関数を指定します。

#include <iostream>
#include <functional>
#include <set>
using namespace std;

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set と multiset と unordered_set

std::set は近い親戚 3 つのうちの 1 つで、適切なものを選ぶことが重要です。

set<int>            // 一意な値、ソート済み、O(log n)
multiset<int>       // 重複を許可、ソート済み、O(log n)
unordered_set<int>  // 一意な値、順序なし、平均 O(1)

メンバーシップ判定だけが必要で順序を気にしないなら unordered_set を選びましょう。ハッシュベースの検索は、平均では set の木ベースの O(log n) より高速です。要素をソートされた順序で扱いたい、lower_bound/upper_bound による範囲クエリが必要、あるいはイテレータの安定した挙動が欲しい場合は set を選びます。multiset は重複に意味があるとき（例えば、繰り返し値のヒストグラム）にのみ使います。multiset では count(x) が 1 より大きい値を返すことがあり、erase(x) は、単一のイテレータで削除しない限りすべてのコピーを削除します。

set の古典的な使い方として、vector の重複除去とソートを一気に行うものがあります。

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

vector のイテレータから set を構築すると、すべての重複が捨てられ残りがソートされます。手作業のループも、std::sort に std::unique を組み合わせる手間もいりません。

次: pair と tuple

insert が返す pair に .first と .second が現れ、構造化束縛（auto [it, inserted]）がそれをきれいに分解するのを見てきました。「いくつかの値をまとめる」こうした軽量な型は STL のいたるところにあります。次は pair と tuple を直接取り上げ、それらをどう作り、どう分解し、構造体をまるごと定義せずに関数から複数の値を返すかを見ていきます。