按std :: set中的键查找

Question

我为应该支持自定义比较操作的std::set苦苦挣扎。我的目标是仅使用key参数即可调用find，而无需首先创建set类型的对象。像这样的东西：

#include <set>
#include <cstdint>
#include <vector>

class TestItem {
  public:
    std::uint64_t id;          // key
    std::vector<double> areas; // some other data
};

struct TestItemCompare {
    bool operator()(const std::uint64_t& lhs, const std::uint64_t& rhs) {
        return lhs < rhs;
    }
    bool operator()(const std::uint64_t& lhs, const TestItem& rhs) {
        return lhs < rhs.id;
    }
    bool operator()(const TestItem& lhs, const std::uint64_t& rhs) {
        return lhs.id < rhs;
    }
    bool operator()(const TestItem& lhs, const TestItem& rhs) {
        return lhs.id < rhs.id;
    }
};

int main() {
    std::set<TestItem, TestItemCompare> store;
    std::uint64_t id = 0;
    TestItem t;
    t.id = 0;

    auto it1 = store.find(t);    // compiles
    auto it2 = store.find(id);   // fails to compile

    return 0;
}

我以为这是可能的...

Answer 1

有可能。但是您的比较器必须是透明的。并且functor中的成员函数需要为const

struct TestItemCompare {
    using is_transparent = int;
    bool operator()(const std::uint64_t& lhs, const std::uint64_t& rhs) const {
        return lhs < rhs;
    }
    bool operator()(const std::uint64_t& lhs, const TestItem& rhs) const {
        return lhs < rhs.id;
    }
    bool operator()(const TestItem& lhs, const std::uint64_t& rhs) const {
        return lhs.id < rhs;
    }
    bool operator()(const TestItem& lhs, const TestItem& rhs) const {
        return lhs.id < rhs.id;
    }
};

Answer 2

您可以像使用std::find_if：

auto it2 = std::find_if(
    std::begin(store), std::end(store),
    [&id](auto&& x) {
        return x.id == id;
    }
);

但是，请注意，这将导致线性时间复杂度，可能不是您想要的。