STL101 B 部分 - List 和 Iterators

引言

这篇文章的第二个想法是介绍另一种容器，即 std::list，讨论两者的区别，并由此讨论不同类型的迭代器以及它们存在的原因。

与第一篇文章一样，您可以通过将下面的代码复制并粘贴到控制台应用程序中来运行它。我将在解释代码时逐步讲解，但这允许您在不下载 zip 文件的情况下创建项目。

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

using std::cout;
using std::vector;
using std::endl;
using std::sort;
using std::ostream_iterator;
using std::copy;
using std::back_inserter;
using std::list;
using std::random_shuffle;
using std::back_inserter;

int main(int argc, char* argv[])
{
    list<int> intList;

    int i;
    for (i=0; i < 30; ++i, intList.push_back(i));

    cout << "Print list pushed from back\n\n";

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

    intList.clear();

    for (i=0; i < 30; ++i, intList.push_front(i));

    cout << "\n\nPrint list pushed from front\n\n";

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

    std::list<int>::reverse_iterator rit = intList.rbegin();
    std::list<int>::reverse_iterator rend = intList.rend();

    cout << "\n\nPrint list in reverse order using reverse iterators\n\n";

    for(;rit != rend;++rit)
        cout << *rit << ", ";

    // Oops
//    random_shuffle(intList.begin(), intList.end());

    vector<int> vecInt;

    copy (intList.begin(), intList.end(), back_inserter(vecInt));

    cout << "\n\nPrint vector in reverse order\n\n";

    copy(vecInt.rbegin(), vecInt.rend(), ostream_iterator<int>(cout, ", "));

    random_shuffle(vecInt.rbegin(), vecInt.rend());

    cout << "\n\nPrint shuffled vector\n\n";

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

    cout << endl;

    return 0;
}

如前所述，STL 描述容器时使用的是性能，而不是实现。然而，性能规范在很大程度上定义了 vector 容器的类型，因为唯一提供即时查找的容器是数组。数组的问题在于，不在末尾的插入操作总是需要重新创建整个数组到新的内存中（即使是末尾的插入也可能如此），并且这会使内存中的任何迭代器失效。另一方面，列表的查找速度最慢——查找链表中的项的唯一方法是从一端开始，一直查找直到找到您想要的内容。但是，添加项和插入项的成本很低。

    list<int> intList;

    int i;
    for (i=0; i < 30; ++i, intList.push_back(i));

    cout << "Print list pushed from back\n\n";

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

    intList.clear();

    for (i=0; i < 30; ++i, intList.push_front(i));

    cout << "\n\nPrint list pushed from front\n\n";

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

这段代码创建了一个 int 列表，并展示了我们可以使用 push_front 和 push_back 在列表的开头或结尾添加项。这与 vector 不同，vector 需要使用 insert 函数来添加到开头，因为与 insert 类似，在 vector 中添加到开头总是成本高昂。 push_back 可能成本不高，如果空间已经预分配，无论是用户预分配还是通过 vector 的增长策略。

    std::list<int>::reverse_iterator rit = intList.rbegin();
    std::list<int>::reverse_iterator rend = intList.rend();

    cout << "\n\nPrint list in reverse order using reverse iterators\n\n";

    for(;rit != rend;++rit)
        cout << *rit << ", ";

我希望通过这些文章来引发一些关于 STL 的讨论并学习一些东西。从上一篇文章中我学到了一件事（虽然我一直都知道），那就是我可以在调用循环之前获取我要在循环中使用的两个迭代器。我不知道为什么以前从未想到过对 STL 做同样的事情，我当然每次都会这样做。这有什么大不了的？嗯，我在每次迭代中节省了一个函数调用。

我以这种方式做是为了向您展示反向迭代器。反向迭代器仍然使用 ++ 进行步进，但它们是从后向前步进。

    // Oops
//    random_shuffle(intList.begin(), intList.end());

random_shuffle，顾名思义，会将容器中的项随机排序。取消注释它并尝试编译，您会发现它无法正常工作。那是因为该算法需要随机访问迭代器。我选择展示这个算法是为了突出不同的迭代器类型，所以现在我已经设置了这样一个人为的例子，让我们来看看……

据我所知，有五种迭代器类型。第一种是前向迭代器。顾名思义，它只能向前遍历容器。第二种是双向迭代器。这就是列表所拥有的，顾名思义，一个人可以从一个项移动到下一个项或前一个项。最后，我们有随机访问迭代器，如 vector 中发现的那样。它们允许通过使用数组元素语法指定位置来查找任何项。此外，我们还有输入迭代器和输出迭代器。我们已经使用了输出迭代器，将我们的容器输出到流。顾名思义，一个只用于输入，另一个只用于输出。这两种迭代器类型都是前向迭代器。

因此， random_shuffle 对列表不起作用的原因是它需要随机访问迭代器。每个算法都需要允许算法实现最高效率的迭代器类型。有些算法，例如 sort，在 list 中被成员函数所取代，该成员函数是一种排序算法，它利用了 list 的特定布局，以便为该容器提供优化解决方案。如果您的容器提供了成员函数，请务必使用它而不是通用解决方案。

    vector<int> vecInt;

    copy (intList.begin(), intList.end(), back_inserter(vecInt));

    cout << "\n\nPrint vector in reverse order\n\n";

    copy(vecInt.rbegin(), vecInt.rend(), ostream_iterator<int>(cout, ", "));

    random_shuffle(vecInt.rbegin(), vecInt.rend());

    cout << "\n\nPrint shuffled vector\n\n";

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

STL 通过迭代器提供的另一个神奇之处在于，容器可以在函数中混合使用。在这里，我们将列表复制到 vector 中。copy 算法是破坏性的——它假定存在空间来插入要复制的项，并覆盖已存在的项。 back_inserter 适配器通过在容器末尾插入要复制的每个元素来解决此问题，从而在复制过程中创建空间。

为了练习的目的，我们在 vector 上调用 random_shuffle，果然，它起作用了，我们的项现在是随机顺序的。

STL 提供了多种容器类型，并根据效率对其进行定义，以便我们可以根据应用程序的性质做出选择。许多算法可以与 list 一起使用，该框架的重点在于通过迭代器机制实现的抽象，使我们能够将容器相互复制，并编写一次可以与多种容器类型使用的算法。可以为任何包含数据的结构编写迭代器，然后算法就可以立即用于该结构。当然，泛化绝不应该以牺牲效率为代价，因此提供了不同的迭代器类型，并且存在一些不兼容性，但如果没有这些，该框架将无法以警告我们尝试走会带来显着性能成本的路径的方式进行配置。