# 【算法】基础数据结构


通过分析C++ STL容器，理解基础数据结构。

## 一、动态数组 vector
数组：相同类型、连续内存、顺序存储。因此能基于下标，实现对数组元素O(1)的随机访问：数组的开始地址 + index * 元素大小。

静态数组需要提前指定数组大小，如果实际使用超过了数组大小，需要手动实现申请一片更大内存，将原来数组的内容拷贝到新内存，并释放原本内存的操作。动态数组把这些细节封装起来，无需用户关注扩容的操作。

### vector定义和扩容实现
```cpp
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{
       ...
protected:
  _Tp* _M_start; //表示目前使用空间的头
  _Tp* _M_finish; //表示目前使用空间的尾
  _Tp* _M_end_of_storage; //表示目前可用空间的尾  
    ...
};
```
存了3个指针，分别表示数组的开始、结束、可用空间的结束。据此可以计算出size和capacity。

当capacity不足时，会触发扩容，测试扩容：
```cpp
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v;
    for (int i = 0; i < 20; i++) {
        std::cout << "size: " << v.size() << " capacity " << v.capacity() << std::endl;
        v.push_back(i);
    }
    return 0;
}
```
输出：
```bash
size: 0 capacity 0
size: 1 capacity 1
size: 2 capacity 2
size: 3 capacity 4
size: 4 capacity 4
size: 5 capacity 8
size: 6 capacity 8
size: 7 capacity 8
size: 8 capacity 8
size: 9 capacity 16
size: 10 capacity 16
size: 11 capacity 16
size: 12 capacity 16
size: 13 capacity 16
size: 14 capacity 16
size: 15 capacity 16
size: 16 capacity 16
size: 17 capacity 32
size: 18 capacity 32
size: 19 capacity 32
```
观察到当size > capacity时会触发扩容。并且capacity按2的指数倍增长。

vector扩容逻辑：
```cpp
  void push_back(const _Tp& __x) {//在最尾端插入元素
    if (_M_finish != _M_end_of_storage) {//若有可用的内存空间
      construct(_M_finish, __x);//构造对象
      ++_M_finish;
    }
    else//若没有可用的内存空间,调用以下函数，把x插入到指定位置
      _M_insert_aux(end(), __x);
  }
  
template <class _Tp, class _Alloc>
  void 
  vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
  {
    if (_M_finish != _M_end_of_storage) {
      construct(_M_finish, *(_M_finish - 1));
      ++_M_finish;
      _Tp __x_copy = __x;
      copy_backward(__position, _M_finish - 2, _M_finish - 1);
      *__position = __x_copy;
    }
    else {
      const size_type __old_size = size();
      const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
      iterator __new_start = _M_allocate(__len);
      iterator __new_finish = __new_start;
      __STL_TRY {
        __new_finish = uninitialized_copy(_M_start, __position, __new_start);
        construct(__new_finish, __x);
        ++__new_finish;
        __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
      }
      __STL_UNWIND((destroy(__new_start,__new_finish), 
                    _M_deallocate(__new_start,__len)));
      destroy(begin(), end());
      _M_deallocate(_M_start, _M_end_of_storage - _M_start);
      _M_start = __new_start;
      _M_finish = __new_finish;
      _M_end_of_storage = __new_start + __len;
    }
  }
```

扩容在`_M_insert_aux`中实现：
1. 确保当前size等于capacity
2. 申请当前size两倍的内存空间
3. 深拷贝
4. 释放原有内存空间
5. 更新vector中的指针

### 思考：为什么会设计成倍增？

若每次扩容固定增加 k 个空间，连续插入 n 个元素的总拷贝次数为：
`k + 2k + 3k + ... + n ≈ n²/(2k) = O(n²)`，
均摊到每次 push_back 是 O(n)，性能随规模急剧恶化。

容量按 1, 2, 4, 8, ..., n 增长，总拷贝次数：
`1 + 2 + 4 + ... + n ≈ 2n = O(n)`，
均摊到每次 push_back 是 O(1)。这就是「push_back 均摊 O(1)」的来源。

所以，vector扩容设计成倍增，是为了保证push_back的均摊复杂度为O(1)。不同的编译器扩容因子可能不同，gcc和clang默认是2，msvc默认是1.5。选2可以做到时间最优，但是为什么有的编译器选择1.5？
1. 1.5的最差空间利用率更高
2. 考虑到内存复用的问题，假设扩容因子为2，已分配块大小依次是 1, 2, 4, 8, 16...：1+2+4+...+2^(k-1)=2^k-1<2^k，前面所有已释放内存加起来，永远不够装下下一次扩容的大小。如果使用对齐内存池，会导致数组扩容只能往堆的高地址不断延伸，对内存分配器不友好。

### 思考：为什么pop不会触发缩容？
扩容是必要性问题，而缩容不是必须的。有可能用户就是需要保持原本的容量，所以是否缩容的选择应该交给使用者。这是STL的设计哲学：零开销抽象，把策略留给用户。

1. 对象池 / 复用：vector 被反复清空再填充，保留 capacity 反而避免了反复申请释放，性能更好。
2. 容量稳定抖动：size 在某个区间波动，释放只会带来无用拷贝。
3. 明确知道不再增长：用户可以主动调用 `shrink_to_fit()`。

同时C++标准层面的硬约束：`pop_back`、`clear`、`erase` 在标准里都被视为不应失败的操作。如果执行缩容，需要重新申请内存，可能会分配失败，就不符合规范（影响整个RAII析构链）。

## 二、双向链表 list
链表：顺序结构，使用指针关联节点地址，无需连续存储，一般来说比数组的内存使用率更高（无需提前分配）。链表更适用于删除、插入、遍历操作频繁的场景，而不适用于随机访问索引频繁的场景，如内存池、LRU。

