STL List和Vector是如何实现的？

Question

STL List和Vector如何实现？

我在接受采访时被问到这个问题.

我刚才说可能是通过使用关于向量的二叉树或哈希表.不确定列表...我错了,我想是的......给一些想法谢谢.

Answer 1

哈希表还是二叉树？为什么？

std::vector正如名称本身所暗示的那样,它是用一个正常的动态分配数组实现的,当它的容量耗尽时(通常是它的大小加倍或类似的东西)重新分配.

std::list相反,(通常是¹)用双向链表实现.

你提到的二叉树是通常的实现std::map; 相反,散列表通常用于unordered_map容器(在即将推出的C++ 0x标准中可用).

1. "通常"因为标准不强制要求特定的实现,而是指定其方法的渐近复杂性,并且使用双向链表很容易满足这些约束.另一方面,对于std::vector"连续空间"要求是由标准强制执行的(从C++ 03开始),因此它必须是某种形式的动态分配数组.