使用std::remove_if跟踪已删除元素

Question

我想从一个vector中删除一些元素，并使用remove_if算法来实现。但是我想要跟踪已删除的元素，以便稍后对它们执行某些操作。我尝试使用以下代码：

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;


struct IsEven
{
    bool operator()(int n) 
    {
        if(n % 2 == 0)
        {
            evens.push_back(n);
            return true;
        }

        return false;
    }

    vector<int> evens;
};

int main(int argc, char **argv)
{

    vector<int> v;
    for(int i = 0; i < 10; ++i)
    {
        v.push_back(i);
    }

    IsEven f;
    vector<int>::iterator newEnd = remove_if(v.begin(), v.end(), f);
    for(vector<int>::iterator it = f.evens.begin(); it != f.evens.end(); ++it)
    {
        cout<<*it<<"\n";
    }

    v.erase(newEnd, v.end());

    return 0;
}

但是这并不起作用，因为remove_if接受我的函数对象的副本，所以存储的evens向量是不可访问的。有什么正确的方法来实现这一点吗？

附注：例如偶数和奇数只是举例说明，我的真正代码与此不同。因此，请不要建议以不同方式识别偶数或奇数。

- Asha

---

你可以通过引用传递你的函数对象。使用 boost 或者 c++11（使用 ref 传递）都是可行的解决方案。 - nabulke

你可以使用以下代码 `for(vector<int>::iterator it = newEnd; it != v.end(); ++it) { cout<<*it<<"\n"; }v.erase(newEnd, v.end());` 来获得正确的结果，而不涉及“evens”。 - megabyte1024

@megabyte1024：不行，那样做不行。超出“newEnd”的元素不能保证是已删除的元素。 - Asha

@megabyte1024：不可以（但请看我的回答）。范围[newEnd，end)包含未指定的值；remove_if通常会_复制_匹配的元素；它不会交换它们。 - MSalters

Answer 1

解决方案不是使用remove_if，而是其近亲partial_sortpartition。它们的区别在于remove_if仅保证[begin, middle)包含匹配元素，而partition还保证[middle, end)包含未匹配谓词的元素。

因此，你的示例现在变成了（请注意，evens不再需要）：

vector<int>::iterator newEnd = partition(v.begin(), v.end(), f);
for(vector<int>::iterator it = newEnd; it != v.end(); ++it)
{
    cout<<*it<<"\n";
}
v.erase(newEnd, v.end());

- MSalters

---

partial_sort 会返回什么？这段代码在我的系统上无法编译。 - Asha

额，我是怎么做到的？修复一下...我想可能是因为看花眼了。 - MSalters

谢谢，我不知道这个。我只是反转了我的谓词条件，现在它运行良好。 - Asha

Answer 2

你最好使用std::partition()函数，该函数会重新排列序列中的所有元素，使得谓词返回true的元素都在返回false的元素之前。

例如：

vector<int>::iterator bound = partition (v.begin(), v.end(), IsEven);
std::cout << "Even numbers:" << std::endl;
for (vector<int>::iterator it = v.begin(); it != bound; ++it)
  std::cout << *it << " ";

std::cout << "Odd numbers:" << std::endl;
for (vector<int>::iterator it = bound; it != v.end(); ++it)
  std::cout << *it << " ";

- yves Baumes

Answer 3

如果您像这样通过引用传递，可以避免复制函数对象（即按值传递）：

vector<int>::iterator newEnd = remove_if(v.begin(), v.end(), 
   boost::bind<int>(boost::ref(f), _1));

如果您无法使用boost，则可以使用std::ref实现相同的功能。我测试了上面的代码，它按预期工作。

- nabulke

---

+1，但请注意，boost::ref是std::ref的前身。它最初是在boost中引入的，然后被纳入TR1（因此许多编译器将其作为std::tr1::ref），最终在C++11中标准化。 - Jan Hudec

Answer 4

另一种间接级别。在本地声明向量，并使IsEven包含其副本。如果它是动态分配的并由shared_ptr管理，则IsEven也可能拥有该向量。实际上，我通常发现本地变量加指针解决方案更方便。类似于：

class IsEven
{
    std::vector<int>* myEliminated;
public:
    IsEven( std::vector<int>* eliminated = NULL )
        : myEliminated( eliminated )
    {
    }
    bool
    operator()( int n ) const
    {
        bool results = n % 2 == 0;
        if ( results && myEliminated != NULL ) {
            myEliminated->push_back( n );
        }
        return results;
    }
}

