STL

STL（Standard Template Library）是C++中的标准模板库组件，由容器、迭代器、算法、适配器、函数对象和空间配置器组成。

1. 容器用于存储和管理数据对象,也就是数据结构。容器分为序列式容器、有序关联式容器和无序关联式容器。序列式容器中元素的顺序由插入的位置决定，主要有vector, deque和list等。有序关联式容器会对插入的元素进行排序，默认为升序，主要有set，map等。无序关联式容器基于哈希表，提供快速查找的功能，但是元素为乱序，主要有unordered_set和unordered_map。

2. 迭代器是连接容器和算法的桥梁，是为了便于访问容器中的元素而设计出来的一种统一的访问接口，可以将其看成是一种指针，称为泛型指针。

3. 算法提供一些通用的函数，用于操作容器中的元素，比如查找元素、排序元素和进行数值运算。

4. 适配器用于修改其他组件的接口，起到适配的作用，比如容器适配器、迭代器适配器和函数适配器。

5. 函数对象是重载了operator()的类，可以像函数一样调用，用于做定制化的操作。

6. 空间配置器负责内存的分配和释放，为容器提供内存管理。

vector

std::vector 是C++ STL中最常用的序列容器，提供动态数组功能。它是一个模板类，可以存储任意类型的元素。

基本特性

• 动态大小：运行时可以改变大小

• 连续内存：元素在内存中连续存储

• 随机访问：支持O(1)时间复杂度的随机访问

• 自动内存管理：自动处理内存分配和释放

xxxxxxxxxx
2
1
#include <vector>
2
using namespace std;  // 或使用 std::vector

声明和初始化

xxxxxxxxxx
24
1
// 空vector
2
std::vector<int> vec1;
3

4
// 指定大小
5
std::vector<int> vec2(10);           // 10个元素，默认值为0
6
std::vector<int> vec3(10, 5);        // 10个元素，每个值为5
7

8
// 初始化列表（C++11）
9
std::vector<int> vec4 = {1, 2, 3, 4, 5};
10
std::vector<int> vec5{1, 2, 3, 4, 5};
11

12
// 拷贝构造
13
std::vector<int> vec6(vec4);
14
std::vector<int> vec7 = vec4;
15

16
// 移动构造（C++11）
17
std::vector<int> vec8 = std::move(vec4);
18

19
// 从数组初始化
20
int arr[] = {1, 2, 3, 4, 5};
21
std::vector<int> vec9(arr, arr + 5);
22

23
// 从其他容器初始化
24
std::vector<int> vec10(vec4.begin(), vec4.end());

xxxxxxxxxx
13
1
// 二维vector
2
std::vector<std::vector<int>> matrix;
3

4
// 指定大小的二维vector
5
std::vector<std::vector<int>> matrix2(3, std::vector<int>(4, 0));
6
// 3行4列，每个元素初始化为0
7

8
// 初始化列表
9
std::vector<std::vector<int>> matrix3 = {
10
    {1, 2, 3},
11
    {4, 5, 6},
12
    {7, 8, 9}
13
};

基本操作

xxxxxxxxxx
21
1
std::vector<int> vec = {1, 2, 3, 4, 5};
2

3
// 下标访问（不检查边界）
4
int val1 = vec[0];        // 第一个元素
5
int val2 = vec[4];        // 最后一个元素
6
vec[0] = 10;              // 修改元素
7

8
// at()访问（检查边界，抛出异常）
9
int val3 = vec.at(0);
10
try {
11
    int val4 = vec.at(10);  // 越界，抛出std::out_of_range
12
} catch(const std::out_of_range& e) {
13
    std::cout << "Index out of range: " << e.what() << std::endl;
14
}
15

16
// 首尾元素访问
17
int first = vec.front();  // 第一个元素
18
int last = vec.back();    // 最后一个元素
19

20
// 获取底层数组指针
21
int* ptr = vec.data();    // C++11

xxxxxxxxxx
14
1
std::vector<int> vec = {1, 2, 3, 4, 5};
2

3
// 大小相关
4
size_t size = vec.size();           // 当前元素个数
5
size_t capacity = vec.capacity();   // 当前容量
6
size_t max_size = vec.max_size();   // 理论最大容量
7
bool empty = vec.empty();           // 是否为空
8

