现在删除与谓词匹配的元素? [英] Now to remove elements that match a predicate?

问题描述

我有一个字符串源容器，我想从源容器中删除与谓词匹配的所有字符串，并将它们添加到目标容器中.

I have a source container of strings I want to remove any strings from the source container that match a predicate and add them into the destination container.

remove_copy_if 等算法只能对容器中的元素进行重新排序，因此必须跟上erase 成员函数.我的书 (Josuttis) 说 remove_copy_if 在目标容器中的最后一个位置之后返回一个迭代器.因此，如果我只有一个进入目标容器的迭代器，我如何在源容器上调用 erase ?我曾尝试使用目标的大小来确定要从源容器的末端向后多远进行擦除，但没有运气.我只提出了以下代码，但它进行了两次调用(remove_if 和 remove_copy_if).

remove_copy_if and other algorithms can only reorder the elements in the container, and therefore have to be followed up by the erase member function. My book (Josuttis) says that remove_copy_if returns an iterator after the last position in the destination container. Therefore if I only have an iterator into the destination container, how can I call erase on the source container? I have tried using the size of the destination to determine how far back from the end of the source container to erase from, but had no luck. I have only come up with the following code, but it makes two calls (remove_if and remove_copy_if).

有人可以告诉我正确的方法吗?我确定两个线性调用不是这样做的方法.

Can someone let me know the correct way to do this? I'm sure that two linear calls is not the way to do this.

#include <iostream>
#include <iterator>
#include <vector>
#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()
{
        vector<string> Strings;
        vector<string> Container;

        Strings.push_back("123");
        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");

        remove_copy_if(Strings.begin(), Strings.end(),
                       back_inserter(Container),
                       Pred);

        Strings.erase(remove_if(Strings.begin(), Strings.end(),
                      not1(Pred)), Strings.end());

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

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

        return 0;
}

推荐答案

我明白您的意思，您希望避免对源容器进行两次传递.不幸的是，我认为没有标准算法可以做到这一点.可以创建自己的算法，将元素复制到新容器并从源容器中删除(与 remove_if 的意义相同；之后您必须执行擦除操作).您的容器大小和性能要求将决定创建这样一个算法的努力是否比两次通过更好.

I see your point, that you'd like to avoid doing two passes over your source container. Unfortunately, I don't believe there's a standard algorithm that will do this. It would be possible to create your own algorithm that would copy elements to a new container and remove from the source container (in the same sense as remove_if; you'd have to do an erase afterward) in one pass. Your container size and performance requirements would dictate whether the effort of creating such an algorithm would be better than making two passes.

我想出了一个快速实现:

I came up with a quick implementation:

template<typename F_ITER, typename O_ITER, typename FTOR>
F_ITER move_if(F_ITER begin, F_ITER end, O_ITER dest, FTOR match)
{
  F_ITER result = begin;
  for(; begin != end; ++begin)
  {
    if (match(*begin))
    {
      *dest++ = *begin;
    }
    else
    {
      *result++ = *begin;
    }
  }

  return result;
}

也许通行证"的含义存在混淆.在 OP 的解决方案中，调用 remove_copy_if() 和调用 remove_if().这些中的每一个都将遍历整个原始容器.然后调用erase().这将遍历从原始容器中移除的所有元素.

Maybe there is confusion in what is meant by a "pass". In the OP's solution, there is a call to remove_copy_if() and a call to remove_if(). Each of these will traverse the entirety of the original container. Then there is a call to erase(). This will traverse any elements that were removed from the original container.

如果我的算法用于将删除的元素复制到新容器(使用 begin() 输出迭代器的原始容器将不起作用，正如直接演示的那样)，它将执行一次传递，将删除的元素复制到通过 back_inserter 或某种此类机制的新容器.仍然需要擦除，就像 remove_if() 一样.对原始容器的一次传递被消除了，我相信这就是 OP 所追求的.

If my algorithm is used to copy the removed elements to a new container (using begin() the original container for the output iterator will not work, as dirkgently demonstrated), it will perform one pass, copying the removed elements to the new container by means of a back_inserter or some such mechanism. An erase will still be required, just as with remove_if(). One pass over the original container is eliminated, which I believe is what the OP was after.

这篇关于现在删除与谓词匹配的元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！