前言
最近写召回、混排算子的时候需要用c ，对我来说就是纯新手入门，这里记录一些常见到的容器和他们的一些特性。
C 容器属于标准库里STL（StandardTemplateLibrary）里面内容，因此同样是使用std作为namespace。另外，标准库中包含很多的头文件，其中和STL相关的头文件有几十上百个。在使用STL的时候，也需要把这些头文件包含到自己的项目中来，现代版本标准库中的头文件名字，已经把.h扩展名去掉，变成了没有扩展名的头文件。比如：
代码语言：javascript复制#include<iostream>
#include<vector>STL里面的容器有很多，本文这里仅以作者实际使用过程中常见的两种容器：vector、unordered_map为例，简单介绍讨论一下。
1. vector
std::vector是C 标准库中的单端数组，其属于顺序容器（Sequence Containers），同时内存分配是连续的，当容量不足以容纳新元素时，它会自动重新分配一块更大的内存区域，然后将现有元素复制到新的内存区域。
从下图可以看出来，往尾端加入元素和从尾端删除元素都应该比较快速；而从中间插入元素比较困难，同时查找速度越不会很快。
1. 创建与初始化vector：
代码语言：javascript复制#include <vector>
std::vector<int> vec = {1, 2, 3, 4, 5}; // 使用初始化列表创建并初始化vector
vec.assign(6, 10); // 将vector的内容替换为6个值为10的元素
std::fill(vec.begin(), vec.end(), 0); // 将vector中的所有元素设置为02. 访问元素：
代码语言：javascript复制int first = vec[0]; // 获取第一个元素
int second = vec.at(1); // 获取第二个元素3. 遍历元素：
for (const auto &elem : vec)这种写法是C 11的新特性，叫做“基于范围的for循环”（Range-based for loop），无需使用迭代器或索引即可遍历访问。
// 范围for循环（推荐）
for (const auto &elem : vec) {
std::cout << elem << " ";
}
// 迭代器
for (auto it = vec.begin(); it != vec.end(); it) {
std::cout << *it << " ";
}
// 索引
for (size_t i = 0; i < vec.size(); i) {
std::cout << vec[i] << " ";
}4. 添加元素：
注意push_back和emplace_back在功能上是没有区别的。emplace_back是C 11的新加的，相比于push_back，emplace_back可以直接在std::vector中构造新元素，从而避免了额外的拷贝或移动操作。因此，尽量使用emplace_back。
vec.push_back(1); // 在尾部添加一个整数1（不推荐）
vec.emplace_back(1); // 在尾部添加一个整数1（推荐）
vec.insert(vec.begin() 1, 3); // 在第二个位置插入整数3
vec1.insert(vec1.end(), vec2.begin(), vec2.end()); // 将vec2拼接到vec15. 删除元素：
因为迭代器.begin()重载了运算符 ，因此可以使用vec.begin() 2这种形式来选择第三个元素。
vec.erase(vec.begin() 2); // 删除第三个元素
vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end()); // 删除值为3的元素
vec.pop_back(); // 删除最后一个元素
vec.clear(); // 删除所有元素6. 查找第一个出现的元素：
如果要查找所有匹配的元素，加一个while循环 迭代器就可以实现了。
代码语言：javascript复制#include <algorithm>
int target = 3;
auto it = std::find(vec.begin(), vec.end(), target);
if (it != vec.end()) {
std::cout << "Found " << target << " at position " << std::distance(vec.begin(), it) << std::endl;
} else {
std::cout << "Not found" << std::endl;
}7. 排序元素：
排序这里可以自定义排序依据，通常使用lambda函数或者是函数对象作为std::sort的第三个参数
#include <algorithm>
// 默认对vector进行升序排序
std::sort(vec.begin(), vec.end());
// 如果有其他需求，则需要使用 lambda 表达式，比如降序
std::sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });8. 其他：
代码语言：javascript复制size_t size = vec.size(); // 获取vector的大小
bool is_empty = vec.empty(); // 检查vector是否为空
std::reverse(vec.begin(), vec.end()); // 反转vector中的元素顺序2. unordered_map
unordered_map属于无序容器，是C 11里推出的容器。无序容器内部一般是用哈希表来实现的。因为是哈希表，所以提供了快速的查找、插入和删除操作，时间复杂度接近 O(1)。
1. 创建与初始化unordered_map：
代码语言：javascript复制#include <unordered_map>
std::unordered_map<int, std::string> umap = {{1, "one"}, {2, "two"}, {3, "three"}}; // 使用初始化列表创建并初始化unordered_map2. 访问元素：
代码语言：javascript复制std::string value1 = umap[1]; // 使用下标操作符访问键为1的元素
std::string value2 = umap.at(2); // 使用at()访问键为2的元素3. 遍历元素：
遍历元素和vector一样，推荐使用Range-based for loop的形式。
代码语言：javascript复制// 范围for循环（推荐）
for (const auto &elem : umap) {
std::cout << "Key: " << elem.first << ", Value: " << elem.second << std::endl;
}
// 迭代器
for (auto it = umap.begin(); it != umap.end(); it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}4. 添加元素：
和vector一样，emplace 是 C 11 引入的新特性，它允许在容器中就地构造元素。这意味着不需要先创建键值对对象，然后再将其插入到容器中。emplace 可以避免额外的拷贝或移动操作，提高性能。
umap[4] = "four"; // 使用下标操作符添加一个键值对
umap.insert({5, "five"}); // 使用insert()添加一个键值对（不推荐）
umap.emplace(6, "six"); // 使用emplace()添加一个键值对（推荐）5. 删除元素：
代码语言：javascript复制umap.erase(1); // 删除键为1的元素
umap.erase(umap.begin()); // 删除第一个元素
umap.clear(); // 清空unordered_map6. 查找元素：
代码语言：javascript复制auto it = umap.find(3);
if (it != umap.end()) {
std::cout << "Found key: " << it->first << ", value: " << it->second << std::endl;
} else {
std::cout << "Not found" << std::endl;
}7. 其他：
代码语言：javascript复制size_t size = umap.size(); // 获取unordered_map的大小
bool is_empty = umap.empty(); // 检查unordered_map是否为空3. unordered_map<int, string>和vector<pair<int, string>>
实际在看别人的代码的时候，会发现有两种写法 unordered_map<int, string>和vector<pair<int, string>>。乍一看感觉功能差不多，实际上有一些细微的差别。
【unordered_map<int, string>优点】：
- 查找效率：哈希表提供了快速的查找、插入和删除操作，时间复杂度接近 O(1)。
- 键的唯一性：每个键在容器中是唯一的，每个键只能对应一个值。（看使用场景，也不一定是优点）
【unordered_map<int, string>缺点】：
- 无序：哈希表中的元素是无序的，无法保证按照插入顺序进行迭代。
- 空间开销：哈希表通常需要更多的内存空间来存储元素和哈希桶。
- 内存分配：哈希表可能需要动态地重新分配内存以调整哈希桶的数量。
【vector<pair<int, string>>优点】：
- 有序：元素按照插入顺序存储，可以按照插入顺序进行迭代。
- 空间开销：动态数组通常比哈希表更节省内存空间。
- 随机访问：vector 提供了快速的随机访问，时间复杂度为 O(1)。
【vector<pair<int, string>>缺点】：
- 查找效率：查找特定键的操作可能需要遍历整个数组，时间复杂度为 O(n)。
- 插入和删除效率：在数组的中间插入或删除元素可能导致其他元素的移动，时间复杂度为 O(n)。
- 重复键：vector 允许存储具有相同整数值的多个元素。（看使用场景，也不一定是缺点）
总得来说，首先需要考虑key是不是唯一性，如果不是唯一的，unordered_map肯定就不用考虑了。剩下的就是性能问题，unordered_map更是一种空间换时间的策略，可以通过使用场景进行评估是否使用。