9
// 容量管理
10
vec.reserve(100);                   // 预留容量，避免频繁重新分配
11
vec.shrink_to_fit();               // 释放多余容量（C++11）
12

13
std::cout << "Size: " << vec.size() << std::endl;
14
std::cout << "Capacity: " << vec.capacity() << std::endl;

xxxxxxxxxx
17
1
std::vector<int> vec;
2

3
// 尾部添加
4
vec.push_back(1);                   // 添加单个元素
5
vec.emplace_back(2);               // 就地构造（C++11）
6

7
// 插入元素
8
vec.insert(vec.begin(), 0);         // 在开头插入0
9
vec.insert(vec.begin() + 1, 5, 10); // 在位置1插入5个10
10
vec.insert(vec.end(), {7, 8, 9});   // 在末尾插入初始化列表
11

12
// 从其他容器插入
13
std::vector<int> other = {20, 21, 22};
14
vec.insert(vec.end(), other.begin(), other.end());
15

16
// emplace插入（C++11）
17
vec.emplace(vec.begin() + 2, 15);   // 在位置2就地构造元素15

xxxxxxxxxx
14
1
std::vector<int> vec = {1, 2, 3, 4, 5, 3, 6};
2

3
// 删除尾部元素
4
vec.pop_back();
5

6
// 删除指定位置元素
7
vec.erase(vec.begin());             // 删除第一个元素
8
vec.erase(vec.begin() + 1, vec.begin() + 3); // 删除范围[1,3)
9

10
// 删除所有等于某值的元素
11
vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());
12

13
// 清空所有元素
14
vec.clear();

xxxxxxxxxx
13
1
std::vector<int> vec = {1, 2, 3};
2

3
// 调整大小
4
vec.resize(5);          // 扩大到5个元素，新元素默认初始化
5
vec.resize(7, 10);      // 扩大到7个元素，新元素初始化为10
6
vec.resize(3);          // 缩小到3个元素
7

8
// 赋值操作
9
vec.assign(5, 100);     // 赋值为5个100
10
vec.assign({1, 2, 3, 4}); // 赋值为初始化列表
11

12
std::vector<int> other = {10, 20, 30};
13
vec.assign(other.begin(), other.end()); // 从其他容器赋值

迭代器

xxxxxxxxxx
13
1
std::vector<int> vec = {1, 2, 3, 4, 5};
2

3
// 正向迭代器
4
std::vector<int>::iterator it = vec.begin();
5
std::vector<int>::const_iterator cit = vec.cbegin();
6

7
// 反向迭代器
8
std::vector<int>::reverse_iterator rit = vec.rbegin();
9
std::vector<int>::const_reverse_iterator crit = vec.crbegin();
10

11
// auto关键字（C++11）
12
auto it2 = vec.begin();
13
auto cit2 = vec.cbegin();

xxxxxxxxxx
22
1
std::vector<int> vec = {1, 2, 3, 4, 5};
2

3
// 传统for循环
4
for(auto it = vec.begin(); it != vec.end(); ++it) {
5
    std::cout << *it << " ";
6
    *it *= 2;  // 修改元素
7
}
8

9
// 范围for循环（C++11）
10
for(const auto& element : vec) {
11
    std::cout << element << " ";
12
}
13

14
// 修改版本
15
for(auto& element : vec) {
16
    element *= 2;
17
}
18

19
// 反向遍历
20
for(auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
21
    std::cout << *rit << " ";
22
}

算法

xxxxxxxxxx
33
1
#include <algorithm>
2
#include <numeric>
3

4
std::vector<int> vec = {5, 2, 8, 1, 9, 3};
5

6
// 排序
7
std::sort(vec.begin(), vec.end());                    // 升序
8
std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序
9

10
// 查找
11
auto it = std::find(vec.begin(), vec.end(), 5);
12
if(it != vec.end()) {
13
    std::cout << "Found at position: " << it - vec.begin() << std::endl;
14
}
15

16
// 计数
17
int count = std::count(vec.begin(), vec.end(), 5);
18

19
// 累加
20
int sum = std::accumulate(vec.begin(), vec.end(), 0);
21

