c++ - "set with class member as key"的最佳数据结构？

Question

我有这个数据结构:

class foo {
   class bar key;
   … some_associated_values …
};

我现在想使用它构建一个 unordered_set/map/whatever。我的问题是 C++14 不支持单独使用键来查找集合的成员，所以 unordered_set 不存在。使用映射需要拆分值类或复制键，但这两者都需要对我现有的代码库进行一些侵入式重构。

像这样的映射的理想数据结构似乎是 std::pair<const class key&, class value> (用引用替换值类中的键也可以)——但我将如何初始化它，最好以可移植的方式？

Answer 1

My problem is that C++14 doesn't support using the key by itself to find members of a set

在 C++14 中，您可以使用 std::set 但不能使用 std::unordered_set(因为无序容器不支持异构查找):

#include <set>
#include <assert.h>

struct bar { int i; };

bool operator<(const bar& l, const bar& r) { return l.i < r.i; }

struct foo
{
  bar key;
  int val;
};

struct cmp
{
  using is_transparent = void;

  bool operator()(const foo& l, const foo& r) const
  {
    return l.key < r.key;
  }

  bool operator()(const foo& l, const bar& r) const
  {
    return l.key < r;
  }

  bool operator()(const bar& l, const foo& r) const
  {
    return l < r.key;
  }
};

int main()
{
  std::set<foo, cmp> s;
  s.insert(foo{{0}, 1});
  s.insert(foo{{2}, 3});

  auto pos = s.find(bar{0});
  assert( pos != s.end() );
  assert( pos->key.i == 0 );
  assert( pos->val == 1 );

  pos = s.find(bar{1});
  assert( pos == s.end() );

  pos = s.find(bar{2});
  assert( pos != s.end() );
  assert( pos->key.i == 2 );
  assert( pos->val == 3 );
}

---

(附:使用 unordered_map 工作是 possible，但它很卑鄙，而且容易出错。)