一、容器和容器适配器概述

容器（Containers）的主要功能是存储一组元素，可以是基本数据类型（如整数、字符串）或自定义对象（如类的实例）。
容器已经帮我们封装好了数据结构（数组，链表，栈，队列，树，哈希表）以及数据结构的增删查改的操作。

• 顺序容器：元素按线性顺序存储，可通过位置访问
• 关联容器：元素通过键（Key）存储，支持快速查找。
  

容器适配器是对现有容器的封装，提供特定的接口和行为。它们本身不是容器，而是通过封装其他容器来实现特定功能。
常见的有：栈、队列、优先队列

二、容器之有序容器

2.1Vector（动态数组）

核心特性：

• 动态扩容：array 大小固定，vector无需预先制定大小，能自动重新分配更大的空间（通常按2倍扩容）
• 支持随机访问。

直接构造：

// 创建空vector，存储int类型
vector<int> v1;     
// 大小为5，默认值为0的向量             
vector<int> v2(5);               
// 大小为5，默认值为10的向量
vector<int> v3(5, 10);          
// 初始化列表 
vector<int> v4 = {1, 2, 3};      
// 从迭代器范围构造，复制v4的元素
vector<int> v5(v4.begin(), v4.end());  

构造二维数组：

//初始化的二维数组
vector<vector<int>> matrix;
vector<vector<int>> matrix = {
    {1, 2, 3},  
    {4, 5, 6},  
    {7, 8, 9}   
};
// 构造一个3行4列的二维数组，初始值全为0
vector<vector<int>> matrix(3, vector<int>(4, 0));

操作	方法
预先分配大小	v.reserve(100)【等同于vector <int> v(100)】
随机访问	v[10]【不检查越界】、v.at(10)【检查越界】
返回第一个元素	v.front()
返回最后一个元素	v.back()
返回当前分配的容量	v.capacity()
返回当前元素数量	v.size()
修改向量的长度	v.resize(5,3)【改长：新增元素会被默认初始化或用指定值填充。改短：尾部元素直接删除】
判空	v.empty()
清空所有元素	v.clear()
尾部插入	v.push_back(42)
尾部删除	v.pop_back()

指定位置插入：

vector<int> v = {1, 2, 4, 5};

// 在第3个元素前插入3（位置为v.begin()+2）
v.insert(v.begin() + 2, 3);  // v变为 {1, 2, 3, 4, 5}
// 在开头插入2个0
v.insert(v.begin(), 2, 0);  // v变为 {0, 0, 1, 2, 3, 4, 5}
// 插入初始化列表
v.insert(v.begin(), {7, 8});  // v变为 {7, 8, 0, 0, 1, 2, 3, 4, 5, 9, 10}
// 从另一个容器插入元素
vector<int> source = {9, 10};
v.insert(v.end(), source.begin(), source.end());  // v变为 {0, 0, 1, 2, 3, 4, 5, 9, 10}

指定位置删除：

vector<int> v = {1, 2, 3, 4, 5};

// 删除第3个元素（位置为v.begin()+2）
v.erase(v.begin() + 2);  // v变为 {1, 2, 4, 5}
// 删除区间[begin+1, begin+3)的元素（即删除第2和第3个元素）
v.erase(v.begin() + 1, v.begin() + 3);  // v变为 {1, 5}

迭代器遍历：

// C++11范围for循环
for (int num : v) {
    cout << num << endl;
}

2.2string（字符串）

2.3list（双向链表）

2.4deque（双端队列）

四、容器之关联容器

4.1map（有序键值对）

map用于存储键值对（Key-Value Pair），且所有键（Key）唯一且自动排序（默认按升序排列）。
底层通常基于红黑树（一种自平衡二叉搜索树），插入、删除、查找操作的时间复杂度均为 O(log n)。

容器	键的唯一性	元素顺序
map	唯一（一对一映射）	按键排序
multimap	可重复（一对多映射）	按键排序
unordered_map	唯一（一对一映射）	无序
unordered_multimap	可重复（一对多映射）	无序

基本构造方法：

// 自定义升序排列
map<string, int> ages;
// 按键的降序排列
map<string, int, greater<string>> ages;
// 使用初始化列表构造
map<string, int> ages = {
    {"Alice", 25},
    {"Bob", 20},
    {"Charlie", 30}
};
//拷贝构造
map<string, int> ages1 = {{"Alice", 25}, {"Bob", 20}};
map<string, int> ages2(ages1);  // 复制ages1到ages2

