C++ 我使用 copy_if 错了吗？

Am I using the copy_if wrong?

提问by Merni

I am using visual studio 2010 and I am trying to use std::copy_if, I want to copy all values that are satisfying a predicate. For example:

我正在使用 Visual Studio 2010 并且我正在尝试使用 std::copy_if，我想复制满足谓词的所有值。例如：

struct comp
{
    bool operator()(const int i) { return i == 5 || i == 7; }
};

int main()
{
    array<int, 10> arr =  { 3, 2, 5, 7, 3, 5, 6, 7 };
    vector<int> res;
    copy_if(arr.begin(), arr.end(), res.begin(), comp());

    for(int i = 0; i < res.size(); i++)
    {
        cout << res[i] << endl;
    }

    return 0;
}

But when I run this code I get: vector iterator not incrementable.

但是当我运行这段代码时，我得到：向量迭代器不可增加。

回答by hidayat

The copy_if algorithm looks something like this(taken from MSVC2010):

copy_if 算法看起来像这样（取自 MSVC2010）：

template<class InIt, class OutIt, class Pr> inline
OutIt copy_if(InIt First, InIt Last, OutIt Dest, Pr Pred)
{
    for (; First != _Last; ++First)
        if (Pred(*_First))
            *Dest++ = *First;
    return (Dest);
}

And as you can see the copy_if does not do a push_back, it just copy the value on the position where the iterator is, and then increments the iterator. What you want do use instead is the std::back_inserter, which pushes the element back of your vector. And if you are using MSVC2010 you can use Lambda instead of a function object, which Microsoft offers as an extension(C++0x)

正如你所看到的，copy_if 没有执行 push_back，它只是复制迭代器所在位置的值，然后递增迭代器。您想要使用的是std::back_inserter，它将元素推回向量。如果您使用的是 MSVC2010，您可以使用 Lambda 而不是函数对象，这是微软作为扩展提供的（C++0x）

int main()
{
    array<int, 10> arr =  { 3, 2, 5, 7, 3, 5, 6, 7 };
    vector<int> res;
    copy_if(arr.begin(), arr.end(), back_inserter(res),[](const int i) { return i == 5 || i == 7; });

    for(unsigned i = 0; i < res.size(); i++)
        cout << res[i] << endl;

    return 0;
}

回答by Bj?rn Pollex

You can use an output iterator:

您可以使用输出迭代器：

copy_if(arr.begin(), arr.end(), std::back_inserter(res), comp());

回答by Neil Justice

Should perf be a concern, consider instead of using std::back_inserter to populate the destination vector (an approach that involves an arbitrary number of costly destination vector reallocations), call std::copy_if with a source-sized destination vector followed by dest.erase(iteratorReturnedByCopyIf, dest.end()) - an approach that involves one allocation up front then one reallocation for the erase().

如果性能是一个问题，请考虑不使用 std::back_inserter 来填充目标向量（一种涉及任意数量的昂贵目标向量重新分配的方法），而是使用源大小的目标向量后跟 dest 调用 std::copy_if。 erase(iteratorReturnedByCopyIf, dest.end()) - 一种涉及预先分配然后为擦除（）重新分配的方法。

Data

数据

Code

代码

#include <algorithm>
#include <chrono>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

long long MeasureMilliseconds(std::function<void()> func, unsigned iterations)
{
   auto beginTime = std::chrono::high_resolution_clock::now();
   for (unsigned i = 0; i < iterations; ++i)
   {
      func();
   }
   auto endTime = std::chrono::high_resolution_clock::now();
   long long milliseconds = std::chrono::duration_cast<
      std::chrono::milliseconds>(endTime - beginTime).count();
   return milliseconds;
}

bool IsEven(int i)
{
   return i % 2 == 0;
}

int main()
{
   const unsigned Iterations = 300000;
   for (size_t N = 0; N <= 100; N += 2)
   {
      std::vector<int> source(N);
      // Populate source with 1,2,...,N
      std::iota(std::begin(source), std::end(source), 1);

      long long backInserterMilliseconds = MeasureMilliseconds([&]
      {
         std::vector<int> dest;
         std::copy_if(std::begin(source), std::end(source), 
            std::back_inserter(dest), IsEven);
      }, Iterations);

      long long sourceSizeAndEraseMilliseconds = MeasureMilliseconds([&]
      {
         std::vector<int> dest(source.size());
         std::vector<int>::iterator copyIfIterator = std::copy_if(
            std::begin(source), std::end(source), std::begin(dest), IsEven);
         dest.erase(copyIfIterator, dest.end());
      }, Iterations);

      std::cout << "N=" << N << '\n';
      std::cout << "Default-size dest and back_inserter: " << 
         backInserterMilliseconds << '\n';
      std::cout << "      Source-sized dest and erase(): " << 
         sourceSizeAndEraseMilliseconds << "\n\n";
   }
   return 0;
}

Code Output

代码输出

N=90
Default-size dest and back_inserter: 469
      Source-sized dest and erase(): 89

N=92
Default-size dest and back_inserter: 472
      Source-sized dest and erase(): 90

N=94
Default-size dest and back_inserter: 469
      Source-sized dest and erase(): 92

N=96
Default-size dest and back_inserter: 478
      Source-sized dest and erase(): 92

N=98
Default-size dest and back_inserter: 471
      Source-sized dest and erase(): 93

N=100
Default-size dest and back_inserter: 480
      Source-sized dest and erase(): 92

References

参考

[alg.copy]
Qt ScatterChart

[alg.copy]
Qt ScatterChart

回答by dubnde

Reserve the array size. hidayatgives the reason for this.

保留数组大小。hidayat给出了原因。

res.resize(arr.size());