C++算法初探 (notes of Thinking in C++ Volume II)

C++的STL为我们提供了一套功能强大而又易用的通用算法，对于有一定C++基础的朋友来说，学习STL的算法是C++进阶的一个很好地途径。下面举一个例子，如果给你一个任务，让你写一个函数，用来拷贝一个数组的内容到另一个数组，给定这个数组的元素都是int类型，你会怎么办？很容易想到写一个copy函数，做一个for循环，循环次数为数组的长度，代码如下

void CopyInt(int* a, int* b, size_t theSize)
{
    for (size_t size = 0; size < theSize; size++)
    {
        *b++ = *a++;
    }
}

再写的好一点的话，把函数写成模板，这样可以做到copy各种类型的数组，而不仅限于整形int，

template<class T>
void Copy(T* a, T* b, size_t theSize)
{
    for (size_t size = 0; size < theSize; size++)
    {
        *b++ = *a++;
    }
}

其实STL已经为我们实现了类似的copy操作，形式略有不同，

template<class InputIterator, class OutputIterator>
  OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
  while (first!=last) {
    *result = *first;
    ++result; ++first;
  }
  return result;
}

输入参数并没有指明要复制的数组的长度，而是给定了一个end的迭代器，指向数组末尾（注意：这里的数组的最后一个元素应该是end的前一个元素）。要使用copy函数，需要包含algorithm文件，即#include 。使用copy的示例代码如下

    int a[] = {10, 20, 30};
    const size_t SIZE = sizeof(a)/sizeof(a[0]);
    int b[SIZE];
    copy(a, a + SIZE, b);

使用STL的算法库时，还需注意一下文档里给出的时间复杂度，比如对于copy来说，复杂度是是

Complexity

Linear in the  between first and last: Performs an assignment operation for each element in the range.

也就是第一个元素到最后一个元素之间呈线性。
算法库中除了copy函数意外，还提供了一些有条件的复制操作，比如remove_copy_if，

template 
  OutputIterator remove_copy_if (InputIterator first, InputIterator last,
                                 OutputIterator result, UnaryPredicate pred);

这个函数实现的功能是把first到last（不好含last本身）中间的除了能满足pred返回true的所有元素复制给result，函数返回指向被复制的数组的最后一个元素的下一个指针。下面给出一个使用remove_copy_if稍微复杂一点的例子，

bool gt15(int x) {return x > 15;}
void copy_ints_from_file()
{
    cout << "-> copy_ints_from_file()" << endl;
    ofstream ints("someInts.dat");
    ints << "3 1 47 5 84 9 15 14 16";
    ints.close();
    ifstream inf("someInts.dat");
    cout << "    ";
    remove_copy_if(istream_iterator<int>(inf),
                   istream_iterator<int>(),
                   ostream_iterator<int>(cout, " "), gt15);
    cout << endl;
}

这段代码首先定义一个函数bool gt15(int)，这个函数当入参x大于15时返回true。然后定义了一个函数void copy_ints_from_file()，函数体中首先定义一个ofstream类型的变量ints，用来读入一串数字到someInts.dat文件中（注意要使用ofstream请记得包含fstream），然后再定义一个ifstream类型的变量inf，用来读取someInts.dat文件中的数字序列，最后使用remove_copy_if函数，将inf中的数字序列中小于15的数字输出到cout上。这里使用了一个技巧，remove_copy_if的第二个参数用的是istream_iterator()，用这样一个默认构造函数，构造了一个特殊值，指向文件的结束。这段代码的输出如下
-> copy_intsfromfile()
    3 1 5 9 15 14