自定义比较函数构造：

// 自定义比较器（按字符串长度排序）
struct Compare {
    bool operator()(const string& a, const string& b) const {
        return a.length() < b.length();
    }
};

map<string, int, Compare> ages_by_length;

查找元素：

• 使用下标操作符[10]（若键不存在，会创建默认值）
• 使用at(10)（若键不存在，抛出out_of_range异常
• find(10)（返回迭代器，若未找到，返回end()迭代器）
• count(10) 统计元素出现次数（只能返回整型 0 或 1）

int alice_age = ages["Alice"];  // 若"Alice"存在，返回值；否则创建"Alice"并初始化为0

int bob_age = ages.at("Bob");  // 安全访问，推荐用于检查键是否存在

auto it = ages.find("Charlie");
if (it != ages.end()) {
    cout << "Charlie's age: " << it->second << endl;
}

• lower_bound(3)：返回第一个大于等于 value 的元素的迭代器
• upper_bound(3)：返回第一个大于 value 的元素的迭代器

// 查找并获取迭代器
auto it = ages.find("Alice");
if (it != ages.end()) {
    cout << "Alice's age: " << it->second << endl;
}
// 范围查找（lower_bound/upper_bound/equal_range）
auto low = ages.lower_bound("Alice");  // 第一个>= "Alice"的元素
auto up = ages.upper_bound("Alice");   // 第一个> "Alice"的元素

• begin()，end()：返回指向首尾的迭代器（支持正向遍历）
• rbegin()，rend()：返回反向迭代器（支持逆向遍历）

// 方式1：使用范围for循环（C++11+）
for (const auto& pair : ages) {
    cout << pair.first << ": " << pair.second << endl;
}

// 方式2：使用迭代器
for (auto it = ages.begin(); it != ages.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
}

// 逆序遍历（按键的降序）
for (auto it = ages.rbegin(); it != ages.rend(); ++it) {
    cout << it->first << ": " << it->second << endl;
}

增加元素：

• 使用insert()插入pair
• 使用下标操作符[]（若键不存在，会自动创建）

ages.insert({"Alice", 25});
ages.insert(make_pair("Bob", 20));

ages["Charlie"] = 30;
ages["Alice"] = 26;  // 修改已存在的键对应的值

删除元素：

• erase() 括号内能放1、指定单个键，2、迭代器所指向的元素，3、迭代器区间的元素
• clear() 清空集合

ages.erase("Bob");

auto it = ages.find("Charlie");
if (it != ages.end()) {
    ages.erase(it);
}

ages.erase(ages.begin(), ages.end());  // 清空map

操作	方法
最大可能容量	map.max_size()
集合内元素的数量	map.szie()
集合判空	map.empty()

4.2set（有序集合）

set是集合，有互异性、确定性等特点，因此插入重复元素时会被自动忽略，且元素会自动排序（默认按升序排列）
集合可以通过迭代器遍历，但是无法通过下标进行遍历。

容器	元素唯一性	元素顺序
set	唯一	有序
multiset	可重复	有序
unordered_set	唯一	无序
unordered_multiset	可重复	无序

基本构造方法：

// 默认构造
set<int> set={1,2,3,2}
// 降序排列的set
set<int, greater<int>> s;

从已有容器构造：

vector<int> v = {3, 1, 4, 1, 5};
set<int> s(v.begin(), v.end());  // 存储 {1, 3, 4, 5}（去重且排序）

自定义类型构造：

struct Person {
    string name;
    int age;
    // 重载<运算符，定义排序规则（必须严格弱序）
    bool operator<(const Person& other) const {
        return age < other.age;  // 按年龄升序排列
    }
};
set<Person> people;

查找元素：

• find(10) 返回迭代器。若未找到，返回end()迭代器
• count(10) 统计元素出现次数（set 中只能是 0 或 1）

set<int> s = {1, 2, 3};
auto it = s.find(2);        // it指向2
if (it != s.end()) {
    cout << *it;            // 输出2
}
cout << s.count(3);

• lower_bound(3)：返回第一个大于等于 value 的元素的迭代器
• upper_bound(3)：返回第一个大于 value 的元素的迭代器
• begin()，end()：返回指向首尾的迭代器（支持正向遍历）
• rbegin()，rend()：返回反向迭代器（支持逆向遍历）