请注意，这也允许operator()()函数是const的。我认为这是正式要求的（尽管我不确定）。

- James Kanze

---

如果它使用引用而不是指针，我会给它+1。当我必须为向量创建一个变量时，我可能会将其保留为普通旧数据并使用初始化程序初始化本地变量。 - Jan Hudec

如果使用引用，则是未定义的行为；函数对象必须是可复制的。而且，将其保留为POD意味着您无法构造临时对象：我的使用模式是声明向量，然后使用“IsEven（&v）”作为“remove_if”的参数。 - James Kanze

哦，我找不到明确的陈述说它必须是可分配的，而不仅仅是可复制构造的，所以我现在有点困惑。参考显然是可复制构造的，但不是可分配的。 - Jan Hudec

@JanHudec 我找不到它必须是C++03的陈述（但也许我没有在正确的地方寻找）。 仍然，由于它们是按值传递的，因此似乎指示了值语义，并且值语义意味着复制和赋值。 （无论如何，如果我要使某个东西公开可复制构造，我也会使其可分配。） - James Kanze

我已经养成了让所有东西都引用的习惯，如果它最终不能工作，例如因为它需要可分配和可复制，我会咒骂并更改它。这是因为指针是邪恶的（使用引用阅读代码时，需要考虑的事情比使用指针少，因此您不必在阅读代码时考虑太多事情）。 - Jan Hudec

@JanHudec 引用的情况下，发生的事情会更少。我同意。特别是，如果你有一个引用，就不能进行赋值操作。我倾向于在函数参数和返回值中以外的地方避免使用引用，在少数需要授予对内部访问权限并且可以确保函数无法找到内部适当部分的情况下才使用引用。即使不会造成问题，我也倾向于在类中避免使用引用。你在 pimpl 惯用语中使用引用吗？ - James Kanze

Answer 5

我看到代码中的问题是，在结构体内创建的evens向量每次调用remove_if算法时都会被创建。因此，无论您是否传递一个函数对象给remove_if，它都会每次创建一个新的向量。因此，一旦删除了最后一个元素，并且当函数调用结束并退出函数时，f.evens将始终获取一个空向量。这可以通过以下两种方式解决：

1. 用类替换结构体，并将evens声明为静态（如果这是您想要的）。
2. 或者你可以让evens成为全局变量。我个人不建议这样做（它会使代码变得糟糕，除非你真的需要它们）。

编辑：

如nabulke所建议的那样，您还可以std::ref一些东西，例如std::ref(f)。这可以防止您使向量成为全局变量，并避免不必要的静态变量。

将其设置为全局变量的示例如下：

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
vector<int> evens;

struct IsEven
{
    bool operator()(int n) 
    {
        if(n % 2 == 0)
        {
            evens.push_back(n);
            return true;
        }

        return false;
    }


};

int main(int argc, char **argv)
{

    vector<int> v;
    for(int i = 0; i < 10; ++i)
    {
        v.push_back(i);
    }

    IsEven f;
    vector<int>::iterator newEnd = remove_if(v.begin(), v.end(), f);
    for(vector<int>::iterator it = evens.begin(); it != evens.end(); ++it)
    {
        cout<<*it<<"\n";
    }

    v.erase(newEnd, v.end());

    return 0;
}

这段代码对我来说似乎完全正常。如果这不是你想要的，请告诉我。

- Ajai

---

使用std::ref传递函数对象会有帮助吗？ - nabulke

@nabulke：嗯，我想是这样。这可能会增加可能的解决方案。 - Ajai

Answer 6

你可能有另一种解决方案；只有在你不需要同时删除元素的情况下（是吗？）。使用 std::for_each()，它返回您的函数对象的副本。例如：

IsEven result = std::for_each(v.begin(), v.end(), IsEven());

// Display the even numbers.
std::copy(result.evens.begin(), result.evens.end(), std::ostream_iterator<int> (cout, "\n"));  

请注意，在可能的情况下，最好在C++中创建未命名变量。这种解决方案并没有完全回答您的主要问题（从源容器中删除元素），但它提醒每个人std::for_each()返回您的函数对象的副本。:-)

- yves Baumes