假设我们有一个包含较大对象和索引值的 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 。
最佳答案
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 解决这类有多种数据索引方式的问题。 .
关于c++ - 用 std::set 替换 std::map 并按索引搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23911960/