c++ - C++ `unordered_set` 中两个 "not working"的交集在类方法中但可与 `set` 一起使用？

Question

我这里有两张“ map ”，xs和ys ，我用它来存储网格中的“点”。 我还有一个数组 std::pair<int,int> arr ，这样 xs[x]返回 arr 中的所有索引x 坐标 x ，和ys[y]返回 y 坐标 y 的所有索引.

让我们有以下内容:

std::unordered_map<int, std::unordered_set<size_t>> xs {
    {3, {2, 0}},
    {11, {1}}
};
std::unordered_map<int, std::unordered_set<size_t>> ys {
    {2, {2 ,1}},
    {10, {0}}
};

std::unordered_set<size_t> intersection;
std::set_intersection(xs[3].begin(), xs[3].end(),
    ys[2].begin(), ys[2].end(),
    std::inserter(intersection, intersection.begin()));
std::cout << intersection.size() << std::endl; // should return 1

intersection.clear();
std::set_intersection(xs[11].begin(), xs[11].end(),
    ys[2].begin(), ys[2].end(),
    std::inserter(intersection, intersection.begin()));
std::cout << intersection.size() << std::endl; // should return 1

他们确实返回了 1和1 。没有什么惊喜。

现在让我们隔离函数中的交集计数器:

size_t count_intersection(const std::pair<int,int>& pt,
        const std::unordered_map<int, std::unordered_set<size_t>>& xs,
        const std::unordered_map<int, std::unordered_set<size_t>>& ys) {
    
    const int x = pt.first, y = pt.second;

    // Omitted some error checking

    std::unordered_set<size_t> intersection;
    std::set_intersection(xs.at(x).begin(), xs.at(x).end(),
        ys.at(y).begin(), ys.at(y).end(),
        std::inserter(intersection, intersection.begin()));

    return intersection.size();
}

std::cout << count_intersection({3, 2}, xs, ys) << std::endl;
std::cout << count_intersection({11, 2}, xs, ys) << std::endl;

到目前为止，一切顺利。

现在，让我们将所有这些隔离在一个类中:

class Counter {

    std::vector<std::pair<int,int>> _pts;
    std::unordered_map<int, std::unordered_set<size_t>> _xs;
    std::unordered_map<int, std::unordered_set<size_t>> _ys;

public:
    void add(const std::pair<int,int>& pt) {
        const int x = pt.first, y = pt.second;
        const size_t ind = _pts.size();

        _pts.push_back(pt);
        _xs[x].insert(ind);
        _ys[y].insert(ind);
    }

    size_t count(const std::pair<int,int>& pt) {
        std::unordered_set<size_t> intersection;
        const int x = pt.first, y = pt.second;

        std::set_intersection(_xs[x].begin(), _xs[x].end(),
            _ys[y].begin(), _ys[y].end(),
            std::inserter(intersection, intersection.begin()));
        return intersection.size();
    }
};

int main() {
    Counter c;
    c.add({3,10}); // ind == 0
    c.add({11,2}); // ind == 1
    c.add({3,2});  // ind == 2

    // By this point,
    // _xs == {3: {0, 2}, 11: {1}}
    // _ys == {10: {0}, 2: {1,2}}
    std::cout << c.count({3,2}) << std::endl;  // Should return 1
    std::cout << c.count({11,2}) << std::endl; // Should return 1
}

相反，我得到的是

1
0

但是，当我替换std::unordered_set时与 std::set ，结果符合预期。

怎么了std::unordered_set ？

顺便说一句，我的编译命令是

g++ -Wall -Wextra -Werror -O3 -std=c++17 -pedantic -fsanitize=address -o main.out main.cpp && ./main.out

还有我的g++ --version是 g++ (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 .

Answer 1

std::set_intersection 需要有序元素。

unordered_map 和 _set 不提供有序元素。