Копирует / освобождает ли unordered_map содержащиеся объекты, если есть операция вставки / удаления / перефразировки?

Question

Я хочу хранить маленькие объекты в unordered_map, просто интересно, может ли он копировать / освобождать содержащиеся объекты, если есть какая-либо операция вставки / удаления / перефразировки?Я думаю, что unordered_map использует список ссылок для хранения пары ключ / значение, ему не нужно копировать / освобождать объекты, такие как vector, для перераспределения памяти.

Answer 1

C ++ 11 стандарт: § 23.2.5 / 8

Элементы неупорядоченного ассоциативного контейнера организованы в сегменты.Ключи с одинаковым хеш-кодом появляются в том же сегменте.Количество сегментов автоматически увеличивается при добавлении элементов в неупорядоченный ассоциативный контейнер, так что среднее количество элементов в сегменте остается ниже границы. Перефразирование делает недействительными итераторы, изменяет порядок между элементами и меняет элементы, в которых они отображаются, но не делает недействительными указатели или ссылки на элементы.Для unordered_multiset и unordered_multimap повторное хеширование сохраняет относительное упорядочение эквивалентных элементов.

Вкратце для unordered_map,
В случае Операции вставки / удаления ,

• Все итераторы становятся недействительными, когда происходит перефразировка, но ссылки остаются без изменений.

Answer 2

Я сделал тест, используя этот код:

#include <iostream>
#include <unordered_set>
#include <unordered_map>

struct A
{
    static int copies;

    A(int a): a(a){}
    A(A const& pA){std::cout << "A copy" << std::endl; ++copies; a = pA.a;}
    A& operator=(A const& pA){std::cout << "= operator" << std::endl; a = pA.a; ++copies; return *this;}

    int a;



    bool operator==(A const& pA)const{return pA.a == a;}
    bool operator!=(A const& pA)const{return pA.a != a;}
    bool operator>(A const& pA)const{return pA.a > a;}
    bool operator<(A const& pA)const{return pA.a < a;}
};
int A::copies = 0;


namespace std{
template<>
class hash<A>
{
public:
    size_t operator()(A const& pA) const
    {
        return pA.a;
    }
};
}


int main()
{

    std::unordered_map<A, A> map;
    std::unordered_set<A> set;

    for(int i=0; i<1000000; ++i)
    {
        set.insert(A(i));
        map.insert(std::pair<A, A>(A(i), A(i)));
    }
    std::cout << A::copies << std::endl;

    return 0;
}

Конструктор копирования для набора вызывался 1 миллион раз - это означает, что каждый объект был скопирован только один раз (в набор). Для копирования карты конструктор вызывался 4 млн раз - 2 раза домашний объект (обратите внимание, что для карты требуется 2 объекта A на каждую вставку). Более того, когда я запускаю тест, в котором я вставляю только один объект (для i <1), копирование construcotr вызывается один раз для набора и 4 раза для карты. </p>

Выводы: Кажется, что перекомпоновка и вставка объектов не перераспределяет объекты ни в unordered_set, ни в unordered_map. Я думаю, что это правда, потому что я не верю, что не было ни одной перефразировки для стольких вставок. Конструктор копирования вызывался один раз для множества (для копирования объекта в узел множества) - очевидно. Почему тогда copy construcotr вызывался 4 раза для каждого вызова вставки карты? Ключ карты - это объект A, а значение - это объект A. Объекты были созданы, затем скопированы в std :: pair (первые 2 копии), а затем pair был скопирован в карту (еще 2 копии) - я думаю, что так оно и есть.

Так что кажется, что объекты в неупорядоченной карте и множестве никогда не перераспределяются, поэтому указатели и ссылки остаются действительными, а итераторы, вероятно, нет - @Alok Save answer. Я сделал этот тест, потому что мне было интересно, перераспределяются ли ключи, когда происходит перефразировка. @Alok Save писал об элементах, но не о ключах (или я не правильно понял его ответ, а элемент означает значение и ключ).

Вопрос: Стандарт говорит что-нибудь о ключах (если они не рассматриваются как элементы)?

PS: Для теста я использовал g ++ 4.8.