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

Question

我有一个 std::unordered_map<std::tuple<A, A>, B> map; .我有一个修改这样的 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[]的签名我的 map 是

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

不匹配 std::tie 的返回类型，但它奏效了。所以我看一下 std::tuple 的构造函数并找到了转换构造函数，这让我想到，拷贝仍然存在(so I tested it)。

有没有办法查询 map ，没有任何不必要的拷贝，并且仍然保持 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 的拷贝构造函数(现场演示:https://wandbox.org/permlink/MxTUb61kO3zL3HmD)。

如果您真的关心 A 的性能和实例复制起来很昂贵，您可以将它们放入某个池中(例如 std::vector<A> )，然后仅将指向它们的指针( std::unordered_map<std::tuple<A*,A*>,B> )放入您的 map 中。

---

更新

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

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 .