C/C++ | 每日一练 (4)

💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

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// TWOstd::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: onecout << 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; // 2for (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: onestd::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; // 2return 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: 2return 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 emptystd::cout << "priority queue is not empty" << std::endl; }// 获取优先队列的大小// priority queue size: 2std::cout << "priority queue size: " << pq.size() << std::endl; return 0;
}

🌺🌺🌺撒花！

如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。