Skip to content

C++ STL

STL（标准模板库）

核心组件

  • Containers：用来管理某一类对象的集合。如 deque，list，vector，map 等。
  • Algorithms：算法作用于容器。
  • iterators：迭代器用于遍历对象集合的元素。

序列式容器

  • array<T, N>：数组，长度固定
  • vector<T>：向量，长度可变
  • deque<T>：双端队列
  • list<T>：双向链表
  • forward_list<T>：单链表

关联式容器

使用红黑树实现，平衡二叉树使得查找、插入、删除的时间复杂度为 O(logN)。

  • map：键值对，键唯一
  • multimap：键值对，键可重复
  • set：集合，键唯一
  • multiset：多重集合，键可重复

无序关联式容器

使用哈希表实现，大多数操作的时间复杂度为 O(1)，但最坏情况下为 O(N)（如哈希冲突）。

  • unordered_map
  • unordered_multimap
  • unordered_set
  • unordered_multiset

容器适配器

  • stack<T>：栈（封装了 deque<T> 容器的适配器类模板）
  • queue<T>：先入先出队列（封装了 deque<T> 容器的适配器类模板）
  • priority_queue<T>：优先权队列（封装了 vector<T> 容器的适配器类模板）

array

定义在 <array> 头文件，使用 std 命名空间。

声明用 array<T, N> 数组名;，其中 T 是类型，N 是长度。

// 声明
array<double, 10> values_1;   // 未初始化
array<double, 10> values_2 {1.0, 2.0};   // 初始化
array<double, 10> values_2 {};   // 初始化为全 0.0

成员函数

  • begin()：返回指向容器中第一个元素的随机访问迭代器
  • end()：返回指向容器最后一个元素之后一个位置的随机访问迭代器
  • rbegin()：返回指向最后一个元素的随机访问迭代器
  • rend()：返回指向第一个元素之前一个位置的随机访问迭代器
  • cbegin()，cend()，crbegin()，crend()：增加 const 属性
  • size()：返回容器中当前元素的数量（始终为 N）
  • max_size()：返回容器可容纳元素的最大数量（始终为 N）
  • empty()：判断是否为空
  • at(n)：返回 n 位置处引用，若超出范围，抛出 out_of_range 异常
  • front()：第一个元素的直接引用
  • back()：最后一个元素的直接引用
  • data()：返回一个指向容器首个元素的指针
  • fill(val)：将 val 这个值赋值给容器中的每个元素
  • array1.swap(array2)：交换两个 array 容器中的元素

访问 array 的第 i 个元素，可用如下的几种方法：

  • 容器名[i]
  • 容器名.at(i)（可防越界）
  • get<i>(容器名) （i 必须是常数）
  • *(容器名.data() + i)

对 array 容器的遍历：

  • for (size_t i = 0; i < values.size(); i++) {}
  • for (auto& value : values) {}
  • for (auto p = values.begin(); p < values.end(); p++) {}

vector

头文件 <vector>，并位于 std 命名空间中。

声明用 vector<T> 向量名;

vector<int> values_1 = {2, 3, 5};  // 初始化
vector<int> values_2(20);  // 指定长度，初值为 0
vector<int> values_3(20， 1);  // 指定长度，初值全为 1（两个参数可以用变量）
vector<int> values_4(values_1);  // 复制 values_1
verctor<int> values_5(begin(value_2), begin(value_2) + 4);   // 初始化并赋值等于 value_2 前 4 个元素

成员函数：

  • begin()，end()，rbegin()，rend()、cbegin()，cend()，crbegin()，crend()，empty()，at(i)，front()，back()，data()，vec1.swap(vec2)：略
  • size()：返回实际元素个数
  • max_size()：一般是 \(2^{32}-1\)
  • resize(n)：改变实际元素个数
  • capacity()：返回当前容量。
  • reserve(n)：增加容量（如果 n 小于等于当前容量，什么也不做）
  • shrink_to_fit()：将内存减少到等于当前元素实际所使用的大小
  • assign()：用新元素替换原有内容。
  • push_back(value)：在序列的尾部通过拷贝添加一个元素
  • emplace(pos, ...)：在指定的位置直接生成一个元素，返回新元素位置的迭代器
  • emplace_back(value)：在序列尾部直接生成一个元素，返回新元素位置的引用
  • pop_back()：在序列的尾部删除一个元素，没有返回值
  • insert()：在指定的位置插入一个或多个元素
    • insert(pos, value)：在迭代器 pos 之前插入一个新元素，返回新元素的迭代器
    • insert(pos, n, value)：在迭代器 pos 之前插入 n 个新元素，返回第一个新元素的迭代器
    • insert(pos, first, last)：在迭代器 pos 之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器
    • insert(pos, initlist)：在迭代器 pos 指定的位置之前，插入初始化列表中所有的元素，并返回表示第一个新插入元素位置的迭代器
  • erase()：移出一个元素或一段元素
    • erase(pos)
    • erase(begin, end)
  • clear()：移出所有元素

非成员函数：

  • swap(elem1, elem2) 交换元素（头文件 <algorithm> 或 <utility>）

  • remove(pos1, pos2, value) 删除与 value 相同的所有元素，返回迭代器（原 vector 大小和容量没变）

