详解C++ STL容器类
|
|
noname
|
12
|
0
|
C/C++

9412 字
|
43 分钟

本文基于cpp参考手册整理所得：cppreference.com

1. STL容器类概述

1.1 简要说明

标准模板库（STL） 是 C++ 的核心组件，提供了一套高效的、可复用的容器类模板，用于管理数据集合。

1.2 分类及对应的cpp参考链接

每个类都加了链接至 cppreference 的源码说明，按需自行参考

  1. 顺序容器（Sequence Containers）：实现了按顺序访问的数据结构
    • array（C++11）：数组，固定大小的连续数组
    • vector：向量，可变大小的连续数组
    • inplace_vector（C++26） ：就地向量，可变大小、固定容量、就地连续数组
    • hive（C++26）：蜂巢容器，重用已删除元素内存的集合
    • deque：双端队列
    • forward_list（C++11）：单向链表
    • list：列表，双向链表
    • string（特化容器）：字符串
  2. 关联容器（Associative Containers）：基于红黑树实现了可快速搜索(O(log n)复杂度)的自动（基于Key）排序数据结构
    • set：集合，按键排序的唯一键集合
    • map：映射，按键排序的键值对集合，键具有唯一性
    • multiset：多重集合，按键排序的键集合
    • multimap：多重映射，按键排序的键值对集合
  3. 无序容器（Unordered Associative Containers）：基于哈希表实现了查找高效（平均时间复杂度 O(1)，最坏情况 O(n)）的无序数组结构
    • unordered_set（C++11）：无序集合，由键哈希的唯一键集合
    • unordered_map（C++11）：无序映射，由键哈希的键值对集合，键唯一
    • unordered_multiset（C++11）：无序多重集合，由键哈希的键集合
    • unordered_multimap（C++11）：无序多重映射，键值对集合，通过键进行哈希存储
  4. 容器适配器（Container Adapters）：为顺序容器提供了不同的接口，是对底层容器的接口封装
    • stack：栈，适配容器以提供栈（后进先出数据结构）功能
    • queue：队列，适配容器以提供队列（先进先出数据结构）
    • priority_queue：优先队列，适配容器以提供优先队列
    • flat_set（C++23）：扁平集合，适配容器以提供按键排序的唯一键集合
    • flat_map（C++23）：扁平映射，适配两个容器以提供按键排序的唯一键值对集合
    • flat_multiset（C++23）：扁平多重集合，适配容器以提供按键排序的键集合
    • flat_multimap（C++23）：扁平多重映射，适配两个容器以提供按键排序的键值对集合
  5. 视图（Views）：用于与元素非拥有数组上的一维或多维视图进行交互
    • span（C++20）：跨度视图，对连续对象序列的跨度视图，支持动态/静态范围
    • mdspan（C++23）：多维跨度视图，支持自定义布局映射

以下是根据您的查询，基于C++标准（截至C++26草案）和优先参考联网信息，对每个容器类的特性、使用场景及所有成员函数（操作）的详细说明。我将按照您提供的结构组织内容：顺序容器、关联容器、无序容器、容器适配器和视图。对于每个容器，我会：

  • 特性：描述容器的核心行为和内部实现。
  • 使用场景：说明典型应用场景和优缺点。
  • 所有成员函数（操作）：列出所有标准成员函数，包括构造函数、迭代器、容量操作、元素访问、修改器等（基于C++26草案，确保全面覆盖）。

我优先参考了联网信息（如提供的摘要和权威来源），并在回答结尾标明了信息来源链接。对于非标准容器（如 inplace_vector 和 hive），我将基于标准C++解释或说明其状态；C++23/C++26新增容器（如 flat_set、span）已包含。

2. 详细用法说明

注：C++26规划的类就略过了，视图也就略过了，感兴趣的自行查看cppreference.com

2.1 顺序容器

2.1.1 array

特性：

固定大小的数组，存储在连续内存中。大小在编译时确定，不支持动态扩容。性能高，无动态分配开销。

时间复杂度：所有访问操作O(1)；fill操作O(N)；swap操作O(N)（实际实现可能优化为O(1)）。

底层实现
原生数组封装（如 T[N]）。

使用场景：

适用于固定大小数组的需求，如缓冲区、小型查找表。优点：随机访问快（O(1)），内存局部性好；缺点：大小不可变，插入/删除元素需整体操作。

所成员函数：

  1. 赋值操作：
    • operator=(const array& other)：拷贝赋值
    • fill(const T& value)：将所有元素设置为value
  2. 元素访问：
    • operator[](size_type pos)：无边界检查访问
    • at(size_type pos)：带边界检查访问，越界抛出std::out_of_range
    • front()：访问第一个元素
    • back()：访问最后一个元素
    • data()：返回指向底层数组的指针
  3. 迭代器：
    • begin()/cbegin()：指向第一个元素的迭代器
    • end()/cend()：指向尾后位置的迭代器
    • rbegin()/crbegin()：反向迭代器，指向最后一个元素
    • rend()/crend()：反向迭代器，指向首前位置
  4. 容量操作：
    • size()：返回元素数量（恒等于N）
    • max_size()：返回可容纳的最大元素数（恒等于N）
    • empty()：检查是否为空（N==0时返回true）
  5. 修改器：
    • swap(array& other)：交换两个array的内容
    • fill(const T& value)：填充所有元素为指定值
  6. 非成员函数：
    • operator==, operator!=, operator<, etc.：按字典序比较
    • std::get<I>(array&)：访问第I个元素（I必须是编译期常量）
    • std::swap(array& a, array& b)：特化的swap算法

