「なぜsetを使っちゃいけないの？」

　ドキュメントを流し読みしていると、気になるタイトルの引用に出くわしました:「なぜsetを使っちゃいけないの?」と題された、4ページちょっとのペーパーです。2000年4月にC++Reportに寄稿されたものですが、ざっくり読んでみるとこれがなかなか面白い。標準C++ライブラリが提供する連想コンテナ:set（とその仲間たち）を使うことが必ずしもベストな選択ではない、と述べています。Matt Austernのコラム:「Why you shouldn't use set」（原文／PDF）の超訳（？）を少しばかりの解説付きでお届けします。

なぜsetを使っちゃいけないの？（かわりに何を使えばいいの？）

　標準C++ライブラリにあるあらゆるものには、それぞれに何らかの存在理由があるのだが、その存在理由はどれも明白とは限らない。標準C++ライブラリは教材ではないのだから、基本的で日常的に使えるコンポーネントと、特別な目的で使えるものとの区別がつかない。

　連想コンテナの一つであるstd::set（あるいはその兄弟たち: map, multiset, multimap）を例に挙げよう。setの利用が理にかなっていることもあれば、そうとも思えないこともある。データの格納と検索を目的とするのなら、標準ライブラリはもっとシンプルでコンパクトで高速なものを提供してくれている。

setとはなにか？

　setは要素の格納と検索とをサポートするSTLコンテナの一つだ。例えばstringを要素とするsetを考えよう:

std::set<std::string> S;

　このSに要素を挿入するのは簡単だ:

S.insert("foo");

　setは同じkeyを持つ要素の重複を許さないので、Sがすでにその中に"foo"を持っていた場合、S.insert("foo")は新たな要素を追加せず、単に"foo"の検索を行うだけだ。戻り値には新たな要素が追加されたか否かを示すフラグが含まれている（※1）。

#include <iostream>
#include <set>
#include <string>

using namespace std;

int main() {
    set<string> S;
    cout << boolalpha;
    auto result = S.insert("foo");
    cout << "1'st insertion of " << *result.first
         << " : " << result.second << endl;
    result = S.insert("foo");
    cout << "2'nd insertion of " << *result.first 
         << " : " << result.second << endl;
}

/* result:
1'st insertion of foo : true
2'nd insertion of foo : false
*/

　すべてのSTLコンテナに対してそうであるように、イテレータを用いてset内の各要素を順に1つずつ渡り歩くことができる。S.begin()はS中の最初の要素を指すイテレータ、S.end()は最後の要素の直後を指すイテレータを返す。set内の要素は常に昇順に並んでおり、それゆえinsertには挿入位置を指定する引数を必要としない。新たな要素は自動的に正しい位置に挿入される。

　setが連想コンテナ（Associative container)と呼ばれるのは、値の検索ができるからだ。

i = S.find("foo");

と書くことで、set内の適切な要素を指すイテレータを返す。もしなければ（どの要素も指していない）S.end()を返す。

　昇順以外の並び順で、あるいは'<'（小なり）の定義されていない要素を格納したいならどうするか。こんなときはsetの第二テンプレート引数に2つの要素のうちどちらが先かを判定する関数オブジェクトを与えてやればいい。デフォルトではstd::less<T>なのでより小さい方が先、つまり昇順となる。逆順（降順）に格納されたstringのsetが必要なら:

std::set<std::string, std::greater<std::string>> S;

と書けばいい。大文字/小文字を区別せずに昇順に並べたいなら:

struct less_nocase {
  static bool compare_chars(char x, char y) {
    return std::toupper(x) < std::toupper(y);
  }
  bool operator()(const string& x, cosnt string& y) const {
    return std::lexicographical_compare(x.begin(), x.end(),
                                        y.begin(), y.end(), compare_chars);
  }
};

std::set<std::string, less_nocase> S;

　より一般的に、複雑なデータ構造をsetの要素としたいなら、その一部を比較に利用して:

struct Client {
  unsigned long id;
  string last_name, first_name;
  ...
};

struct id_compare {
  bool operator()(const Client& xm, const Client& y) const {
    return x.id < y.id;
  }
};

std::set<Client,id_compare> clients;

　もちろんこれらがsetのすべてではない。STLコンテナが具備するものはすべて持っているし、setだけの特別なメンバ関数もいくつかある。とはいえ基本的な目的は検索可能な要素の集合を管理することだ（連想コンテナ:mapはsetと非常によく似ている。異なるのは、setでは要素そのものが検索keyであるのに対し、mapはkeyと、keyに紐づけられたvalueの組:pairを要素とするところだ）。