跳到主要内容

STL 容器

顺序容器​

实现按顺序访问的数据结构

1. array (C++11)​

静态的连续数组，封装固定大小数组的容器

template<
    class T, // 元素类型
    std::size_t N //数组大小
> struct array;

特点​

  • 结合了 C 风格数组的性能，可访问性与容器可获取大小，支持赋值，随机访问迭代器等优点。
  • 在连续的内存位置中储存对象

成员函数​

元素访问
    at() // 返回指定位置的引用，同时进行越界检查
    operator[] // 访问指定位置的引用，无边界检查
    front() // 返回首元素的引用，容器为空时，对 front 的调用是未定义的
    back() // 返回最后一个元素的引用，容器为空时未定义
    data() // 返回指向底层数组的指针，范围为 [data(), data() + size()]，container.data() 优于 &container[0]
迭代器
    begin() / cbegin() // 返回指向起始的迭代器
    end() / cend() // 返回指向末尾的迭代器，为占位符，无法解引用
    rbegin() / crbegin() // 返回指向起始的逆向迭代器
    rend() / crend() // 返回指向末尾的逆向迭代器，为占位符，无法解引用
容量
    empty() // 检查容器是否为空
    size() // 返回容纳的元素数
    max_size() // 返回可容纳的最大元素数
操作
    fill() // 以指定值填充容器
    swap() // 交换内容

2. vector​

动态连续数组

template<
    class T, // 元素类型，元素需满足可复制赋值，可复制构造，可擦除要求
    class Allocator = std::allocator<T> // 分配器，负责封装堆内存管理的对象
> class vector;

特点​

  • 线性储存，可通过迭代器，也可通过指向元素的常规指针访问元素，实现快速随机访问
  • 储存自动管理，按需扩展收缩。但通常会比静态数组占用更多空间，用以管理将来的增长。其只在额外内存耗尽时重分配。分配的内存总量可用capacity()函数查询，通过shrink_to_fit()（C++11 起）可将多余内存释放。
  • 如元素数量已知，可用reserve()提高capacity()值，消除内存重分配
  • 标准库对类型bool特化，为空间效率优化

成员函数​

// 同 array，新增：
基本
    get_allocator() // 返回相关分配器
容量
    reserve() // 预留储存空间
    capacity() // 返回当前储存空间能容纳的元素数
    shrink_to_fit() // 释放未使用空间
修改
    clear() // 清除内容
    insert() // 插入元素
    emplace() // 原位构造元素
    erase() // 擦除元素
    push_back() // 将元素添加到容器末尾
    emplace_back() // 在末尾就地构造元素
    pop_back() // 移除末元素
    resize() // 改变容器可储存元素个数
    swap() // 交换内容，仅整体交换，不会在单独元素上调用任何移动，复制或交换操作

迭代器失效​

部分操作会使迭代器失效

// 只读操作不会导致失效
swap() // end() 失效
clear(), operator=, assign() // 全部失效
reserve(), shrink_to_fit() // vector 容量改变时，全部失效
erase() // 被擦除元素及之后的所有元素（包括 end()) 失效
push_back(), emplace_back() // vector 容量改变时全部失效，否则只有 end() 失效
insert(), emplace() // vector 容量改变时，全部失效，否则只有插入点和其后失效
resize() // vector 容量改变时全部失效，否则只有 end() 与被擦除元素
pop_back() // 被擦除元素及 end() 失效

3. deque (double-ended queue)​

双端队列

template<
    class T,
    class Allocator = std::allocator<T>
> class deque;

特点​

  • 有下标顺序容器，允许在首尾两端快速插入及删除，且在任一端插入或删除不会使指向其余元素的指针或引用失效
  • 不是连续存储的，典型实现为用单独分配的固定尺寸数组，外加额外的登记。这表示下标访问必须进行二次指针解引用，与之相比vector只需要一次
  • 储存按需扩展收缩，扩张时，不涉及到复制元素到新位置。其拥有较大的最小内存开销，只保存一个元素时也需要分配整个内部数组

