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

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

48 голосов
/ 21 апреля 2011

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

iterator i = m.find(33);

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

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

iterator i = m.find(33);

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

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

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

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

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

  1. найдите узел в дереве, ключ которого я хочу изменить.
  2. отсоединиться от дерева (не освобождать)
  3. 1026 * ребаланс *
  4. изменить ключ внутри отдельного узла
  5. вставить узел обратно в дерево
  6. 1032 * ребаланс *

Ответы [ 7 ]

33 голосов
/ 03 июля 2017

В C ++ 17 новая функция map::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" } }
31 голосов
/ 21 апреля 2011

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

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

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

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

Обновление

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

24 голосов
/ 21 апреля 2011

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

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);
}
6 голосов
/ 21 апреля 2011

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

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

5 голосов
/ 21 апреля 2011

Вы не можете.

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

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

1 голос
/ 21 апреля 2011

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

Как вы говорите, при смене ключа может произойти перебалансировка.Так работает дерево.Возможно, 22 - первый узел в дереве, а 33 - последний?Что мы знаем?

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

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

0 голосов
/ 24 декабря 2018

Если вы знаете, что новый ключ действителен для положения на карте (его изменение не изменит порядок), и вам не нужны дополнительные операции по удалению и добавлению элемента на карту, вы можете использоватьconst_cast для изменения ключа, как в unsafeUpdateMapKeyInPlace ниже: 

template <typename K, typename V, typename It>
bool isMapPositionValidForKey (const std::map<K, V>& m, It it, K key)
{
    if (it != m.begin() && std::prev (it)->first >= key)
        return false;
    ++it;
    return it == m.end() || it->first > key;
}

// Only for use when the key update doesn't change the map ordering
// (it is still greater than the previous key and lower than the next key).
template <typename K, typename V>
void unsafeUpdateMapKeyInPlace (const std::map<K, V>& m, typename std::map<K, V>::iterator& it, K newKey)
{
    assert (isMapPositionValidForKey (m, it, newKey));
    const_cast<K&> (it->first) = newKey;
}

Если вам нужно решение, которое изменяется только на месте, когда оно действительно, и иначе изменяет структуру карты: 

template <typename K, typename V>
void updateMapKey (const std::map<K, V>& m, typename std::map<K, V>::iterator& it, K newKey)
{
    if (isMapPositionValidForKey (m, it, newKey))
    {
        unsafeUpdateMapKeyInPlace (m, it, newKey);
        return;
    }
    auto next = std::next (it);
    auto node = m.extract (it);
    node.key() = newKey;
    m.insert (next, std::move (node));
}
...