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

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，这样值就不能访问密钥.如果 value 包含 key，则需要对其进行复制.
  • 实际上并不强制值中的键不会以某种方式改变
  • 看起来是一个非常好的解决方案，使用自定义比较方法通过键提供唯一性，直到您意识到它使您的整个值变为常量，而不仅仅是键字段.
  • 可以使用线性搜索，或者如果项目保持排序则进行二分搜索.但是我怀疑这在性能方面并不是最优的，需要某种额外的层才能真正实现所需的行为.

  推荐答案

  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;
  

  允许你这样做:

  main.cpp

  #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<>

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

  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 中包含的不同类型的元素来执行搜索和删除?
  • unique_ptrs 集的原始指针查找
  • 通过多个键索引对象:如何多键索引查询STL map容器?
  • 高效实现双映射:有没有更高效的双向地图实现方式?