2.1.2 vector

特性：

动态数组，存储在连续内存中。支持快速随机访问（O(1)），末端插入/删除高效（O(1) 摊销），中间插入/删除慢（O(n)）。自动扩容时重新分配内存。

时间复杂度：随机访问O(1)；尾部插入/删除在不扩容时O(1)，需要扩容时O(n)（但均摊分析为O(1)）；中间/头部插入/删除O(n)；查找操作O(n)（无序时）。

底层实现

动态分配的数组（扩容时重新分配，通常按 2 倍增长）。

使用场景：

适用于需要动态数组的场景，如数据收集、动态列表。优点：末端操作快，内存紧凑；缺点：中间插入/删除性能低，扩容可能导致性能抖动。

成员函数：

  1. 赋值操作：
    • operator=(const vector& other)：拷贝赋值
    • operator=(vector&& other)：移动赋值(C++11)
    • operator=(std::initializer_list<T> ilist)：初始化列表赋值(C++11)
    • assign(size_type count, const T& value)：赋值count个value拷贝
    • assign(InputIt first, InputIt last)：用范围[first,last)赋值
    • assign(std::initializer_list<T> ilist)：用初始化列表赋值
  2. 元素访问：
    • operator[](size_type pos)：访问指定位置元素（无边界检查）
    • at(size_type pos)：访问指定位置元素（有边界检查，越界抛出异常）
    • front()：访问首元素
    • back()：访问末尾元素
    • data()：返回指向底层数组的指针(C++11)
  3. 迭代器：
    • begin()/end()：返回指向首元素和尾后位置的迭代器
    • cbegin()/cend()：const版本迭代器
    • rbegin()/rend()：反向迭代器
    • crbegin()/crend()：const反向迭代器
  4. 容量操作：
    • empty()：检查容器是否为空
    • size()：返回元素数量
    • max_size()：返回可容纳的最大元素数
    • capacity()：返回当前分配的存储容量
    • reserve(size_type new_cap)：增加容量（如new_cap > capacity()）
    • shrink_to_fit()：请求移除未使用的容量(C++11)
  5. 修改器：
    • clear()：清空容器
    • insert(const_iterator pos, const T& value)：在pos前插入value
    • insert(const_iterator pos, size_type count, const T& value)：插入count个value
    • insert(const_iterator pos, InputIt first, InputIt last)：插入范围元素
    • emplace(const_iterator pos, Args&&... args)：在pos前就地构造元素(C++11)
    • erase(const_iterator pos)：删除pos处的元素
    • erase(const_iterator first, const_iterator last)：删除范围元素
    • push_back(const T& value)：尾部添加元素
    • emplace_back(Args&&... args)：尾部就地构造元素(C++11)
    • pop_back()：删除尾部元素
    • resize(size_type count)：改变容器大小
    • resize(size_type count, const T& value)：改变大小并用value填充新元素
    • swap(vector& other)：交换内容
  6. 非成员函数：
    • operator==, operator!=, operator<, operator<=, operator>, operator>=：比较两个vector
    • std::swap(vector& lhs, vector& rhs)：特化的swap算法
    • std::erase(vector& c, const T& value)：删除所有等于value的元素(C++20)
    • std::erase_if(vector& c, Predicate pred)：删除所有使pred为true的元素(C++20)

2.1.3 deque

特性：

双端队列，存储在多个块中（分段连续内存）。

时间复杂度：头尾插入/删除O(1)；随机访问O(1)；中间插入/删除O(n)（通常比vector快，因为不需要移动所有元素）；迭代器递增/递减O(1)；排序O(n log n)。

底层实现：

使用一个动态数组（指针数组）管理多个固定大小的连续内存块，类似一个“动态二维数组”，即由多个固定大小的块（chunk）组成”块链“结构，使用中央映射表（map）管理块指针。

使用场景：

需两端操作的场景，如队列管理。优点：两端操作快；缺点：内存不连续，局部性差。

成员函数：

  1. 赋值操作：
    • operator=(const deque& other)：拷贝赋值
    • assign(size_type count, const T& value)：赋值count个value拷贝
    • assign(InputIt first, InputIt last)：用范围[first,last)赋值
  2. 元素访问：
    • operator[](size_type pos)：访问指定位置元素（无边界检查）
    • at(size_type pos)：访问指定位置元素（有边界检查，越界抛出异常）
    • front()：访问第一个元素
    • back()：访问最后一个元素
  3. 迭代器：
    • begin()/end()：返回指向首元素/尾后元素的迭代器
    • rbegin()/rend()：返回反向迭代器
    • cbegin()/cend()：const版本迭代器
    • crbegin()/crend()：const反向迭代器
  4. 容量操作：
    • empty()：检查是否为空
    • size()：返回元素数量
    • max_size()：返回可容纳的最大元素数
    • shrink_to_fit()：请求减少内存使用（非强制）
  5. 修改器：
    • clear()：删除所有元素
    • insert(const_iterator pos, const T& value)：在pos前插入value
    • insert(const_iterator pos, size_type count, const T& value)：插入count个value
    • insert(const_iterator pos, InputIt first, InputIt last)：插入范围元素
    • emplace(const_iterator pos, Args&&... args)：在pos前就地构造元素
    • erase(const_iterator pos)：删除pos处元素
    • erase(const_iterator first, const_iterator last)：删除范围元素
    • push_back(const T& value)：在尾部插入元素
    • emplace_back(Args&&... args)：在尾部就地构造元素
    • pop_back()：删除尾部元素
    • push_front(const T& value)：在头部插入元素
    • emplace_front(Args&&... args)：在头部就地构造元素
    • pop_front()：删除头部元素
    • resize(size_type count)：调整容器大小
    • resize(size_type count, const T& value)：调整大小并用value填充新元素
    • swap(deque& other)：交换两个deque内容
  6. 非成员函数：
    • operator==, operator!=, operator<, operator<=, operator>, operator>=：比较两个deque
    • std::swap(deque& lhs, deque& rhs)：交换两个deque

