罠

以下の二つについて正しく答えられますか？

`erase`

std::multiset<int> ms;
ms.insert(0);
ms.insert(10);
ms.insert(10);
std::cout << ms.count(10) << std::endl;  // 2

ms.erase(10);
std::cout << ms.count(10) << std::endl;  // ?

10 が一つ消えて 1 と出力されるか，全て消えて 0 と出力される，などが考えられますね．

`count`

ms の要素数が \(n\) のとき，ms.count(x) の計算量はいくらでしょう？

答え合わせ

ms.erase(10) では 10 が全て消え，0 が出力されます．また，x と等価な要素が \(m\) 個入っているとき，ms.count(x) の計算量は \(O(m+\log n)\) になります．

よく言われる（妄想？）こととして，「10 が一つだけ消えて 1 と出力されてほしい」「count も \(O(\log n)\) でやってほしい」などがありますが，それがつらそうだという説明を書きます．

解説

要素の型が int だと不都合なので，以下のようなクラス person を考えます．

struct person {
  int height;
  std::string name;

  person() = default;
  person(int h, std::string const& n): height(h), name(n) {}

  bool operator <(person const& other) const {
    return height < other.height;
  }
};

比較順は背の順で，名前の順は不問です*1．

これを扱う multi set を考えます．

std::multiset<person> ms;
ms.emplace(151, "a");
ms.emplace(150, "b");
ms.emplace(151, "c");
ms.emplace(152, "d");
ms.emplace(151, "a");
for (auto const& p: ms)
  std::cout << p.height << ' ' << p.name << std::endl;

出力結果は以下のようになります．

< で比較して等価な要素がすでに入っている場合，その upper bound の位置に挿入されます．

これに対して，person(151, "c") を消そうとして，以下のようなコードを書いたとします．

ms.erase(person(151, "c"));

person(151, "a") と区別して person(151, "c") のみを消すのは不可能であることを察してほしいんですが，理由の一つとして，person には operator == は定義されていません．std::multiset が要求しているのは < のみです．

あるいは，定義されていて，== で等しい要素のみを消す仕様だったとして，person(151, *) であるような要素一つ一つに対して調べる必要があり，これは大変そうです．

つらいケースの例として，person(151, "a") がたくさん入っていて person(151, "b") を消そうとする処理をたくさん行う場合を考えてみるといいかもしれません．

結局，ms.erase(x) が行う処理は，!(a < x) && !(x < a) な要素，直感的には \(x \le a\) かつ \(x \ge a\) な要素 \(a\) を全て消すというものです*2．

ms.erase(person(151, "x"));

こうしたコードを書いても同様に person(151, "a") や person(151, "c") が消されることはもうわかりますね．

このように，必ずしも完全にメンバが同じでなくとも等価であるという比較がなされる場合もあるため，競プロでよく行われるような std::map<要素の型, 個数を表す型> のように個数を管理する方法は（一般の場合には）適しません．各要素をループで出力しようとして person(151, "a") が三回出力されて person(151, "c") が出力されないような仕様だと困っちゃいますね．

さて，（おそらく）こうした事情で等価な要素を一つ一つ持っているので，count する際も一つ一つ数える必要があり，\(O(m+\log n)\) 時間かかってしまいます．

かしこい平衡二分木であれば，lower_bound と upper_bound を求めた後，その間の要素数を \(O(\log n)\) 時間で数えられるので，全体として \(O(\log n)\) 時間で count に答えられるのですが，残念ながら STL の std::multiset にはそうした規定はされていません．

きになる

もちろん，規定されているのは計算量の上界であって，各コンパイラがより効率よく処理するのは認められているので，そうした処理系があるかもしれない気もするんですが．

気もするんですが，把握していない仕様（空間計算量？コンストラクタの時間計算量？）などでそういうのが制限されているかもしれません？（なさそう．）

たとえば，std::vector が余分なメモリを無限に食うような処理系は許されるのかな？と考えたときに，コンストラクタが線形時間で済まなさそうなので，そういうことはなさそうな気がしますね，というような論法の話です．

おわり

えびちゃんはこういう風に解釈して納得しているのですが，納得できない人もいるかもしれません？言ってもらえたら考え直します．

抽象化のことをあまり考えたことがない人だと，こういう話をしても伝わりにくいのかもしれません？

もちろん int のような型では不便な仕様ではあると思います．適宜イテレータを取得して消すやつをする必要があるので．

auto it = ms.find(x);
if (it != ms.end()) ms.erase(it);

person のようなクラスの場合，find で得られた要素が必ずしも x と同一とは限らないのですけどね（等価な要素を探してくるだけなので）．

そういう用途で使いたい場合は operator < をよく考えて定義しないとハマってしまいそうです．

*1:strict weak ordering になっているのでこういう比較でも C++ 的には問題ないはず．

*2:~~ならし定数時間と規定されていますね．~~ 訂正：これは嘘で，\(O(m+\log n)\) 時間．全体が \(n\) 個で該当する要素が \(m\) 個．