《STL源码剖析》之三：序列式容器

程序员文章站 2024-02-11 21:20:34

...

谈到编程，大家首推的可能就是数据结构与算法，几乎任何特定的数据结构都是为了实现某种特定的算法。在STL中将运用最广的一些数据结构实现出来，比如：array（数组），list（链表），tree（树），stack（栈），queue（队列），hash table（散列表），set（集合），map（映射表）等等。

根据数据结构在容器中的排列特性，这些数据结构被分为序列式和关联式两种。

序列式容器

所谓序列式容器，其中的元素都可序，但未必有序。在c++本身提供了一个序列式容器array，STL另外再提供vector，list，deque，stack，queue，priority-queue等等序列式容器。

1，vector

vector与array非常相似，差别在于空间运用的灵活性。array是静态空间，一旦配置了就不能改变；vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新的元素。

1.1 vector的迭代器

vector维护的是一个连续线性空间，所以不论其元素型别为何，普通指针都可以作为vector的迭代器，进行一些迭代器所需要的操作，如：operator*，operator->，operator++，operator+，operator–，operator-，operator+=，operator-=，vector支持随机存取。

1.2 vector的数据结构

vector所采用的的数据结构非常简单：线性连续空间。

template < class T, class Alloc = alloc >
class vector{
...
protected:
iterator start;           //表示目前使用空间的头
iterator finish;          //表示目前使用空间的尾
iterator end_of_storage;  //表示目前可用空间的尾

运用start，finish，end_of_storage三个迭代器，便可以很容易地得到容器的首位标识，大小，容量，空容器判断，注标运算子，最前端元素值，最后端元素值…等
对应得到的函数为：

template < class T, class Alloc = alloc >
class vector{
...
public：
iterator begin(){ return start; }
iterator end(){ return finish; }
size_type size() const { return size_type(end() - begin()); }
size_type capacity() const { return size_type(end_of_storage() - begin()); }
bool empty() const { return end() == begin(); }
reference operator() (size_type n){ return *(begin() + n); }
reference front() { return *begin(); }
reference back() { return *(end()-1); }
...

vector示意图如下所示：
《STL源码剖析》之三：序列式容器

1.3 vector的构造与内存管理：constructor,push_back

push_back():当我们以push_back（）将新元素插于vector尾端时，该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器finish，使vector变大。如果没有备用空间了，就扩充空间（重新配置，移动数据，释放原空间）
《STL源码剖析》之三：序列式容器