22
// 变换
23
std::transform(vec.begin(), vec.end(), vec.begin(), 
24
               [](int x) { return x * 2; });
25

26
// 过滤（移除）
27
vec.erase(std::remove_if(vec.begin(), vec.end(), 
28
                        [](int x) { return x % 2 == 0; }), 
29
          vec.end());
30

31
// 二分查找（需要先排序）
32
std::sort(vec.begin(), vec.end());
33
bool found = std::binary_search(vec.begin(), vec.end(), 5);

内部实现原理

内存布局

xxxxxxxxxx
13
1
// vector的典型实现包含三个指针
2
template<typename T>
3
class vector {
4
private:
5
    T* start;        // 指向第一个元素
6
    T* finish;       // 指向最后一个元素的下一位置
7
    T* end_of_storage; // 指向分配内存的末尾
8
    
9
public:
10
    size_t size() const { return finish - start; }
11
    size_t capacity() const { return end_of_storage - start; }
12
    bool empty() const { return start == finish; }
13
};

动态扩容机制

xxxxxxxxxx
18
1
// 扩容示例
2
void demonstrate_capacity() {
3
    std::vector<int> vec;
4
    
5
    for(int i = 0; i < 20; ++i) {
6
        vec.push_back(i);
7
        std::cout << "Size: " << vec.size() 
8
                  << ", Capacity: " << vec.capacity() << std::endl;
9
    }
10
    
11
    // 输出可能类似：
12
    // Size: 1, Capacity: 1
13
    // Size: 2, Capacity: 2
14
    // Size: 3, Capacity: 4
15
    // Size: 4, Capacity: 4
16
    // Size: 5, Capacity: 8
17
    // ...
18
}

扩容策略

• 增长因子：通常为1.5或2

• 重新分配：当容量不足时，分配新的更大内存块

• 元素移动：将旧元素移动到新内存位置

• 释放旧内存：释放原来的内存块

应用

xxxxxxxxxx
54
1
// 读取不定数量的输入
2
std::vector<int> read_numbers() {
3
    std::vector<int> numbers;
4
    int num;
5
    
6
    while(std::cin >> num) {
7
        numbers.push_back(num);
8
    }
9
    
10
    return numbers;
11
}
12

13
// 矩阵运算
14
class Matrix {
15
private:
16
    std::vector<std::vector<double>> data;
17
    size_t rows, cols;
18
    
19
public:
20
    Matrix(size_t r, size_t c) : rows(r), cols(c) {
21
        data.resize(rows, std::vector<double>(cols, 0.0));
22
    }
23
    
24
    double& operator()(size_t i, size_t j) {
25
        return data[i][j];
26
    }
27
    
28
    const double& operator()(size_t i, size_t j) const {
29
        return data[i][j];
30
    }
31
};
32

33
// 缓存系统
34
template<typename T>
35
class Cache {
36
private:
37
    std::vector<T> buffer;
38
    size_t capacity;
39
    size_t current_size;
40
    
41
public:
42
    Cache(size_t cap) : capacity(cap), current_size(0) {
43
        buffer.reserve(capacity);
44
    }
45
    
46
    void add(const T& item) {
47
        if(current_size < capacity) {
48
            buffer.push_back(item);
49
            ++current_size;
50
        } else {
51
            // 实现LRU或其他替换策略
52
        }
53
    }
54
};

总结

选择vector的场景：

• 需要随机访问元素

• 主要在尾部进行插入/删除操作

• 需要连续内存布局

• 元素数量动态变化

避免使用vector的场景：

• 频繁在中间或开头插入/删除

• 需要稳定的迭代器和引用

• 对内存使用有严格限制

deque

std::deque（double-ended queue，双端队列）是C++ STL中的一个序列容器，支持在两端进行高效的插入和删除操作。

基本特性

• 双端操作：在头部和尾部都能进行O(1)的插入和删除

• 随机访问：支持O(1)时间复杂度的随机访问

• 动态大小：运行时可以改变大小

• 分段连续：内部使用分段的连续内存块

• 稳定的迭代器：中间插入/删除不会使两端的迭代器失效

xxxxxxxxxx
2
1
#include <deque>
2
using namespace std;  // 或使用 std::deque

