STL是C++的核心组成部分，其主要包括了容器、迭代器、算法三大组件。

其中容器负责存储数据，迭代器是容器和算法的桥梁，负责对容器中的元素进行操作。本文主要针对容器部分。

STL主要容器

STL容器根据特性进行分类，可以分为序列式容器、关联容器、容器适配器

序列容器

序列容器重点在于根据元素的插入顺序而进行线性排列。

常见的序列容器有5种，分别是vector,list,deque,array,forward_list，这5种序列容器的底层实现原理和核心特性总结如下：

容器	底层原理	核心特性
vector	拥有连续存储空间的动态数组，底层由3个指针，分别是:start,finish,end_of_stroage，通过这三个底层指针可以实现一些常规操作；具备动态扩容机制（一般为2倍）	支持随机访问（[]/at()），尾插和删除的复杂度为O(1)，中间插入/头插/删除元素 O(n)
list	底层数据结构是双向链表（内存空间不连续），每个节点都有数据，前驱指针和后继指针	不支持随机访问，在任意位置插入/删除为 O(1)，遍历元素效率O(n)
deque	分段连续内存，有一个指针数组，存放每一段连续存储空间的地址	支持双端高效插入/删除 O(1)，随机访问效率略低于vector，整体来说集成了vector和list的优点
array	固定大小的静态数组，内存分配在栈上	大小不可变，随机访问高效，适合存储已知固定数量的元素
forward_list	单向链表（仅包含后继指针）	内存占用比list更小，仅支持单向遍历，插入/删除 O(1)

关联式容器

关联容器重点在于键值对的关联，元素根据按照键Key排序，元素的插入顺序不会影响到元素所处的位置，可以分为有序关联容器和无序关联容器。

有序关联容器

有序关联容器以键为核心，元素会自动按照键的大小进行排序（默认情况下是升序排列std::less<key>，降序std::greater<int>）。这一类容器的底层数据结构是采用的红黑树（Red-Black Tree)，红黑树是一种自平衡的二叉搜索树，红黑树的插入、删除、查找的时间复杂度都是O(logn).

有序关联容器主要分为4种：set、map、multiset、multimap。它们的核心区别在于键是否唯一以及是否存储键值对.

1、set

存储唯一键的有序容器，其元素本身就是键(键=值)，并且这里也不允许键重复，新插入的元素会按照键的大小自动排序，同时set种的元素是常量，不能直接修改（可能会破坏红黑树的性质），修改的正确操作过程应该是先删除旧元素，再插入新元素。由于红黑树的性质，在set插入或删除元素时，除被删除元素的迭代器外，其他迭代器均不会失效。

常见的接口操作：

• insert(key)返回的是pair<iterator, bool>，标识是否插入成功
• erase(key)/erase(iterator)删除匹配键的元素和迭代器指向的元素
• find(key)查找某个key
• count(key)计算某个key出现的次数
• lower_bound(key)找到第一个不小于key（≥key)的迭代器，upper_bound(key)返回第一个大于key的元素迭代器

2、multiset

可以在set的基础上允许插入重复的键，元素按照键的大小有序排列。

常见的接口操作：

• insert(key)返回新插入元素的迭代器
• erase(key)删除所有匹配键的元素
• count(key)计算某个key出现的次数
• equal_range(key)返回是一个pair包含所有匹配键的元素范围[first, second)，左闭右开区间

3、map

map 是存储键值对（key-value） 的有序容器，键（key）唯一，值（value）可修改。元素按键的大小自动排序，通过键可以快速访问对应的值。

底层基于红黑树，树的每个节点存储一个pair<const key, value>，所以键不可修改，值可以通过迭代器和[]修改

在插入时，不允许插入重复的键，insert会忽略重复键的插入；键一般用来查找和排序，值用来存储实际的元素，并且按照默认升序排列。

常见接口：

• insert(pair<key, value>)（返回pair<iterator, bool>）、map[key] = value（若键存在则修改值，否则插入新键值对）。
• erase(key)（删除键对应的键值对）、erase(iterator)。
• find(key)（返回指向键值对的迭代器）。
• at(key)（安全访问，键不存在时抛异常）、map[key]（非安全访问，键不存在时插入默认值）。
• lower_bound、upper_bound和set一样

