如何创建一个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 ::地图
  • 似乎要求存储是std :: pair,这样值就无法访问密钥.如果值包含密钥,则需要重复该密钥.
  • 实际上并不强制执行值内部的键不会以某种方式更改
• 的std ::设为
  • 看起来是一个非常好的解决方案,使用自定义比较方法按键提供唯一性,直到您意识到它使您的整个值成为常量,而不仅仅是关键字段.
• std :: vector(或其他数组/列表之类的解决方案)
  • 可以使用线性搜索,或者如果项目保持排序二进制搜索.但是我怀疑这在性能方面并不是最优的,并且需要额外的某种层才能真正实现所需的行为.

Answer 1

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

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

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:
    // /sf/ask/1422218941/
    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 {
    // /sf/ask/1422218941/
    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);
}

也可以看看

• 是否可以使用与std :: set中包含的类型不同的元素来执行搜索和删除？
• 原始指针查找的unique_ptrs集
• 通过多个键索引对象：如何通过多个键索引和查询STL映射容器？
• 有效地实现双向地图：双向地图是否有更有效的实现？

Answer 2

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

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