C++ 積集合set_intersectionを使う時にunordered_setだと期待する出力が得られないのは何故？

質問

std::set_intersectionを使う時に、
unordered_set<int>を使うと期待する出力が得られなかったのですが、
どういった理由でこのような挙動をしているのか知りたいです。

経緯

積集合の扱い方を調べていて自作するしか無さそうだったので
std::set_intersectionのリファレンスのサンプルを元に、
unordered_set<int>での実装を試みてみましたが上手くいきませんでした。

（他言語だと論理演算式[C=A&B]のような書き方で集合積が得られていた感覚ですがC++では使えなかった）

試したこと

unordered_set<int>
↓
set<int>に変更したら期待通りの出力を得られました。

コード

C++
1#include <bits/stdc++.h>
2using namespace std;
3
4template <class T>
5T fn(const T& a, const T& b) {
6  T r;
7  set_intersection(a.begin(), a.end(), b.begin(), b.end(),
8                   inserter(r, r.end()));
9  return r;
10}
11
12int main() {
13  set<int> sa = {1, 2, 3};
14  set<int> sb = {2, 3, 4};
15  set<int> sr = fn(sa, sb);
16  cout << "          set: sr.size() = " << sr.size() << "\n";
17
18  unordered_set<int> ua = {1, 2, 3};
19  unordered_set<int> ub = {2, 3, 4};
20  unordered_set<int> ur = fn(ua, ub);
21  cout << "unordered_set: ur.size() = " << ur.size() << "\n";
22}

out
1          set: sr.size() = 2
2unordered_set: ur.size() = 0

補足情報（FW/ツールのバージョンなど）

Ubuntu 20.04 LTS
WSL2
VSCode 1.74.1
Windows10 22H2 19045.2251
C++17
g++ 9.4.0
gdb

dameo

2022/12/17 03:06

unordered_setは「非順序連想コンテナ」で順序がないからです。平たく言うとiterateしたときの順序が保証されないということになります。 https://onlinegdb.com/01PmE5Lvc #include <iostream> #include <set> #include <unordered_set> using namespace std; int main() { auto init = {1, 2, 3}; set<int> sa = init; unordered_set<int> ua = init; for(auto e: sa) cout << "[set]: " << e << endl; for(auto e: ua) cout << "[unordered_set]: " << e << endl; return 0; } [set]: 1 [set]: 2 [set]: 3 [unordered_set]: 3 [unordered_set]: 2 [unordered_set]: 1 なので「2つのソート済み範囲の積集合を得る」が出来ません。