C++STL细节，底层实现，面试题04

19. STL

C++标准库容器，官方文档https://learn.microsoft.com/zh-cn/cpp/standard-library/stl-containers?view=msvc-170

19.1. 序列容器

可顺序访问元素。

19.1.1. vector

19.1.1.1. 底层实现和特点

• 底层实现为动态数组（使用数组指针），动态分配空间。连续内存空间，支持随机访问。
• 它通过下标访问元素，时间复杂度o(1)。
• 尾部插入和删除操作，时间复杂度o(1)。
• 其余部分插入和删除，需要移动元素，时间复杂度o(n)。
• 当内存空间不足时，会重新分配内存空间，扩充为原来的两倍，并拷贝原有数据。
• 应用场景：适用于需要随机访问或频繁在序列尾部进行操作的场景。

19.1.1.2. 常用函数

• front() 返回第一个元素的引用。
• back() 返回最后一个元素的引用。
• begin() 返回第一个元素的迭代器。
• end() 返回超过末尾迭代器。
• clear() 清空。
• empty() 判空。
• emplace_back() 将就地构造的元素添加到末尾。
• push_back() 将元素添加到末尾。
• pop_back() 删除末尾元素。
• erase(position),erase(first,end) 删除元素。
• insert(positon,value) 添加元素。
• swap（）交换容器元素。
• resize(size),resize(size,value) 指定新的大小。

19.1.1.3. emplace_back() vs push_back()

• emplace_back()的参数会使用forward<>完美转发给构造函数，然后在容器提供的位置就地构造。即只构造一次，如下图。
  

• push_back()的参数作为右值传入，先构造元素，再移动到末尾，即先调用构造函数，然后调用移动构造函数，如下图。
  

• 【注意】 emplace_back()的参数 {1,2} 会自动转换成initializer_list并进行完美转发，但vector并没有initializer_list的构造函数，所以报错。

    vector<pair<int, int>> v;
    v.push_back({1,2});
    v.emplace_back({1,2}); //报错

19.1.2. array

19.1.2.1. 底层实现和特点

• 底层实现为数组，固定大小。连续内存空间，支持随机访问。

19.1.2.2. 常用函数

• fill() 替换所有的元素。
• swap() 交换容器元素。

19.1.3. deque

19.1.3.1. 底层实现和特点

• 底层实现为中控器+缓冲区+迭代器。
  • 中控器，将分段连续的内存空间链接起来，才能在逻辑上连续，支持随机访问。使用指针数组，存放缓存区的地址。
  • 迭代器，四个指针。
    • T* cur，指向缓冲区的当前元素。
    • T* first，指向缓冲区的头。
    • T* last，指向缓存区的尾（含备用空间）。
    • T** node，指向管控中心，即缓冲区的标记位置。
• 双端队列，首尾两端进行动态增删。
• 相比vector和list，deque不适合遍历，因为每次访问元素，都要检查是否到达了内存片段的边界，造成了额外开销。
• 应用场景：适用于需要频繁在序列两端进行操作的场景。

19.1.3.2. 常用函数

• emplace_back() 将就地构造的元素添加到末尾。
• emplace_front() 将就地构造的元素添加到开头。
• push_back() 将元素添加到末尾。
• push_front() 将元素添加到开头。
• pop_back() 删除末尾元素。
• pop_front() 删除开头元素。
• swap() 交换容器元素。

19.1.4 list

19.1.4.1. 底层实现和特点

• 底层实现为双链表，动态分配内存。离散内存空间，不支持随机访问。
• 通过指针访问元素，需要遍历直至要访问的元素，时间复杂度o(n)。
• 支持在任意位置快速插入和删除操作，时间复杂度o(1)。
• 支持双向遍历。
• 内存空间的使用效率并不高，一来它存放在离散而非连续的内存空间；二来它需要消耗更多内存空间来保存元素之间的关联信息。
• 应用场景：适用于需要频繁在任意位置进行操作，但不需要随机访问的场景。

19.1.4.2. 常用函数

• emplace_back() 将就地构造的元素添加到末尾。
• emplace_front() 将就地构造的元素添加到开头。
• push_back() 将元素添加到末尾。
• push_front() 将元素添加到开头。
• pop_back() 删除末尾元素。
• pop_front() 删除开头元素。
• remove() 删除指定值。
• reverse() 反转元素。
• sort() 按升序排序，sort( greater<>() ) 按降序排序。
• swap() 交换容器元素。
• rbegin() 返回反向第一个元素的迭代器。
• rend() 返回反向超过末尾迭代器。

