我是否错误地使用了copy_if函数？

Question

我正在使用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;
}

但是当我运行这段代码时，出现了“vector iterator not incrementable”错误。

- Merni

Answer 1

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

正如你所看到的，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;
}

- hidayat

---

虽然这个答案得出了正确的结论，但是解释比较混乱。错误与向量是否为空无关。该算法只是期望满足输出迭代器概念的迭代器。此外，在您的最终代码示例中，您使用了一个谓词的lambda表达式，这在当前标准的C++中不受支持（并且OP没有提到C++0x）。 - Björn Pollex

但是copy_if也不是当前标准库的一部分，然而copy_if和lambda表达式都是C++0x最近草案的一部分。 - hidayat

@hidyat：你说得对，不过微软将其作为自定义扩展提供。如果OP没有标记他们的问题为C++0x，你至少应该在你的答案中提到它。 - Björn Pollex

我觉得把C++0x或者Lambda称为“自定义”扩展有点奇怪。它们并没有什么特殊的地方。从明年开始（当新标准发布时），任何不支持它们的编译器都将被视为非标准的。 - Fabio Fracassi

@Fabio：「自定义」可能是一个不好的词。@hidayat：请忘记我的第一条评论，它是错误的（正如@visitor向我解释的那样）。 - Björn Pollex

Answer 2

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

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

代码输出

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

参考文献

[alg.copy]
Qt散点图

- Neil Justice

---

如果在调用copy_if之前调用dest.reserve(source.size())，那么针对std::back_inserter的测试会有何不同？ - OnlineCop

在我的电脑上，使用Visual Studio 2017 - Visual C++ 14.1，dest.reserve(source.size())实际上略微更快... - Teris

Answer 3

你可以使用输出迭代器：

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

- Björn Pollex

---

尽管你的答案得出了正确的结论，但我觉得你的解释有些令人困惑。你不需要在向量中插入新项，只要向量的大小足够，你就可以使用copy_if来覆盖现有的项。 - visitor

Answer 4

预留数组大小。 hidayat 给出了这个原因。

res.resize(arr.size());

- dubnde

---

@space: 从某种意义上来说，重新调整大小是有帮助的。Vector的迭代器作为输出迭代器效果很好（如果it指向一个有效位置，你可以这样做*it = n;）。例如，你可以像这样使用它，使用返回值来删除多余的项：http://ideone.com/QKnry。或者你可以使用count_if来确定结果向量需要多大。是否这些是好的方法是另一个问题。 - visitor

正如@visitor所解释的那样，您的答案确实是正确的。但是，除非您编辑您的答案，否则我无法取消踩。 - Björn Pollex

@Space_C0wb0y，我进行了一项小修改，使您可以点赞。 - dubnde

你还需要在复制正确的元素后修剪掉多余的元素，可以使用 res.erase(copy_if(...),res.end())。我认为，使用 back_inserter 更容易理解。 - Mike Seymour