如何制作一个C ++映射容器，其中键是值的一部分? [英] How to make a C++ map container where the key is part of the value?

问题描述

我想存储一堆键值对象，但是值对象本身(及其引用)知道它的键.我还想仅通过键就可以有效地查找这些对象.

I want to store a bunch of key-value objects, but where the value object itself (and references to it) knows its key. I also want to efficiently lookup these objects given only the key.

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::map
    • Seems to require that the storage is an std::pair, such that the value cant access the key. If the value contains the key, it needs to be duplicated.
    • Does not actually enforce that the key inside the value does not get changed in some way
    • 看起来像是一个非常好的解决方案，使用自定义的比较方法按键提供唯一性，直到您意识到它使整个值成为常量，而不仅仅是键字段.
    • 可以使用线性搜索，或者如果各项保留排序，则使用二进制搜索.但是，我怀疑这在性能上不是最佳选择，需要使用某种额外的层才能真正实现所需的行为.

    推荐答案

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

    C++14 std::set::find non-key searches

    如 http://en.cppreference.com/w/cpp/container/set/find C ++ 14添加了两个新的find API:

    As mentioned at http://en.cppreference.com/w/cpp/container/set/find C++14 has added two new find APIs:

    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上进行了测试，使用:

    Tested on Ubuntu 16.10, g++ 6.2.0, with:

    g++ -std=c++14 -Wall -Wextra -pedantic -o main.out main.cpp
    ./main.out
    

    使用自定义类而不是less<>

    Using a custom class instead of less<>

    这使事情更加明确，并允许您为每个类编写多个比较器:

    This makes things a bit more explicit and allows you to write multiple comparators per class:

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

    另请参见

    • 是否可以使用与std :: set中所包含类型不同的元素来执行搜索和删除?
    • 对不重复的指针集的原始指针查找
    • 通过多个键索引对象:双向地图有更有效的实现吗?
    • 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
    • index objects by multiple keys: How to index and query STL map containers by multiple keys?
    • implement a bimap efficiently: Is there a more efficient implementation for a bidirectional map?

    这篇关于如何制作一个C ++映射容器，其中键是值的一部分?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！