从STL列表中删除项目

Erase returns an iterator 指向删除后的元素:

std::list<MyClass>::iterator it = myList.begin();
while (it != myList.end())
{
  if(myCondition(*it))
  {
    myOtherList.push_back(*it);
    it = myList.erase(it);
  }
  else
  {
    ++it;
  }
}

STL列表有一个有趣的特性: splice() 方法允许您破坏性地将元素从一个列表移动到另一个列表。

拼接() 在恒定时间内运行,不会复制元素或执行任何免费存储分配/释放。请注意,两个列表的类型必须相同,并且它们必须是单独的列表实例(不是对同一列表的两个引用)。

下面是一个示例,说明如何使用 拼接() :

for(std::list<MyClass>::iterator it = myList.begin(); it != myList.end(); ) {
    if(myCondition(*it)) {
        std::list<MyClass>::iterator oldIt = it++;
        myOtherList.splice(myOtherList.end(), myList, oldIt);
    } else {
        ++it;
    }
}

解决方案1

template<typename Fwd, typename Out, typename Operation>
Fwd move_if(Fwd first, Fwd last, Out result, Operation op)
{
    Fwd swap_pos = first;
    for( ; first != last; ++first ) {
        if( !op(*first) ) *swap_pos++ = *first;
        else *result++ = *first;
    }
    return swap_pos;
}

这个想法很简单。你想做的是 去除 一个容器中的元素,如果谓词为真,则将它们放在另一个容器中。所以,取 std::remove() 算法,它已经完成了删除部分,并使其适应您的额外需求。在上面的代码中,我添加了 else 行在谓词为true时复制元素。

注意,因为我们使用 STD:: 代码,该算法实际上不会收缩输入容器。不过,它确实返回了输入容器的更新后的结束迭代器,所以您可以使用它并忽略额外的元素。使用 erase-remove idiom 如果您真的想收缩输入容器。

解决方案2

template<typename Bidi, typename Out, typename Operation>
Bidi move_if(Bidi first, Bidi last, Out result, Operation op)
{
    Bidi new_end = partition(first, last, not1(op));
    copy(new_end, last, result);
    return new_end;
}

第二种方法使用STL来实现算法。我个人认为它比第一个解决方案更具可读性,但它有两个缺点:第一,它要求输入容器使用更强大的双向迭代器,而不是我们在第一个解决方案中使用的前向迭代器。第二,这对您来说可能是一个问题,也可能不是一个问题,这些容器不能保证在调用之前具有相同的顺序。 std::partition() . 如果您希望保持顺序,请用调用替换该调用 std::stable_partition() . std::稳定分区() 可能稍微慢一点,但它的运行时复杂性与 标准::分区() .

任何一种方法:调用函数

list<int>::iterator p = move_if(l1.begin(), l1.end(),
                                back_inserter(l2),
                                bind2nd(less<int>(), 3));

最后备注

在编写代码时,我遇到了一个难题:应该 move_if() 算法返回?一方面,算法应该返回一个指向输入容器新的结束位置的迭代器,这样调用方就可以使用erase-remove习惯用法来收缩容器。但另一方面,该算法应该返回结果容器末尾的位置,否则调用方查找结果容器的成本可能很高。在第一个解决方案中, result 迭代器在算法结束时指向此位置,而在第二个解决方案中,它是由返回的迭代器 std::copy() 就是这个位置。我可以返回一对迭代器,但为了使事情简单化,我只返回其中一个迭代器。

std::list<MyClass>::iterator endMatching =
    partition(myList.begin(), myList.end(), myCondition);
myOtherList.splice(myOtherList.begin(), myList, endMatching, myList.end());

注意,partition()为您提供了足够的区分匹配对象和不匹配对象的能力。 (然而,list::splice()很便宜)

请参阅以下代码,了解从 Now to remove elements that match a predicate?

#include <iostream>
#include <iterator>
#include <list>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;

class CPred : public unary_function<string, bool>
{
public:
        CPred(const string& arString)
                :mString(arString)
        {
        }

        bool operator()(const string& arString) const
        {
                return (arString.find(mString) == std::string::npos);
        }
private:
        string mString;
};

int main()
{
        list<string> Strings;

        Strings.push_back("213");
        Strings.push_back("145");
        Strings.push_back("ABC");
        Strings.push_back("167");
        Strings.push_back("DEF");

        cout << "Original list" << endl;
        copy(Strings.begin(), Strings.end(),ostream_iterator<string>(cout,"\n"));

        CPred Pred("1");

        // Linear. Exactly last - first applications of pred, and at most (last - first)/2 swaps. 
        list<string>::iterator end1 =
        partition(Strings.begin(), Strings.end(), Pred);

        list<string> NotMatching;

        // This function is constant time. 
        NotMatching.splice(NotMatching.begin(),Strings, Strings.begin(), end1); 

        cout << "Elements matching with 1" << endl;
        copy(Strings.begin(), Strings.end(), ostream_iterator<string>(cout,"\n"));

        cout << "Elements not matching with 1" << endl;
        copy(NotMatching.begin(), NotMatching.end(), ostream_iterator<string>(cout,"\n"));

        return 0;
}

另一次尝试:

for(std::list<MyClass>::iterator it = myList.begin(); it != myList.end; ) {
    std::list<MyClass>::iterator eraseiter = it;
    ++it;
    if(myCondition(*eraseiter)) {
        myOtherList.push_back(*eraseiter);
        myList.erase(eraseiter);
    }
}

template <typename ForwardIterator, typename OutputIterator, typename Predicate>
void splice_if(ForwardIterator begin, ForwardIterator end, OutputIterator out, Predicate pred)
{
    ForwardIterator it = begin;
    while( it != end )
    {
        if( pred(*it) )
        {
            *begin++ = *out++ = *it;
        }
        ++it;
    }
    return begin;
}

myList.erase( 
    splice_if( myList.begin(), myList.end(), back_inserter(myOutputList),
        myCondition
    ),
    myList.end()
)