💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥
文章目录
- C/C++ | 每日一练 (4)
- 题目
- 参考答案
- 基础容器
- 序列容器
- `std::array`
- `std::vector`
- `std::deque`
- `std::list`
- `std::forward_list`
- 关联容器
- 有序关联容器
- `std::set`
- `std::map`
- `std::multiset`
- `std::multimap`
- 无序关联容器
- `std::unordered_set`
- `std::unordered_map`
- `std::unordered_multiset`
- `std::unordered_multimap`
- 容器适配器
- `std::stack`
- `std::queue`
- `std::priority_queue`
C/C++ | 每日一练 (4)
题目
c++ 中 STL 常见容器有哪些？简述一下底层实现的原理。
参考答案
在 c++ 中根据容器的特点和结构分为如下两大类：
- 基础容器
- 容器适配器
下面基于以上列举的两大类型进行一一总结。
基础容器
在 c++ 标准库中，基础容器是构建其他容器（如容器适配器）的底层实现，它们提供了丰富的数据存储和管理功能。
基础容器主要分为两大类：序列容器和关联容器。
序列容器
序列容器用于存储线性排列的元素，支持随机访问或顺序访问。它们的特点是元素的顺序由插入顺序决定。
c++ 标准库中提供的序列容器有：std::array、std::vector、std::deque、std::list、std::forward_list。
std::array
c++11 引入的固定大小的序列容器，底层是静态数组。它的大小在编译时确定，因此不支持动态大小。
例如：
#include <iostream>
#include <array>
int main()
{
std::array<int, 5> arr = {1, 2, 3, 4, 5};
// 访问元素
std::cout << arr[2] << std::endl; // 3
// 修改元素
arr[2] = 10;
std::cout << arr[2] << std::endl; // 10
// 因为 array 是固定大小的容器，不能动态增加、删除元素
// 遍历
for (int i : arr)
{
std::cout << i << " "; // 1 2 10 4 5
}
std::cout << std::endl;
return 0;
}
std::vector
底层是基于动态数组实现，支持随机访问。它在内存中分配一块连续的空间来存储元素，当容器中的元素数量超过当前分配的空间时，会触发扩容机制，扩容因子根据不同的标准库实现有不同的大小，目前是存在1.5倍和2倍的大小。
例如：
#include <iostream>
#include <vector>
int main()
{
std::vector<int> vec = {1, 2, 3, 4, 5};
// 访问元素
std::cout << vec[2] << std::endl; // 3
// 修改元素
vec[2] = 10;
std::cout << vec[2] << std::endl; // 10
// 在末尾添加元素
vec.push_back(6);
std::cout << vec.back() << std::endl; // 6
// 删除最后一个元素
vec.pop_back();
std::cout << vec.size() << std::endl; // 5
// 遍历
for (int i : vec)
{
std::cout << i << " "; // 1 2 10 4 5
}
std::cout << std::endl;
return 0;
}
std::deque
std::deque的底层结构可以看作是一个指针数组，其中每个指针指向一个固定大小的缓冲区（称为块）。这些块组成了整个 std::deque的数据存储。通过这种结构，std::deque可以在头尾进行高效的插入和删除操作，同时也能提供快速的随机访问。
- 指针数组：
std::deque使用一个数组来存储指向各个数据块（缓冲区）的指针。这个指针数组是连续的，即指针存储在一个连续的数组中。 - 数据块（缓冲区）：每个指针指向一个固定大小的缓冲区，这些缓冲区用于实际存储数据。缓冲区中的数据是连续存储的，但是缓冲区之间在内存中可能不是连续的。其中每个数据块大小是
4096 / sizeof(T)(其中T是存储的类型)
例如：
#include <iostream>
#include <deque>
int main()
{
std::deque<int> dq = {1, 2, 3, 4, 5};
// 访问元素
std::cout << dq[2] << std::endl; // 3
// 修改元素
dq[2] = 10;
std::cout << dq[2] << std::endl; // 10
// 在头部和尾部添加元素
dq.push_front(0);
dq.push_back(6);
std::cout << dq.front() << " and " << dq.back() << std::endl; // 0 and 6
// 删除头部和尾部元素
dq.pop_front();
dq.pop_back();
std::cout << dq.size() << std::endl; // 5
// 遍历
for (int i : dq)
{
std::cout << i << " "; // 1 2 10 4 5
}
std::cout << std::endl;
return 0;
}
std::list
双向链表，每个元素包含一个数据域和两个指针（分别指向前后元素）。它不依赖连续的内存空间。std::list 的大小可以动态增加或减少，允许在常数时间内插入或删除元素（只需调整指针）。另外 std::list 不支持随机访问，访问元素时需要从链表头或尾开始遍历。
例如：
#include <iostream>
#include <list>
int main()
{
std::list<int> lst = {1, 2, 3, 4, 5};
// 访问第一个元素
std::cout << lst.front() << std::endl; // 1
// 修改第一个元素
lst.front() = 10;
std::cout << lst.front() << std::endl; // 10
// 在头部和尾部添加元素
lst.push_front(0);
lst.push_back(6);
std::cout << lst.front() << " and " << lst.back() << std::endl; // 0 and 6
// 删除第一个和最后一个元素
lst.pop_front();
lst.pop_back();
std::cout << lst.size() << std::endl; // 5
// 遍历
for (int i : lst)
{
std::cout << i << " "; // 10 2 3 4 5
}
std::cout << std::endl;
return 0;
}
std::forward_list
单向链表，每个元素只包含一个数据域和一个指针（指向后元素），只能单向遍历。与 std::list 一样不依赖于连续的内存空间，可以在常数时间内操作元素（调整指针），也同样不支持随机访问，访问元素时需要从链表头或尾开始遍历。
例如：
#include <iostream>
#include <forward_list>
int main()
{
std::forward_list<int> flst = {1, 2, 3, 4, 5};
// 访问第一个元素
std::cout << flst.front() << std::endl; // 1
// 修改第一个元素
flst.front() = 10;
std::cout << flst.front() << std::endl; // 10
// 在头部添加元素
flst.push_front(0);
std::cout << flst.front() << std::endl; // 0
// 删除第一个元素
flst.pop_front();
std::cout << flst.front() << std::endl; // 10
// 遍历
for (int i : flst)
{
std::cout << i << " "; // 10 2 3 4 5
}
std::cout << std::endl;
return 0;
}
关联容器
在 c++ 标准库中，关联容器是一类特殊的容器，用于存储键值对，并根据键的值自动组织数据。
c++ 标准库提供了两种主要的关联容器类型，如下所示：
- 有序关联容器：
std::set、std::map、std::multiset、std::multimap。 - 无序关联容器：
std::unordered_set、std::unordered_map、std::unordered_multiset、std::unordered_multimap。
有序关联容器
std::set
存储唯一的键，所有元素按照键的顺序自动排序。std::set 底层使用红黑树实现，因此具有高效的插入、删除和查找操作。
例如：
#include <iostream>
#include <set>
int main()
{
std::set<int> mySet;
// 增：插入元素
mySet.insert(10);
mySet.insert(20);
mySet.insert(30);
mySet.insert(20); // 重复元素不会插入
// 查找元素
auto it = mySet.find(20);
if (it != mySet.end())
{
std::cout << *it << std::endl; // 20
}
else
{
std::cout << "Not found!" << std::endl;
}
// set 的键值不可直接修改，需要删除后重新插入
mySet.erase(it); // 删除元素
mySet.insert(25); // 插入新值
// 删除元素
mySet.erase(30);
// 遍历
for (const auto &value : mySet)
{
std::cout << value << " "; // 10 25
}
std::cout << std::endl;
return 0;
}
std::map
以键值对的形式存储数据，键唯一，并且所有元素都按键的顺序自动排序。std::map 底层使用红黑树实现，因此具有高效的插入、删除和查找操作。
例如：
#include <iostream>
#include <map>
int main()
{
std::map<int, std::string> myMap;
// 插入键值对
myMap[1] = "one";
myMap[2] = "two";
myMap[3] = "three";
// 通过键访问值
std::cout << myMap[2] << std::endl; // two
// 修改键对应的值
myMap[2] = "TWO";
std::cout << myMap[2] << std::endl; // TWO
// 删除键值对
myMap.erase(3);
// 遍历
// 1: one
// 2: TWO
// for (const auto &[key, value] : myMap)
// {
// std::cout << key << ": " << value << std::endl;
// }
for (const auto &it : myMap)
{
std::cout << it.first << ": " << it.second << std::endl;
}
return 0;
}
std::multiset
用于存储多个键，允许重复元素，并且所有元素按照键的顺序自动排序。std::multiset 使用红黑树实现，因此具有高效的插入、删除和查找操作。
例如：
#include <iostream>
#include <set>
int main()
{
std::multiset<int> myMultiSet;
// 插入元素
myMultiSet.insert(10);
myMultiSet.insert(20);
myMultiSet.insert(20);
myMultiSet.insert(30);
// 查找元素
auto it = myMultiSet.find(20);
if (it != myMultiSet.end())
{
std::cout << *it << std::endl; // 20
}
else
{
std::cout << "Not found!" << std::endl;
}
// multiset 的键值不可直接修改，需要删除后重新插入
myMultiSet.erase(it); // 删除一个元素
myMultiSet.insert(25); // 插入新值
// 删除所有值为20的元素
myMultiSet.erase(20);
// 遍历
for (const auto &value : myMultiSet)
{
std::cout << value << " "; // 10 25 30
}
std::cout << std::endl;
return 0;
}
std::multimap
以键值对的形式存储数据，允许重复元素，并且所有元素都按键的顺序自动排序。std::multimap 底层使用红黑树实现，因此具有高效的插入、删除和查找操作。
例如：
#include <iostream>
#include <map>
int main()
{
std::multimap<int, std::string> myMultiMap;
// 插入键值对
myMultiMap.insert({1, "one"});
myMultiMap.insert({2, "two"});
myMultiMap.insert({2, "TWO"});
myMultiMap.insert({3, "three"});
// 查找键对应的值（可能有多个）
auto range = myMultiMap.equal_range(2);
for (auto it = range.first; it != range.second; ++it)
{
// two
// TWO
std::cout << it->second << std::endl;
}
// 修改某个键值对的值
auto it = myMultiMap.find(2);
if (it != myMultiMap.end())
{
it->second = "TWO MODIFIED";
}
// 删除某个键值对
myMultiMap.erase(it);
// 遍历
// 1: one
// 2: TWO
// 3: three
// for (const auto &[key, value] : myMultiMap)
// {
// std::cout << key << ": " << value << std::endl;
// }
for (const auto &it : myMultiMap)
{
std::cout << it.first << ": " << it.second << std::endl;
}
return 0;
}
无序关联容器
std::unordered_set
用于存储唯一的键，所有元素不按特定顺序排序。std::unordered_set 底层使用哈希表实现，因此具有常数时间复杂度的插入、删除和查找操作。
例如：
#include <iostream>
#include <unordered_set>
int main()
{
std::unordered_set<int> us;
// 插入元素
us.insert(1);
us.insert(2);
us.insert(3);
// 查找元素
auto it = us.find(2);
if (it != us.end())
{
std::cout << *it << std::endl; // 2
}
else
{
std::cout << "Not found!" << std::endl;
}
// unordered_set 不支持直接修改键，只能删除后重新插入
us.erase(it);
us.insert(25);
// 删除
us.erase(1);
// 遍历
for (const auto &elem : us)
{
std::cout << elem << " "; // 25 3
}
std::cout << std::endl;
return 0;
}
std::unordered_map
以键值对的形式存储数据，键唯一，并且所有元素都不按特定顺序排序。std::unordered_map 底层使用哈希表实现，因此具有常数时间复杂度的插入、删除和查找操作。
例如：
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<int, string> um;
// 插入键值对
um[1] = "one";
um[2] = "two";
um[3] = "three";
// 通过键访问值
std::cout << um[2] << std::endl; // two
// 修改键对应的值
um[2] = "TWO";
std::cout << um[2] << std::endl; // TWO
// 删除键值对
um.erase(3);
// 遍历
for (const auto &pair : um)
{
// 2: TWO
// 1: one
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
std::unordered_multiset
用于存储键，允许相同的元素出现多次，所有元素不按特定顺序排序。std::unordered_multiset 底层使用哈希表实现，因此具有常数时间复杂度的插入、删除和查找操作。
例如：
#include <iostream>
#include <unordered_set>
int main()
{
std::unordered_multiset<int> ums;
// 插入元素
ums.insert(1);
ums.insert(2);
ums.insert(2);
ums.insert(3);
// 查找元素
auto range = ums.equal_range(2);
std::cout << std::distance(range.first, range.second) << std::endl; // 2
// unordered_multiset 不支持直接修改键，只能删除后重新插入
ums.erase(1);
ums.insert(10);
// 删除所有值为2的元素
ums.erase(2);
// 遍历
for (const auto &elem : ums)
{
std::cout << elem << " "; // 10 3
}
std::cout << std::endl;
return 0;
}
std::unordered_multimap
以键值对的形式存储数据，允许相同的键值出现多次，每个键可以对应多个值（键值对），并且所有元素都不按特定顺序排序。std::unordered_multimap 底层使用哈希表实现，因此具有常数时间复杂度的插入、删除和查找操作。
例如：
#include <iostream>
#include <unordered_map>
int main()
{
std::unordered_multimap<int, std::string> umm;
// 插入键值对
umm.insert({1, "one"});
umm.insert({2, "two"});
umm.insert({2, "TWO"});
umm.insert({3, "three"});
// 查找键对应的值（可能有多个）
auto range = umm.equal_range(2);
std::cout << distance(range.first, range.second) << std::endl; // 2
for (auto it = range.first; it != range.second; ++it)
{
std::cout << it->second << " "; // TWO two
}
std::cout << std::endl;
// 修改某个键值对的值
auto it = umm.find(2);
if (it != umm.end())
{
it->second = "TWO_UPDATED";
}
// 删除某个键值对
umm.erase(3);
// 遍历
for (const auto &pair : umm)
{
// 2: TWO_UPDATED
// 2: two
// 1: one
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
容器适配器
容器适配器是一种特殊的容器，它们基于标准容器（如std::vector、std::deque、std::list等），通过封装和限制其接口来提供特定的抽象数据类型。容器适配器并不直接存储数据，而是通过底层容器来数据存储，并且只暴露部分功能，以满足特定的使用场景。
c++ 标准库中提供了三个容器适配器：std::stack、std::queue、std::priority_queue。
std::stack
后进先出（LIFO）的数据结构，支持在栈顶插入和删除元素。默认基于 std::deque 实现，可以使用 std::vector 或 std::list 作为底层容器。
template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack {
//...
}
例如：
#include <iostream>
#include <stack>
#include <vector>
#include <list>
int main()
{
std::stack<int> s;
// 使用 std::vector
// std::stack<int, std::vector<int>> s1;
// 使用 std::list
// std::stack<int, std::list<int>> s2;
// 插入元素
s.push(1);
s.push(2);
s.push(3);
// 查询栈顶元素
std::cout << s.top() << std::endl; // 3
// 弹出栈顶元素
s.pop();
std::cout << s.top() << std::endl; // 输出新栈顶元素的值 2
// 判断栈是否为空
if (!s.empty())
{
std::cout << "stack is not empty" << std::endl; // stack is not empty
}
// 获取栈的大小
std::cout << s.size() << std::endl; // 2
return 0;
}
std::queue
先进先出（FIFO）的数据结构，支持在队尾插入元素，在队头删除元素。默认基于 std::deque 实现，可以使用 std::list 作为底层容器。
template<typename _Tp, typename _Sequence = deque<_Tp> >
class queue
{
// ...
}
需要注意的是：std::vector 是一个动态数组，支持快速的尾部插入和删除操作（push_back 和 pop_back），但不支持高效的头部删除操作（pop_front）。因此， std::vector 无法作为 std::queue 的底层容器。
例如：
#include <iostream>
#include <queue>
#include <list>
int main()
{
std::queue<int> q;
// 使用 std::list
// std::queue<int, std::list<int>> q1;
// 元素入队
q.push(1);
q.push(2);
q.push(3);
// 输出队头元素
std::cout << q.front() << std::endl; // 1
// 输出队尾元素
std::cout << q.back() << std::endl; // 3
// 元素出队
q.pop();
std::cout << q.front() << std::endl; // 2
// 判断队列是否为空
if (!q.empty())
{
std::cout << "queue is not empty" << std::endl; // queue is not empty
}
// 获取队列的大小
std::cout << "queue size: " << q.size() << std::endl; // queue size: 2
return 0;
}
std::priority_queue
优先队列，元素会按照优先级顺序排（默认是大顶堆，如果需要小顶堆，则需要自定义比较器）。默认基于 std::vector 作为底层容器，可以使用 std::deque 作为底层容器。
template<typename _Tp, typename _Sequence = vector<_Tp>,
typename _Compare = less<typename _Sequence::value_type> >
class priority_queue
{
// ...
}
需要注意的是：std::list 只支持双向迭代器，不支持随机访问。而优先队列需要上浮和下沉操作（需要随机访问的支持），所以 std::list 无法作为 std::priority_queue 的底层容器。
例如：
#include <iostream>
#include <queue>
#include <deque>
int main()
{
std::priority_queue<int> pq;
// std::priority_queue<int, std::deque<int>> pq;
// 堆中插入元素
pq.push(1);
pq.push(3);
pq.push(2);
// 查询堆顶元素
std::cout << pq.top() << std::endl; // 3
// 删除堆顶元素
pq.pop();
std::cout << pq.top() << std::endl; // 2
// 判断堆是否为空
if (!pq.empty())
{
// priority queue is not empty
std::cout << "priority queue is not empty" << std::endl;
}
// 获取优先队列的大小
// priority queue size: 2
std::cout << "priority queue size: " << pq.size() << std::endl;
return 0;
}
🌺🌺🌺撒花！
如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。
