如何仅从forward_list中删除单个元素，如何有效地将其删除？

Question

好吧，我认为这个问题几乎可以总结出来。我有一个独特商品的forward_list，想从中删除一个商品：

std::forward_list<T> mylist;
// fill with stuff

mylist.remove_if([](T const& value)
  {
    return value == condition;
  });

我的意思是，这种方法效果很好，但是效率不高，因为一旦找到并删除了该项目，它就会继续搜索。有更好的方法还是我需要手动进行？

Answer 1

如果你只是想删除的第一场比赛，你可以使用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)这样，您将无法获得比它更有效的效果。