2.1.4 forward_list

特性：

单向链表，每个元素指向下一个。仅支持前向遍历。

时间复杂度：插入/删除O(1)（已知位置时）；随机访问O(n)；查找O(n)。

底层实现：

使用头节点简化边界条件处理，维护头指针和尾指针（部分实现优化）

使用场景：

内存受限或需高效插入/删除的场景。优点：小内存开销；缺点：无反向迭代器。

成员函数：

  1. 赋值操作：
    • operator=(const forward_list& other)：拷贝赋值
    • assign(size_type count, const T& value)：赋值count个value拷贝
    • assign(InputIt first, InputIt last)：用范围[first,last)赋值
  2. 元素访问：
    • front()：访问首元素（空链表时行为未定义）
  3. 迭代器：
    • before_begin()：返回指向第一个元素前位置的迭代器
    • begin()：返回指向第一个元素的迭代器
    • end()：返回尾后迭代器
    • cbefore_begin(), cbegin(), cend()：const版本
  4. 容量操作：
    • empty()：检查是否为空链表
    • max_size()：返回可容纳的最大元素数
  5. 修改器：
    • clear()：删除所有元素
    • insert_after(const_iterator pos, const T& value)：在pos后插入value
    • insert_after(const_iterator pos, size_type count, const T& value)：插入count个value
    • insert_after(const_iterator pos, InputIt first, InputIt last)：插入范围元素
    • emplace_after(const_iterator pos, Args&&... args)：在pos后就地构造元素
    • erase_after(const_iterator pos)：删除pos后的元素
    • erase_after(const_iterator first, const_iterator last)：删除范围元素
    • push_front(const T& value)：在链表头插入元素
    • emplace_front(Args&&... args)：在链表头就地构造元素
    • pop_front()：删除链表头元素
    • resize(size_type count)：调整链表大小为count
    • resize(size_type count, const T& value)：调整大小并用value填充新元素
    • swap(forward_list& other)：交换两个链表内容
  6. 链表操作：
    • merge(forward_list& other)：合并两个已排序链表
    • merge(forward_list& other, Compare comp)：用comp比较合并
    • splice_after(const_iterator pos, forward_list& other)：将other的所有元素移到pos后
    • splice_after(const_iterator pos, forward_list& other, const_iterator it)：移动it后的元素
    • splice_after(const_iterator pos, forward_list& other, const_iterator first, const_iterator last)：移动范围元素
    • remove(const T& value)：删除所有等于value的元素
    • remove_if(UnaryPredicate p)：删除所有使p为true的元素
    • reverse()：反转链表顺序
    • unique()：删除连续重复元素
    • unique(BinaryPredicate p)：用p判断是否重复
    • sort()：升序排序链表
    • sort(Compare comp)：用comp比较排序
  7. 非成员函数：
    • operator==, operator!=, operator<, operator<=, operator>, operator>=：比较两个链表
    • std::swap(forward_list& lhs, forward_list& rhs)：交换两个链表

2.1.5 list

特性：

双向链表，每个元素指向前后元素。支持双向遍历。

时间复杂度：插入/删除操作O(1)；查找操作O(n)；sort操作O(n log n)；merge/reverse/unique等操作O(n)；size()操作：O(1)（C++11起）。

底层实现：

通常实现为环形双向链表，带哨兵节点，维护头指针和尾指针，可能包含size缓存（C++11后）

使用场景：

需频繁中间插入/删除的场景，如 LRU 缓存。优点：稳定迭代器；缺点：内存开销大。

