为何标准容器效率如此低下？

不，它们的效率并不低下。或许“和什么比较？”会是一个更有用的回答。当人们抱怨标准库容器的性能时，通常会是以下三个现实问题之一：

• 复制开销
• 查表很慢
• 我写的（浸入式）链表比 std::list 要快得多

    在优化之前，请先考虑是否真有性能问题。在我收到的大多数案例中，性能问题只是理论上的或者只存在于想象中：首先仔细思量，除非必要，就不要优化。

    让我们一个接一个地来分析这些问题。通常，vector<X> 要慢于某些人专门写的 My_container<X>，因为 My_container<X> 的实现是“一个保存指向 X 的指针的容器”。标准容器保存值的拷贝，当你将一个值放入容器时，该值是被复制进去的。对小型的值来说，这是无可挑剔的，但对大型对象来说，这又是非常的不合适的：

                vector<int> vi;
                vector<Image> vim;
                // ...
                int i = 7;
                Image im("portrait.jpg"); // 使用文件来初始化 Image
                // ...
                vi.push_back(i); // 将 i（的一个拷贝）放入 vi
                vim.push_back(im); // 将 im（的一个拷贝）放入 vim

    假若 portrait.jpg 有好几兆那么大，而且 Image 是值语义（value semantics。例如，复制赋值和复制构造会创建新的拷贝），那么 vim.push_back(im) 的开销无疑是非常大的。但——俗话说得好——不要做赔本的买卖。取而代之，你应该使用容器来保存句柄或者指针。例如，如果 Image 是引用语义（reference semantics），那么上面的代码招致的仅仅是调用复制构造函数的开销，而且这个开销和大多数图像处理操作相比是微不足道的。如果某些类，比如 Image，因为一些合适的理由，必须采用复制语义（copy semantics），那么使用容器来保存其指针通常是个合理的解决方案：

                vector<int> vi;
                vector<Image> vim;
                // ...
                Image im("portrait.jpg"); // 使用文件来初始化 Image
                // ...
                vi.push_back(7); // 将 i（的一个拷贝）放入 vi
                vim.push_back(&im); // 将 &im（的一个拷贝）放入 vim

    自然而然，如果你使用指针，就必须考虑资源管理的问题，不过，保存指针的容器本身就可以是一个有效且低开销的资源处理器（通常，你需要这么一种容器：它带有用于删除“属于它的”对象的析构函数）。

    第二个常见的现实问题是使用 map 来处理数量庞大的 (string,X) pair。map 适用于处理相对小型的容器（例如好几百或好几千个元素——访问 10000 个元素的 map 中的一个元素需要大约 9 次比较）。这些相对小型的容器的“小于”比较应该是低开销的，并且不能构建出优秀的哈希函数。如果你要处理大量字符串，而且也有一个优秀的哈希函数，那么 你应该使用哈希表。标准委员会的技术报告（Tecnical Report）中定义的 unordered_map 目前已经广泛可用，而且远远胜于大多数人的“私藏佳酿”。

    有时，你可以使用 (const char*,X) pair 来代替 (string,X) pair，从而提高程序效率。但切记 < 并不能比较 C 风格的字符串。而且，如果 X 很庞大，你还是有可能遇到复制问题（可选用一种常用办法来解决）。

    浸入式链表当然可以很快。然而，首先你应该考虑一下你是否需要使用链表：vector 更加紧凑，因此它比链表更小，而且在很多情况下也比链表更快——甚至于进行插入/删除操作时亦是如此。例如，如果你的 list 只不过拥有为数不多的整型元素，那么使用 vector 无疑会明显快于 list（无论任何链表）。而且，浸入式链表不能直接保存内建类型（int 没有 link 成员变量）。所以，假设你真的需要使用链表，而且你可以为每种元素类型提供 link 成员变量，才可以使用浸入式链表。每当进行插入元素的操作，标准库 list 默认会进行一次内存分配，然后将该元素复制到新分配好的空间里（而每当进行删除元素的操作，list 都会进行一次内存回收）。对于使用默认分配器的 std::list 来说，这样做可能会带来很明显的性能损失。对于复制开销不大的小型元素，可以考虑使用经过优化的分配器。只有当你需要使用链表并且不能错失哪怕是一盎司的 性能提升时，才应该使用自制的浸入式链表。

    人们有时会担心 std::vector 的增长开销。我过去也担心这个，并且使用 reserve() 来优化其增长。在仔细思量代码，并且一次又一次地在实际程序中遇到难以计算 reserve() 所带来的性能提升这个麻烦之后，我停止了使用 reserve()，除非是为了避免迭代器失效（我的代码中很少有这种情况）而不得不使用它。重申：优化前请仔细思量。

原文地址：http://www.research.att.com/~bs/bs_faq2.html#slow-containers