C++ STL 容器重要概念

本文所有内容均在 GNU C++ (64位) 里瞎搞出来，有很多猜测，仅供参考。

# 1. 如何定义

vector<T, allocator<T>>
deque<T, allocator<T>>
list<T, allocator<T>>
forward_list<T, allocator<T>>

set<T, less<T>, allocator<T>>
map<T, U, less<T>, allocator<pair<T, U>>>
unordered_set<T, hash<T>, equal_to<T>, allocator<T>>
unordered_map<T, U, hash<T>, equal_to<T>, allocator<pair<T, U>>>
// 省略 multiset, multimap, unordered_multiset, unordered_multimap

basic_string<T, char_traits<T>, allocator<T>>
basic_stringstream<T, char_traits<T>, allocator<T>>
// using string = basic_string<char>

queue<T, deque<T>>
stack<T, deque<T>>
priority_queue<T, vector<T>, less<T>>

array<T, N>
bitset<N>

# 2. 内存分配

• queue, stack, priority_queue 是由其他容器改造过来的（第二个模板参数），queue, stack 默认是 deque，priority_queue 默认是 vector。
• array, bitset 都是固定长度，没有内存分配器，估计和数组行为一致。
• list, forward_list, set, map 这些链表数据结构（unordered 每个桶也是链表），每个结点的指针的内存不通过自定义内存分配器分配。目前初步估计 set / map 的每个结点有额外 24 字节（通过鸡兔同笼法），其余懒得算。
• vector<bool> 很奇葩，最好不用。

# 3. 时间复杂度

• list 的 size() 是 $O(n)$ 的！（forward_list 干脆不定义这个函数），想用 list 代替 deque 的同学要注意这个坑点。（事实上 list::size() 在 C++ 11 标准里已经要求 $O(1)$ 了，但是实际不一定）
• array / bitset 的 swap() 是 $O(n)$ 的（要把它当 C 的数组看待）。
• 其他复杂度还没发现不正常的。

# 4. 迭代器

• 由其他容器改造的容器（queue, stack, priority_queue）都没有迭代器。
• bitset 没有迭代器。
• stringstream 没有迭代器（不考虑特殊迭代器）。

# 5. vector 行为分析

引用了我的一篇博客园文章。

众所周知，vector 的 size() 其实并不代表它占用的空间，它实际占用空间可以用 capacity() 查看。

众所周知，push_back() 时，如果 size == capacity 则会使 capacity 从 0 变 1 或者变为原来两倍，当然如果 size<capacity 则不会触发内存分配。

众(gui)所(cai)周(zhi)知(dao)，一旦触发内存分配，原来的指针或者迭代器失效，因为 vector 的所有内容搬迁到新的内存里了。

你可能觉得 push_back() 奇慢无比，那倒也不至于，因为平均下来 push_back() 复杂度确实是 $O(1)$。

当然慢也是有一定道理的，因为如果直接用 vector 数组作为邻接表来存图，效率并不理想。

比如我们定义了 vector<int> a[100010];，随机建边的时候就会疯狂触发内存分配导致愉快地 TLE。（不过图论题这么毒瘤的也不常见）

解决方法是前向星或者手写分配器。如果不手写分配器用 list 替代 vector 貌似更慢了。（虽然我也不知道为什么，另外 forward_list 和 vector 差不多的亚子）

众(gui)所(cai)周(zhi)知(dao)，不止 push_back()，像 resize(), reserve() 等都会触发内存分配。

众(gui)所(cai)周(zhi)知(dao)，像 clear(), pop_back() 等并不会释放内存（也就不会使 capacity 变小），只有 shrink_to_fit() 等少数几个操作才能使 capacity 变小。因此有些不得已的情况会用 a = vector<int>() 来代替 a.clear()。

当然也有可能 a.clear() 导致 MLE，a = vector<int>() 导致 TLE（笑）。

众(gui)所(cai)周(zhi)知(dao)，vector 对内存分配的惰性其实是为了效率考虑的，它很好地规避了频繁的分配释放空间。vector 满足了很多常见需求。但是像图论等某些地方还是不能偷懒，还得花点功夫写分配器，或者用前向星、手写 queue 这种朴素方法代替 STL。

手写分配器的方法如下：

static char space[10000000],*sp=space;
template<typename T>
struct allc:allocator<T>{
    allc(){}
    template<typename U>
    allc(const allc<U> &a){}
    template<typename U>
    allc<T>& operator=(const allc<U> &a){return *this;}
    template<typename U>
    struct rebind{typedef allc<U> other;};
    inline T* allocate(size_t n){
        T *res=(T*)sp;
        sp+=n*sizeof(T);
        return res;
    }
    inline void deallocate(T* p,size_t n){}
};
vector<int,allc<int>> a;

# 6. deque 行为分析

引用了我的一篇博客园文章。

上次队友因为 deque 导致 MLE 惨案，今天好奇想要看看 deque 是怎么操作的（非专业分析）。

我重载了 allocator 然后输出一下内存占用和释放情况，发现如下现象：

• 就算不使用 deque，只要声明了 deque 就占用 512 字节（比如 128 个 int，64 个 long long）（如果无法整除，比如 tuple<int,int,int>，512 无法整除 12，那会比 512 字节少一点），另外占用少量字节用于索引。
• 如果数据量超出当前的 size，会多申请 512 字节，每次都是 512 亘古不变。
• 当然，所有的块显然是不连续的，因此有如下猜测：索引存在的意义就是让 deque 的随机访问控制在 $O(1)$ 复杂度内，同样索引也可以灵活分配 push_back、push_front 所需要的内存。
• 另外 clear() 是真的会释放内存的，而不是和 vector 一样保留内存。