如何在迭代无序集合时高效地替换元素？

Question

假设您拥有一个

std::unordered_set<std::shared_ptr<A>> as;
// (there is an std::hash<std::shared_ptr<A>> specialisation)

如果你想在迭代时替换其中的一些元素：

for (auto it = as.begin(); it != as.end(); ++it) {
  if ((*it)->condition()) {
    as.erase(it);
    as.insert(std::make_shared<A>(**it));
  }
}

这可能会使erase和insert中的迭代器无效（如果重新散列），因此该循环将展示未定义的行为，并且很可能会崩溃。

我能想到的一个解决方案是使用两个独立的vector来缓冲insert和erase操作，然后使用接受迭代器对的重载进行删除和插入（这可能更加友好地执行重新散列）。

即使我使用了缓冲区方法，这仍然似乎是臃肿的代码，并且可能会导致两次重新散列，这两次重新散列都可能是不必要的。

所以，有更好的方法吗？

- bitmask

Answer 1

我刚刚想到了一种可能的方法（就在问完之后），但也许还有更好的方法。

将所有内容复制到一个向量中，然后从向量中重建集合应该会更快：

std::vector<std::shared_ptr> buffer;
buffer.reserve(as.size());
for (auto it = as.begin(); it != as.end(); ++it) {
  if ((*it)->condition()) {
    buffer.push_back(std::make_shared<A>(**it));
  } else {
    buffer.push_back(*it);
  }
}
as = std::unordered_set<std::shared_ptr<A>>(buffer.begin(),buffer.end());

- bitmask

---

不要忘记assign方法，它可以有效地将容器重置为一个新内容。 - Matthieu M.

@MatthieuM：相较于operator=，有什么优势？ - bitmask

有趣的是：似乎没有。对于vector或list，有一个，但似乎关联容器没有一个。通常的优点是您不需要构造临时存储（就像在这里所做的那样）。您始终可以通过使用as.clear(); as.insert(buffer.begin(), buffer.end());来模拟它，尽管在列表等中分配（assign）可能通过重用现有存储而不是逐个释放和重新分配节点来进行更好的优化。 - Matthieu M.

@MatthieuM：嗯，构造一个新对象可能不比插入更糟糕，而且operator=很可能是常数时间，因为它会将内容从临时对象中交换出来。但我从来不确定何时必须使用std::move来允许这种行为。 - bitmask

实际上，构建一个新对象可能比插入更糟糕。考虑一个vector（因为它很简单）。如果你取一个有5个元素的向量，并使用3个元素应用assign，它只会覆盖前3个元素并设置大小。如果你首先构建一个新的向量（使用operator=），那么你将需要为这个新向量动态分配内存。 - Matthieu M.

Answer 2

当您调用as.erase(it)时，迭代器it将变为无效。插入到无序关联容器会使所有迭代器无效。因此，插入操作需要与迭代器分离。避免插入操作也是必要的，以避免处理新插入的对象：

std::vector<std::shared_ptr<A>> replaced;
for (auto it = as.begin(); it != as.end(); ) {
    if ((*it)->condition()) {
        replaced.push_back(std::make_shared<A>(**it));
        as.erase(it++);
    }
    else {
        ++it;
    }
}
std::copy(replaced.begin(), replaced.end(), std::inserter(as, as.begin());

- Dietmar Kühl

---

不，我不想这样做，因为在无序集合中，即使是insert操作也会使所有迭代器失效，正如我在问题描述中指出的那样。此外，erase操作会使所有迭代器失效，而不仅仅是当前被删除的迭代器！ - bitmask

根据23.2.5 [unord.req]第13段，它不会使除了被删除的迭代器之外的迭代器无效:“...erase成员只应该使指向被删除元素的迭代器和引用无效。”然而，这意味着在同一个循环中插入和删除是行不通的（我将从我的回复中移除这一部分）。 - Dietmar Kühl

现在我想起来了，std::inserter 可能会导致多次重新哈希，所以我不认为它比只导致两次重新哈希的解决方案（参见 OP）有所改进。 - bitmask

直接将元素插入回去可能会导致新插入的元素再次被迭代：新元素可能会在当前迭代器位置之后。将它们插入回去后，潜在的重新散列数量不会改变：每个插入对象都有一个潜在的重新散列。 - Dietmar Kühl

不，看看原帖中代码块后面的第二和第三段。代码块本身只是我的意图。 - bitmask

Answer 3

我会把这个作为对@bitmask答案的评论。为什么不直接使用向量来替换元素呢？

std::vector<decltype(as)::value_type> buffer;
buffer.reserve(as.size());
for (auto it = as.begin(); it != as.end(); )
{
  if ((*it)->condition())
  {
    buffer.push_back(*it);
    it = as.erase(it);
  }
  else
  {
    ++it;
  }
}
as.insert(buffer.begin(),buffer.end());

而且，如果*it已经是一个shared_ptr<A>，我看不出为什么要再次使用make_shared()。只需分配并让复制构造函数/赋值运算符发挥其魔力。

- user666412

Answer 4

在你的情况下，我认为你可以直接交换：

for(auto iter = as.begin(); iter != as.end(); ++iter)
{
    if(/*Check deletion condition here*/)
    {
        auto newItem = std::make_shared<A>(/*...*/);
        swap(*iter, newItem);
    }
}

- zahir

---

天啊！那将会彻底摧毁这个映射。永远不要改变哈希值的元素。永远不要！ - bitmask

但是你在你的问题中使用了复制构造函数，这就是为什么我提供了交换的原因。这就是我说“在你的情况下”的原因。如果之后要更改内部状态，那么这与更改键相同。 - zahir

哈希表由指针值组成，因此即使我进行复制构造，它的哈希值仍然与先前指针相同。交换操作将更改元素，而不允许映射将该元素放入正确的插槽中；newItem将被归档到*iter的哈希下，这必须不同，因为**iter是旧指针，而*newItem刚刚被构造出来。 - bitmask