92507


setやmultisetは素集合を管理するデータ構造ですが、これをset A;とset B;のように宣言して、A ==
Bのように比較した場合、計算量はどうなるのか疑問に思いました。  
vector A;とvector B;においてA ==
Bの時にはイテレーター同士を比較していくと思うので、O(N)になると思うのですが、この見解についても誤っていたら教えていただきたいです。


CC BY-SA 4.0
2022-11-30T00:52:18.660
92505
2022-11-30T01:07:44.423
55503
question
c++
C++のset/multisetを等価演算子で比較したときの計算量がどうなるのか教えていただきたいです。


cpprefjp に書いてありますね。きっと規格でもそのように定義されているのでしょう。

[set operator==
計算量](https://cpprefjp.github.io/reference/set/set/op_equal.html)

> `size()` に対して線形時間。ただし、xとyのサイズが異なる場合は定数時間。

[multiset operator==
計算量](https://cpprefjp.github.io/reference/set/multiset/op_equal.html)

> `size()` に対して線形時間。ただし、xとyのサイズが異なる場合は定数時間。


CC BY-SA 4.0
2022-11-30T01:05:04.167
92506
2022-11-30T01:05:04.167
3475
92505
answer


言語仕様ではコンテナ要件 ([Container requirements](https://timsong-
cpp.github.io/cppwp/n3337/container.requirements#tab:containers.container.requirements))
として `==` の挙動が含まれており、計算量は線形 (つまりビッグオー記法でいうところの O(N) のこと) であることを要求しています。

つまり言語仕様中でコンテナとして定義されている型 (もちろん `set` や `multiset` を含む) はいずれも O(N) で比較できます。


CC BY-SA 4.0
2022-11-30T01:07:44.423
92507
2022-11-30T01:07:44.423
3364
92505
answer