Когда `ключ/значение` вставляется в `std::map`, создает ли он собственную копию объектов?

Это вдохновлено первым изданием Item in Effective C#, предупреждающим о наивном переопределении GetHashCode().

Извините, у меня нет кода поддержки. Кстати, это не домашняя работа, я просто не очень знаком с C++/STL, и не смог найти информации по реализации.

Предположим, я создаю свой собственный класс с именем person, который имеет 3 общедоступных изменяемых строковых поля:

  • Имя,
  • Второй инициал
  • Фамилия

Он также предоставляет оператор меньше, чем для сравнения одного человека с другим на основе сначала имени, затем среднего имени, а затем фамилии - вот и все.

Я создаю карту от человека к целому (скажем, возраст) и заполняю ее примерно 20 парами ключ/значение. Я также храню указатели на свои ключи в массиве. Затем я меняю первое имя объекта, на который указывает пятый указатель, и пытаюсь найти соответствующий возраст, используя этот измененный ключ (помните, что объект изменчив и широко открыт).

Почему это случилось?

А) Потому что ключ, используемый std::map, не изменился (скопировался), а я изменил свою копию и теперь мой ключ не найден. Но как это может быть? Я не предоставил свой собственный конструктор копирования. Возможно, компилятор создал дефолтный?

Б) Коллекция std::map на самом деле является красно-черным деревом, и у меня оказался прямой указатель на ключ. Когда я изменил ключ, я изменил его прямо в узле дерева. Теперь вполне вероятно, что мой узел расположен неправильно и не будет найден с помощью правильного алгоритма поиска по дереву. Я должен был удалить узел, затем изменить ключ, а затем снова вставить его. Если это так, то я подозреваю, что STL коллекции вообще довольно опасны и заставляют нубов делать много ошибок.

В) Что-то еще?

Я был бы признателен за ваши идеи.


c++ stl stdmap
person Hamish Grubijan    schedule 16.04.2011    source источник
comment
Какие конкретные типы данных вы используете в своем ключе? Вы говорите строка, но для ясности, это std::strings? Если это так, верно A — контейнеры STL будут копировать все данные в ключе и значении.   -  person Joe    schedule 16.04.2011

Ответы (4)


arrow_upward
12
arrow_downward

При использовании стандартных контейнеров все данные копируются в контейнер. Для карт это ничем не отличается.

Одно ограничение, которое карта накладывает на данные, заключается в том, что ключ не может быть изменен. После того, как он вставлен, он фиксируется для изменения ключа, который вы должны найти / стереть и повторно вставить, чтобы изменить значение ключа.

struct Person
{
   std::string   first;
   std::string   middle;
   std::string   last;
   Person(std::string const& f, std::string const& s, std::string const& l) { BLABLA }
   bool operator<(Person const& rhs)                                        { return BLABLABLA;}
};
std::map<Person,int>   ageMap;

ageMap[Person("Tom", "Jones", "Smith")] = 68;
ageMap[Person("Tom", "I",     "Smith")] = 46;
ageMap[Person("Tom", "II",    "Smith")] = 24;

Когда вы создаете свой массив Person, он завершится ошибкой, если массив не содержит константных указателей.

Person* pMap[3];
pMap[0] = &ageMap.begin().first;       // Fail need a const pointer.

Person const* pMapConst[3];
pMapConst[0] = &ageMap.begin().first;  // OK. Note a const pointer.
person Martin York    schedule 16.04.2011

arrow_upward
7
arrow_downward

Стандартный контейнер требует, чтобы хранящийся в нем класс имел семантику значений, и поэтому они копируются. Но

  • если вы храните указатели любого типа, то, очевидно, то, что указано, не копируется;
  • если вы попытаетесь изменить сохраненный ключ (вы можете получить ссылку на него), особенно играя трюки с изменяемыми членами или const_cast, чтобы иметь возможность сделать это таким образом, что порядок сортировки не сохраняется, вы в сфере УБ.
person AProgrammer    schedule 16.04.2011
comment
Что такое мир УБ? Или где это? - person idichekop; 09.06.2017

arrow_upward
3
arrow_downward

Записи всегда делают копию. Если тип ключа std::string, то да, это копия. (За кулисами std::string выполняет некоторые оптимизации, поэтому символы не обязательно всегда копируются, но это не главное.)

(Я думаю, что нет способа получить указатель на объекты карты, поэтому вы не можете снова изменить этот ключ, просто получите копии при итерации или другом поиске.)

Теперь, если ваш тип ключа — *std::string (указатель!), тогда биты в указателе копируются, но если значение конкретного экземпляра строки позже изменится, то ключ будет фактически изменен.

(И компаратор должен соответствовать вашему типу ключа.)

person david van brink    schedule 16.04.2011

arrow_upward
2
arrow_downward

Да, когда вы вставляете элемент в std::map, вы передаете его по значению, поэтому он содержит копию того, что вы передали. Да, компилятор синтезирует для вас конструктор копирования, если вы сами его не объявите.

Можно создать (например) карту, которая использует указатель в качестве ключа (вместе с функцией сравнения/функтором, который сравнивает то, на что ссылаются указатели). Однако если вы попытаетесь изменить ключи, на которые указывают эти указатели, вы получите UB. Если вы хотите изменить ключ в наборе/карте/мультимножестве/мультикарте, вам нужно удалить существующий элемент из коллекции, изменить свою копию, а затем вставить измененную версию обратно в коллекцию.

person Jerry Coffin    schedule 16.04.2011