Эффективный узел extract() + insert() в unordered_map

Question

Используя функции узла C++17, я могу изменить ключ, не перераспределяя узел. В моем конкретном случае использования я заменяю ключ на равный, поэтому я хотел бы использовать insert()-with-hint, чтобы избежать полного второго поиска, и это отлично работает при использовании std::map:

      struct Replacement { std::string from, to; };
std::map<std::string_view, Replacement> replacements;
~~~~
std::string from = ~~~;
std::string to = ~~~:
auto [it, inserted] = replacements.try_emplace(from, std::move(from), std::move(to));
if (inserted) {
    // need to patch up the key, which points to invalid data now:
    auto node = replacements.extract(it--);    // 1
    node.key() = node.mapped().from;           // 2
    replacements.insert(it, std::move(node));  // 3
}

Насколько я insert() новый узел, он будет продолжать указывать на from.data(), который, однако, перемещается как часть конструкции в закладке. Из-за SSO (оптимизация малых строк) перемещенная строка может отличаться от исходной строки. data(), аннулируя, как только fromсрок жизни заканчивается, возможно, раньше. Итак, нам нужно переустановить key_type указать на mapped_type, для которого мы (1) извлекаем узел, убедившись, что он остается действительным, уменьшая его перед extract(), затем (2) исправление ключа по мере необходимости и, наконец, (3) повторная вставка узла в старую позицию, указанную подсказкой it.

Все идет нормально. Теперь попробуйте то же самое с:

      ~~~~
std::string from = ~~~;
std::string to = ~~~:
auto [it, inserted] = replacements.try_emplace(from, std::move(from), std::move(to));
if (inserted) {
    // need to patch up the key, which points to invalid data now:
    // auto node = replacements.extract(it--); // ERROR: unordered_map isn't bidirectional
    auto node = replacements.extract(it++);    // only thing possible, but wrong direction
    node.key() = node.mapped().from;           // 2
    replacements.insert(it, std::move(node));  // 3
}

Здесь я столкнулся с проблемой, что, будучи vector<forward_list>, имеет только прямые итераторы, поэтому я не могу, как в mapслучае, вернитесь назад, чтобы запомнить точную точку вставки последней вставки с подсказкой (3). Кажется, у меня есть только два варианта:

1. используйте insert(node) без подсказки, вызывая полный второй поиск
2. увеличьте итератор и передайте это как подсказку. В std говорится, что вставка выполняется как можно ближе к подсказке, но с итераторами внутри сегмента, по крайней мере, только для пересылки, если моя хеш-таблица настолько разрежена, насколько это требуется для хорошей производительности, увеличиваемый итератор может быть несколькими ведра вниз по списку, делая подсказку бесполезной.

Итак, подсказка для </rubberducking> бесполезна. Чтобы сохранить вопрос, поговорим, тогда :)

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

Answer 1

Если ваша единственная цель - сохранить значения ключевых настроек, вам не нужно ничего извлекать: просто оберните свой ключ в класс, который имеет его как mutable член (или удерживает его через std::unique_ptr) , Так что вы можете законно изменить его на карте. Вам нужно будет определить операции сравнения / хеширования для типа оболочки, но это не больше кода, чем уловка итератора.