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

2022-01-24 00:00:00 dictionary containers c++ stl

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

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容器?
      • 高效实现双映射:有没有更高效的双向地图实现方式?

相关文章