我有一堆元素存储在某个容器中。他们的订单对我来说无关紧要。
我对容器进行迭代，并为每个元素检查一些谓词-p。如果P为true，则从容器中移除元素。如果P为false，则转到下一个。如果在迭代过程中至少删除了一个元素，我会重复这个过程。在新的迭代中，对于在以前的迭代中为假的元素，P有可能为真。
我已经为这个写了一个代码
std::unordered_map<T, T> container;
auto it = container.begin();
while (it != container.end()) {
if (predicate(*it)) {
it = container.erase(it);
} else {
it++;
}
}
我有一个问题：考虑到我的容器中有大约500个元素，有没有更好的方法来做到这一点(从干净的代码和时间效率的角度来看(。
在循环中使用std::erase_if()：
while (std::erase_if(your_set, your_predcate))
/**/;
如果你没有C++20，不要绝望。Cppreference.com也给出了一个实现示例。
如果它被证明是一个瓶颈，那么手动滚动您自己的all_erase_if()并专门用于基于节点的容器可能会很有用：
template <class T>
constexpr bool has_node_type = requires { typename T::node_type; };
template <class T>
constexpr bool is_node_based = has_node_type<T>;
template <class C, class P>
auto all_erase_if(C& c, F f) requires is_node_based<C> {
const auto old_size = std::size(c);
if (!old_size)
return old_size;
auto it = std::begin(c), stop = std::begin(c);
do {
while (f(*it)) {
it = stop = c.erase(it);
if (it != std::end(c))
/**/;
else if (std::empty(c))
return old_size;
else
it = stop = std::begin(c);
}
if (++it == std::end(c))
it = std::begin(c);
} while (it != stop);
return old_size - std::size(c);
}
template <class C, class P>
auto all_erase_if(C& c, F f) requires !is_node_based<C> {
const auto old_size = std::size(c);
while (std::erase_if(c, std::ref(f)))
/**/;
return old_size - std::size(c);
}
您想要在容器上循环迭代，直到完成了一个完整的过程，其中没有删除任何内容。
template<class C, class F>
void multi_pass_erase( C& c, F&& f )
{
auto stop_at = c.end();
auto it = current;
while (true)
{
if (c.empty())
return;
if (f(*it))
{
it = c.erase(it);
if (it == c.begin())
stop_at = c.end();
else
stop_at = it;
}
else
{
++it;
if (it == stop_at)
return;
}
if (it == c.end())
it = c.begin();
}
}
在循环开始时，它指的是要测试的下一个元素，并且仅在容器为空时指的是end。
因此，如果容器是空的，请返回。
stop_at跟踪元素，如果我们到达它，我们已经遍历了整个容器，但没有找到要过滤的内容。
如果我们删除一些东西，我们会注意到，停止的正确位置是在我们删除的元素之后。
如果我们不删除某些内容，我们将推进迭代器，并检查是否应该停止。
然后，如果我们已经到达容器的末尾，我们就回到起点。
我们在测试"；停止"；在我们将它从结束移回开始之前，所以我们永远不应该将stop_at存储为引用begin()。
现在让我们将其与进行比较
while (true) {
if (!std::erase_if( set, test ))
break;
}
想象一下，如果每个循环都删除一个元素。这可能需要O(n^2(时间。
multi_pass_erase在这种情况下不会做得更好。如果每个元素都导致前一个元素被擦除，那么multi_pass_erase不会减少任何访问；在这两种情况下，在找到下一个要删除的节点之前，都必须访问每个未删除的节点。
基本上，每当至少有1次擦除时，对multi_pass_erase的所有幻想都会使每个调用的集合平均减少一半的迭代，就好像我们假设最后一次擦除是随机定位的一样，我们跳过了容器的平均一半。
增加的复杂性可能不值得
但我们能写一些更复杂、更高效的东西吗？
通常，当您删除一些可能导致其他内容需要删除的内容时，您可以获得有关这些其他内容的信息。
考虑跟踪这些信息，只查看这些元素，而不是再次查看整个列表。
template<class C, class Test, class Dependencies>
void dependent_erase( C& c, Test&& t, Dependencies&& d ) {
auto it = c.begin();
using key_type = typename C::key_type;
std::vector<key_type> todo_list;
while (it != c.end())
{
if (t(*it)) {
d( *it, &todo_list );
it = c.erase(it);
} else {
++it;
}
}
// remove duplicates:
std::vector<key_type> next_todo_list;
while (!todo_list.empty()) {
// better to shrink the list and ask f(x) less often
std::sort(todo_list.begin(), todo_list.end());
todo_list.erase( std::unique(todo_list.begin(), todo_list.end()), todo_list.end() );
for (auto&& todo : todo_list) {
auto it = c.find( todo );
if (f(*it))
{
d( *it, &next_todo_list );
c.erase(it);
}
}
todo_list = std::move( next_todo_list );
next_todo_list.clear();
}
}
这里有我们的测试t(我们想删除这个项目吗？(如果我们删除了，我们调用d( item, vector* )并存储我们想在那里重新测试的任何直接依赖项。
然后我们检查容器，根据需要取出东西。然后，我们检查依赖项，并删除任何提到的应该消失的内容，重复直到我们不再找到要删除的新项目。
如果我们假设您的代码是一堆引用了其他节点的节点，并且您正在进行垃圾收集，那么在许多情况下，这应该要好得多。
未测试甚至未编译的代码。但我以前也这样做过，所以它可能会起作用。它至少应该作为伪代码工作。
如果您期望每个删除的节点有很多依赖项，并且有很多重叠，那么基于集合的todo列表可能比向量列表更好。也就是说，如果你去掉了N个元素，每个元素都有M个依赖项，那么向量就会增长到NM大小。但是，如果M往往很小，并且与其他元素没有太多重叠，那么向量将比基于节点的集合快得多。