声明和初始化

xxxxxxxxxx
25
1
// 空deque
2
std::deque<int> dq1;
3

4
// 指定大小
5
std::deque<int> dq2(10);           // 10个元素，默认值为0
6
std::deque<int> dq3(10, 5);        // 10个元素，每个值为5
7

8
// 初始化列表（C++11）
9
std::deque<int> dq4 = {1, 2, 3, 4, 5};
10
std::deque<int> dq5{1, 2, 3, 4, 5};
11

12
// 拷贝构造
13
std::deque<int> dq6(dq4);
14
std::deque<int> dq7 = dq4;
15

16
// 移动构造（C++11）
17
std::deque<int> dq8 = std::move(dq4);
18

19
// 从数组初始化
20
int arr[] = {1, 2, 3, 4, 5};
21
std::deque<int> dq9(arr, arr + 5);
22

23
// 从其他容器初始化
24
std::vector<int> vec = {1, 2, 3, 4, 5};
25
std::deque<int> dq10(vec.begin(), vec.end());

基本操作

xxxxxxxxxx
18
1
std::deque<int> dq = {1, 2, 3, 4, 5};
2

3
// 下标访问（不检查边界）
4
int val1 = dq[0];        // 第一个元素
5
int val2 = dq[4];        // 最后一个元素
6
dq[0] = 10;              // 修改元素
7

8
// at()访问（检查边界，抛出异常）
9
int val3 = dq.at(0);
10
try {
11
    int val4 = dq.at(10);  // 越界，抛出std::out_of_range
12
} catch(const std::out_of_range& e) {
13
    std::cout << "Index out of range: " << e.what() << std::endl;
14
}
15

16
// 首尾元素访问
17
int first = dq.front();  // 第一个元素
18
int last = dq.back();    // 最后一个元素

xxxxxxxxxx
9
1
std::deque<int> dq = {1, 2, 3, 4, 5};
2

3
// 大小相关
4
size_t size = dq.size();           // 当前元素个数
5
size_t max_size = dq.max_size();   // 理论最大容量
6
bool empty = dq.empty();           // 是否为空
7

8
std::cout << "Size: " << dq.size() << std::endl;
9
std::cout << "Empty: " << (dq.empty() ? "Yes" : "No") << std::endl;

双端插入和删除

xxxxxxxxxx
17
1
std::deque<int> dq;
2

3
// 尾部操作
4
dq.push_back(1);                   // 尾部添加
5
dq.push_back(2);
6
dq.emplace_back(3);               // 就地构造（C++11）
7
std::cout << dq.back() << std::endl; // 访问尾部元素
8
dq.pop_back();                     // 删除尾部元素
9

10
// 头部操作
11
dq.push_front(0);                  // 头部添加
12
dq.push_front(-1);
13
dq.emplace_front(-2);             // 就地构造（C++11）
14
std::cout << dq.front() << std::endl; // 访问头部元素
15
dq.pop_front();                    // 删除头部元素
16

17
// 结果：dq = {-1, 0, 1, 2}

任意位置插入和删除

xxxxxxxxxx
20
1
std::deque<int> dq = {1, 2, 3, 4, 5};
2

3
// 插入元素
4
dq.insert(dq.begin(), 0);          // 在开头插入0
5
dq.insert(dq.begin() + 2, 5, 10);  // 在位置2插入5个10
6
dq.insert(dq.end(), {7, 8, 9});     // 在末尾插入初始化列表
7

8
// 从其他容器插入
9
std::vector<int> other = {20, 21, 22};
10
dq.insert(dq.end(), other.begin(), other.end());
11

12
// emplace插入（C++11）
13
dq.emplace(dq.begin() + 2, 15);     // 在位置2就地构造元素15
14

15
// 删除元素
16
dq.erase(dq.begin());               // 删除第一个元素
17
dq.erase(dq.begin() + 1, dq.begin() + 3); // 删除范围[1,3)
18

19
// 清空所有元素
20
dq.clear();

调整大小和赋值

xxxxxxxxxx
13
1
std::deque<int> dq = {1, 2, 3};
2

