Использование std :: map :: extract для изменения ключа

Question

Моя реализация использует std :: map для хранения данных. Когда я начал свой код, это казалось лучшим вариантом. Теперь я дошел до того, что мне нужно изменить ключевые значения всех объектов на карте.

Проблема в том, что каждый объект указывает на другой объект внутри карты:

class AND : public node{
    vector <node*> inputs;
    vector <node*> outputs;
}

И карта объявлена ​​так:

map<unsigned int, AND> all_ANDs;

Мой вопрос: Если я использую map :: extract из C ++ 17 для изменения значений ключей в карте all_ANDs, мои указатели (например, внутри входов атрибутов) будут продолжать указывать на правильные места?

Другими словами: Если я изменю значение «первого» элемента с помощью extract, адрес «second» останется неизменным?

Я заметил из этой ссылки , что строка "папайя" остается прежней (и работает изящно). Но я хотел быть уверен в указателях.

Answer 1

Ваш map содержит действительные AND объекты, а не указатели на объекты. Таким образом, если указатели AND*, хранящиеся внутри ваших vector, указывают на объекты map AND, то эти указатели станут недействительными, как только эти объекты будут стерты из * 1009. *.

Тем не менее, извлечение просто отсоединяет указанный узел от map, узел и, следовательно, его ключ и значение по-прежнему действительны в памяти. Узел может быть повторно вставлен в map, не влияя на адреса ключа и значения узла. В связи с этим, указатели в vector НЕ БУДУТ недействительными (хотя нельзя разыменовывать их, пока узел отсоединен от контейнера).

Другой вариант - поменять map на указатели AND*. Или лучше рассмотреть возможность использования std::shared_ptr<AND> в map и std::shared_ptr<node> в vector s вместо необработанных указателей. Тогда не имеет значения, будут ли map записи стерты или извлечены , объекты AND будут оставаться действительными до тех пор, пока на них имеются активные ссылки shared_ptr.

Answer 2

Мой ответ выше отвечает на ваш ближайший вопрос.Однако, как я предположил в комментарии, это, похоже, проблема XY .Что я подозреваю:

1. У вас есть некоторая структура AND объектов, которые связаны через свои поля inputs и outputs.Эта связь не должна нарушаться при любом перераспределении, поэтому вы не можете хранить их в растущем vector<AND> с перераспределением.

2. Вы также хотите упорядочить эти объекты в соответствии с некоторыми key и поэтому сохранили их в map<Key,AND>, который действительно не перераспределяется при выращивании.

3. Теперь вы хотите заказать их в соответствии с другим ключом (и / или изменить все ключи).

(Если вы на самом деле не заинтересованы вупорядочивая, но просто находя объекты по их ключам, вы должны были использовать unordered_map вместо map, который поддерживает find() в O(n) вместо O(log(n)) операций.)

Я предлагаюразличное расположение ваших данных:

1. Вы храните свои AND объекты таким образом, чтобы их количество можно было увеличить без перераспределения.Очевидным выбором здесь является deque<AND>, поскольку вставка и удаление

   на любом конце deque никогда не отменяет указатели или ссылки на остальные элементы

   Вы также можете сделать AND не копируемыми и неподвижными, гарантируя, что после выделения их адрес никогда не изменится (а указатели на них останутся действительными до уничтожения).

2. Вы можете поддерживать любые операции поиска по ключу или упорядочения по ключу, фактически работая с указателями на хранимые объекты, либо сортируя вектор по pair<key,AND*>, либо используя map<key,AND*> или unordered_map<key,AND*>.Вы даже можете одновременно иметь различные ключи для каждого объекта (и карту для каждого).

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

Answer 3

YES Ссылка , которую вы уже цитировали в своих постах, ясно говорит о том, что элементы не копируются или перемещаются . (Это предполагает, что node в вашем фрагменте кода не ссылается на map::node_type).

То же самое относится к операции insert узла карты (после изменения его ключа):

Если вставка прошла успешно, указатели и ссылки на элемент, полученные при его удержании в дескрипторе узла, становятся недействительными, а указатели и ссылки, полученные на этот элемент до его извлечения, становятся действительными. (начиная с C ++ 17)

Однако доступ к объекту между extract() ion и re * insert() имеет неопределенное поведение, и его адрес, полученный в извлеченном состоянии, имеет ограниченное использование. Цитирование из стандарта:

Члены извлечения делают недействительными только итераторы для удаленного элемента; указатели и ссылки на удаленный элемент остаются действительными. Тем не мение, доступ к элементу с помощью таких указателей и ссылок, в то время как Элемент принадлежит node_type с неопределенным поведением. Ссылки и указатели на элемент, полученный в то время как он принадлежит типу узла становится недействительным, если элемент успешно вставлен.

Объяснение

По сути, map<> реализован в виде дерева узлов, каждый из которых содержит key и T (которые отображаются как pair<const Key, T> для пользователя). Узлы распределяются (обычно) в куче, а адрес вашего объекта связан с адресом узла. map::extract() отсоединяет узел от его дерева и возвращает дескриптор узла (объект, содержащий указатель на узел карты), но AFAIK сам узел не перераспределяется, перемещается или копируется. После map::insert(handle) узел повторно связывается с деревом в соответствии с его (новым) ключом. Опять же, это не требует перераспределения, перемещения или копирования узла.

Примечание

Выше приведен примерный набросок. То, как на самом деле все делается, вероятно, более сложное и также определяется реализацией Как объяснено здесь a node_handle позволяет изменять клавишу с помощью функции-члена

Key &node_handle::key() const;

Как это делается под капотом, не указано, и я предполагаю, что реализация использует объединение или некоторую приведение для этого. Конечно, карта должна представлять пользователям pair<const Key,T>, чтобы не дать им сменить ключ и, следовательно, сломать карту, но это не имеет значения для элемента, извлеченного из карты.