C ++ ассоциативные контейнеры - почему стандарт не определяет методы для обмена и замены ключей?

Question

Мне нужно заменить определенные значения ключей, тогда как остальная часть value_type остается нетронутой. Что мне действительно нужно сделать, это скопировать значение, стереть запись и снова вставить ее с измененным значением ключа. Это абсолютно плохо. Мне нужно дважды скопировать весь тип value_type и снова освободить / выделить.

Почему стандарт не определяет такие методы:

// returns count of exchanged keys
size_type exchange_key(key_type const& x, key_type const& y);
// returns count of replaced keys
size_type replace_key(key_type const& old_key, key_type const& new_key);

Есть ли что-то, что я пропускаю?

Answer 1

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

Если бы стандарт должен был добавить replace_keyфункция, он также должен был бы указать, что это должно иметь другую сложность, чем существующая комбинация стирания-вставки.Как это может сделать это без утечки деталей реализации?Если не гарантируется, что функция будет быстрее в всех реализациях, она довольно бесполезна.

Когда вы говорите, что она, очевидно, будет быстрее, вы делаете предположения о деталях реализации, которые стандартпытается избежать.

Answer 2

Ну, честно говоря, за экранами это все равно приведет к операции вставки и удаления, с той лишь разницей, что значение-часть не будет скопировано. Хотя это, кажется, является вашей самой большой проблемой, если ваш объект не будет слишком сильно копировать в большом контейнере, операция обновления для повторной стабилизации заказанного контейнера все равно будет тяжелее.

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

1. Класс std::pair нуждается в обновлении, потому что вы должны иметь возможность обновлять ключ без создания новой пары (так как это также скопирует объект значения).
2. Вам нужна функция обновления, которая удаляет пару из дерева, вызывает новую логику из 1. и вставляет ее заново.

Я думаю, что основная проблема связана с первой, поскольку std::pair на данный момент на самом деле очень простая оболочка, и ваше предложение исключит этот принцип и добавит к нему некоторую (ненужную) сложность. Также обратите внимание, что вызов 2 на самом деле не добавляет новых функций, но оборачивает систему, которую разработчик мог бы легко управлять с помощью ссылок и тому подобного. Если бы они добавили всю эту упаковку в std, она стала бы действительно огромной раздутой библиотекой.

Если вам нужен этот принцип, вам следует поискать более сложные библиотеки (вероятно, в boost есть некоторые). Или вы должны просто использовать ссылку / shared_ptr в качестве значения_типа.

Answer 3

Ассоциативные контейнеры реализованы таким образом, что не позволяют эффективно менять «ключ».Чтобы сделать это явным, он не предоставляет удобные методы для замены ключа.Ассоциативный контейнер также должен быть удален и вставлен снова под крышками.

Answer 4

Это связано с тем, что изменение ключа может повлиять на структуру ассоциативных контейнеров. В частности, std::map, которое обычно является красно-черным деревом, структура дерева в основном будет изменена после того, как вы измените ключ (например, вращение поддеревьев). В некоторых структурах данных даже такие динамические изменения запрещены. Поэтому сложно представить такую ​​операцию как стандарт в ассоциативном контейнере.

Что касается служебных данных, которые вы затронули, когда у вас есть value_type в качестве указателя или ссылки, накладные расходы на удаление / вставку пары не так уж плохи.

Answer 5

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

Мне кажется, я где-то читал, что Boost.MultiIndex предоставил эту возможность.