链表主要包括单链表、双向链表、循环链表。STL中的list则是循环双向链表: 实现双向迭代器，支持`std::reverse`、`list::reverse()`、`list::sort()`等算法的实现。

### list定义和实现

链表节点的定义：
```cpp
template <class T>
struct __list_node {
  __list_node<T>* next;  // 前驱节点指针
  __list_node<T>* prev; // 后继节点指针
  T data; //存储数据
};
```

list定义：
```cpp
template<typename T>
class list{
    protected:
        typedef __list_node<T> list_node; // 显示定义list_node类型
        typedef allocator<list_node> nodeAllocator; // 定义allocator类型
    public:
        typedef T                  value_type;
        typedef T&                 reference;
        typedef value_type*        pointer;
        typedef list_node*         link_type;
        typedef const value_type*  const_pointer;
        typedef size_t             size_type;
    public:
        typedef __list_iterator<value_type> iterator; // 迭代器类型重写
    private:
        link_type node; // dummy节点
        // ......
}
```
每个list都有一个虚拟节点，用于标记整个循环链表的首位连接处：

![alt text](image.png)

dummy节点的引入是为了统一end语义：end指向的都是无效值。因此遍历list写法：
```cpp
for (std::list<int>::iterator it=mylist.begin(); it != mylist.end(); ++it) {
    std::cout << ' ' << *it;
}
```

insert和erase实现：
```cpp
// 在position之前插入节点
iterator insert(iterator position, const T& x) {
  lik_type tmp = create_node(x); // 创建一个临时节点
  tmp->next = position.node; // 将该节点的后继指针指向当前位置的节点
  tmp->prev = position.node->prev; // 将该节点的前驱指针指向当前位置的前驱节点
  (link_type(position.node->prev))->next = tmp; // 将前驱节点本来指向当前节点的后继指针改为指向该临时节点
  position.node->prev = tmp; // 同样，当前位置的前驱指针也要修改为指向该临时节点
  return tmp;
}
// 删除position的节点
iterator erase(iterator position) {
  link_type next_node = link_type(position.node->next);
  link_type prev_node = link_type(position.node->prev);
  prev_node->next = next_node;
  next_node->prev = prev_node;
  destroy_node(position.node);
  return iterator(next_node);
}
```
据此可以实现：
1. `push_back(x)`: `insert(end(), x)`
2. `push_front(x)`: `insert(begin(), x)`
3. `pop_back()`: `erase(--end())`
4. `pop_front()`: `erase(begin())`

### 注意事项
1. 遍历list的缓存命中率极差，实际遍历速度比vector慢一个数量级。
2. list每个节点额外存了两个指针，16字节，不一定比vector利用率更高。
3. list比vector的优势在于可以快速进行头插入和头删除，其他场景都建议使用vector。

## 三、双端队列 deque
队列的所有操作都发生在队列的两端。双端队列（double ended queue）在队列两端都可以进行插入和删除操作，更加灵活。

### deque定义和实现
deque使用了分级的思想，使用map管理多段连续内存（**分段连续空间**）：

![alt text](image-1.png)

```cpp
template <class _Tp, class _Alloc>
class _Deque_base {
  ...
protected:
  _Tp** _M_map;
  size_t _M_map_size;  
  iterator _M_start;
  iterator _M_finish;
  ...
}
```

deque的迭代器屏蔽了底层分块连续的细节，对外可以认为deque的内存空间是连续的。可以直接队deque的元素进行随机访问，时间复杂度是O(1)。

以push_back为例，看push操作的实现：
1. 如果当前node下面还有空间，直接使用下面的空间即可。
2. 如果当前node已经占满了，查看map。
3. 如果map下面还有没有使用的node，使用这个node。
4. 如果map下面没有剩余node，查看map使用量。
5. 如果map使用率没有过一半，把当前map上已用区间放到中间位置，然后执行3。
6. 如果map使用率超过一半，重新申请一个map，然后执行3。

pop操作则是在一个node空闲后，回收这段内存。所以在临界点反复push和pop每次都会触发node内存的申请和释放（对象池复用vector比deque更香）。

### 思考：为什么不使用vector或list？

1. vector在头部插入元素的时间复杂度是O(n)，不符合队列两端操作都要高效的需求。如果是大小确定的循环队列，用vector实现就比较合适。
2. list不支持随机访问，并且list每push一个元素就需要去申请内存，相比当前的实现一次性可以申请一段连续内存，list方案申请内存的频率更高，性能更差。

deque的随机访问也是O(1)，扩容也不需要深拷贝，实现看起来比vector更加全面。但是每次随机访问需要计算map位置和node中偏移，并且缓存命中率更低，实际性能不如vector。"只有在真的需要两端高效" 的场景才用 deque，否则 vector 永远是更快的选择。

### 思考：node该开多大？
STL的策略：每个node 512字节，或者每个node固定16个元素。
```cpp
// 每个 node 的元素数：若 sizeof(T) < 512，则为 512/sizeof(T)，否则为 1
inline size_t __deque_buf_size(size_t n, size_t sz) {
    return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}
```
分析：
1. node太小：map大，缓存命中率低
2. node太大：单node内存浪费严重（和vector的缺点类似）
3. 512字节接近一个cpu cache line的大小，是性能拐点。

---

> 作者: [jup](https://satoing.github.io)  
> URL: https://www.fullcomb.top/posts/%E4%B8%9A%E5%8A%A1%E5%BC%80%E5%8F%91%E7%AE%97%E6%B3%95/1.%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/