C++的顺序容器类型和相关操作总结

发布时间:2023年12月22日

顺序容器类型

C++ 标准库提供了一组顺序容器,用于存储和管理元素的集合。以下是 C++ 中常用的顺序容器:
在这里插入图片描述

vector (向量)

  • std::vector 是一个动态数组,支持快速随机访问。
  • 元素存储在连续的内存位置中,支持动态增长和缩减大小。
  • 常用于需要频繁访问元素,但较少进行插入和删除操作的场景。

deque (双端队列)

  • std::deque 支持在两端快速插入和删除元素。
  • 可能不是连续存储的,但仍然支持快速随机访问。
  • 适合于需要在两端添加或移除元素的场景。

list (双向链表)

  • std::list 是一个双向链表,支持在任何位置快速插入和删除元素。
  • 不支持快速随机访问,适合于元素经常在中间插入或删除的场景。

forward_list (单向链表)

  • std::forward_list 是一个单向链表,每个元素只有一个指向下一个元素的指针。
  • 占用空间少,但只能向前遍历。
  • 适合于只需要单向遍历且关注内存使用的场景。

array (固定大小数组)

  • std::array 是一个固定大小的数组,大小在编译时确定。
  • 支持快速随机访问,元素存储在连续内存位置中。
  • 适合于已知元素数量且数量不变的场景。

string (字符串)

  • std::string 专门用于存储和操作字符串的容器。
  • 提供了丰富的成员函数来处理字符串,如拼接、查找、替换等操作。
  • 实际上是 std::basic_string<char> 的特化版本,可以动态增长和缩减。

顺序容器操作

在这里插入图片描述

添加元素的操作

push_back
  • 在容器的末尾添加一个元素。
  • 适用于 vector, deque, list, 和 forward_list
push_front
  • 在容器的开头添加一个元素。
  • 适用于 dequelist
emplace_back
  • 在容器的末尾直接构造一个元素。
  • 适用于 vector, deque, 和 list
emplace_front
  • 在容器的开头直接构造一个元素。
  • 适用于 dequelist
insert
  • 在容器的指定位置插入一个或多个元素。
  • 适用于 vector, deque, 和 list
emplace
  • 在指定位置直接构造一个元素。
  • 适用于 vector, deque, 和 list

其他操作与迭代器

  • at(index):返回指定位置的元素引用,带边界检查。
  • operator[]:返回指定位置的元素引用,不带边界检查。
  • erase(iterator):移除迭代器指向的元素或一段元素区间。
  • clear():移除容器中的所有元素。
  • resize(n):改变容器大小,适应新的元素数量。
  • swap(container):交换两个同类型容器的内容。
  • begin() / end():返回指向容器第一个/尾后元素的迭代器。
  • rbegin() / rend():返回指向容器最后一个/尾前元素的逆向迭代器。
  • cbegin() / cend():返回指向容器第一个/尾后元素的常量迭代器。
  • capacity():返回容器不重新分配内存时的最大容量。

迭代器与反向迭代器的例子

在这里插入图片描述

list<string> lst;
auto iter = lst.begin();
while (cin >> word)
    iter = lst.insert(iter, word); // 等价于调用 push_front
vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin();
while (iter != vi.end()) {
    if (*iter % 2) {
        iter = vi.insert(iter, *iter);
        iter += 2;
    } else
        iter = vi.erase(iter);
}

补充:vector 对象的增长模式

当向 vector 添加新元素,而当前的存储空间不足以容纳更多元素时,vector 将执行以下步骤来增长其容量:

  • 分配新的更大的内存空间:vector 会分配一个新的内存块,其大小通常是当前容量的两倍(这个增长因子可能因库实现而异,但通常是 1.5 到 2 倍之间)。这样做是为了平衡内存使用和性能。如果增长因子太小,vector 将频繁重新分配内存,导致性能下降;如果增长因子太大,可能会浪费内存。
  • 复制或移动现有元素:现有元素将从旧内存空间复制(或移动,如果元素类型支持移动语义)到新分配的内存空间。
  • 释放旧内存空间:一旦所有元素都被复制或移动到新的内存空间,vector 将释放旧的内存块。
  • 更新容器的元数据:vector 更新其内部数据结构,如指向元素的指针、大小和容量,以反映新的内存布局。
文章来源:https://blog.csdn.net/qq_46348508/article/details/135102832
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。