成员函数​

//同 vector

迭代器失效​

// 只读操作不会导致失效
swap() // end() 迭代器可能失效
shrink_to_fit(), clear(), insert(), emplace(), push_front(), //
push_back(), emplace_front(), emplace_back()                 // 全部失效
erase() // 如果起始擦除，则只有被擦除元素失效，如果在末尾擦除，则被擦除元素和 end() 失效。否则全部失效
resize() // 尺寸变大，则所有迭代器失效，尺寸变小，则只有被擦除元素和 end() 失效，尺寸不变，则无失效
pop_front() // 只有被擦除元素
pop_back() // 被擦除元素和 end()

4. forward_list (C++11)​

单链表

template<
    class T,
    class Allocator = std::allocator<T>
> class forward_list;

特点​

  • 支持在任何位置进行快速插入删除，不支持快速随机访问，实现为单链表，与std::list(双链表) 相比，其在不需要双向迭代时有更高的空间效率
  • 从链表移除元素时，指代对应元素的迭代器或引用会被非法化

成员函数​

迭代器
    before_begin() / cbefore_begin() // 返回指向第一个元素之前的迭代器
修改
    insert_after() // 在元素后插入
    emplace_after() // 在元素后原位构造
    erase_after() // 擦除元素后的元素
    push_front() // 插入元素到容器起始
    emplace_front() // 在容器头部原位构造
    pop_front() // 移除首元素
    resize() // 改变容器中可储存元素的个数
    swap() // 交换内容
操作
    merge() // 合并两个已排序列表
    splice_after() // 从另一个 forward_list 中移动元素
    remove() / remove_if() // 移除满足特定标准的元素
    reverse() // 将链表的所有元素顺序反转
    unique() // 删除连续的重复元素
    sort() // 对元素进行排序

5. list​

双链表

template<
    class T,
    class Allocator = std::allocator<T>
> class list;

特点​

  • 支持在任何位置进行快速插入删除，不支持快速随机访问，通常实现方法为双链表，与std::forward_list相比，其提供双向迭代但在空间上效率较低。

成员函数​

// 同 vector

关联容器​

实现快速查找的数据结构 (O(log n))

1. set​

唯一键集合，按照键排序

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

特点​

  • 使用比较函数进行排序，标准库如果a与b相互不小于对方，则认为他们等价： （!comp(a, b) && !comp(b, a)）
  • 搜索，移除和插入拥有对数复杂度，通常以红黑树实现

成员函数​

// 部分
修改
    emplace_hint() // 使用提示原位构造元素
    extract() // 从另一容器释出节点
    merge() // 从另一容器结合节点
查找
    count() // 返回匹配特定键的元素数量
    find() // 寻找带有特定键的元素
    contains() // (C++20) 检查容器是否含有带特定键的元素
    equal_range() // 返回匹配特定键的元素范围
    lower_bound() // 返回指向首个不小于给定键的元素的迭代器
    upper_bound() // 返回指向首个大于给定键的元素的迭代器
观察器
    key_comp() // 返回用于比较键的函数
    value_comp() // 返回用于在 value_type 类型的对象中比较键的函数

2. map​

键值对的集合，按照键排序，键是唯一的

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;

特点​

  • 储存键值对，特性同set

成员函数​

// 部分
修改
    insert_or_assign() // 插入元素，或若键已存在则赋值给当前元素
    try_emplace() // 若键不存在则原位插入，若键存在则不做任何事

3. multiset​

键的集合，按照键排序

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class multiset;

特点​

  • 允许多个Key拥有等价值的有序集容器，使用比较函数排序
  • 搜索，插入，删除操作拥有对数复杂度
  • （C++ 11 起）插入等价元素时按插入顺序，且不会更改（稳定排序）

4. multimap​

键值对的集合，按照键排序

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class multimap;

