c++ - 用 std::set 替换 std::map 并按索引搜索

Question

假设我们有一个包含较大对象和索引值的 map 。索引值也是较大对象的一部分。

我想知道是否可以用 set 替换 map，提取索引值。

创建一个 set 是相当容易的，该 set 通过提取索引值对比较两个较大对象的仿函数进行排序。

这还剩下按索引值搜索，我认为 set 默认不支持它。

我正在考虑使用 std::find_if，但我认为搜索是线性的，忽略了我们已经设置的事实。

然后我想到将 std::binary_search 与比较较大对象和值的仿函数一起使用，但我相信它在这种情况下不起作用，因为它不会利用结构并将使用遍历，因为它没有随机访问迭代器。它是否正确？或者是否有重载可以在 set 上正确处理此调用？

然后最后我考虑使用 boost::containter::flat_set，因为它有一个底层 vector ，因此大概应该能够与 std::binary_search 一起工作?

但也许有更简单的方法来做到这一点？

在您回答之前，只需在应该使用 map 的地方使用 map - 我实际上使用的是手动排序的 vector (好吧 std::lower_bound)并且正在考虑将其替换为 boost::container::flat_set，但这样做似乎并不容易，所以我可能会坚持使用 vector 。

Answer 1

C++14 将引入通过不需要构建整个存储对象的键查找的能力。这可以按如下方式使用:

#include <set>
#include <iostream>

struct StringRef {
    StringRef(const std::string& s):x(&s[0]) { }
    StringRef(const char *s):x(s) { std::cout << "works: " << s << std::endl; }
    const char *x;    
};

struct Object {
    long long data;
    std::size_t index;
};
struct ObjectIndexer {
    ObjectIndexer(Object const& o) : index(o.index) {}
    ObjectIndexer(std::size_t index) : index(index) {}
    std::size_t index;
};
struct ObjComp {
    bool operator()(ObjectIndexer a, ObjectIndexer b) const { 
        return a.index < b.index; 
    }
    typedef void is_transparent; //Allows the comparison with non-Object types.
};

int main() {
    std::set<Object, ObjComp> stuff;
    stuff.insert(Object{135, 1});
    std::cout << stuff.find(ObjectIndexer(1))->data << "\n";
}

更一般地说，可以使用 Boost.MultiIndex 解决这类有多种数据索引方式的问题。 .