4、multimap

在map的基础上允许插入重复的键，键值对按照键的大小有序排列。多个键值对可以有相同的键，按键有序排列（相同键的键值对相邻），由于键不唯一，所以不能使用[]操作符号，只能使用find或者equal_range

常见接口：

• insert(pair<key, value>)总是成功，返回新元素迭代器
• equal_range(key)返回包含所有相同键的键值对范围
• erase(key)、find(key)返回第一个匹配键的迭代器，与map类似

所以有序管理容器的总结如下：

容器	底层原理	核心特点
set	红黑树，键值唯一，元素就是值	元素自动按键升序排列，插入 / 删除 / 查找复杂度为O (log n)
multiset	红黑树，键可以重复插入	特性同set，但支持键重复，插入 / 删除 / 查找仍为 O (log n)
map	红黑树，存储键值对，键唯一	按键升序排列，通过键快速访问值（[]/at()），键不可重复
mutlimap	红黑树，键值对，键可以重复，插入到相邻位置	特性同map，但键可重复，不支持[]操作符（需用find()/equal_range()）

无序关联容器

无序关联容器以键（key） 为核心的容器，其元素不按键的大小排序，而是通过哈希表（Hash Table）实现存储和访问。插入/删除/查找的平均时间复杂度为O(1)。

底层的核心原理是哈希表（hashtable)，重点包含以下三个部分：

• 桶（Buckets）：一个动态数组，每个元素（桶）是一个链表或红黑树的头指针，用于存储哈希值相同的元素（处理哈希冲突）
• 哈希函数（Hash Function）：将键（key）映射为桶的索引（整数），决定元素应该放入哪个桶
• 相等比较器（Equality Comparator）：判断两个键是否 “相等”（用于处理哈希冲突时，区分不同键但哈希值相同的元素）

在插入新元素时，通过哈希函数计算键的哈希值，得到桶的索引，将元素放入对应桶中；查找元素时，先通过哈希函数定位桶索引，然后在桶内遍历比较键，找到目标元素；当元素过多，超过负载因子时，触发重hash，分配更大的桶数组，重新计算哈希值，并且迁移到新的桶中。

1、unordered_set

存储唯一键的无序容器，元素本身就是键（“键 = 值”），键不允许重复，元素无序排列。适用于需要快速去重但是不需要关注元素顺序的场景

在插入重复键时，insert会被忽略，并且元素的顺序由哈希函数和插入顺序决定，于键的大小无关；由于键是常量，所有更新键的信息，需要删除旧元素插入新元素；插入时可能导致rehash导致所有迭代器失效，删除时只有被删除的元素的迭代器失效。

常见接口：

• insert(key)返回pair<iterator, bool>，bool表示是否插入成功
• erase(key)删除所有匹配键的元素，返回删除数量、erase(iterator)
• find(key)返回指向键的迭代器，不存在则返回end()
• count(key)返回键的出现次数，只能是 0 或 1
• bucket_count()当前桶数量、load_factor()当前负载因子、rehash(n)强制将桶数量设置为≥n

2、unordered_map

存储键值对（key-value） 的无序容器，键（key）唯一，值（value）可修改，元素无序排列，适用于需要通过唯一键快速查询值且不关心键顺序的场景，例如：缓存（键为 ID，值为缓存数据）、字典（无需按字母排序的键值映射）

插入重复键时，insert操作忽略，[]操作符会覆盖旧值;键用于哈希和查找，值存储实际数据，值可通过迭代器或[]修改；键值对顺序由哈希函数决定，与插入顺序和键大小无关。

常见接口：

• insert(pair<key, value>)、map[key] = value键不存在则插入，存在则修改值
• at(key)安全访问，键不存在抛异常、map[key]不安全访问，键不存在插入默认值
• find(key)、erase(key)等与unordered_set类似

3、unordered_multiset

unordered_set的 “多重” 版本，允许存储重复的键（键可以不唯一），元素无序排列（相同键的元素相邻），适用于需要存储重复元素且不关心顺序的场景，例如：统计元素出现频率（如词频统计）、存储多个相同优先级的任务

