【琢磨 STL】序列式容器

array

1.at()与[]

at()函数在访问指定元素前会进行越界检查，超出界限会抛出异常

[]不会越界检查，越界后会返回一个随机值

可以通过两者修改元素的值

2.size()=max_size
3.array.fill(const T& value)，将 array 中所有元素的值修改为 value

vector

1. theSize，theCapacity，max_size

   theSize：已申请的连续空间中已经使用的大小

   theCapacity：已申请的连续空间中可以使用的大小

   max_size：整个内存空间中可以使用的大小

   max_size>>theCapacity>=theSize

2. 按需两倍扩容

   vector 有三个迭代器 start、finish 和 end_of_storage 分别指向连续空间的头部、被使用部分的尾部和整块连续空间的尾部

   在使用过程中，有备用空间（finish 之后，end_of_storage 之前）用来存储插入到尾部的元素。当备用空间不足时，vector 按照当前总容量的两倍进行扩容

   扩容的实际步骤是：

   1. 重新配置两倍容量的空间
   2. 移动原内容到新空间，在原内容后构造新内容元素
   3. 释放原空间

if (theSize == theCapacity)
    reserve(2 * theCapacity + 1);

std::vector<int> vector = {0, 1, 2}; // 实际空间是3
        std::cout << "size:" << vector.size() << std::endl;
        std::cout << "max_size:" << vector.max_size() << std::endl;
        std::cout << "capacity:" << vector.capacity() << std::endl;
        std::cout << "插入一个元素" << std::endl;
        vector.push_back(3);
        std::cout << "size:" << vector.size() << std::endl;
        std::cout << "max_size:" << vector.max_size() << std::endl;
        std::cout << "capacity:" << vector.capacity() << std::endl;
}
/*
size:3
max_size:4611686018427387903
capacity:3
插入一个元素
size:4
max_size:4611686018427387903
capacity:6
*/

根据初始化 vector 时，申请了三个大小的空间；当插入第四个元素时，扩容至 3 的两倍
3. 手动扩容与压缩

reserve(size_type new_cap)：手动扩展空间至 new_cap 大小

shrink_to_fit()：释放未使用的空间

        vector.reserve(10);
        std::cout << "size:" << vector.size() << std::endl;
        std::cout << "max_size:" << vector.max_size() << std::endl;
        std::cout << "capacity:" << vector.capacity() << std::endl;
        vector.shrink_to_fit();
        std::cout << "size:" << vector.size() << std::endl;
        std::cout << "max_size:" << vector.max_size() << std::endl;
        std::cout << "capacity:" << vector.capacity() << std::endl;
/*
size:4
max_size:4611686018427387903
capacity:10
size:4
max_size:4611686018427387903
capacity:4
*/

4.pop_bash()：移除末尾元素，不改变空间大小

void pop_back(){
    theSize--;
}

假设 size=4，capacity=8，移除后 size=3，capacity=8

5.clear()：清除空间元素，同上，不改变空间大小
6.push_back()与emplace_back()的区别

push_back()：先构建一个临时对象，然后调用拷贝构造函数（c++11 后调用转移构造函数）放入备用空间，实现插入，最后再释放临时变量

emplace_back()：在备用空间原地构造，不会触发拷贝构造（转移构造），节省资源

deque

1. 逻辑上来看，是一整段连续空间，实际上动态链接多段的定量连续空间（称作缓冲区），在缓冲区中存储数据，空间不足时分配新的空间并链接在头部或尾部
2. deque 的主控是一个连续空间，所谓的 map（与容器中的 map 不同）。通过这个 map 存储指向缓冲区的指针。使用 deque 时可以指定缓冲区大小，默认大小是 512 字节
   
3. deque 通过迭代器重载 ++ 和- -，来实现『整体连续』的假象
   

   map：deque 的本体，存储每个 buffer 的地址

   start：指向第一个 buffer 的 iterator

   finish：指向最后一个 buffer 的 iterator

   iterator：

   ​ node：指向本 buffer 在 map 中的位置，方便在本 buffer 遍历结束后找到下一个 buffer 的 位置

   ​ first：指向本 buffer 的空间中的开头地址

   ​ finish：指向本 buffer 的空间中的结尾地址

   ​ cur：指向 buffer 中某个具体的元素

   重点：finish 的 cur 指向最后一个元素的下一个位置

4. 尽可能使用 vector，需要对 deque 进行排序时，先复制进 vector，调用 sort，再复制回 deque
5. 适配器stack，queue通过复合的方式，默认以deque作为基础容器（也可以选择list），调用 deque 的成员函数，完成自己的功能

   stack：先进后出的栈，也可以使用vector作为基础容器

   queue：先进先出的队列

   两者不允许遍历，说明无法在中间插入元素

List

1. 结点类有两个指针，next和prev，分别指向下一个结点和上一个结点

template<typename T>
class _list_node {
public:
    typedef void *void_pointer;
    void_pointer prev;  // 类型也可以设置为_list_node<T>*
    void_pointer next;
    T data;
};

2. list 实际上是一个环状双向链表，巧妙的利用一个空结点记录 list 的头部和尾部

template<class Object>
class list {
protected:
    typedef _list_node<Object> list_node;
public:
    typedef list_node *link_type;
protected:
    int theSize;
    link_type node;
};

list 中的node指针指向一个空置 data 的 node，这个 node 利用 next 和 prev 记录 list 的头部和尾部

我在自己设计双向链表的时候，想到的是直接用两个指针来分别指向头部和尾部，现在学到了利用环状链表来解决问题

在利用继承的情况下，这个 data 甚至不会空置

template<class Object>
class list_node_base {
public:
    typedef list_node_base<Object> *void_pointer;
    void_pointer prev;
    void_pointer next;
};

template<class Object>
class list_node : public list_node_base<Object> {
public:
    Object data;
};

这样，只需要在list类中声明一个list_node_base<Object>类型的成员变量，就可以用来指向表头和表尾
3. list 利用 default constructor 构建一个空 list

public:
    void empty_initialize() {
        node = get_node();  // 返回一个node
        node->next = node;
        node->prev = node;
    }

4.iterator通过继承const_iterator，来实现通过迭代器修改data
5. 迭代器中需要有一个const list<Object>类型的指针，用来保存 list 的位置，以便需要时可以找到 list
6. list 的迭代器通过操作符重载，完成前移、后移和取值等操作

7.erase(iterator itr)修改被删除结点的前驱和后继结点的指针，使之相互链接。delete被删除指针并自减theSize，返回了被删除结点后面的结点

通过调用erase()方法来实现其他方法

void pop_front(){
    erase(begin());
}

void clear(){
    while(!empty())
        pop_front();
}

8. list 的析构函数，通过clear()删除所有结点后，再delete指向链表的 node 成员变量，完成析构

~list(){
    clear();
    delete node;
}