成员函数：

  1. 赋值操作：
    • operator=(const list& other)：拷贝赋值
    • operator=(list&& other)：移动赋值(C++11)
    • assign(size_type count, const T& value)：赋值count个value拷贝
    • assign(InputIt first, InputIt last)：用范围[first,last)赋值
    • assign(initializer_list<T> ilist)：用初始化列表赋值(C++11)
  2. 元素访问：
    • front()：访问首元素（空链表时行为未定义）
    • back()：访问尾元素（空链表时行为未定义）
  3. 迭代器：
    • begin()：返回指向第一个元素的迭代器
    • end()：返回尾后迭代器
    • rbegin()：返回指向尾元素的反向迭代器
    • rend()：返回指向首前位置的反向迭代器
    • cbegin(), cend(), crbegin(), crend()：const版本(C++11)
  4. 容量操作：
    • empty()：检查是否为空链表
    • size()：返回元素数量（C++11起保证O(1)）
    • max_size()：返回可容纳的最大元素数
  5. 修改器：
    • clear()：删除所有元素
    • insert(const_iterator pos, const T& value)：在pos前插入value
    • insert(const_iterator pos, size_type count, const T& value)：插入count个value
    • insert(const_iterator pos, InputIt first, InputIt last)：插入范围元素
    • emplace(const_iterator pos, Args&&... args)：在pos前就地构造元素(C++11)
    • erase(const_iterator pos)：删除pos处的元素
    • erase(const_iterator first, const_iterator last)：删除范围元素
    • push_back(const T& value)：在链表尾插入元素
    • emplace_back(Args&&... args)：在链表尾就地构造元素(C++11)
    • pop_back()：删除链表尾元素
    • push_front(const T& value)：在链表头插入元素
    • emplace_front(Args&&... args)：在链表头就地构造元素(C++11)
    • pop_front()：删除链表头元素
    • resize(size_type count)：调整链表大小为count
    • resize(size_type count, const T& value)：调整大小并用value填充新元素
    • swap(list& other)：交换两个链表内容
  6. 链表操作：
    • merge(list& other)：合并两个已排序链表
    • merge(list& other, Compare comp)：用comp比较合并
    • splice(const_iterator pos, list& other)：将other的所有元素移到pos前
    • splice(const_iterator pos, list& other, const_iterator it)：移动it处的元素
    • splice(const_iterator pos, list& other, const_iterator first, const_iterator last)：移动范围元素
    • remove(const T& value)：删除所有等于value的元素
    • remove_if(UnaryPredicate p)：删除所有使p为true的元素
    • reverse()：反转链表顺序
    • unique()：删除连续重复元素
    • unique(BinaryPredicate p)：用p判断是否重复
    • sort()：升序排序链表
    • sort(Compare comp)：用comp比较排序
  7. 非成员函数：
    • operator==, operator!=, operator<, operator<=, operator>, operator>=：比较两个链表
    • std::swap(list& lhs, list& rhs)：交换两个链表(C++11)

2.1.6 string

特性：

std::string 是 std::basic_string<char> 的特化，动态字符串存储在连续内存。

时间复杂度：随机访问O(1)；在末尾插入/删除均摊O(1)；在中间插入/删除O(n)；查找操作最坏情况O(n*m)。

底层实现：

内存布局与vector类似但额外保证以’\0’结尾，典型实现使用SSO优化（通常16字节以下字符串直接存储）。

使用场景：

文本处理、配置存储。优点：字符串操作丰富；缺点：大字符串操作可能慢。

成员函数：

  1. 赋值操作：
    • operator=(const string& str)：拷贝赋值
    • operator=(const char* s)：从C字符串赋值
    • operator=(char ch)：赋值为单个字符
    • assign()：多种重载形式，功能类似构造函数
  2. 元素访问：
    • operator[](size_type pos)：无检查访问字符
    • at(size_type pos)：带边界检查访问字符
    • front()：访问首字符
    • back()：访问末尾字符
    • data()：返回底层字符数组(C++11起保证以null结尾)
    • c_str()：返回C风格字符串指针
  3. 迭代器：
    • begin()/end()
    • rbegin()/rend()
    • cbegin()/cend()
    • crbegin()/crend()
  4. 容量操作：
    • empty()：检查是否为空
    • size()/length()：返回字符数
    • max_size()：返回最大可能字符数
    • reserve(size_type new_cap)：预留存储空间
    • capacity()：返回当前分配的存储容量
    • shrink_to_fit()：请求减少容量以适应大小
  5. 修改操作：
    • clear()：清空内容
    • insert()：多种重载形式插入字符/字符串
    • erase()：删除字符
    • push_back(char ch)：追加字符
    • pop_back()：删除末尾字符
    • append()：追加字符/字符串
    • operator+=()：追加字符/字符串
    • replace()：替换子串
    • resize()：调整大小
    • swap(string& other)：交换内容
  6. 字符串操作：
    • substr(size_type pos = 0, size_type count = npos)：返回子串
    • compare()：多种重载形式比较字符串
    • find()：查找子串/字符
    • rfind()：反向查找
    • find_first_of()：查找字符集中任一字符首次出现
    • find_last_of()：查找字符集中任一字符最后出现
    • find_first_not_of()：查找不在字符集中的字符首次出现
    • find_last_not_of()：查找不在字符集中的字符最后出现
  7. 非成员函数：
    • operator+：字符串连接
    • operator>>/operator<<：流输入/输出
    • getline()：从流读取一行
    • 数值转换函数：stoi(), stol(), stof()等
    • hash<string>：哈希支持

2.2 关联容器

基于红黑树实现。

2.2.1 set

特性：

唯一键集合，键不可重复，自动排序。

时间复杂度：查找操作O(log n)；插入操作O(log n)；删除操作O(log n)；遍历操作O(n)。

底层实现：

红黑树（自平衡二叉查找树）实现。

使用场景：

需唯一元素和有序访问的场景，如去重集合。优点：查找快；缺点：插入/删除慢于无序容器。