4、unordered_multimap

unordered_map的 “多重” 版本，允许存储重复的键（键值对的键可以不唯一），元素无序排列（相同键的键值对相邻），多个键值对可拥有相同的键，相同键的键值对在同一桶中相邻，适用于需要通过重复键映射多个值且不关心顺序的场景。

无序关联容器总结：

容器	底层原理	核心特性
unordered_set	哈希表（数组 + 链表 / 红黑树），键唯一	元素无序，插入 / 删除 / 查找平均复杂度 O (1)（最坏 O (n)，取决于哈希冲突），键唯一。
unordered_map	哈希表，存储键值对，键唯一	无序，通过键快速访问值，平均 O (1) 操作，键唯一
unordered_multiset	哈希表，键可重复	无序，支持键重复，平均 O (1) 操作
unordered_multimap	哈希表，键值对，键可重复	无序，键可重复，平均O (1) 操作

容器适配器

容器适配器是一类特殊的容器，它们不直接实现数据存储，而是通过封装底层容器（如vector，deque，list等）来提供特定的接口和功能。核心作用是：限制对底层容器的访问方式，只暴露符合特定数据结构逻辑的操作

主要特点：

• 本身不存储数据，数据实际上存储在底层容器中，适配器仅仅提供上层的接口
• 屏蔽底层容器的大部分操作，只保留符合自身发展逻辑的接口（stack仅允许栈顶操作）
• 适配器没有迭代器，不支持遍历或者随机访问
• 默认使用特定的容器作为底层实现（如stack使用deque），但是也可以通过模板参数指定其他符合要求的容器

主要的容器适配器类型

1、stack

stack遵循后进先出规则，仅仅允许在栈顶进行操作，插入、删除和访问等。

其底层的容器为deque，主要原因是：

• deque的尾部插入和删除的效率都是O(1)
• deque可以减少频繁扩容导致的内存重分配
• 跟list相比，deque的内存连续性更好，缓存利用率更高

核心操作有：

• push(val)：在栈顶插入元素（调用底层容器的push_back）。
• pop()：删除栈顶元素（调用底层容器的pop_back，不返回元素）。
• top()：返回栈顶元素的引用（调用底层容器的back）。
• empty()：判断栈是否为空。
• size()：返回元素个数。

实现

template <typename T, typename Sequence = std::deque<T>> 
class stack {
public:
    using value_type = typename Sequence::value_type;
    using size_type = typename Sequence::size_type;
    using reference = typename Sequence::reference;
    using const_reference = typename Sequence::const_reference;
    using container_type = Sequence;
    
    // 各类接口
    bool empty() const {
        return container_.empty();
    }
    
    size_type size() const {
        return container_.size();
    }
    
    const_reference top() const {
        return container_.back();
    }
    
    void push(const value_type &v)  {
        container_.push_back(v);
    }
    
    void pop() {
        container_.pop_back();
    }
    
    template<typename... Args>
    void emplace(Args&& ...args) {
        container_.emplace_back(std::forward<Args>(args)...);
    }
    
    void swap(stack& other) {
        container_.swap(other.container_);
    }
    
private:
    // 唯一的成员变量就是底层的容器
    containter_type container_;
}

2、queue

queuq遵循FIFO规则，允许在队尾插入，队头删除和访问。

底层的默认容器还是deque，主要原因是：

• deque支持队尾插入（push_back）和队头删除（pop_front），两者效率均为O (1)
• 若用vector作为底层，pop_front操作需移动所有元素（O (n)，效率低）
• list虽支持 O (1) 的头尾操作，但内存连续性差，缓存命中率低

核心操作有：

• push(val)：在队尾插入元素（调用push_back）。
• pop()：删除队头元素（调用pop_front，不返回元素）。
• front()：返回队头元素的引用（调用front）。
• back()：返回队尾元素的引用（调用back）。
• empty()/size()：判断空或返回元素个数。

实现

template <typename T, typename Sequence = std::deque<T>>
class queue {
public:
    using value_type = typename Sequence::value_type;
    using size_type = typename Sequence::size_type;
    using reference = typename Sequence::reference;
    using const_reference = typename Sequence::const_reference;
    using container_type = Sequence;
    