19.2. 关联容器

通过key访问元素。

19.2.1. map

19.2.1.1. 底层实现和特点

• 底层实现为红黑树，有序。
• 应用场景：适用于需要通过key快速查找value的场景。

19.2.1.2. 常用函数

• contains() （C++20）是否包含指定键的元素。
• count() 是否包含指定键的元素。
• emplace() 就地插入构造的元素，即不执行复制或移动操作。
• find() 返回指定键的迭代器。
• erase(key)，erase(iter_position) 移除指定键或指定位置的元素。
• lower_bound() 返回键值等于或大于指定键的第一个元素的迭代器。
• upper_bound() 返回键值大于指定键的第一个元素的迭代器。

19.2.1.3. map vs unordered_map

• 底层实现为哈希表，无序。
• 应用场景：适用于需要通过key快速查找value的场景，但不关心key的顺序。
• unordered_map 直接访问元素的速度更快，尤其在大规模时，因为它通过直接计算key的哈希值来访问元素，时间复杂度o(1)。
• 但unordered_map 内存占用更高，因为底层的哈希表需要预分配足够的空间。

19.2.2. set

19.2.2.1. 底层实现和特点

• 底层实现为红黑树，有序。
• 元素自身就是key。
• 元素有唯一性，不允许出现重复的元素，且元素不可更改，但可以插入或删除。
• 应用场景：适用于需要快速查找和去重的场景。

19.2.2.2. 常用函数

• contains() （C++20）是否包含指定键的元素。
• count() 是否包含指定键的元素。
• emplace() 就地插入构造的元素，即不执行复制或移动操作。
• find() 返回指定键的迭代器。
• erase(key)，erase(iter_position) 移除指定键或指定位置的元素。
• lower_bound() 返回键值等于或大于指定键的第一个元素的迭代器。
• upper_bound() 返回键值大于指定键的第一个元素的迭代器。

19.2.2.3. set vs unordered_set

• 底层实现为哈希表，无序。
• 应用场景：适用于需要快速查找和去重的场景，但不关心元素的顺序。
• unordered_set 直接访问元素的速度更快，尤其在大规模时，因为它通过直接计算key的哈希值来访问元素，时间复杂度o(1)。
• 但unordered_set 内存占用更高，因为底层的哈希表需要预分配足够的空间。

19.2.3 自定义比较函数对象，来定义元素的比较方式。

#include<iostream>
#include<set>
using namespace std;

// 自定义比较函数对象，按照 pair 的第二个值进行比较
struct CompareBySecond {
    bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) const {
        return p1.second < p2.second;
    }
};

int main() 
{
    set<pair<int, int>, CompareBySecond> s = { {1,20},{2,10},{3,30},{4,5} };
  
    for (auto&& u : s)
        cout << u.first << " " << u.second << endl;
   
    return 0;
}

19.3. 容器适配器

本身只是一个封装层，必须依赖指定的底层容器，才能实现具体功能。即它是序列容器或关联容器的变体。

19.3.1 queue

19.3.1.1. 底层实现和特点

• 底层容器默认deque。
• 队列，先进先出。
• 应用场景：适用于需要先进先出操作的场景，如广度优先搜索、任务调度、数据缓冲区等。

19.3.1.2. 常用函数

• front() 返回第一个元素的引用。
• back() 返回最后一个元素的引用。
• empty() 返回是否空。
• pop() 头部移除元素。
• push() 尾部添加元素。
• size() 返回元素数量。

19.3.2 priority_queue

19.3.2.1. 底层实现和特点

• 底层容器默认vector。
• 优先队列，元素按照优先级排序，每次弹出最高优先级的元素，即默认最大堆。
• 最小堆使用 greater<> 作比较器。
• 应用场景：适用于需要按照优先级处理元素的场景，如任务调度、最大（小）堆实现等。

19.3.2.2. 常用函数

• top() 返回顶部元素的常量引用，即返回值不是左值。
• empty() 返回是否空。
• pop() 顶部移除元素，即弹出最大元素。
• push() 添加元素。
• size() 返回元素数量。

19.3.3 stack

19.3.3.1. 底层实现和特点

• 底层容器默认deque。
• 栈，后进先出。
• 不允许遍历，只能访问顶部元素。
• 应用场景：适用于需要后进先出操作的场景，如深度优先搜索、表达式求值、括号配对等。

19.3.3.2. 常用函数

• top() 返回顶部元素的引用。
• empty() 返回是否空。
• pop() 顶部移除元素。
• push() 顶部添加元素。
• size() 返回元素数量。