好吧,我认为这个问题几乎可以总结出来。我有一个独特商品的forward_list,想从中删除一个商品:
std::forward_list<T> mylist; // fill with stuff mylist.remove_if([](T const& value) { return value == condition; });
我的意思是,这种方法效果很好,但是效率不高,因为一旦找到并删除了该项目,它就会继续搜索。有更好的方法还是我需要手动进行?
如果你只是想删除的第一场比赛,你可以使用std::adjacent_find其次成员erase_after
std::adjacent_find
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接受一个二进制谓词,并且通过仅比较第二个参数,我们在要删除的元素之前获得了一个迭代器,因此erase_after实际上可以将其删除。复杂性就是O(N)这样,您将无法获得比它更有效的效果。
adjacent_find
O(N)