数组（Array），向量（Vector），链表（Linked List），双端队列（Deque），栈（Stack），队列（Queue），优先队列（Priority Queue），集合（Set），无序集合（Unordered Set），映射（Map），无序映射（Unordered Map）…

C++ STL中常用的数据结构

1. 数组（Array）

• 简介：固定大小的连续内存块，用于存储相同类型的元素。
• 优点：访问时间快（O(1)）。
• 缺点：大小固定，插入和删除操作代价高。

2. 向量（Vector）

• 简介：动态数组，大小可以动态调整。
• 优点：支持随机访问，自动调整大小。
• 缺点：插入和删除操作代价高（除非在末尾）。

示例

#include <vector>
std::vector<int> vec;
vec.push_back(1);
vec.push_back(2);

3. 链表（Linked List）

• 简介：由节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针。
• 优点：插入和删除操作高效（O(1)）。
• 缺点：访问时间慢（O(n)），占用额外内存。

示例

#include <list>
std::list<int> linkedList;
linkedList.push_back(1);
linkedList.push_back(2);

4. 双端队列（Deque）

• 简介：允许在两端插入和删除的序列。
• 优点：支持快速的两端插入和删除。
• 缺点：访问时间慢（O(n)）。

示例

#include <deque>
std::deque<int> deq;
deq.push_back(1);
deq.push_front(2);

5. 栈（Stack）

• 简介：遵循后进先出（LIFO）原则的容器。
• 优点：插入和删除操作高效（O(1)）。
• 缺点：只允许在一端进行插入和删除。

示例

#include <stack>
std::stack<int> stk;
stk.push(1);
stk.push(2);
stk.pop();

6. 队列（Queue）

• 简介：遵循先进先出（FIFO）原则的容器。
• 优点：插入和删除操作高效（O(1)）。
• 缺点：只允许在一端插入，另一端删除。

示例

#include <queue>
std::queue<int> que;
que.push(1);
que.push(2);
que.pop();

7. 优先队列（Priority Queue）

• 简介：类似于队列，但每个元素都有优先级，优先级高的元素优先出队。
• 优点：插入和删除操作高效（O(log n)）。
• 缺点：访问时间慢（O(n)）。

示例

#include <queue>
std::priority_queue<int> pq;
pq.push(1);
pq.push(3);
pq.push(2);

8. 集合（Set）

• 简介：存储唯一元素的容器，通常基于红黑树实现。
• 优点：查找、插入和删除操作高效（O(log n)）。
• 缺点：不允许重复元素。

示例

#include <set>
std::set<int> s;
s.insert(1);
s.insert(2);

9. 无序集合（Unordered Set）

• 简介：存储唯一元素的容器，基于哈希表实现。
• 优点：查找、插入和删除操作平均时间复杂度为 O(1)。
• 缺点：不允许重复元素。

示例

#include <unordered_set>
std::unordered_set<int> us;
us.insert(1);
us.insert(2);

10. 映射（Map）

• 简介：键值对存储的数据结构，通常基于红黑树实现。
• 优点：查找、插入和删除操作高效（O(log n)）。
• 缺点：不允许重复键。

示例

#include <map>
std::map<int, std::string> m;
m[1] = "one";
m[2] = "two";

11. 无序映射（Unordered Map）

• 简介：键值对存储的数据结构，基于哈希表实现。
• 优点：查找、插入和删除操作平均时间复杂度为 O(1)。
• 缺点：不允许重复键。

示例

#include <unordered_map>
std::unordered_map<int, std::string> um;
um[1] = "one";
um[2] = "two";

赏

谢谢你请我吃糖果

支付宝

微信