3
// 调整大小
4
dq.resize(5);          // 扩大到5个元素，新元素默认初始化
5
dq.resize(7, 10);      // 扩大到7个元素，新元素初始化为10
6
dq.resize(3);          // 缩小到3个元素
7

8
// 赋值操作
9
dq.assign(5, 100);     // 赋值为5个100
10
dq.assign({1, 2, 3, 4}); // 赋值为初始化列表
11

12
std::vector<int> vec = {10, 20, 30};
13
dq.assign(vec.begin(), vec.end()); // 从其他容器赋值

迭代器

xxxxxxxxxx
13
1
std::deque<int> dq = {1, 2, 3, 4, 5};
2

3
// 正向迭代器
4
std::deque<int>::iterator it = dq.begin();
5
std::deque<int>::const_iterator cit = dq.cbegin();
6

7
// 反向迭代器
8
std::deque<int>::reverse_iterator rit = dq.rbegin();
9
std::deque<int>::const_reverse_iterator crit = dq.crbegin();
10

11
// auto关键字（C++11）
12
auto it2 = dq.begin();
13
auto cit2 = dq.cbegin();

xxxxxxxxxx
22
1
std::deque<int> dq = {1, 2, 3, 4, 5};
2

3
// 传统for循环
4
for(auto it = dq.begin(); it != dq.end(); ++it) {
5
    std::cout << *it << " ";
6
    *it *= 2;  // 修改元素
7
}
8

9
// 范围for循环（C++11）
10
for(const auto& element : dq) {
11
    std::cout << element << " ";
12
}
13

14
// 修改版本
15
for(auto& element : dq) {
16
    element *= 2;
17
}
18

19
// 反向遍历
20
for(auto rit = dq.rbegin(); rit != dq.rend(); ++rit) {
21
    std::cout << *rit << " ";
22
}

内部实现原理

xxxxxxxxxx
21
1
// deque的典型实现结构
2
template<typename T>
3
class deque {
4
private:
5
    T** map;              // 指向块指针数组的指针
6
    size_t map_size;      // map数组的大小
7
    
8
    iterator start;       // 指向第一个元素
9
    iterator finish;      // 指向最后一个元素的下一位置
10
    
11
    static const size_t buffer_size = 512 / sizeof(T);
12
    
13
public:
14
    // 迭代器实现
15
    class iterator {
16
        T* cur;           // 当前元素指针
17
        T* first;         // 当前块的开始
18
        T* last;          // 当前块的结束
19
        T** node;         // 指向当前块的map节点
20
    };
21
};

deque是由多个片段组成的，片段内部是连续的，但是片段之间不连续的，分散的，多个片段被一个称为中控器的结构控制（也称为map，但跟std::map不是一回事）。

所以说deque是在物理上是不连续的，但是逻辑上是连续的。

初始化deque时，根据元素的个数分配一些缓冲区片段

在缓冲区片段中存放实际的元素，这里以int型元素为例。通常情况下，在初始化时第一个元素会被放置在第一个缓冲区中相对靠前的位置（而非第一个缓冲区的首地址，这样方便在头部添加元素）。

前后相邻的两个元素在逻辑上是连续的，但是物理层面上可能并不是连续的。

同时还会生成一个数组中控器（map），存放每个缓冲区片段的首地址。（注意map中的元素是int*，而不是严格意义的数组指针，这一点从源码中可以进行理解）

通常情况下，第一个缓冲区片段的首地址被放在中控器map的居中位置。

deque初始化完成后，进行添加元素的操作：

如果在尾部添加元素value

找到最后一个存放着元素的缓冲区片段，在其中最后一个元素的后面添加元素value。

如果此时最后的缓冲区片段是满的，那么就再申请一个新的缓冲区片段，将要添加的元素value存放在新片段的首个位置。同时中控器也加上一个元素（新片段的首地址），让中控器与新片段联系起来。

如果此时中控器已经满了，还要添加内容，那么开辟新的更大的空间作为中控器，将原本中控器中记录的地址值复制到新的中控器，并将最后一个缓冲区片段的首地址加入。

如果是在deque的头部添加元素value

找到已经存储的第一个元素的位置，在它的前面存放新元素value。

