我想存储一堆键值对象,但值对象本身(及其对它的引用)知道它的键.我还想在只给出密钥的情况下有效地查找这些对象.
class SomeObject
{
private:
//String or integer. int seem cheap enough to duplicate with std::map, but
//strings seem pretty expensive when there may be thousands of objects in existence.
//Reference/Pointer to key is fine
const SomeOtherObject key;
...other stuff...
public:
...methods, some of which use the key in some way...
};
> std :: map
>似乎要求存储是一个std :: pair,这样值就无法访问密钥.如果值包含密钥,则需要重复该密钥.
>实际上并不强制执行值内部的键不会以某种方式更改
> std :: set
>看起来是一个非常好的解决方案,使用自定义比较方法通过键提供唯一性,直到您意识到它使您的整个值变为常量,而不仅仅是关键字段.
> std :: vector(或其他数组/列表解决方案)
>可以使用线性搜索,或者如果项目保持排序二进制搜索.但是我怀疑这在性能方面并不是最优的,并且需要额外的某种层才能真正实现所需的行为.
解决方法:
C 14 std :: set ::查找非键搜索
正如在http://en.cppreference.com/w/cpp/container/set/find C 14中提到的,添加了两个新的查找API:
main.cpp中
template< class K > iterator find( const K& x );
template< class K > const_iterator find( const K& x ) const;
允许你这样做:
#include <cassert>
#include <set>
class Point {
public:
// Note that there is _no_ conversion constructor,
// everything is done at the template level without
// intermediate object creation.
//Point(int x) : x(x) {}
Point(int x, int y) : x(x), y(y) {}
int x;
int y;
};
bool operator<(const Point& c, int x) { return c.x < x; }
bool operator<(int x, const Point& c) { return x < c.x; }
bool operator<(const Point& c, const Point& d) {
return c.x < d;
}
int main() {
// std::less<> because of:
// https://*.com/questions/20317413/what-are-transparent-comparators
std::set<Point, std::less<>> s;
s.insert(Point(1, -1));
s.insert(Point(2, -2));
s.insert(Point(0, 0));
s.insert(Point(3, -3));
assert(s.find(0)->y == 0);
assert(s.find(1)->y == -1);
assert(s.find(2)->y == -2);
assert(s.find(3)->y == -3);
// Ignore 1234, find 1.
assert(s.find(Point(1, 1234))->y == -1);
}
在Ubuntu 16.10,g 6.2.0上测试,具有:
g++ -std=c++14 -Wall -Wextra -pedantic -o main.out main.cpp
./main.out
使用自定义类而不是更少<>
这使得事情更加明确,并允许您为每个类编写多个比较器:
#include <cassert>
#include <set>
class Point {
public:
Point(int x, int y) : x(x), y(y) {}
int x;
int y;
};
struct PointCmpY {
// https://*.com/questions/20317413/what-are-transparent-comparators
typedef std::true_type is_transparent;
bool operator()(const Point& lhs, int rhs) const {
return lhs.y < rhs;
}
bool operator()(int lhs, const Point& rhs) const {
return lhs < rhs.y;
}
bool operator()(const Point& lhs, const Point& rhs) const {
return lhs.y < rhs.y;
}
};
int main() {
std::set<Point, PointCmpY> s;
s.insert(Point(1, -1));
s.insert(Point(2, -2));
s.insert(Point(0, 0));
s.insert(Point(3, -3));
assert(s.find(0)->x == 0);
assert(s.find(-1)->x == 1);
assert(s.find(-2)->x == 2);
assert(s.find(-3)->x == 3);
assert(s.find(Point(1234, -1))->x == 1);
}
也可以看看
> Is it possible to use elements of a different type than contained in a std::set to perform search and deletion?
> Raw pointer lookup for sets of unique_ptrs
>按多个键索引对象:How to index and query STL map containers by multiple keys?
>有效实施bimap:Is there a more efficient implementation for a bidirectional map?