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

Question

Это связано с первым выпуском Item в Effective C # с предупреждением о переопределении GetHashCode() наивно.

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

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

• Имя,
• Средний инициал
• Фамилия

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

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

Почему это произошло?

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

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

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

Буду признателен за ваши идеи.

Answer 1

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

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

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 он не будет работать, если только массив не содержит указателей const.

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.

Answer 2

В стандартном контейнере есть требование, чтобы хранимый в нем класс имел значение семантическое и, следовательно, они копировались.Но

• , если вы храните указатели любого типа, то, что указано, не копируется;
• , если вы пытаетесь изменить сохраненный ключ (вы можете получить ссылку на него)особенно играя трюки с изменяемыми членами или const_cast, чтобы иметь возможность сделать это таким образом, что порядок сортировки не сохраняется, вы находитесь в области UB.

Answer 3

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

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

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

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

Answer 4

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

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