访问 vector 中单个元素

  • 向量名[i]
  • 向量名.at(i)
  • *(向量名.data() + i)

迭代

  • for (size_t i = 0; i < values.size(); i++) {} // 不要用 capacity()
  • for (auto&& value : values) {}
  • for (auto p = values.begin(); p < values.end(); p++) {}

注意

vector 容器容量变化时，内存地址可能会改变，之前的迭代器有可能失效

set

头文件 <set>，位于 std 命名空间中。

容器模板：

template < class T,                        // 键 key 和值 value 的类型
           class Compare = less<T>,        // 指定 set 容器内部的排序规则
           class Alloc = allocator<T>      // 指定分配器对象的类型
           > class set;

创建 set 容器：

set<T> myset;
set<string> myset2{"1","b","ad"};
set<T> myset3(myset);
set<int> myset4(++myset3.begin(), myset3.end());

成员函数：

  • begin()，end()，rbegin()，rend()，cbegin()，cend()，crbegin()，crend()，empty()，size()，max_size()，set1.swap(set2)，clear()：略
  • find(val)：在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回 end() 迭代器。
  • lower_bound(val)：返回一个指向当前 set 容器中第一个小于或等于 val 的元素的双向迭代器。
  • upper_bound(val)：返回一个指向当前 set 容器中第一个大于 val 的元素的双向迭代器。
  • equal_range(val)：该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）。
  • insert()：向 set 容器中插入元素。
    • insert(val)：向 set 容器中插入值为 val 的元素，返回值为 pair 类型，第一个元素是一个迭代器，指向值为 val 的元素，第二个元素是一个 bool 类型的值，表示插入是否成功（如果元素已存在，则插入失败）。
    • insert(pos, val)：从迭代器 pos 指定的位置开始，找到插入 val 的位置并插入，返回指向新插入元素的迭代器。
    • insert(pos1, pos2)：将另一个容器中 [pos1, pos2) 范围内的元素插入到当前 set 容器中。
    • insert({e1, e2, ...})：将多个元素插入到当前 set 容器中。
  • emplace()：在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。
  • emplace_hint()：在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。
  • erase()：删除 set 容器中存储的元素。
    • erase(pos)：删除迭代器 pos 指向的元素
    • erase(val)：删除值为 val 的元素
    • erase(pos1, pos2)：删除区间 [pos1, pos2) 内的元素
  • count(val)：在当前 set 容器中，查找值为 val 的元素的个数，并返回，因为 set 容器中各个元素是唯一的，所以该方法的返回值只能是 0 或 1。

注意

  1. set 容器并未提供 at() 函数，也未对 [] 进行重载，故要访问 set 容器中的元素只能用 set 容器迭代器，set 容器迭代器比较只能用 == 和 !=。
  2. 对于初学者来说，切勿尝试直接修改 set 容器中已存储元素的值，这很有可能破坏 set 容器中元素的有序性，最正确的修改 set 容器中元素值的做法是：先删除该元素，然后再添加一个修改后的元素。

unordered_map

头文件 <unordered_map>，位于 std 命名空间。

容器模板如下

template < class Key,                   //键值对中键的类型
           class T,                     //键值对中值的类型
           class Hash = hash<Key>,      //容器内部存储键值对所用的哈希函数
           class Pred = equal_to<Key>,  //判断各个键值对键相同的规则
           class Alloc = allocator< pair<const Key,T> >  // 指定分配器对象的类型
           > class unordered_map;

创建 unordered_map 容器示例：

unordered_map<string, string> umap_1;
unordered_map<string, string> umap_2 {
    {"key1", "value1"},
    {"key2", "value2"}
};
unordered_map<string, string> umap_3(umap_2);

成员方法：

  • begin()，end()，cbegin()，cend()，empty()，size()，max_size()：略
  • at(key)：返回 key 的值，若不存在，抛出异常
  • find(key)：返回指向 key 对应键值对的正向迭代器，若没找到，返回 end() 一样的迭代器
  • count(key)：查找以 key 为键的键值对个数
  • equal_range(key)，返回两个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。

stack

头文件 <stack>，定义在 std 命名空间。

声明：stack<T> 栈名; stack<T, 基础容器> 栈名;（基础容器默认 deque）

成员函数：

  • empty()，size()：略
  • top()：返回栈顶元素的引用
  • push(obj)：压栈
  • pop()：弹出栈顶，没有返回值
  • emplace(arg...)：arg... 可以是一个参数，也可以是多个参数，但它们都只用于构造一个对象，并在栈顶直接生成该对象，作为新的栈顶元素。
  • swap(other_stack)：将两个 stack 适配器中的元素进行互换，需要注意的是，进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同。

queue

头文件 <queue>，定义于 std 命名空间。

定义 queque<T, Container=deque<T>>

成员函数：

  • front()，back()，empty()，size()：略
  • push(obj)：在尾部添加一个元素
  • emplace(obj)：在尾部直接生成一个元素
  • pop()：删除 queue 第一个元素，没有返回值
  • swap(other_queue)：将两个 queue 容器适配器中的元素进行互换，需要注意的是，进行互换的 2 个 queue 容器适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同。