经过若干次头部添加元素之后，如果第一个缓冲区片段满了，还要继续在头部添加元素，则新开辟一个缓冲区片段（作为第一个片段），将value存在这个片段中的最后一个位置。同时在中控器的相应位置存放新的缓冲片段的首地址。

如果一直往deque头部添加元素，中控器的前半部分已经满了，后半部分还没满，就将中控器中记录的地址全都后移，将这个第一个缓冲区的首地址存入中控器的第一个位置。如果中控器全都满了，那就再开辟新的更大的空间作为中控器。

算法

xxxxxxxxxx
32
1
#include <algorithm>
2
#include <numeric>
3

4
std::deque<int> dq = {5, 2, 8, 1, 9, 3};
5

6
// 排序
7
std::sort(dq.begin(), dq.end());                    // 升序
8
std::sort(dq.begin(), dq.end(), std::greater<int>()); // 降序
9

10
// 查找
11
auto it = std::find(dq.begin(), dq.end(), 5);
12
if(it != dq.end()) {
13
    std::cout << "Found at position: " << it - dq.begin() << std::endl;
14
}
15

16
// 计数
17
int count = std::count(dq.begin(), dq.end(), 5);
18

19
// 累加
20
int sum = std::accumulate(dq.begin(), dq.end(), 0);
21

22
// 变换
23
std::transform(dq.begin(), dq.end(), dq.begin(), 
24
               [](int x) { return x * 2; });
25

26
// 过滤（移除）
27
dq.erase(std::remove_if(dq.begin(), dq.end(), 
28
                        [](int x) { return x % 2 == 0; }), 
29
         dq.end());
30

31
// 旋转
32
std::rotate(dq.begin(), dq.begin() + 2, dq.end());

应用

滑动窗口

xxxxxxxxxx
26
1
// 滑动窗口最大值
2
std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
3
    std::deque<int> dq;  // 存储数组下标
4
    std::vector<int> result;
5
    
6
    for(int i = 0; i < nums.size(); ++i) {
7
        // 移除超出窗口的元素
8
        while(!dq.empty() && dq.front() <= i - k) {
9
            dq.pop_front();
10
        }
11
        
12
        // 移除比当前元素小的元素
13
        while(!dq.empty() && nums[dq.back()] <= nums[i]) {
14
            dq.pop_back();
15
        }
16
        
17
        dq.push_back(i);
18
        
19
        // 窗口形成后记录最大值
20
        if(i >= k - 1) {
21
            result.push_back(nums[dq.front()]);
22
        }
23
    }
24
    
25
    return result;
26
}

双端队列应用

xxxxxxxxxx
54
1
// 回文检查
2
bool isPalindrome(const std::string& str) {
3
    std::deque<char> dq;
4
    
5
    // 只添加字母和数字
6
    for(char c : str) {
7
        if(std::isalnum(c)) {
8
            dq.push_back(std::tolower(c));
9
        }
10
    }
11
    
12
    // 从两端比较
13
    while(dq.size() > 1) {
14
        if(dq.front() != dq.back()) {
15
            return false;
16
        }
17
        dq.pop_front();
18
        dq.pop_back();
19
    }
20
    
21
    return true;
22
}
23

24
// 工作窃取队列
25
template<typename T>
26
class WorkStealingQueue {
27
private:
28
    std::deque<T> queue;
29
    mutable std::mutex mtx;
30
    
31
public:
32
    void push(T item) {
33
        std::lock_guard<std::mutex> lock(mtx);
34
        queue.push_back(std::move(item));
35
    }
36
    
37
    bool pop(T& item) {
38
        std::lock_guard<std::mutex> lock(mtx);
39
        if(queue.empty()) return false;
40
        
41
        item = std::move(queue.back());
42
        queue.pop_back();
43
        return true;
44
    }
45
    
46
    bool steal(T& item) {
47
        std::lock_guard<std::mutex> lock(mtx);
48
        if(queue.empty()) return false;
49
        
50
        item = std::move(queue.front());
51
        queue.pop_front();
52
        return true;
53
    }
54
};

缓存系统

