Index to unordered map via tuple of data heavy objects

Question

I have an std::unordered_map<std::tuple<A, A>, B> map;. I have a function that modifies such map

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

Now I am a bit concerned about unnecessary copies of A's. Here are my attempts.

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

It looks clean, but it constructs temporary key (tuple) from copies of a1, a2.

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

This looks promising, because it constructs std::tuple<const A&, const A&> and passes that to map's operator[]. Signature of operator[] for my map is

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

Which doesn't match return type of std::tie, but it worked. So I look at a constructors of std::tuple and found converting constructors, which made me think, that copies are still made (so I tested it).

Is there a way to query the map, without any unnecessary copies, and still preserve O(1) average lookup complexity?

Answer 1

My best guess is that you cannot avoid copying here. The whole problem boils down to something like this:

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

Both constructions of t2 and t3 invokes a copy constructor of A (live demo: https://wandbox.org/permlink/MxTUb61kO3zL3HmD).

If you really care about performance and instances of A are expensive to copy, you can place them into some pool (e.g., std::vector<A>) and then put into your map only pointers to them (std::unordered_map<std::tuple<A*,A*>,B>).

---

UPDATE

Note that you can also design your own "tuple/pair" class that can be constructed either by values or by references. A very basic solution could look like:

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(); }
  };
}

Its usage does not trigger any copy/move constructor during elements access in 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;

I don't like it much but it works. T must be default-constructible here and default constructor is supposed to be cheap. A live demo: https://wandbox.org/permlink/obSfPEJXn3Yr5oRw.