Индекс для неупорядоченной карты через кортеж тяжелых данных

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&> и передает его на operator[] карты. Подпись operator[] для моей карты

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

Который не соответствует типу возврата std::tie, но это сработало. Поэтому я посмотрел на конструкторы std::tuple и нашел конвертирующие конструкторы, что заставило меня подумать, что копии все еще сделаны (, поэтому я протестировал его ).

Есть ли способ запросить карту, без каких-либо ненужных копий и при этом сохранить O (1) среднюю сложность поиска?

Answer 1

Я не думаю, что вы можете избежать копирования. Вместо использования кортежей я написал базовый класс пар шаблонов и просто подставил его в ваш код с вашего сайта, используя семантику перемещения, и вот что я придумал:

template<typename T>
struct Pair {
    T t1;
    T t2;

    Pair<T>() : t1(), t2() {}
    Pair<T>( T a, T b ) : t1( std::move(a) ), t2( std::move(b) ) {}

    Pair<T>( const Pair<T>& p ) : t1( std::move( p.t1 ) ), t2( std::move( p.t2 ) ) {}
    Pair<T>( Pair<T>&& p ) : t1( std::move( p.t1 ) ), t2( std::move( p.t2 ) ) {}

    Pair<T>& operator=( const Pair<T>& p ) {
        t1 = std::move( p.t1 );
        t2 = std::move( p.t2 );
        return *this;
    }

    Pair<T>& operator=( Pair<T>&& p ) {
        t1 = std::move( p.t1 );
        t2 = std::move( p.t2 );
        return *this;
    }
};

struct verbose {
    explicit verbose( int val ) : val( val ) { std::cout << " default ctor\n"; }
    ~verbose() { std::cout << val << " dtor\n"; }

    verbose( const verbose& v ) : val( v.val ) { std::cout << val << " copy ctor\n"; }
    verbose( verbose&& v ) : val( v.val ) { std::cout << val << " move ctor\n"; }

    verbose& operator=( const verbose& v ) {
        val = v.val;
        std::cout << val << " copy assign\n";
        return *this;
    }
    verbose& operator=( verbose&& v ) {
        val = v.val;
        std::cout << val << " move assign " << std::endl;
        return *this;
    }

    int val;
};

struct verbose_hash {
    std::size_t operator()( const Pair<verbose>& v ) const {
        return std::hash<int>{}(std::move( v.t1 ).val ^ std::move( v.t2 ).val);
    }
};

struct verbose_eq {
    bool operator()( const Pair<verbose>& lhs, const Pair<verbose>& rhs ) const {
        return (std::move( lhs ).t1).val == (std::move( rhs ).t1).val &&
            (std::move( lhs ).t2).val == (std::move( rhs ).t2).val;
    }
};

std::unordered_map<Pair<verbose>, int, verbose_hash, verbose_eq> map;

void modify1( const verbose& v1, const verbose& v2 ) {
    map[{v1, v2}] = 1;
}

void modify2( const verbose& v1, const verbose& v2 ) {
    //map[std::tie(v1, v2)] = 1;  // won't work not using tuple
}

int main() { 

    map.emplace(  std::move( Pair<verbose>( verbose(1) , verbose(2) ) ), std::move( 0 ) );
    std::cout << "After emplace\n";

    verbose v1( 1 ), v2( 2 );
    std::cout << "Before lookup1\n";
    modify1( std::move(v1), std::move(v2) );
    std::cout << "Before dtors\n";

    std::cout << "\nPress any key and enter to quit.\n";
    std::cin.get();
    return 0;
}

Выход:

 default ctor
1 move ctor
2 move ctor
1 dtor
2 dtor
1 move ctor
2 move ctor
2 dtor
1 dtor
After emplace
 default ctor
 default ctor
Before lookup1
2 copy ctor        // copy
1 copy ctor        // copy
1 move ctor
2 move ctor
1 dtor
2 dtor
2 dtor
1 dtor
Before dtors

Код использует семантику перемещения, но потому что функция связана с lvalue посредством константной ссылки; ты не уйдешь от копий.

Answer 2

Мое лучшее предположение, что вы не можете избежать копирования здесь. Вся проблема сводится к следующему:

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>).

---

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

Его использование не вызывает конструктора копирования / перемещения при доступе к элементам на карте:

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.