STL源码剖析——序列式容器

序列式容器

• 所谓序列化容器，其中的元素都可序，但未必有序。C++语言本省提供了一个序列式容器array，STL另外提供了vector，list，deque，stack，queue，priority_queue等序列式容器。其中stack和queue由于只是将deque作为底层实现，技术上被归类为一种配接器。

• 文章只是将一些细节知识点总结，底层源码不涉及。

vector

• vector的数据结构

  • 数组。

• vector和array的区别

  • array是静态空间，一旦配置了就不能改变；要存入大于空间个数的元素，需要客户端自己实现。
  • vector是动态空间，随着元素的加入，它的内部机制会自行扩充以容纳新元素。
  • 两者均为线性连续空间。

#include<iostream>
#include<vector>

int main(int argc, char* argv[]) {
    //*************array************
    int a[5] = { 0,1,2,3,4 };
    //换大空间
    int b[10] = { 0 };
    for (int i = 0; i < 5;++i) {
        b[i] = a[i];
    }
    b[5] = 10;
    //***************vector****************
    vector<int> vec{1,2,3};
    cout << vec.size() << endl; //3,size表示元素个数
    cout << vec.capacity() << endl; //3，capacity表示占用的空间，capacity>=size
    vec.push_back(4);
    vec.push_back(5);
    cout << vec.size() << endl; //5
    cout << vec.capacity() << endl;  //6，空间自行扩充
    getchar();
    return 0;
}

• vector空间满载情况

  • 为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容器的概念。也就是说，一个vector的容量永远大于等于其大小，一旦等于，便需扩充。
  • vector空间满载，将会进行“配置新空间/数据移动/释还旧空间”，时间成本很高。因此，vector在配置新空间时，一般以旧空间的两倍来扩充。注意，这里扩充指的是容量capacity，size表示加入元素的个数。
  • 空间配置原则：如果原大小为0，则配置capacity=1$capacity=1$；如果原大小不为0，则配置原大小的两倍(capacity新=2∗capacity旧$capacit{y}_{新}=2\ast capacit{y}_{旧}$)。
    

• vector的迭代器

  • vector维护的是一个连续线性空间，普通指针即可满足需求，提供随机存取迭代器。
  • 因vector满载需进行“配置新空间/数据移动/释还旧空间”操作，因而vector的迭代器会失效。
    

• vector空间释放

  • clear()函数：清除所有元素，但容量不改变。即size=0,capacity!=0$size=0,capacity!=0$。
    
  • 下面演示程序可知：当push_back和pop_back时size的大小（元素个数）改变，而capacity的大小只有在分配新空间时改变，且capacity新=2∗capacity旧$capacit{y}_{新}=2\ast capacit{y}_{旧}$，只增不减。（vector容量只增不减。）
  • 因vector容量只增不减，所以对于释放vector占有的内存有必要了解一下。
    
    • 方法一：与临时变量swap。
    • 方法二：clear()+shink_to_fit()。先清除所有的元素，再将容量大小调整为元素大小即可。

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char* argv[]) {
    vector<int> vec{1,2,3,4};
    cout << vec.size() << endl; //4,size表示元素个数
    cout << vec.capacity() << endl; //4，capacity表示占用的空间，capacity>=size
    vec.push_back(5);
    cout << vec.size() << endl; //5,size表示元素个数
    cout << vec.capacity() << endl; //8，空间自行扩充
    vec.push_back(6);
    vec.push_back(7);
    cout << vec.size() << endl; //7
    cout << vec.capacity() << endl;  //8
    vec.push_back(8);
    vec.push_back(9);
    cout << vec.size() << endl; //9
    cout << vec.capacity() << endl;  //16，空间自行扩充
    //************************方法一************************
    /*
    vector<int>().swap(vec);
    cout << vec.size() << endl; //0
    cout << vec.capacity() << endl;  //0
    */
    //************************方法二************************
    vec.clear();
    vec.shrink_to_fit();
    cout << vec.size() << endl; //0
    cout << vec.capacity() << endl;  //0
    getchar();
    return 0;
}

• vector优缺点

  • 优点：随机存取。时间复杂度O(1)。
  • 缺点：插入和删除的时间复杂度O(N)。需要对元素进行移动。

list

• list的数据结构

  • list是一个环状双向链表。所以它只需要一个指针，就可以完整的表现整个链表。
  • 只要刻意在环状链表的尾端加上一个空白节点，便可满足“前闭后开”区间。
    

• list的空间分配

  • list不像vector是连续存储空间，需要预留空间来节省“配置新空间/数据移动/释还旧空间”操作的成本。因而容量大小等于元素个数。
  • 每次配置一个节点大小，当元素删除时，相应空间一并删除。

• list的迭代器

  • list不能像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。
  • list是一个环状双向链表，迭代器必须具备前移、后移的能力，所以list提供的是双向迭代器。
  • 插入操作和接合操作都不会造成原有的list迭代器失效，只有在删除元素时，“指向被删除元素”的那个迭代器失效，其他迭代器不受影响。

• 注意

  • 插入操作：分配一个节点，“插入在…之前”。
    
  • 移除操作：删除元素，并释放空间。
    
  • 迁移操作
    
    • 将某连续范围的元素迁移到特定位置之前。只进行节点间的指针移动即可。
    • list中的splice(接合操作)、merge(合并操作)、reverse(反转操作)、sort(排序操作)均是以迁移操作为基础。
    • 图解
      

• list优缺点

  • 优点：无预留空间。插入和删除在常数时间内完成。
  • 缺点：不能进行随机存取。时间复杂度为O(N)。

deque

• vector和deque的区别

  • vector是单向开口的连续线性空间，deque是双向开口的连续线性空间。
  • deque允许常数时间内对起头端进行元素的插入或移除操作。vector需要将起头端之后的元素进行整体的前移或后移操作，时间复杂度为O(N)，效率极差。
  • deque没有所谓的容量概念，它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来（随后会介绍）。

• deque的中控器

  • deque采用一块所谓的map（不是map容器）作为主控。这里所谓的map是一小块连续空间，其中每个元素都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。
  • deque的连续空间其实是假象，是由一段一段的定量连续空间构成。
    

• deque的迭代器

  • deque的迭代器包含四个指针

    • cur：指向缓冲区中的现行元素
    • first：指向缓冲区的头
    • last：指向缓冲区的尾
    • node：指向管控中心

  • 当map所指的缓冲区容量满载时，需要对map进行扩充，扩充过程：配置更大的，拷贝原来的，释放原来的。因此deque的迭代器会失效。

  • deque的中控器、缓冲区、迭代器的相互关系
    

• deque在尾端添加元素，引发新缓冲区的配置（条件：map中控器未满载，不需要考虑map）。
  

• deque在最前端添加元素，引发新缓冲区的配置（条件：map中控器未满载，不需要考虑map）。
  

• map满载时，扩充map（配置更大的，拷贝原来的，释放原来的）。

• deque优缺点

  • 可随机存取。时间复杂度为O(1)。可在头部和尾部进行插入操作，相对于vector的头插操作效率较高。
  • 插入和删除操作时间复杂度为O(N)（头插和尾插时间复杂度为O(1)，头删和尾删时间复杂度为O(1)）。若插入位置之前的元素个数较少，则将之前的元素前移，反之将之后的元素后移。删除操作类似插入操作。