如何有效地从一个forward_list的remove_if仅一个元件的? [英] How do I efficiently remove_if only a single element from a forward_list?

查看:170
本文介绍了如何有效地从一个forward_list的remove_if仅一个元件的?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

嗯,我认为这个问题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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