C++一分钟之-容器概览:vector, list, deque

本文涉及的产品
大数据开发治理平台 DataWorks,不限时长
实时数仓Hologres,5000CU*H 100GB 3个月
检索分析服务 Elasticsearch 版,2核4GB开发者规格 1个月
简介: 【6月更文挑战第21天】STL中的`vector`是动态数组,适合随机访问,但插入删除非末尾元素较慢;`list`是双向链表,插入删除快但随机访问效率低;`deque`结合两者优点,支持快速双端操作。选择容器要考虑操作频率、内存占用和性能需求。注意预分配容量以减少`vector`的内存重分配,使用迭代器而非索引操作`list`,并利用`deque`的两端优势。理解容器内部机制和应用场景是优化C++程序的关键。

在C++的世界里,STL(Standard Template Library,标准模板库)为我们提供了丰富而强大的数据结构和算法,其中容器部分是开发中不可或缺的一部分。今天,我们将快速浏览三种常用且功能各异的序列容器:vectorlistdeque,探讨它们的特点、适用场景以及常见的使用误区与避免策略。
image.png

1. vector:动态数组

vector是C++中最常用的容器之一,它在内部表现为一个动态数组,能够高效地进行随机访问,但插入和删除非末尾元素可能较慢,因为这可能导致内存的重新分配和元素的复制。

常见问题与避免策略:

  • 内存重新分配:当vector容量不足以容纳新元素时,它会自动扩容,这个过程可能导致性能开销。可以通过reserve()预先分配足够的容量来避免频繁的内存重分配。
std::vector<int> vec;
vec.reserve(100); // 预先分配空间
  • 插入和删除:尽量减少在vector中间的插入和删除操作,尤其是当这些操作频繁发生时,考虑使用其他容器如list

2. list:双向链表

list是一个双向链表,每个元素都有指向前一个和后一个元素的指针。它支持快速的插入和删除操作,尤其是在链表中间,但随机访问效率较低。

常见问题与避免策略:

  • 随机访问:由于list不支持随机访问迭代器,因此应避免使用基于索引的操作,改用迭代器遍历或直接使用插入/删除接口。
std::list<int> lst;
lst.push_back(1); // 在末尾插入元素
auto it = lst.begin();
lst.insert(++it, 2); // 在第二个位置插入元素
  • 内存占用:相较于vectorlist每个节点额外存储了指针,因此在大量小对象存储时,内存占用较高。选择list前应考虑这一点。

3. deque:双端队列

deque(双端队列)结合了vector的随机访问能力和list的快速插入删除特性,特别是在两端。它在内部使用分块的连续内存,使得头部和尾部的插入删除操作都非常高效。

常见问题与避免策略:

  • 中间操作:虽然deque两端操作高效,但在中间插入和删除仍然需要线性时间。尽量利用其两端操作的优势。
std::deque<int> deq;
deq.push_front(1); // 在前端插入
deq.push_back(2); // 在后端插入
  • 内存模型理解:虽然deque提供了类似vector的随机访问能力,但其内部实现差异意味着某些操作(如直接访问特定偏移量的元素)可能不如vector直观或高效。

总结

选择合适的容器是优化C++程序性能的关键一环。vector适合于需要快速随机访问且元素数量相对稳定的情况;list在频繁插入删除的场景下表现更佳;而deque则在需要快速在两端进行操作的应用中大放异彩。理解每种容器的内部机制和优缺点,能帮助我们做出更合理的选择,从而提升代码的效率和可维护性。在实际应用中,还需根据具体需求权衡,适时使用reserve()、选择正确的插入删除策略,以及考虑内存和性能的综合影响,才能最大化STL容器的价值。

目录
相关文章
|
2天前
|
存储 Java C++
【c++】list详细讲解
【c++】list详细讲解
14 5
|
2天前
|
Java C++ Python
【c++】list 模拟
【c++】list 模拟
7 1
|
10天前
|
存储 编译器 C语言
【C++】list模拟实现
本文档介绍了C++ STL中`list`容器的模拟实现,包括`ListNode`节点类、迭代器类和`list`类的详细设计。`ListNode`模板类存储数据并维护前后指针;`ListIterator`是一个复杂的模板类,提供解引用、自增/自减以及比较操作。`list`类包含了链表的各种操作,如插入、删除、访问元素等,并使用迭代器作为访问接口。实现中,迭代器不再是简单的指针,而是拥有完整功能的对象。此外,文档还提到了迭代器的实现对C++语法的特殊处理,使得`it-&gt;_val`的写法成为可能。文章通过分步骤展示`list`的各个组件的实现,帮助读者深入理解STL容器的内部工作原理。
|
10天前
|
算法 搜索推荐 C++
【C++】list的使用(下)
`C++` 中 `std::list` 的 `merge()`、`sort()` 和 `reverse()` 操作: - `merge(x)` 和 `merge(x, comp)`: 合并两个已排序的`list`,将`x`的元素按顺序插入当前`list`,`x`清空。比较可自定义。 - `sort()` 和 `sort(comp)`: 对`list`元素排序,保持等价元素相对顺序。内置排序基于稳定排序算法,速度较慢。 -reverse(): 反转`list`中元素的顺序。 这些操作不涉及元素构造/销毁,直接移动元素。注意,`sort()`不适合`std::list`,因链表结构不利于快速排序
|
10天前
|
C++ 容器
【C++】list的使用(下)
这篇博客探讨了C++ STL中`list`容器的几个关键操作,包括`splice()`、`remove()`、`remove_if()`和`unique()`。`splice()`允许高效地合并或移动`list`中的元素,无需构造或销毁。`remove()`根据值删除元素,而`remove_if()`则基于谓词移除元素。`unique()`则去除连续重复的元素,可选地使用自定义比较函数。每个操作都附带了代码示例以说明其用法。
|
10天前
|
编译器 C++ 容器
【C++】list的使用(上)
迭代器在STL中统一了访问接口,如`list`的`begin()`和`end()`。示例展示了如何使用正向和反向迭代器遍历`list`。注意`list`的迭代器不支持加减操作,只能用`++`和`--`。容器的`empty()`和`size()`用于检查状态和获取元素数。`front()`和`back()`访问首尾元素,`assign()`重载函数用于替换内容,`push_*/pop_*`管理两端元素,`insert()`插入元素,`erase()`删除元素,`resize()`调整大小,`clear()`清空容器。这些接口与`vector`和`string`类似,方便使用。
|
10天前
|
存储 C++ 索引
|
10天前
|
存储 C++ 容器
|
10天前
|
存储 编译器 C语言
【C++】list的使用(上)
**C++ STL的list是一个基于双向循环链表的容器,支持常数时间内插入和删除,但不支持随机访问。默认构造函数、填充构造、迭代器范围构造和拷贝构造提供多种初始化方式。析构函数自动释放内存,赋值运算符重载用于内容替换。示例代码展示了构造和赋值操作。**
|
10天前
|
存储 算法 程序员
C++基础知识(八:STL标准库(Vectors和list))
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合,它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等. STL容器的提供是为了让开发者可以更高效率的去开发,同时我们应该也需要知道他们的底层实现,这样在出现错误的时候我们才知道一些原因,才可以更好的去解决问题。