Блог

#c #performance #dictionary #binary-tree #std

#c #Производительность #словарь #двоичное дерево #std

Вопрос:

 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. @sehe, я не думаю, что это проблема со структурой данных, если бы я собирался создать свою собственную, я бы в итоге получил то же красно-черное дерево с той лишь разницей, что у него был бы метод, который повторно использовал бы узел вместо выделения и перераспределения.

3. «1. обходит дерево три раза ( баланс) вместо дважды ( баланс)» — это дважды вместо одного раза… обход не требуется для end() .

4. @TonyDelroy Я считаю, что operator[] является третьим.

5. @luizfls: есть обход для find , затем erase(i) принимает итератор в качестве аргумента (не значение, подлежащее удалению), избегая другого обхода, но конечному insert действительно нужно выполнить второй обход, чтобы найти новое место для вставки (так как при изменении ключа он потенциально будет находиться в несвязанном положении — если вы знаете, что новая вставка должна быть очень близка в дереве к старой, вы можете предоставить подсказку о вставке).

Ответ №1:

 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:

Комментарии:

1. Я попробую связаться с ним (не уверен, с чего начать, но уверен, что Google поможет). История, стоящая за моим вопросом, заключается в том, что я разрабатывал такую карту для компании, которая предпочитает не использовать внешние библиотеки (встроенные системы), и свойство RB trees, заключающееся в том, что они сохраняют свои элементы отсортированными, и быстрая смена ключа оказалась решающей в некоторых случаях. Я хотел сохранить API таким же, как в std :: map, но, к моему удивлению, не нашел ничего, что решило бы эту проблему. Итак, я попытаюсь реализовать то, что вы предложили по ссылке, спасибо.

2. Пожалуйста, не стесняйтесь обращаться ко мне напрямую, если вам нужна помощь в определении вашего представителя NB. Примечание для всех остальных: шансы включить это в стандарт сводятся к нулю, если это поддерживают только два человека. Если вы хотите, чтобы эта функциональность была добавлена в упорядоченные и неупорядоченные ассоциативные контейнеры, тогда лоббируйте это! Не ждите до 2016 года, а затем жалуйтесь, когда узнаете, что его там нет. Сейчас самое время действовать.

3. @HowardHinnant, эм, ты пытался перенести это в C 11? Как насчет C 14?

4. @Dewfy: erase уничтожает объект на карте и освобождает узел, содержащий этот объект. emplace_hint выделяет новый узел и создает новый объект в этом узле из аргументов emplace_hint . Каждая из этих функций-членов определена изолированно, и у них нет способа узнать, когда они используются в указанной вами комбинации. Вот последнее предложение по этому вопросу, и новая редакция выйдет через несколько недель: open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0083r1.pdf

5. @LukasBarth: Вы совершенно правы! И это будет настолько хорошо, насколько возможно. Цикл извлечения / вставки будет использовать существующий узел, избегая любого выделения / освобождения (за исключением любого вашего переназначения ключа).

Ответ №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);
}
  

Комментарии:

1. @Viktor, хм, во-вторых, std::swap выполняет два назначения и также вводит временное значение (по умолчанию). Но если (…) { m[22] = it-> second; m.erase(it); } , вероятно, подойдет.

2. @Peter: Если копирование или присвоение value_type является проблемой производительности, std::swap<value_type> должно быть специализированным, чтобы быть более эффективным, чем одиночное присвоение в m[22] = it->second; .

3. @Peter: если ваш value_type является таким простым типом, то исключение копирования является нано-оптимизацией в этом контексте.

4. @Viktor, верно, я думал в общем случае.

5. @aschepler, я знаю, что это просто придирчивый выбор, но я считаю, что любая специализация на std:: swap обязательно должна была бы выполнить (чтобы быть правильной) одно избыточное присвоение обратно ему-> второе. В любом случае, я согласен с последним замечанием Виктора в том, что этот дополнительный asssignment был наименее беспокоящим.

Ответ №4:

Ответ №5:

Ответ №6:

 template <typename K, typename V, typename It>
bool isMapPositionValidForKey (const std::map<K, V>amp; m, It it, K key)
{
    if (it != m.begin() amp;amp; 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>amp; m, typename std::map<K, V>::iteratoramp; it, K newKey)
{
    assert (isMapPositionValidForKey (m, it, newKey));
    const_cast<Kamp;> (it->first) = newKey;
}
  

 template <typename K, typename V>
void updateMapKey (const std::map<K, V>amp; m, typename std::map<K, V>::iteratoramp; 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));
}