STL 101 A 部分 - Vector

引言

本系列文章的初衷是介绍标准模板库（STL），这是一个包含相互关联的容器和算法的库，它是 C++ 标准库的一部分。另一个主要部分是 IOStreams，也会不时地涉及。我的目标是表明，这些容器不仅是标准的 C++，而且在许多方面都优于 MFC 的等效类。MFC 的容器类之所以被提供，是因为当时 STL 还不是标准的一部分。然而，出于法律原因，微软在 VC .NET 之前无法升级其 STL 实现，这意味着他们不得不采用一个不够优化的 STL。我建议在 VC++ 6 或更早版本上安装 STLPort 作为替代。但是，如果我使用的代码没有 STLPort 就无法编译，我保证会尽量记住提醒你。

在第一篇文章中，我将介绍 std::vector，这是迄今为止使用最广泛的容器。它大致相当于 CArray，因为它为数组提供了一个封装。这意味着插入操作的开销很大，而查找操作则很便宜。在第二篇文章中，我将介绍 std::list，以及相对效率和不同类型的迭代器。我无意涵盖模板，如果你不知道这个是什么意思：MyClass<int> MyIntClass;，那么我建议你在继续之前阅读 C++ 资源网上其他关于 STL 的入门文章。

在开始讲解实际代码之前，我想指出几点。首先，我包含了 ctime 而不是 time.h。大多数人都知道包含 iostream 而不是已弃用的 iostream.h，但我很少看到人们使用 C 头文件的最新版本，这些版本前面有一个 C，并且去掉了 .h 后缀。使用新的头文件很重要，尤其是因为它们填充的是 std 命名空间而不是全局命名空间。这引出了我的第二点。我不会使用 `using namespace std;`，我只使用我需要的函数。这是因为如果我写“using namespace std;”，我就会用 std 命名空间中的所有内容污染全局命名空间，这就违背了命名空间的目的。我将在这里发布整个代码，而不是提供一个 zip 文件。要使用它，你只需要创建一个控制台应用程序（“hello world”就可以了），然后将 main.cpp 文件中的所有代码替换为以下内容：

#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <vector>
#include <algorithm>
#include <functional>

using std::cout;
using std::vector;
using std::endl;
using std::sort;
using std::partition;
using std::less;
using std::bind2nd;
using std::ostream_iterator;
using std::copy;
using std::back_inserter;


int main(int argc, char* argv[])
{
    // Seed random number generator

    srand(time(NULL));

    vector <int> vecInt;

    // declaring it here once will compile under dodgy VC, and also 
    // standards conforming compilers, VC included if you set a flag.
    int i;

    cout << "Inserting values into vector\n\n";

    for (i = 0; i <= 20; ++i)
    {
        vecInt.push_back(rand() % 200);
        cout << vecInt.at(i) << ", ";
    }

    cout << "\n\nIterating through vector and doubling values" << endl;

    std::vector<int>::iterator it;

    for (it = vecInt.begin(); it != vecInt.end(); ++it)
    {
        *it *= 2;
        cout << *it << ", ";
    }

    cout << "\n\nPartitioning values under 200\n";

    std::vector<int>::iterator itBelow200 = partition(vecInt.begin(),
                                                            vecInt.end(), 
                                                            bind2nd(less<int>(), 200));

    copy (vecInt.begin(), vecInt.end(), ostream_iterator<int>(cout, ", "));

    cout << "\n\nCopying values below 200 to new vector\n";

    vector<int> vecInt2;

    copy(vecInt.begin(), itBelow200, back_inserter(vecInt2));

    copy (vecInt2.begin(), vecInt2.end(), ostream_iterator<int>(cout, ", "));

    cout << "\n\nSorting the first vector and output the result\n";

    sort(vecInt.begin(), vecInt.end());

    copy (vecInt.begin(), vecInt.end(), ostream_iterator<int>(cout, ", "));

    cout << endl;

    return 0;
}

