常用STL的操作以及特点
C++ 标准模板库(STL)提供了很多常用的数据结构和算法,极大简化了开发工作。STL 包括容器(如 vector
、list
、map
等)、算法(如排序、查找等)以及迭代器。以下是一些常用 STL 容器的操作以及它们的特点:
1. vector
(动态数组)
vector
是一个动态数组,大小可以动态增长或缩小。
常用操作:
std::vector<int> vec = {1, 2, 3};
vec.push_back(4); // 在末尾添加元素
vec.pop_back(); // 删除末尾元素
vec.size(); // 返回元素个数
vec.empty(); // 判断是否为空
vec[1]; // 访问第二个元素
vec.clear(); // 清空所有元素
特点:
- 动态大小:可以根据需要自动扩展。
- 随机访问:支持常数时间复杂度的随机访问操作(
operator[]
和at()
)。 - 内存管理:当需要扩展时,可能会导致重新分配内存,效率略低。
- 时间复杂度:插入/删除操作的时间复杂度为 O(1)(末尾),其他位置为 O(n)。
2. list
(双向链表)
list
是双向链表,适合频繁进行插入和删除操作的场景。
常用操作:
std::list<int> lst = {1, 2, 3};
lst.push_back(4); // 在末尾添加元素
lst.push_front(0); // 在头部添加元素
lst.pop_back(); // 删除末尾元素
lst.pop_front(); // 删除头部元素
lst.size(); // 返回元素个数
lst.clear(); // 清空所有元素
lst.remove(2); // 删除所有等于 2 的元素
特点:
- 双向链表:支持常数时间复杂度的插入和删除操作。
- 顺序访问:不支持随机访问,需要顺序遍历。
- 空间占用较大:由于每个节点都需要存储前后指针,空间利用率相对较低。
- 时间复杂度:插入、删除为 O(1),访问为 O(n)。
3. deque
(双端队列)
deque
是双端队列,支持两端的高效插入和删除操作。
常用操作:
std::deque<int> deq = {1, 2, 3};
deq.push_back(4); // 在末尾添加元素
deq.push_front(0); // 在头部添加元素
deq.pop_back(); // 删除末尾元素
deq.pop_front(); // 删除头部元素
deq.size(); // 返回元素个数
deq[1]; // 访问第二个元素
deq.clear(); // 清空所有元素
特点:
- 双端操作:支持 O(1) 时间复杂度的双端插入和删除。
- 随机访问:支持常数时间复杂度的随机访问。
- 适用于双端处理:比
list
更灵活,可以高效操作两端。
4. stack
(栈)
stack
是基于 deque
或 vector
实现的后进先出(LIFO)数据结构。
常用操作:
std::stack<int> stk;
stk.push(1); // 压栈
stk.pop(); // 弹栈
stk.top(); // 返回栈顶元素
stk.empty(); // 判断是否为空
stk.size(); // 返回栈中的元素个数
特点:
- 后进先出:只能访问栈顶元素,无法随机访问。
- 基于容器实现:默认使用
deque
,但也可以使用vector
或list
。 - 时间复杂度:常数时间的插入、删除和访问操作。
5. queue
(队列)
queue
是基于 deque
实现的先进先出(FIFO)数据结构。
常用操作:
std::queue<int> que;
que.push(1); // 入队
que.pop(); // 出队
que.front(); // 返回队首元素
que.back(); // 返回队尾元素
que.empty(); // 判断是否为空
que.size(); // 返回队列中元素个数
特点:
- 先进先出:只能操作队首和队尾。
- 时间复杂度:常数时间的插入、删除和访问操作。
6. priority_queue
(优先队列)
priority_queue
是基于堆实现的队列,元素按优先级顺序出队。
常用操作:
std::priority_queue<int> pq;
pq.push(10); // 入队
pq.pop(); // 出队,移除优先级最高的元素
pq.top(); // 返回优先级最高的元素
pq.empty(); // 判断是否为空
pq.size(); // 返回队列中元素个数
特点:
- 优先级排序:默认最大堆,优先级高的元素优先出队。
- 时间复杂度:插入和删除的时间复杂度为 O(log n)。
7. set
和 unordered_set
(集合)
set
是有序集合,unordered_set
是无序集合(基于哈希表实现)。
常用操作:
std::set<int> s;
s.insert(1); // 插入元素
s.erase(1); // 删除元素
s.count(1); // 判断元素是否存在
s.find(1); // 查找元素
s.size(); // 返回元素个数
s.clear(); // 清空集合
特点:
set
:基于红黑树实现,支持自动排序。插入、删除、查找的时间复杂度为 O(log n)。unordered_set
:基于哈希表实现,不保证元素顺序,插入、删除和查找的时间复杂度为 O(1)。
8. map
和 unordered_map
(映射)
map
是有序键值对映射,unordered_map
是无序键值对映射。
常用操作:
std::map<int, std::string> mp;
mp[1] = "one"; // 插入或更新元素
mp.erase(1); // 删除键为 1 的元素
mp.find(1); // 查找键为 1 的元素
mp.size(); // 返回元素个数
mp.clear(); // 清空映射
特点:
map
:基于红黑树实现,按键值排序。插入、删除、查找的时间复杂度为 O(log n)。unordered_map
:基于哈希表实现,不保证元素顺序,插入、删除和查找的时间复杂度为 O(1)。
9. algorithm
(算法)
STL 提供了很多常用算法,如排序、查找、遍历等。
常用操作:
std::vector<int> vec = {3, 1, 4, 1, 5};
std::sort(vec.begin(), vec.end()); // 排序
std::reverse(vec.begin(), vec.end()); // 逆序
std::find(vec.begin(), vec.end(), 4); // 查找元素 4
std::count(vec.begin(), vec.end(), 1); // 统计元素 1 的个数
std::accumulate(vec.begin(), vec.end(), 0); // 求和
特点:
- 泛型算法:与任何 STL 容器配合使用。
- 高效实现:大多数算法的时间复杂度为 O(n log n) 或 O(n)。
10. 迭代器(Iterator)
STL 容器的元素可以通过迭代器进行遍历和操作。
常用操作:
std::vector<int> vec = {1, 2, 3};
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
特点:
- 抽象访问:可以无缝遍历任何 STL 容器,而无需关心其内部结构。
- 灵活操作:支持常见的迭代模式,如前向、双向、随机访问等。
总结
STL 提供了强大的数据结构和算法库,使得开发者可以快速、高效地解决许多常见的问题。每种容器和算法
原文地址:https://blog.csdn.net/qq_43587345/article/details/142869963
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!