c++ - 如何制作一个 C++ 映射容器，其中键是值的一部分？

Question

我想存储一堆键值对象，但是值对象本身（以及对它的引用）知道它的键。我还想有效地查找仅给定键的这些对象。

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::pair，这样值就不能访问密钥。如果值包含键，则需要复制。
- 实际上并没有强制值内的键不会以某种方式改变
标准::设置
- 看起来是一个非常好的解决方案，使用自定义比较方法通过键提供唯一性，直到您意识到它使您的整个值变为常量，而不仅仅是键字段。
std::vector （或其他类似数组/列表的解决方案）
- 可以使用线性搜索，或者如果项目保持排序，则进行二分搜索。但是我怀疑这在性能方面并不是最优的，并且需要某种额外的层来真正实现所需的行为。

score 9 · Accepted Answer

C++14std::set::find非键搜索

如http://en.cppreference.com/w/cpp/container/set/find所述， C++14 添加了两个新findAPI：

主文件

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、6.2.0 上测试g++，其中：

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);
}

也可以看看

score 2 · Accepted Answer

C++ 提供了mutable允许您使用第二种解决方案的关键字—— a set. 将您的值声明为mutable在您的项目类中将允许修改它，即使项目是const. 另请参阅： 'mutable' 关键字除了允许变量由 const 函数修改之外是否还有其他用途？

或者，更简单的是，为您的值实现一个访问器，const_cast以消除项目的恒定性。

score 2 · Accepted Answer

我感觉到你的痛苦。让我生气的是，set并且map总是在底层使用相同的数据结构来实现，这是一个tree使用密钥提取器参数化的值。不幸的是，标准中没有这样的东西。

如果 boost 没问题，使用Boost.MultiIndex来实现你所需要的。也看看Boost.Intrusive。

score 1 · Accepted Answer

...但是值对象本身（以及对它的引用）知道它的键

地图：

对象不能知道“它的”键，因为指向同一对象的指针可能会使用不同的键添加到多个映射中。密钥属于地图；不是一个对象。

放：

当这个成员的值发生变化时会发生什么？您将如何强制重新索引？这就是为什么 set 强制执行 constness。

--

您正在尝试根据其成员之一索引给定类的项目，但您不想复制此成员以用于索引目的，并且您不想使对象 const（我假设您确实想要使成员 const)。

我会在 Red-Black 或 AVL 树上构建它。

我对 ybungalobill 建议的 Boost.MultiIndex 不够熟悉。我不确定它的实例化代码是否复制了索引成员，或者它如何处理该成员的值更改。

c++ - 如何制作一个 C++ 映射容器，其中键是值的一部分？

4 回答 4

Related

Reference