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

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

复制开销
查表很慢
我写的(浸入式)链表比 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(),除非是为了避免迭代器失效(我的代码中很少有这种情况)而不得不使用它。重申:优化前请仔细思量。