找工作 stl源码剖析 顺序容器1(总体)

本文简单地总结了STL的顺序容器的知识点。文中并不涉及具体的实现技巧，对于细节的东西也没有提及。一来不同的标准库有着不同的实现，二来关于具体实现《STL源码剖析》已经展示得全面细致。所以本文仅仅是对容器基础知识的归纳。至于容器提供的接口与使用实例，建议查取官方文档。文章难免有错漏，希望指出。

容器，置物之所也。像桶可装水，碗可盛汤，C++的容器，可以存储对象。容器有多种，用来处理不同的元素操作诉求。按照元素存储到容器中以及访问方式的差异，容器分为顺序容器与关联容器。顺序容器也称为序列式容器。序列式容器按元素插入的顺序存储元素，这些元素可以进行排序，但未必是有序的。C++本身内置了一个序列式容器array（数组），STL另外提供了vector,list,forward_list,deque,stack,queue,priority-queue，string等等序列式容器。所有的容器都是基于模板实现的，因为容器必须保证能装得下各种各样的类型。其中，stack，queue都是基于deque来实现的，priority-queue基于heap来实现，从技术上来说它们属于容器适配器（adapter）。其中array与forward_list是C++11添加的新容器类型。

array的底层数据结构是固定数组。与C-style的数组类似，它的大小在定义后就不能被改变。由于array具有固定的大小，它不支持添加和删除元素或改变容器大小等其他容器拥有的操作。在定义一个array容器的时候必须指定大小：

在内存分配策略上，array也与C-style数组类似。找工作 stl源码剖析编译器在哪里为array分配内存，取决于array定义的位置和方式。找工作 stl源码剖析

若作为函数的局部对象，则将从栈上获得内存，与之对比是的vector，vector底层数据结构是动态数组，从自由存储区上分配内存：

若使用new操作符分配内存，则是在自由存储区上分配内存。

若作为全局变量或局部静态变量，则是在全局/静态存储区上分配的内存。

例如，在函数定义的array局部对象在栈上分配内存，与此对比的是vector，它底层数据结构为动态数组，因此在自由存储区上分配内存：

结果：

array比数组更安全。它提供了opeartor[]与at()成员函数，后者将进行数组越界检查。

与其他容器相似，array也有自己的迭代器，因此array能够更好地与标准算法库结合起来。

通过array::swap函数，可以实现线性时间内的两个数组内容的交换。

另外，不像C-style数组，array容器类型的名称不会自动转换为指针。对于C++程序员来说，array要比C-style数组更好用。

forward_list的底层数据结构为单向链表。如C++标准所讲，forward_list容器支持前向遍历元素序列，允许常数时间内在任意位置的插入或删除操作并进行自动的内存管理。与list的主要区别是forward_list没有反方向的迭代器，不过也正因如此，forward_list的每个节点都节省了迭代器大小的开销，在元素众多的时候，将比list消耗少得多的内存。

受单向链表这种特殊结构的影响，forward_list在很多地方表现得和其他容器不同：

在所有已知的STL容器中，forward_list是唯一一个不提供size()的容器。不提供的原因在于计算一个forward_list的长度需要线性的时间，库用户有时无法忍受这样的时间开销。其他容器提供的size()操作皆可以在常数时间内完成（在C++98时，list也是线性时间）。为了节省内存，forward_list甚至不跟踪序列的长度，要想获得某个forward_list对象的长度，用户需要通过distance()来计算。这带来了一些不便，但使得用户远离了size()带来的高消耗。每个容器类型都有三个与大小相关的操作：max_size(),empty(),size(),而forward_list只提供了前两个。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-61869-1.html