成员函数：

  1. 赋值操作：
    • operator=(const set& other)：拷贝赋值
    • operator=(std::initializer_list<T> ilist)：用初始化列表赋值
  2. 元素访问：
    • 不提供直接访问元素的operator[]
  3. 迭代器：
    • begin(), cbegin()：返回指向首元素的迭代器（最小元素）
    • end(), cend()：返回尾后迭代器
    • rbegin(), crbegin()：返回指向尾元素的反向迭代器（最大元素）
    • rend(), crend()：返回反向尾后迭代器
  4. 容量操作：
    • empty()：检查是否为空
    • size()：返回元素数量
    • max_size()：返回可容纳的最大元素数
  5. 修改器：
    • clear()：删除所有元素
    • insert(const T& value)：插入元素
    • insert(T&& value)：移动插入元素
    • insert(const_iterator hint, const T& value)：在hint位置附近插入
    • insert(InputIt first, InputIt last)：插入范围元素
    • insert(std::initializer_list<T> ilist)：插入初始化列表
    • emplace(Args&&... args)：就地构造元素
    • emplace_hint(const_iterator hint, Args&&... args)：在hint位置附近就地构造
    • erase(const_iterator pos)：删除pos位置的元素
    • erase(const T& key)：删除键等于key的元素
    • erase(const_iterator first, const_iterator last)：删除范围元素
    • swap(set& other)：交换两个集合内容
    • extract(const_iterator pos)：提取节点（C++17）
    • extract(const T& key)：提取键等于key的节点（C++17）
    • merge(set& source)：合并source集合（C++17）
  6. 查找操作：
    • count(const T& key)：返回键等于key的元素数量（0或1）
    • find(const T& key)：查找键等于key的元素
    • contains(const T& key)：检查是否包含键等于key的元素（C++20）
    • equal_range(const T& key)：返回匹配键的范围
    • lower_bound(const T& key)：返回首个不小于key的元素迭代器
    • upper_bound(const T& key)：返回首个大于key的元素迭代器
  7. 观察器：
    • key_comp()：返回键比较器
    • value_comp()：返回值比较器（与key_comp相同）
  8. 非成员函数：
    • operator==, operator!=, operator<, operator<=, operator>, operator>=：比较两个集合
    • std::swap(set& lhs, set& rhs)：交换两个集合
    • std::erase_if(set& c, Predicate pred)：删除满足条件的元素（C++20）

示例用法：

std::set<int> mySet;
mySet.insert(10);
mySet.insert(20);
mySet.insert(30);
mySet.insert(40);

// 输出 set 中的元素
for (int num : mySet) {
std::cout << num << " ";
}
// 查找元素
if (mySet.find(20) != mySet.end()) {
    std::cout << "20 is in the set." << std::endl;
} else {
    std::cout << "20 is not in the set." << std::endl;
}

2.2.2 map

特性：

键值对集合，键唯一，基于红黑树。键自动排序。

底层实现：

红黑树（自平衡二叉查找树）实现。

使用场景：

字典或配置映射。优点：按键查找快；缺点：内存开销大。

成员函数：

  1. 赋值操作：
    • operator=(const map& other)：拷贝赋值
    • operator=(initializer_list<pair<const Key, T>> ilist)：初始化列表赋值
  2. 元素访问：
    • at(const Key& key)：访问指定键的元素，键不存在时抛出异常
    • operator[](const Key& key)：访问或插入指定键的元素
    • operator[](Key&& key)：移动语义版本
  3. 迭代器：
    • begin(), cbegin()：返回指向首元素的迭代器
    • end(), cend()：返回尾后迭代器
    • rbegin(), crbegin()：返回反向迭代器
    • rend(), crend()：返回反向尾后迭代器
  4. 容量操作：
    • empty()：检查是否为空
    • size()：返回元素数量
    • max_size()：返回可容纳的最大元素数
  5. 修改器：
    • clear()：清空所有元素
    • insert(const pair<const Key, T>& value)：插入元素
    • insert(pair<const Key, T>&& value)：移动插入
    • insert(const_iterator hint, const pair<const Key, T>& value)：提示位置插入
    • emplace(Args&&... args)：就地构造元素
    • emplace_hint(const_iterator hint, Args&&... args)：提示位置就地构造
    • erase(iterator pos)：删除指定位置元素
    • erase(const Key& key)：删除指定键的元素
    • erase(iterator first, iterator last)：删除范围元素
    • swap(map& other)：交换内容
  6. 查找操作：
    • find(const Key& key)：查找指定键
    • count(const Key& key)：返回匹配键的数量（0或1）
    • contains(const Key& key)（C++20）：检查是否包含键
    • lower_bound(const Key& key)：返回首个不小于key的元素迭代器
    • upper_bound(const Key& key)：返回首个大于key的元素迭代器
    • equal_range(const Key& key)：返回匹配键的范围
  7. 观察器：
    • key_comp()：返回键比较函数
    • value_comp()：返回值比较函数
  8. 非成员函数：
    • operator==, operator!=, <, <=, >, >=：比较两个map
    • std::swap(map& lhs, map& rhs)：交换两个map

示例用法：

std::map<std::string, int> ageMap;
ageMap["Alice"] = 25;          // 插入或更新
ageMap.insert({"Bob", 30});    // 插入
ageMap.emplace("Charlie", 35); // 就地构造

if (ageMap.find("Alice") != ageMap.end()) {
    std::cout << "Alice's age: " << ageMap["Alice"] << std::endl;
}

for (const auto& [name, age] : ageMap) {
    std::cout << name << ": " << age << std::endl;
}

2.2.3 multiset

特性：

类似 set，有序，键可重复。元素自动按升序排列（或自定义排序规则）

时间复杂度：插入O(log n)；查找O(log n)；删除O(log n) + O(m)（m为删除的相同键元素数量）；遍历O(n)。

底层实现：

