C++のset/multisetを等価演算子で比較したときの計算量がどうなるのか教えていただきたいです。


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




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

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




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

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