xxxxxxxxxx
48
1
// LRU缓存（使用deque实现）
2
template<typename Key, typename Value>
3
class LRUCache {
4
private:
5
    struct CacheItem {
6
        Key key;
7
        Value value;
8
        CacheItem(const Key& k, const Value& v) : key(k), value(v) {}
9
    };
10
    
11
    std::deque<CacheItem> cache;
12
    std::unordered_map<Key, typename std::deque<CacheItem>::iterator> index;
13
    size_t capacity;
14
    
15
public:
16
    LRUCache(size_t cap) : capacity(cap) {}
17
    
18
    Value get(const Key& key) {
19
        auto it = index.find(key);
20
        if(it == index.end()) {
21
            throw std::runtime_error("Key not found");
22
        }
23
        
24
        // 移动到前面（最近使用）
25
        CacheItem item = *it->second;
26
        cache.erase(it->second);
27
        cache.push_front(item);
28
        index[key] = cache.begin();
29
        
30
        return item.value;
31
    }
32
    
33
    void put(const Key& key, const Value& value) {
34
        auto it = index.find(key);
35
        
36
        if(it != index.end()) {
37
            // 更新现有项
38
            cache.erase(it->second);
39
        } else if(cache.size() >= capacity) {
40
            // 移除最久未使用的项
41
            index.erase(cache.back().key);
42
            cache.pop_back();
43
        }
44
        
45
        cache.emplace_front(key, value);
46
        index[key] = cache.begin();
47
    }
48
};

总结

std::deque 是一个功能强大的容器，具有以下优势：

• 双端高效操作：头部和尾部插入删除都是O(1)

• 随机访问支持：支持O(1)的随机访问

• 内存效率：相比vector，不需要预留大量连续内存

• 迭代器稳定性：中间操作对两端迭代器影响较小

适用场景

• 需要频繁在两端进行插入删除操作

• 需要随机访问但不想预分配大量内存

• 实现队列、双端队列等数据结构

• 滑动窗口算法

• 工作窃取队列

注意事项

• 中间插入删除性能不如list

• 随机访问性能略逊于vector

• 内存布局不如vector紧凑

• 迭代器在某些操作后可能失效

选择deque的关键是：当需要双端操作的高效性，同时又需要随机访问能力时，deque是最佳选择。

list

std::list 是 C++ STL 中的双向链表容器，提供了高效的插入和删除操作。

基本特性

• 双向遍历：支持前向和后向迭代

• 非连续存储：元素在内存中不连续存储

• 动态大小：可以在运行时动态增长和收缩

• 稳定的迭代器：插入和删除操作不会使其他位置的迭代器失效

• O(1) 插入删除：在任意位置插入/删除元素的时间复杂度为常数

• 无随机访问：不支持下标访问，只能通过迭代器顺序访问

• 内存效率：只在需要时分配内存，无预分配开销

声明和初始化

xxxxxxxxxx
13
1
#include <list>
2
#include <iostream>
3

4
// 基本声明
5
std::list<int> lst1;                    // 空链表
6
std::list<int> lst2(5);                 // 5个默认值元素
7
std::list<int> lst3(5, 10);             // 5个值为10的元素
8
std::list<int> lst4{1, 2, 3, 4, 5};     // 初始化列表
9
std::list<int> lst5(lst4);              // 拷贝构造
10
std::list<int> lst6(lst4.begin(), lst4.end()); // 迭代器范围构造
11

12
// 自定义类型
13
std::list<std::string> strList{"hello", "world", "list"};

基本操作

xxxxxxxxxx
8
1
std::list<int> lst{1, 2, 3, 4, 5};
2

3
// 访问首尾元素
4
int front = lst.front();    // 获取第一个元素：1
5
int back = lst.back();      // 获取最后一个元素：5
6

7
// 注意：list不支持随机访问，没有operator[]
8
// lst[2];  // 编译错误！

xxxxxxxxxx
5
1
std::list<int> lst{1, 2, 3};
2

3
bool isEmpty = lst.empty();     // 检查是否为空
4
size_t size = lst.size();       // 获取元素个数：3
5
// list没有capacity概念，因为是链表结构

xxxxxxxxxx
20
1
std::list<int> lst;
2

3
// 前端添加
4
lst.push_front(1);              // [1]
5
lst.push_front(0);              // [0, 1]
6