    bool empty() const {
        return container_.empty();
    }
    
    size_type size() const {
        return container_.size();
    }
    
    reference front() const {
        return container_.front();
    }
    
    const_reference front() const {
        return container_.front();
    }
    
    reference_back() {
        return container_.back();
    }
    
    const_reference back() const {
        return container_.back();
    }
    
    void push(value_type& v) {
        container_.push_back(v);
    }
    
    void pop() {
        container_.pop_front();
    }
    
    template<typename ...Args>
    void emplace_back(Args&& ...args) {
        container_.emplace_back(std::forward<Args>(args)...);
    }
    
    void swap(queue& other) {
        container_.swap(other.container_);
    }
    
private:
    container_type container_;
}

3、priority_que

priority_que是优先级队列，也是一种适配器，每次删除的其中的优先级最高的元素（默认最大元素），插入时会自动调整元素的位置以维持优先级顺序。

priority_que底层使用的容器是vector，主要原因是：

• priority_que逻辑是一个二叉堆，需要随机访问定位父子节点的位置（如父节点的下标为i，那么其左孩子的下标为2*i + 1，右孩子的下标为2*i + 2)
• vector随机访问的效率最好，内存连续，具有局部性原理，并且堆的上浮和下沉操作效率更高

它默认使用std::less<T>作为比较器（大顶堆），std::greater<T>为小顶堆

如priority_queue<int, vector<int>, std::greater<int>> min_heap

核心操作有

• push(val)：插入元素并调整堆结构（确保优先级最高的元素在顶部，复杂度 O (log n)）。
• pop()：删除顶部（优先级最高）的元素并调整堆（复杂度 O (log n)，不返回元素）。
• top()：返回顶部元素的引用（调用底层容器的front）。
• empty()/size()：判断空或返回元素个数。

实现

template<typename T, typename Container = std::vector<int>,
                        typename Comp = std::less<typename Container::value_type>>
 class priority_queue {
 public:
     using value_type = T;
     using size_type = typename Container::size_type;
     
     /// 构造函数
     explicit priority_queue(const Container& container = Container(), const Comp& comp = Comp())  : comp_(comp), container_(container){
         /// 利用容器的头尾迭代器构造一个堆
         std::make_heap(container_.begin(), container_.end(), comp_);
     }
     
     // 拷贝构造和移动构造，赋值，移动赋值都是默认
     priority_queue(priority_queue &&) noexcept = default;
​
     priority_queue &operator=(priority_queue &&) noexcept= default;
​
     priority_queue(const priority_queue &) = default;
​
     priority_queue &operator=(const priority_queue &) = default;
     
     /// 输入迭代器版本的构造函数
     template<typename InputIterator>
     priority_queue(InputIterator first, InputIterator last, const Comp& comp = Comp(), const Container& container = Container()) : container_(container), comp_(comp) {
         std::make_heap(container_.begin(), container_.end(), comp_);
     }
     
     // 下面是常见的接口
     bool empty() const {
         return container_.empty();
     }
     
     size_type size() const {
         return container_.size();
     }
     
     const value_type& top() const {
         return container_.front();
     }
     
     value_type& top() {
         return container_.front();
     }
     
     void push(const valye_type& value) {
         container_.push_back(value);
         std::push_heap(container_begin(), container_.end(), comp_);
     }
     
     void push(valye_type&& value) {
         container_.push_back(std::move(value));
         std::push_heap(container_begin(), container_.end(), comp_);
     }
     
     void pop() {
         std::pop_heap(container_.begin(), container_end(), comp_);
         container_.pop_back();
     }
     
    void swap(priority_que& other) {
        std::swap(comp_, other.comp_);
        std:;swap(container_, other.container_);
    }
     
     template<typename ...Args>
     void emplace_back(Args&& ...args) {
         container_.emplace_back(std::forward<Args>(args)...);
         std::push_heap(container_.begin(), container_.end(), comp_);
     }
     
 private:
     // 成员变量主要有比较器和容器
     Container container_;
     Comp comp_;
 }