如何在迭代时有效地替换 unordered_set 中的元素？

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 （如果发生重新散列），因此这个循环将表现出未定义的行为，并且很可能会严重崩溃。

我能想到的一个解决方案是使用两个单独的 vectors 来缓冲 insert 和 erase 操作，然后使用采用迭代器对进行擦除和插入的重载（这可能更适合重新散列）。

即使我使用缓冲区方法，这仍然看起来是臃肿的代码，并且可能导致两次可能都是不必要的重新哈希。

那么，有没有更好的方法呢？

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());

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());

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() 再次。只需分配并让复制构造函数/赋值运算符发挥其魔力。

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);
    }
}