特点​

  • 允许多个元素拥有同一键
  • 同multiset

无序关联容器（C++11 起）​

提供快速查找的无序（哈希）数据结构。(平均O(1), 最坏O(n))

1. unordered_set​

唯一键的集合，按照键生成散列

template<
    class Key,
    class Hash = std::hash<Key>, // 对键进行哈希的函数
    class KeyEqual = std::equal_to<Key>, // 比较键相等的函数
    class Allocator = std::allocator<Key>
> class unordered_set;

特点​

  • 插入，搜索和移除都有平均O(1)的时间复杂度
  • 在内部元素并不被排序，而是根据其哈希值被分入不同的桶 (Bucket，扁平化的数据结构，内容在同一个逻辑层级) 中，以实现对单独元素的快速访问
  • 不可修改元素（即使通过非常指针）。因为修改会导致元素的哈希改变，并破坏容器

成员函数​

// 部分
桶接口
    bucket_count() // 返回桶数
    max_bucket_count() // 返回桶的最大数量
    bucket_size() // 返回在特定桶中的元素数量
    bucket() // 返回带有特定键的桶
哈希策略
    load_factor() // 返回每个桶的平均元素数量，即 size() / bucket_count()
    max_load_factor() // 管理每个桶的平均元素数量的最大值，若 load_factor 超过此值，自动增加桶数
    rehash() // 为至少为指定数量的桶预留储存空间并重新生成哈希表
    reserve() // 为至少为指定数量的元素预留储存空间并重新生成哈希表
观察器
    hash_function() // 返回用于对键哈希的函数
    key_eq() // 返回用于比较键的相等性的函数

迭代器失效​

swap() // end() 失效
clear(), rehash(), reserve(), operator= // 全部失效
insert(), emplace(), emplace_hint(), operator[] // 发生重哈希时，全部失效
erase() // 仅指向被擦除元素的失效

2. unordered_map​

键值对的集合，按照键生成散列，键是唯一的

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

特点​

  • 带有唯一键 - 值对的容器。
  • 同unordered_set

3. unordered_multiset​

键的集合，按照键生成散列

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_multiset;

特点​

  • 含有非唯一 Key 类型的对象集合
  • 同unordered_set

4. unordered_multimap​

键值对的集合，按照键生成散列

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_multimap;

特点​

  • 支持等价的键和将键与另一类型的值关联
  • 同unordered_set

容器适配器​

stack​

适配一个容器以提供栈（LIFO 数据结构）

template<
    class T,
    class Container = std::deque<T>
    // 用于储存元素的底层容器类型，容器必须满足序列容器的要求，并且提供以下函数：
    // back(), push_back(), pop_back()
    // 标准容器 vector, deque, list 满足
> class stack;

成员函数​

元素访问
    top() // 访问栈顶元素
容量
    empty() // 检查是否为空
    size() // 返回容纳的元素数
修改
    push() // 向栈顶插入元素
    emplace() // 在顶部原位构造元素
    pop() // 删除栈顶元素
    swap() // 交换内容

queue​

适配一个容器以提供队列（FIFO 数据结构）

template<
    class T,
    class Container = std::deque<T>
    // 必须满足序列容器的要求，并且提供以下函数：
    // back(), front(), push_back(), pop_front()
    // 标准容器 deque, list 满足
> class queue;

成员函数​

// 部分
front() // 访问第一个元素
back() // 访问最后一个元素

priority_queue​

适配一个容器以提供优先级队列

template<
    class T,
    class Container = std::vector<T>,
    // 容器需满足序列容器的要求，其迭代器满足老式随机访问迭代器的要求，且提供以下函数：
    // front(), push_back(), pop_back()
    // 标准容器 vector (包括 vector<bool>), deque 满足要求
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

特点​

  • 提供O(1)的最大元素查找，O(logn)的插入与提取
  • 通过用户提供的Compare()更改顺序
  • 工作原理类似管理某些随机访问容器中的堆
最后于 更新