总之，你会注意到的第一件事是，vector 是一个模板类，任何通用容器都必须是。添加元素的语法是 vector::push_back(element)。要删除一个元素，我们可以使用 vector::pop_back，它会返回被删除的元素。你会注意到我们使用成员函数 at() 来引用每个元素并将其发送到 cout。实际上，有一个临时变量来存储 int 并打印它会更有效率，但这只是一个演示示例，而不是为了优化。你也可以使用 [ ] 运算符来访问元素，但 at() 是经过边界检查的。实际上，如果边界检查失败，会触发 ASSERT，所以最终结果可能差别不大。

接下来需要注意的是，我们为 vector 类型创建了一个迭代器。迭代器有点像 CList 中的 POSITION，但迭代器可以与所有 STL 容器一起使用，实际上，这是遍历容器过程通用化的方式，允许算法（几乎）适用于所有容器。第二部分将解释“几乎”这个词的含义……我们可以使用 begin() 函数获取一个指向容器开始的迭代器，使用 end() 函数获取一个指向容器末尾之后一个位置的迭代器。为什么是一个位置之后呢？这样我们就可以创建一个循环来遍历容器，这与零索引的概念一致。这不是使 vector 中的值翻倍的最佳方法，我这样做只是为了向你展示一种遍历容器的方法。正如你所见，解引用迭代器可以得到对底层值的引用（因此如果我们改变它，vector 中的值也会改变）。如果你的容器中存储的是指针，这可能会导致问题，我稍后会深入讨论这个问题。

使用标准容器的意义不仅仅在于容器本身，更在于它们附带了一个丰富的函数库，可以用于它们。这些函数声明在 <algorithm> 和 <numeric> 中。我们将使用 partition 算法，因为它给了我一个机会来展示另外几个东西。partition 算法允许你设置一个规则，所有符合该规则的元素都会被移动到容器的左半部分（但不排序）。stable_partition 也能做到这一点，但它还会保证每一半元素的顺序不变。由于我们将 vector 填充了小于 200 的整数，然后将它们全部翻倍，我将进行分区，使小于 200 的数字（希望大约占一半）都移到前面。这个函数返回一个迭代器，它表示已分区最后一个元素的位置。

关于这一点需要快速说明一下——因为 vector 是一个数组，某些操作（例如插入）可能导致整个 vector 在内存中的其他位置被重新构建。这意味着你应该留意这种情况，并意识到当它们发生时，你存储的任何迭代器都可能变得无效。此外，如果 partition 操作发现所有元素都匹配，它将返回 end() 迭代器。解引用这个迭代器是一个无效操作，所以这种情况应该首先进行检查。

partition 的语法接受两个迭代器来定义一个操作范围，几乎所有的 STL 算法都是如此。最后一个参数一开始有点令人困惑。less <int> 是一个模板化的二元函数，这意味着它接受两个参数，在这种情况下，它表示当第一个参数小于第二个参数时返回 true。它定义在 <functional> 中，bind2nd 也是如此。bind2nd 通过将函数作为第一个参数，将一个值作为第二个参数，将一个二元函数转换为一个一元函数（接受一个参数）。这意味着我们将遍历 vector，并对每个值调用 less<int> 来检查该值是否小于 200。

下一行也非常酷。我们使用 copy 算法来复制整个 vector，但是我们将它复制到 cout。这个魔法是通过 ostream_iterator 实现的，顾名思义，它是一个满足算法要求的迭代器，但它会将写入它的内容通过管道传输到 ostream，在本例中是 cout。第二个参数是一个分隔符，它会输出在每个传入项之间。最终结果是，这一行代码将我们的整个 vector 打印到控制台，并且可以同样轻松地将其输出到文件，或者我们自己编写的任何其他 ostream。

接下来我们创建一个新的 vector，并使用 partition 的返回值来填充它，只包含小于 200 的值，然后也输出它们。最后，我们对第一个 vector 进行完全排序并输出。

本文的目的是介绍 vector、迭代器、一些常用算法以及一些常用函数对象和适配器。如果其中一些部分你不太理解，不用担心，在未来的文章中它们都会被更全面地介绍。