set<int> s = {1, 3, 5, 7};
auto it1 = s.lower_bound(3); // it1指向3
auto it2 = s.upper_bound(3); // it2指向5
auto range = s.equal_range(3); // 返回{指向3的迭代器, 指向5的迭代器}

// 示例：正向遍历
for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " "; // 输出: 1 2 3
}
// 示例：反向遍历（降序）
for (auto it = s.rbegin(); it != s.rend(); ++it) {
    cout << *it << " "; // 输出: 3 2 1
}

增加元素：

• insert() 括号内能放1、指定单个值，2、列表（多个值），3、迭代器区间

set<int> s;
s.insert(3);                // 1、插入3，返回{iterator指向3, true}
s.insert(3);                // 1、重复插入，返回{iterator指向3, false}
s.insert({1, 2, 3});        // 2、插入{1, 2}（3已存在，忽略）
vector<int> v = {4, 5};
s.insert(v.begin(), v.end()); //3、 插入{4, 5}

删除元素：

• erase() 括号内能放1、指定单个值，2、迭代器所指向的元素，3、迭代器区间的元素
• clear() 清空集合

set<int> s = {1, 2, 3, 4, 5};
s.erase(3);                 // 1、删除3，s={1, 2, 4, 5}
auto it = s.find(4);
s.erase(it);                // 2、删除4，s={1, 2, 5}
s.erase(s.begin(), s.end()); // 3、清空s

操作	方法
最大可能容量	set.max_size()
集合内元素的数量	set.szie()
集合判空	set.empty()

五、容器适配器

栈和队列：

• stack 和 queue 默认使用 deque作为底层容器。
• 栈和队列只能通过默认构造或复制已有容器初始化，不支持直接用初始化列表。
• 栈和队列没有.clear()这个方法，且都不支持不可以访问内部元素。

优先队列：

• priority_queue 默认使用 vector作为底层容器。
• 不能访问内部元素，只能访问堆顶。
• 优先队列不保证除堆顶外的元素有序，仅确保堆顶元素是最大 / 最小值。

5.1stack（栈）

基本构造方法：

// 默认使用deque作为底层容器
stack<int> s1;
// 显式指定底层容器为vector
stack<int, vector<int>> s2;

从已有容器构造：

vector<int> v = {1, 2, 3};
// 用vector初始化栈（元素顺序不变，但栈的弹出顺序相反）
stack<int, vector<int>> s(v);  // 栈内元素：栈顶→3→2→1

操作	方法
入栈	st.push(10)
出栈	st.pop()
栈顶元素	st.top()
栈内元素的数量	st.szie()
判空	st.empty()

5.2queue（队列）

直接构造方法：

// 默认使用deque作为底层容器
queue<int> q1;
// 显式指定底层容器为list
queue<int, list<int>> q2;

从已有容器构造：

list<int> l = {1, 2, 3};
// 用list初始化队列（元素顺序不变）
queue<int, list<int>> q(l);  // 队列内元素：队首→1→2→3→队尾

操作	方法
入队	que.push(10)
出队	que.pop()
队首元素	que.front()
队尾元素	que.back()
队内元素的数量	que.size()
判空	que.empty()

5.3Priority_queue（优先队列）

优先队列实际上就是堆。

堆的直接初始化：priority_queue(类型，容器，比较器） que

// 默认：最大堆（降序）
priority_queue<int> maxHeap;
// 使用greater<int>实现最小堆（升序）
priority_queue<int, vector<int>, greater<int>> minHeap;

堆从已有容器初始化：

vector<int> v = {3, 1, 4, 1, 5};
// 方式1：逐个插入（效率较低）
priority_queue<int> heap1;
for (int num : v) {
    heap1.push(num);
}
// 方式2：通过构造函数批量初始化（效率更高）
priority_queue<int> heap2(v.begin(), v.end());

自定义类型的优先队列，

struct Person {
    string name;
    int age;
    // 重载<运算符，定义优先级规则
    bool operator<(const Person& other) const {
        return age < other.age;  // 年龄大的优先
    }
};
priority_queue<Person> peopleHeap;

操作	方法
入堆	que.push(10)
出堆	que.pop()
堆顶元素	que.top()
队内元素的数量	que.size()
判空	que.empty()

六、其他

6.1pair（二元组）