红黑树结构保持平衡，相同键值的元素存储在相邻位置，维护树根指针和比较函数对象。

使用场景：

允许多个相同元素的集合，如计数系统。

成员函数：

与set类似。特有成员函数如下：

  1. 插入操作：
    • iterator insert(const T& value)：总是插入成功，返回指向新元素的迭代器
    • iterator insert(T&& value)：移动插入版本
    • void insert(InputIt first, InputIt last)：范围插入
  2. 查找操作：
    • size_type count(const T& key) const：返回等于key的元素数量（可能>1）
    • std::pair<iterator,iterator> equal_range(const T& key)：返回等于key的元素范围
    • iterator lower_bound(const T& key)：返回第一个不小于key的元素
    • iterator upper_bound(const T& key)：返回第一个大于key的元素
  3. 删除操作：
    • size_type erase(const T& key)：删除所有等于key的元素，返回删除数量

示例用法：

std::multiset<int> scores = {90, 85, 90, 78, 85, 92};

// 统计90分的人数
auto count = scores.count(90);  // 返回2

// 获取所有85分的迭代器范围
auto [begin, end] = scores.equal_range(85);
for (auto it = begin; it != end; ++it) {
    std::cout << *it << " ";  // 输出：85 85
}

// 删除所有90分
scores.erase(90);  // 返回删除数量2

2.2.4 multimap

特性：

类似 map，有序，键可重复。

插入性能相比map略快(不需要检查键是否已存在)；查找性能与map相同(O(log n))；内存占用每个节点需要额外存储父指针和颜色标记。

底层实现：

红黑树结构保持平衡，相同键值的元素存储在相邻位置，维护树根指针和比较函数对象。

使用场景：

一键多值的映射。

成员函数：

类似 map，但无 operator[]（因键不唯一）。特有成员函数如下：

  1. 范围查找：
    • equal_range(const Key& key)：返回包含所有匹配键的元素范围[pair<iterator,iterator>]
    • count(const Key& key)：返回匹配键的元素数量
  2. 插入操作：
    • insert(const value_type& value)：总是插入新元素(即使键已存在)
    • insert(InputIt first, InputIt last)：插入范围元素
    • emplace(Args&&... args)：就地构造新元素
  3. 查找操作：
    • find(const Key& key)：返回第一个匹配键的元素的迭代器
    • lower_bound(const Key& key)：返回第一个不小于key的元素迭代器
    • upper_bound(const Key& key)：返回第一个大于key的元素迭代器

示例用法：

std::multimap<std::string, int> mmap;

// 插入重复键
mmap.insert({"apple", 1});
mmap.insert({"apple", 2});
mmap.insert({"banana", 3});

// 查找所有"apple"对应的值
auto range = mmap.equal_range("apple");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";  // 输出: 1 2
}

// 遍历所有元素(按键排序)
for (const auto& [key, value] : mmap) {
    std::cout << key << ":" << value << " "; 
    // 可能输出: apple:1 apple:2 banana:3
}

2.3 无序容器

无序容器基于哈希表实现，元素无序，平均查找 O(1)。

2.3.1 unordered_set

特性：

唯一键集合，哈希表实现。元素唯一且无序存储。

底层实现：

基于哈希表实现的集合容器，使用链地址法解决哈希冲突，动态调整桶数量以保持负载因子，每个桶存储一个链表头节点。

使用场景：

需快速查找且不关心顺序的场景。优点：平均性能高；缺点：哈希冲突时性能降级。

与set的主要区别：

特性 unordered_set set
实现方式 哈希表 红黑树
元素顺序 无序 有序
时间复杂度 平均O(1)，最坏O(n) 稳定O(log n)
内存占用 较高(需维护桶数组) 较低
迭代器稳定性 插入可能使所有迭代器失效 插入删除保持稳定

成员函数：

与set类似。特有成员函数如下：

  1. 桶接口：
    • bucket_count()：返回桶的数量
    • max_bucket_count()：返回最大可能的桶数
    • bucket_size(size_type n)：返回第n个桶中的元素数
    • bucket(const Key& key)：返回key对应的桶索引
  2. 哈希策略：
    • load_factor()：返回当前负载因子(元素数/桶数)
    • max_load_factor()：返回/设置最大允许负载因子
    • rehash(size_type count)：设置桶数为至少count
    • reserve(size_type count)：预留空间至少容纳count个元素
  3. 哈希函数：
    • hash_function()：返回使用的哈希函数对象
    • key_eq()：返回键相等比较函数对象

2.3.2 unordered_map

参考unordered_set与set的区别。

特性：

键值对集合，哈希表实现。键唯一，元素无序存储。

平均情况下插入/删除/查找时间复杂度O(1)；最坏情况下时间复杂度O(n)（哈希冲突严重时）；支持透明操作（C++14起）。

使用场景：

快速键值查找。

与map的主要区别：

特性 unordered_map map
底层结构 哈希表 红黑树
元素顺序 无序 按键排序
时间复杂度 平均O(1)，最坏O(n) 稳定O(log n)
迭代器稳定性 可能因rehash失效 始终稳定
内存占用 较高（需维护哈希表） 较低
适用场景 需要快速查找且不关心顺序 需要有序遍历或稳定性能
透明哈希支持 是（C++14起） 否
自定义哈希函数 必须提供 不需要

成员函数：

