现在要删除与谓词匹配的元素吗？

Question

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

remove_copy_if等算法只能对容器中的元素进行重新排序，因此后面必须要加上erase成员函数。 我的书（Josuttis）说 remove_copy_if 在目标容器中的最后一个位置之后返回一个迭代器。 因此，如果我只有一个进入目标容器的迭代器，如何在源容器上调用erase？ 我尝试使用目标的大小来确定距离源容器末尾多远的位置以进行擦除，但没有成功。 我只提出了以下代码，但它进行了两次调用（remove_if 和 remove_copy_if）。

有人可以让我知道执行此操作的正确方法吗？ 我确信两个线性调用不是 这样做的方法。

#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;
}

Answer 1

出于对 Fred 辛勤工作的尊重，让我补充一点：在抽象级别上，move_if 与 remove_copy_if 没有什么不同。 唯一的实现级别更改是 end() 迭代器。 您仍然没有得到任何erase()。 接受的答案不会erase()匹配的元素——OP问题陈述的一部分。

至于OP的问题：你想要的是一个in-放置拼接。 对于列表来说这是可能的。 但是，对于向量，这是行不通的。 了解迭代器何时、如何以及为何失效。 您必须采用两遍算法。

remove_copy_if等算法只能对容器内的元素进行重新排序，

来自 SGI 的文档 remove_copy_if：

此操作是稳定的，这意味着复制的元素的相对顺序与 [first, last) 范围内的相同。

因此不会发生相对重新排序。 此外，这是一个副本，这意味着您的情况下来自 Source vector 的元素将被复制到 Container vector 中。

如何在源容器上调用擦除？

您需要使用不同的算法，称为 remove_if：

remove_if 从范围 [first, last) 中删除每个元素 x，使得 pred(x)是真的。 也就是说，remove_if 返回一个迭代器 new_last，使得范围 [first, new_last) 不包含 pred 的元素> 是真的。 [new_last, last) 范围内的迭代器仍然可以取消引用，但它们指向的元素未指定。 Remove_if 是稳定的，意味着未删除的元素的相对顺序不变。

因此，只需将 remove_copy_if 调用更改为：

vector<string>::iterator new_last = remove_if(Strings.begin(), 
                                              Strings.end(), 
                                              Pred);

就可以了。 请记住，您的字符串向量的范围不再是由迭代器[first(), end())定义的，而是由[first ()、new_last)。

如果您愿意，您可以通过以下方式删除剩余的 [new_last, end())：

Strings.erase(new_last, Strings.end());

现在，您的 vector 已被缩短，并且您的 end( ) 和 new_last 是相同的（最后一个元素之后），因此您可以一如既往地使用：

copy(Strings.begin(), Strings.end(), ostream_iterator(cout, "\"));

在控制台上打印字符串（stdout）。

Answer 2

我明白您的观点，您希望避免对源容器进行两次传递。 不幸的是，我不相信有一个标准算法可以做到这一点。 您可以创建自己的算法，一次性将元素复制到新容器并从源容器中删除（与remove_if 含义相同；之后必须进行擦除）。 您的容器大小和性能要求将决定创建此类算法的工作是否会比进行两次传递更好。

编辑：我想出了一个快速实现：

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()。 这将遍历从原始容器中删除的所有元素。

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

Answer 3

将有copy_if和remove_if。

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

最好理解代码，其中Predicate类在存在某些内容时回答“true”。 在这种情况下，您不需要 not1 两次。

因为 std::find 从一开始就查找不是必需的子字符串，因此您需要将“beginning with 1”更改为“with 1”，以避免将来对代码产生误解。

Answer 4

1. remove_* 算法不擦除元素的全部原因是因为单独通过迭代器“擦除”元素是不可能的。 无法通过迭代器获取容器
   这一点在《Effective STL》一书中有更详细的解释

   。remove_

2. 使用'copy_if'，然后是'remove_if'。 remove_copy_if 不会修改源。

3. 在列表上，您可以做得更好 - 重新排序，然后拼接。

Answer 5

如果您不介意将字符串放在同一个容器中，并且只用一个迭代器来分隔它们，则此代码可以工作。

#include "stdafx.h"

#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;

        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");

        vector<string>::iterator end1 = 
        partition(Strings.begin(), Strings.end(), Pred);

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

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

        return 0;
}

Answer 6

remove*() 并不真正删除元素，它只是对它们重新排序并将它们放在集合的末尾，并在同一容器中返回一个 new_end 迭代器，指示新的结尾在哪里。 然后，您需要调用擦除以从向量中删除该范围。

source.erase(source.remove(source.begin(), source.end(), element), source.end());

remove_if() 执行相同的操作，但带有谓词。

source.erase(source.remove_if(source.begin(), source.end(), predicate), source.end());

remove_copy_if() 只会复制与谓词不匹配的元素，保持源向量完整并为您提供目标向量上的结束迭代器，以便您可以缩小它。

// target must be of a size ready to accomodate the copy
target.erase(source.remove_copy_if(source.begin(), source.end(), target.begin(), predicate), target.end());