7
// 后端添加
8
lst.push_back(2);               // [0, 1, 2]
9
lst.push_back(3);               // [0, 1, 2, 3]
10

11
// 就地构造
12
lst.emplace_front(-1);          // [-1, 0, 1, 2, 3]
13
lst.emplace_back(4);            // [-1, 0, 1, 2, 3, 4]
14

15
// 任意位置插入
16
auto it = lst.begin();
17
std::advance(it, 2);            // 移动到第3个位置
18
lst.insert(it, 99);             // [-1, 0, 99, 1, 2, 3, 4]
19
lst.insert(it, 3, 88);          // 插入3个88
20
lst.insert(it, {77, 66});       // 插入初始化列表

xxxxxxxxxx
25
1
std::list<int> lst{1, 2, 3, 2, 4, 2, 5};
2

3
// 删除首尾元素
4
lst.pop_front();                // 删除第一个元素
5
lst.pop_back();                 // 删除最后一个元素
6

7
// 删除指定位置
8
auto it = lst.begin();
9
std::advance(it, 1);
10
lst.erase(it);                  // 删除第2个元素
11

12
// 删除范围
13
auto start = lst.begin();
14
auto end = lst.begin();
15
std::advance(end, 2);
16
lst.erase(start, end);          // 删除前两个元素
17

18
// 删除特定值
19
lst.remove(2);                  // 删除所有值为2的元素
20

21
// 条件删除
22
lst.remove_if([](int x) { return x > 3; }); // 删除所有大于3的元素
23

24
// 清空
25
lst.clear();                    // 删除所有元素

xxxxxxxxxx
13
1
std::list<int> lst;
2

3
// 调整大小
4
lst.resize(5);                  // 调整为5个元素，新元素为默认值
5
lst.resize(8, 99);              // 调整为8个元素，新元素为99
6
lst.resize(3);                  // 缩小到3个元素
7

8
// 赋值操作
9
lst.assign(5, 10);              // 赋值为5个10
10
lst.assign({1, 2, 3, 4});       // 赋值为初始化列表
11

12
std::list<int> other{7, 8, 9};
13
lst.assign(other.begin(), other.end()); // 赋值为其他容器的范围

迭代器

xxxxxxxxxx
11
1
std::list<int> lst{1, 2, 3, 4, 5};
2

3
// 双向迭代器
4
std::list<int>::iterator it = lst.begin();
5
std::list<int>::const_iterator cit = lst.cbegin();
6
std::list<int>::reverse_iterator rit = lst.rbegin();
7
std::list<int>::const_reverse_iterator crit = lst.crbegin();
8

9
// C++11 auto简化
10
auto it2 = lst.begin();
11
auto cit2 = lst.cbegin();

xxxxxxxxxx
23
1
std::list<int> lst{1, 2, 3, 4, 5};
2

3
// 前向遍历
4
for (auto it = lst.begin(); it != lst.end(); ++it) {
5
    std::cout << *it << " ";
6
}
7

8
// 反向遍历
9
for (auto rit = lst.rbegin(); rit != lst.rend(); ++rit) {
10
    std::cout << *rit << " ";
11
}
12

13
// 范围for循环（推荐）
14
for (const auto& elem : lst) {
15
    std::cout << elem << " ";
16
}
17

18
// 迭代器移动
19
auto it = lst.begin();
20
++it;                           // 前进一步
21
--it;                           // 后退一步
22
std::advance(it, 3);            // 前进3步
23
std::advance(it, -2);           // 后退2步

list特有操作

1. 拼接操作

xxxxxxxxxx
15
1
std::list<int> lst1{1, 2, 3};
2
std::list<int> lst2{4, 5, 6};
3
std::list<int> lst3{7, 8, 9};
4

5
// 拼接整个链表
6
lst1.splice(lst1.end(), lst2);  // lst1: [1,2,3,4,5,6], lst2: []
7

8
// 拼接单个元素
9
auto it = lst3.begin();
10
lst1.splice(lst1.begin(), lst3, it); // 移动lst3的第一个元素到lst1开头
11

12
// 拼接范围
13
auto start = lst3.begin();
14
auto end = lst3.end();
15
lst1.splice(lst1.end(), lst3, start, end); // 移动lst3剩余元素到lst1末尾