通过数据重对象的元组索引无序映射

Question

我有一个std::unordered_map<std::tuple<A, A>, B> map;.我有一个修改这样的地图的功能

void modify(const A& a1, const A& a2)
{
    map[/* a1, a2 */].modify();
}

现在我有点担心不必要的副本A.这是我的尝试.

map[{a1, a2}].modify();

看起来干净,但它构建了从副本临时密钥(元组)a1,a2.

map[std::tie(a1, a2)].modify();

这看起来很有希望,因为它构造std::tuple<const A&, const A&>并将其传递给map operator[].operator[]我的地图签名是

B& operator[](const std::tuple<A, A>&)
B& operator[](std::tuple<A, A>&&)

哪个与返回类型不匹配std::tie,但它有效.所以我看一下构造函数,std::tuple并发现转换构造函数,这让我想到,复制品仍在制作中(所以我测试了它).

有没有办法查询地图,没有任何不必要的副本,仍然保持O(1)平均查找复杂性？

Answer 1

我最好的猜测是你不能避免在这里复制.整个问题归结为这样的事情:

A x1;
std::tuple<A&> t1{x1};
const std::tuple<A>& t2{t1};
const std::tuple<A>& t3{std::tuple<A&>{x1}};

两者的构造t2和t3调用A(live demo:https://wandbox.org/permlink/MxTUb61kO3zL3HmD)的复制构造函数.

如果你真的关心性能和A复制昂贵的实例,你可以将它们放入某个池(例如std::vector<A>),然后只将指针放到你的地图中(std::unordered_map<std::tuple<A*,A*>,B>).

UPDATE

请注意,您还可以设计自己的"元组/对"类,可以通过值或引用来构造.一个非常基本的解决方案可能如下:

struct construct_from_ref_tag { };

template <typename T> class ref_pair {
  public:
    ref_pair(T v1, T v2)
      : v1_(std::move(v1)), v2_(std::move(v2)), r1_(v1_), r2_(v2_) { }
    ref_pair(const T& r1, const T& r2, construct_from_ref_tag)
      : r1_(r1), r2_(r2) { }
    bool operator==(const ref_pair<T>& rhs) const {
      return ((r1_ == rhs.r1_) && (r2_ == rhs.r2_)); }
    size_t hash() const {
      return std::hash<T>{}(r1_) ^ std::hash<T>{}(r2_); }
  private:
    T v1_, v2_;
    const T& r1_;
    const T& r2_; 
};

namespace std {
  template <typename T> struct hash<ref_pair<T>> {
    size_t operator()(const ref_pair<T>& v) const { return v.hash(); }
  };
}

它的用法在map中的元素访问期间不会触发任何复制/移动构造函数:

std::unordered_map<ref_pair<A>, int> map;
map[ref_pair<A>(1, 2)] = 3;

A a1{1};
A a2{2};

std::cout << "before access" << std::endl;
map[ref_pair<A>(a1, a2, construct_from_ref_tag{})] += 1;

我不喜欢它但它有效.T必须是默认构造在这里,默认构造函数应该是便宜的.现场演示:https://wandbox.org/permlink/obSfPEJXn3Yr5oRw.