如何有效地从一个forward_list的remove_if仅一个元件的? [英] How do I efficiently remove_if only a single element from a forward_list?
问题描述
嗯,我认为这个问题pretty的多总结起来。我有一个独特的项目一个forward_list,并希望从中取出一个单一的项目:
Well I think the question pretty much sums it up. I have a forward_list of unique items, and want to remove a single item from it:
std::forward_list<T> mylist;
// fill with stuff
mylist.remove_if([](T const& value)
{
return value == condition;
});
我的意思是,这种方法效果不错,但它是低效率的,因为它继续寻找,一旦该项目被发现和删除。有没有更好的方法或做我需要做手工?
I mean, this method works fine but it's inefficient because it continues to search once the item is found and deleted. Is there a better way or do I need to do it manually?
推荐答案
如果你只是想去掉的第一场比赛,你可以使用的std :: adjacent_find
其次是成员 erase_after
If you only want to remove the first match, you can use std::adjacent_find
followed by the member erase_after
#include <algorithm>
#include <cassert>
#include <forward_list>
#include <iostream>
#include <ios>
#include <iterator>
// returns an iterator before first element equal to value, or last if no such element is present
// pre-condition: before_first is incrementable and not equal to last
template<class FwdIt, class T>
FwdIt find_before(FwdIt before_first, FwdIt last, T const& value)
{
assert(before_first != last);
auto first = std::next(before_first);
if (first == last) return last;
if (*first == value) return before_first;
return std::adjacent_find(first, last, [&](auto const&, auto const& R) {
return R == value;
});
}
int main()
{
auto e = std::forward_list<int>{};
std::cout << std::boolalpha << (++e.before_begin() == end(e)) << "\n";
std::cout << (find_before(e.before_begin(), end(e), 0) == end(e)) << "\n";
auto s = std::forward_list<int>{ 0 };
std::cout << (find_before(s.before_begin(), end(s), 0) == s.before_begin()) << "\n";
auto d = std::forward_list<int>{ 0, 1 };
std::cout << (find_before(d.before_begin(), end(d), 0) == d.before_begin()) << "\n";
std::cout << (find_before(d.before_begin(), end(d), 1) == begin(d)) << "\n";
std::cout << (find_before(d.before_begin(), end(d), 2) == end(d)) << "\n";
// erase after
auto m = std::forward_list<int>{ 1, 2, 3, 4, 1, 3, 5 };
auto it = find_before(m.before_begin(), end(m), 3);
if (it != end(m))
m.erase_after(it);
std::copy(begin(m), end(m), std::ostream_iterator<int>(std::cout, ","));
}
这将尽快找到一个匹配停止。请注意, adjacent_find
取二进制predicate,并通过比较仅第二个参数,我们得到了我们想要删除的元素前一个迭代器,使 erase_after
其实可以将其删除。复杂性是 O(N)
,所以你不会得到比这更有效。
This will stop as soon as a match is found. Note that the adjacent_find
takes a binary predicate, and by comparing only the second argument, we get an iterator before the element we want to remove, so that erase_after
can actually remove it. Complexity is O(N)
so you won't get it more efficient than this.
这篇关于如何有效地从一个forward_list的remove_if仅一个元件的?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!