STL 容器 Ⅰ

LIZHAO • • Modern Cpp
阅读量 0 次 • 评论量 0 个

string

string，一般不被认为是一个容器，但是与容器有较多的共同点。

string，是模板类basic_string 对于char类型的特化即typedef basic_string<char> string;,理解为只能放char的容器，而其他容器是可以存放任意类型的对象。

string 的成员函数

和其他容器一样，都具有以下成员函数。

  • begin，返回迭代器，指向第一个元素
  • end，返回迭代器，指向尾后。
  • empty，容器是否为空
  • size，容器大小
  • swap，和另一个容器交换内容。

cpp容器是一个半开半闭的区间，即begin指向第一个元素，而end却不是指向最后一个元素，而是最后一个元素的后面（尾后）。

对于string来说，end指向代表字符串结束的\0字符。

在代码中推荐使用string来管理字符串，但对于接口，则不建议使用const string&，除非调用者持有string。

在接口调用中，若调用者只有const char *，则会带来额外的构造string的开销，所以如果在接口中不对字符串进行处理复杂的处理的话，不建议使用string。

对于不改变字符串内容的接口，但有需要对字符串进行复杂操作的接口，推荐使用cpp17中的string_view作为参数，这样即便是传入的是 const char *也不会引发必要的内存拷贝。

vector

相对常用的容器，可理解为动态数组，拥有连续的内存空间，具备随机存取的能力。由于内存布局的原因，vector适合在尾部进行数据的插入删除操作。

除了容器类的共同点，vector 允许下面的操作（不完全列表）：

  • 可以使用中括号的下标来访问其成员（同 string）可以使用 data 来获得指向其内容的裸指针（同 string）
  • 可以使用 capacity 来获得当前分配的存储空间的大小，以元素数量计（同 string）
  • 可以使用 reserve 来改变所需的存储空间的大小，成功后 capacity() 会改变（同 string）
  • 可以使用 resize 来改变其大小，成功后 size() 会改变（同 string）
  • 可以使用pop_back 来删除最后一个元素（同 string）
  • 可以使用 push_back在尾部插入一个元素（同 string）可以使用 insert 在指定位置前插入一个元素（同 string）
  • 可以使用 erase 在指定位置删除一个元素（同 string）可以使用 emplace 在指定位置构造一个元素可以使用 emplace_back在尾部新构造一个元素

解释noexcept

当对容器的操作导致内存重新分配的时候，vector 会重新分配内存空间，vector会移动元素到新的内存中去。为了保证强异常安全性，对于没有提供保证不抛出异常的移动构造函数，vector会使用拷贝构造函数。所以对于拷贝开销巨大的类型，我们应该提供保证不抛出异常的移动构造函数。

emplace 系列函数

push_back 会生成临时对象，而emplace_back不会。

使用reserve 函数为vector保留足够的内存

在某些情况下，我们知道vector所需要的内存，那么通过reserve函数为vector保留所需要的内存空间，避免后面随着元素的插入导致内存vector重新分配内存，并移动元素带来的开销。

deque

双端队列，可在头尾快速的添加和删除元素。
deque 不提供 data、capacity 和 reserve 成员函数。

内存布局：

由以上内存布局来看：

  • 头尾添加删除元素效率高（但不及vector），在中间插入删除元素效率低。
  • 由于内存部分连续，所以没有办法取得数据的裸指针（data）。
  • 支持随机访问，即通过下标，或者at成员函数访问。

deque适合需要在头尾频繁插入或删除。

list

双向链表，既然是链表，那么就意味着内存不连续，并拥有高效的任意位置的插入和删除操作。

  • 无法提供随机访问能力，查找元素需要遍历链表。
  • 任意位置插入删除效率高。

内存布局：

值得注意的是，某些标准算法在list会出错，list提供了一些成员来代替：

  • merge
  • remove
  • remove_if
  • reverse
  • sort
  • unique

forward_list

单向链表，同样内存不连续，拥有高效的插入删除操作。

其内存布局如下：

与list相比，forward_list缺少以下成员函数：

  • back
  • size
  • push_back
  • emplace_back
  • pop_back

元素小，数量少时，单链表能节约内存，提高内存的利用效率。

容器适配器

queue

队列，一种先进先出的数据结构。在STL中的queue默认用容器deque来实现。
拥有以下成员函数：

  • emplace
  • push
  • pop

其内存布局如下：

stack

栈，一种先进后出的数据结构，其默认的实现方式也是deque。

拥有以下成员成员函数：

  • emplace
  • push
  • pop
  • top 返回栈定元素。

其内存布局如下：

以上内容为 极客时间，“现代C++实战30讲” 的学习笔记。
https://time.geekbang.org/column/article/173167
喵~