我想存储一堆键值对象，但值对象本身（及其对它的引用）知道它的键。我还想在只给出密钥的情况下有效地查找这些对象。
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...
};
C ++ 14 std::set::find非键搜索
正如在http://en.cppreference.com/w/cpp/container/set/find上提到的，C ++ 14增加了两个新的find 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://stackoverflow.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
使用自定义类而不是less<>
这使得事情更加明确，并允许您为每个类编写多个比较器：
#include <cassert>
#include <set>
class Point {
public:
Point(int x, int y) : x(x), y(y) {}
int x;
int y;
};
struct PointCmpY {
// https://stackoverflow.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);
}
也可以看看
我感觉到你的痛苦。让我发疯的是set和map总是使用相同的数据结构来实现，这是一个用密钥提取器参数化的tree值。不幸的是，标准中没有这样的东西。
如果提升可以，请使用Boost.MultiIndex来达到您的需求。看看Boost.Intrusive也是如此。
C ++提供了mutable关键字，允许您使用第二个解决方案 - set。在项目类中将您的值声明为mutable将允许修改它，即使该项目是const。另见：Does the 'mutable' keyword have any purpose other than allowing the variable to be modified by a const function?
或者，更简单的是，为你的价值实现一个访问者，const_casts远离项目的常数。
...但是值对象本身（以及对它的引用）知道其密钥
地图：
对象无法知道“其”键，因为可以使用不同的键将指向同一对象的指针添加到多个映射中。密钥属于地图;不是一个对象。
组：
当该成员的价值发生变化时会发生什么？你会如何强制重建索引？这就是set强制执行constness的原因。
--
您正在尝试根据其中一个成员索引给定类的项目，但您不希望复制此成员以进行索引，并且您不希望使对象成为const（我假设您确实想要使成员const）。
我会在Red-Black或AVL树之上构建它。
我对ybungalobill建议的Boost.MultiIndex不够熟悉。我不确定它的实例化代码是否复制索引成员，或者它如何处理该成员的值更改。