4

使用 C++17 节点extract()函数，我可以更改密钥而无需重新分配节点。在我的特定用例中，我将密钥替换为相等的密钥，因此我想使用 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()是一个新节点时，它key_type会继续指向，但是，它会作为emplacementfrom.data()中的构造的一部分而被移出。mapped_type由于 SSO（小字符串优化），移动的字符串data()可能与源字符串的 不同，一旦的生命周期结束，可能会更快地data()使 无效。因此，我们需要将 to 重新设置为，为此我们 (1) 提取节点，确保通过在 之前递增它来保持有效，然后 (2) 根据需要修补密钥，最后 (3) 重新- 在提示给出的旧位置插入节点。key_typefromkey_typemapped_typeitextract()it

到目前为止，一切都很好。现在尝试相同的unordered_map：

~~~~
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++);    // only thing possible, but wrong direction
    // auto node = replacements.extract(it--); // right direction, but ERROR: unordered_map isn't bidirectional
    node.key() = node.mapped().from;           // 2
    replacements.insert(it, std::move(node));  // 3
}

在这里，我遇到了一个问题unordered_map，作为 a vector<forward_list>，只有前向迭代器，所以我不能，因为我不得不，向后记住迭代顺序中最终 insert-with-hint (3) 的确切插入点。看来我只有两个选择：

  1. 在没有提示的情况下使用 insert(node)，导致完整的第二次查找
  2. 递增迭代器并将其作为提示传递。标准表示插入是尽可能接近提示执行的，但至少使用桶内迭代器是仅向前的，如果我的哈希表与良好性能所需的一样稀疏，则递增的迭代器可能是桶列表中的几个桶，使提示无用。

所以，好吧，提示对unordered_map</rubberducking> 没用。为了保存问题，让我们谈谈unordered_multimap，然后:)

在unordered_map中，提示可能很有用，因为与 不同unordered_map，unordered_multimap需要扫描存储桶以将新节点放入equal_range()密钥的潜在位置。有没有比后增量或根本不产生提示更好的方法？

4

1 回答 1

1

如果您的唯一目标是保留值的键调整，则无需提取任何内容：只需将您的键包装在一个将其作为mutable成员（或通过 a 保存std::unique_ptr）的类中，以便您可以在地图中合法地更改它。您必须为包装器类型定义比较/散列操作，但这只不过是迭代器诡计的代码。

于 2021-08-10T08:49:12.453 回答