类似 unordered_set，增加 at, operator[]。特有成员函数如下：

  1. 桶接口：
    • bucket_count()：返回桶数量
    • max_bucket_count()：返回最大桶数量
    • bucket_size(size_type n)：返回第n个桶的元素数
    • bucket(const Key& key)：返回键key所在的桶索引
  2. 哈希策略：
    • load_factor()：返回当前负载因子（元素数/桶数）
    • max_load_factor()：返回/设置最大负载因子
    • rehash(size_type count)：设置至少count个桶
    • reserve(size_type count)：预留空间至少容纳count个元素
  3. 哈希函数：
    • hash_function()：返回哈希函数对象
  4. 键相等比较：
    • key_eq()：返回键相等比较函数对象

2.3.3 unordered_multiset

unordered_multiset 与 unordered_set 的区别参考 multiset 与 set 的区别，unordered_multiset 与 multiset 的区别参考 unordered_set 与 set 的区别。

明显区别就是允许键重复。

略。

2.3.4 unordered_multimap

unordered_multimap 与 unordered_map 的区别参考 multimap 与 map 的区别，unordered_multimap 与 multimap 的区别参考 unordered_map 与 map 的区别。

明显区别就是允许键重复。

略。

2.4 容器适配器

容器适配器提供特定接口，基于其他容器实现。

2.4.1 stack

特性：

LIFO（后进先出）栈，默认基于 deque。只允许在栈顶进行插入和删除操作，不提供迭代器功能。

时间复杂度：插入/删除O(1)；访问栈顶O(1)；搜索：O(n)。

底层实现：

默认使用deque实现，但也可以指定其他容器（需满足以下操作）：

back()、push_back()、pop_back()

常用底层容器选择：

deque（默认）：综合性能好；vector：内存连续，但扩容时性能下降；list：每次操作内存分配开销较大

使用场景：

函数调用栈、撤销操作。

成员函数：

  1. 赋值操作：
    • operator=(const stack& other)：拷贝赋值
    • operator=(stack&& other)：移动赋值
  2. 元素访问：
    • top()：返回栈顶元素的引用（空栈时行为未定义）
    • top() const：const版本
  3. 容量操作：
    • empty()：检查是否为空栈
    • size()：返回元素数量
  4. 修改器：
    • push(const T& value)：将value压入栈顶
    • push(T&& value)：移动压入栈顶
    • emplace(Args&&... args)：在栈顶就地构造元素
    • pop()：移除栈顶元素（空栈时行为未定义）
    • swap(stack& other)：交换两个栈的内容
  5. 非成员函数：
    • operator==, operator!=, operator<, operator<=, operator>, operator>=：比较两个栈
    • std::swap(stack& lhs, stack& rhs)：交换两个栈

2.4.2 queue

特性：

FIFO（先进先出）队列，默认基于 deque。只允许在队尾插入元素、队头删除元素，不支持随机访问和中间插入/删除操作。

底层实现：

默认使用deque作为底层容器，也可指定list等支持以下操作的容器：

back()、front()、push_back()、pop_front()、empty()、size()

使用场景：

需要先进先出处理的场景、任务调度、消息队列、广度优先搜索(BFS)算法。

成员函数：

  1. 赋值操作：
    • operator=(const queue& other)：拷贝赋值
    • operator=(queue&& other)：移动赋值
  2. 元素访问：
    • front()：访问队头元素（空队列时行为未定义）
    • back()：访问队尾元素（空队列时行为未定义）
  3. 容量操作：
    • empty()：检查队列是否为空
    • size()：返回队列中元素数量
  4. 修改器：
    • push(const T& value)：在队尾插入元素
    • push(T&& value)：在队尾移动插入元素
    • emplace(Args&&... args)：在队尾就地构造元素
    • pop()：删除队头元素
  5. 非成员函数：
    • operator==, operator!=, operator<, operator<=, operator>, operator>=：比较两个队列
    • std::swap(queue& lhs, queue& rhs)：交换两个队列内容

2.4.3 priority_queue

特性：

优先级队列（堆结构实现），默认基于 vector。元素按优先级排序。元素部分有序（堆序），非完全排序。插入/删除操作时间复杂度O(log n)，顶部元素访问时间复杂度O(1)。

底层实现：

使用完全二叉树（堆）结构。

使用场景：

需要频繁访问最大/最小元素的场景、任务调度系统、图算法。

成员函数：

  1. 赋值操作：
    • operator=(const priority_queue& other)：拷贝赋值
    • operator=(priority_queue&& other)：移动赋值
  2. 元素访问：
    • top()：访问顶部元素（最大/最小元素）
  3. 容量操作：
    • empty()：检查是否为空
    • size()：返回元素数量
  4. 修改器：
    • push(const T& value)：插入元素并维护堆性质
    • push(T&& value)：移动插入元素
    • emplace(Args&&... args)：就地构造元素并插入
    • pop()：删除顶部元素
    • swap(priority_queue& other)：交换内容
  5. 非成员函数：
    • swap(priority_queue& lhs, priority_queue& rhs)：交换两个队列

2.4.4 flat_set

特性：

C++23新引入的，基于排序数组的集合，键唯一，连续存储。查找 O(log n)，插入/删除 O(n)。

使用场景：

内存敏感场景，需快速迭代。优点：内存局部性好；缺点：修改慢。

与set对比：

