Какой самый быстрый способ изменить ключ элемента внутри std:: map

Я понимаю причины, по которым нельзя просто сделать это (перебалансировка и прочее):

iterator i = m.find(33);

if (i != m.end())
  i->first = 22;

Но пока единственный способ (я знаю) изменить ключ - удалить node из дерева alltogether, а затем вставить значение обратно с помощью другого ключа:

iterator i = m.find(33);

if (i != m.end())
{
  value = i->second;
  m.erase(i);
  m[22] = value;
}

Это кажется мне неэффективным по нескольким причинам:

  • пересекает дерево три раза (+ баланс) вместо двух (+ баланс)
  • еще одна ненужная копия значения
  • ненужное освобождение, а затем перераспределение node внутри дерева

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

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

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

Ответы

Ответ 1

В С++ 17 новая функция, которая позволяет сменить ключ, функция extract() Пример:

std::map<int, std::string> m{ {10, "potato"}, {1, "banana"} };
auto nodeHandler = m.extract(10);
nodeHandler.key() = 2;
m.insert(std::move(nodeHandler)); // { { 1, "banana" }, { 2, "potato" } }

Ответ 2

Я предложил ваш алгоритм для ассоциативных контейнеров около 18 месяцев назад здесь:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839

Ищите комментарий с пометкой: [2009-09-19 Говард добавляет:].

В то время мы были слишком близки к FDIS, чтобы рассмотреть это изменение. Однако я считаю, что это очень полезно (и вы, по-видимому, согласны), и я хотел бы получить его в TR2. Возможно, вы могли бы помочь, найдя и уведомив представителя С++ National Body о том, что это функция, которую вы хотели бы видеть.

Обновление

Не уверен, но я думаю, что есть хороший шанс, мы увидим эту возможность в С++ 17!: -)

Ответ 3

Вы можете опустить копирование значения;

const int oldKey = 33;
const int newKey = 22;
const iterator it = m.find(oldKey);
if (it != m.end()) {
  // Swap value from oldKey to newKey, note that a default constructed value 
  // is created by operator[] if 'm' does not contain newKey.
  std::swap(m[newKey], it->second);
  // Erase old key-value from map
  m.erase(it);
}

Ответ 4

Вы не можете.

Как вы заметили, это невозможно. Карта организована так, что вы можете эффективно изменить значение, связанное с ключом, но не наоборот.

Взгляните на Boost.MultiIndex и, в частности, на разделы эмуляции стандартных контейнеров. Контейнеры Boost.MultiIndex обеспечивают эффективное обновление.

Ответ 5

Ключи в STL-картах должны быть неизменными.

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

Ответ 6

Вы должны оставить выделение распределителю.: -)

Как вы говорите, при изменении ключа может быть много перебалансировки. Это то, как дерево работает. Возможно, 22 является первым node в дереве и 33 последним? Что мы знаем?

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

Для приключений:
Если вы точно знаете, что изменение ключа не влияет на порядок, и вы никогда, никогда не ошибетесь, немного const_cast будет позволять вам менять ключ в любом случае.