特性 flat_set std::set
内存布局 连续 节点分散
内存占用 小（无指针开销） 大（每个元素额外开销）
查找性能 优（缓存友好） 良
插入/删除性能 差（O(n)移动元素） 优（O(1)节点操作）
指针稳定性 无 有
实现复杂度 简单（数组+二分查找） 复杂（红黑树）

成员函数：

类似 set，增加 extract 和容器接口。

2.4.5 flat_map

特性：

C++23新引入的，基于排序数组的键值对容器，键唯一，连续存储。查找复杂度O(log n)，插入/删除复杂度O(n)，插入/删除操作会使所有迭代器失效。

底层实现：

使用两个单独的vector分别存储keys和values（部分实现优化），维护排序状态，插入时保持有序。

使用场景：

需要关联容器且内存连续性重要的场景。

与map的主要对比：

特性 flat_map std::map
底层实现 排序数组（vector） 红黑树
内存布局 连续内存 非连续内存（节点分散）
查找性能 O(log n)，缓存友好 O(log n)，缓存不友好
插入性能 O(n)（需要移动元素） O(log n)
删除性能 O(n)（需要移动元素） O(log n)
迭代性能 极快（顺序访问） 较慢（指针跳转）
内存开销 小（仅需存储元素） 大（每个节点额外开销）
元素稳定性 插入/删除会使所有迭代器失效 只有被删除元素的迭代器失效
排序保证 始终排序 始终排序
最佳使用场景 小数据集/频繁迭代/内存敏感 大数据集/频繁插入删除

成员函数：

类似 map，增加 extract 和容器接口。

2.4.6 flat_multiset

特性：

C++23新引入的，基于排序向量的多重映射容器，键唯一，内存连续布局，缓存友好。查找复杂度O(log n)，插入/删除复杂度O(n)。

使用场景：

需要快速遍历和范围查询的场景。

与map对比：

特性 flat_multimap multimap
底层实现 排序的vector 红黑树
内存布局 连续内存 非连续内存
缓存友好性 高 低
查找复杂度 O(log n) O(log n)
插入复杂度 O(n)（需要移动元素） O(log n)
删除复杂度 O(n)（需要移动元素） O(log n)
迭代器稳定性 插入/删除会使所有迭代器失效 只有被删除元素的迭代器失效
内存使用 更紧凑（无指针开销） 每个节点有额外指针开销
范围查询性能 极佳（内存连续） 一般
适合场景 查询多、修改少、需要内存效率 频繁插入删除、需要稳定迭代器
最大优势 缓存局部性和内存效率 稳定的插入删除性能

成员函数：

类似 multimap，增加 extract 和容器接口。

3. 高阶知识

3.1 迭代器失效

失效场景与解决方案

容器类型 导致失效的操作 失效范围 安全操作方案
vector/string 插入（致容量变化）
删除/erase()		 所有迭代器、指针、引用 使用erase()返回的新迭代器：
it = vec.erase(it);
插入后需重新获取迭代器
deque 头尾插入/删除
中间插入/删除		 插入：所有迭代器失效
删除：被删元素相关迭代器		 插入后完全重新获取迭代器
删除时用erase()返回值：
it = deq.erase(it);
关联容器
(map/set等)		 删除当前元素 当前元素的迭代器 删除前获取下一位置：
auto next = map.erase(it++);
或C++11起：it = map.erase(it);
无序容器
(unordered_map等)		 重哈希（rehash）
删除当前元素		 重哈希：所有迭代器失效
删除：当前元素迭代器		 删除方案同关联容器
插入后避免保存迭代器

经典错误案例

// 错误：删除后继续使用失效迭代器
for(auto it = map.begin(); it != map.end(); ++it) {
  if(condition) map.erase(it);  // it立即失效，后续++操作未定义行为
}

// 正确方案（C++11起）：
for(auto it = map.begin(); it != map.end(); ) {
  if(condition) it = map.erase(it);
  else ++it;
}

3.2 线程安全

核心原则

  1. STL容器非线程安全：所有STL容器默认不保证并发访问安全（C++标准明确要求）
  2. 读写分离场景：多线程读安全（只读操作不修改容器状态）
  3. 写操作需同步：任何写入操作（插入/删除/修改）必须互斥

线程安全实现方案

  • 方案1：粗粒度锁（简单场景）

    #include 
#include 

template
class ThreadSafeMap {
public:
  V& operator[](const K& key) {
      std::lock_guard lock(mutex_);
      return data_[key];
  }

  bool insert(const K& key, const V& value) {
      std::lock_guard lock(mutex_);
      return data_.insert({key, value}).second;
  }

  // 其他接口需类似加锁...
private:
  std::map data_;
  std::mutex mutex_;
};

  • 方案2：细粒度锁（高性能场景）

    适用unordered_map + 分段锁（bucket-level locking）：读写锁（std::shared_mutex）优化读多写少场景。

    #include 
class ThreadSafeCache {
public:
  int get(const Key& k) {
      std::shared_lock lock(mutex_); // 读锁
      return data_.at(k);
  }
  void update(const Key& k, int v) {
      std::unique_lock lock(mutex_); // 写锁
      data_[k] = v;
  }
private:
  std::unordered_map data_;
  std::shared_mutex mutex_;
};

注意事项

  1. 迭代器与回调：遍历时持有锁将阻塞所有写操作
  2. 死锁风险：避免嵌套锁，使用std::scoped_lock解决多锁场景
  3. 自定义类型：若key/value为自定义类，需保证其拷贝/移动操作的异常安全

C++
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
															
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