目录

一、情景

题目要求

解答

二、时间复杂度

O(1)：常数时间复杂度

O(log N)：对数时间复杂度

O(N)：线性时间复杂度

O(N²)：平方时间复杂度

经典的冒泡排序

暴力枚举解决“两数之和”问题

O(N!) :阶乘时间复杂度

三、容器

vector动态数组

list双向链表容器

map关联数组

unordered_map无序的键值对容器

元素操作时间复杂度比较

随机访问

头部插入 / 删除

尾部插入 / 删除

中间插入 / 删除

查找

排序

 

一、情景

题目要求

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值target  的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

进阶：给出一个复杂度小于 o(n²) 的算法

解答

本题目使用哈希表查找。首先构建键值对 key:value，这里key为函数传入的具体数字，value为该数字在传入vector中的下标。根据哈希表的存储结构，我们可以通过已知的key直接找到这个键值对存储的位置，从而获得其value，也就是要查找的数字在传入vector中对应的下标，也就是题目要求的返回值。关于哈希表的详细介绍在本文第三节——unordered_map无序的键值对容器。

而且本程序采用边查找边存入的方式进行，遍历传入数组的同时在unordered_map对象中不断查找 target-num是否存在，如果存在便及时返回当前num下标及target-num下标并退出函数。这样即完成了目标任务，不再需要将数组后面的值继续存入基于哈希表寻址的unordered_map容器中了，可以节省一部分时间。

class Solution  
{
public:
    vector<int> twoSum(vector<int>& nums, int target) //LeetCode给定模板
    {
        //新建哈希表，其中键和值均为int类型：key为输入的nums，value为其对应的输入nums序列中的下标
        unordered_map<int, int> numMap;

        for (int i = 0; i < nums.size(); ++i) 
        {
            int complement = target - nums[i];
            // 遍历nums,检查目标与遍历项差值是否已存在于哈希表中，存在：直接返回下标，退出程序
            //不存在：将新值存入哈希表，不必将所有的值都存入哈希表这样最大程度地降低时间成本
            if (numMap.find(complement) != numMap.end()) 
            {
                return {numMap[complement], i}; //numMap[key]=value
            }
            numMap[nums[i]] = i;//以key为索引存入value
        }
        return {};//如果无解，则返回空容器
    }
};

该任务使用unordered_map无序键值对容器检索效率最高，平均为常数时间复杂度O(1)，满足题目的进阶要求。当然也可以使用暴力枚举的算法去做，但这样的时间复杂度就变成了O(N²)，具体的实现在第二节——暴力枚举解决“两数之和”问题。

二、时间复杂度

题目中要求最好给出一个时间复杂度小于o(n²)的实现算法，这里有必要先解释一下时间复杂度的概念。在现代的计算机领域中，当提到时间复杂度的时候，不关注算法所用的时间，只关注其所用的步数。因此，当运行程序的时候，认为影响算法性能的主要因素是其所需的步数。量化线性查找效率较准确的方式应该是：对于具有N个元素的数组，线性查找最多需要f_{(N)}步。

为了方便表达数据结构和算法的时间复杂度，计算机科学家从数学界借鉴了一种简洁又通用的方式，那就是大O记法。这种规范化语言使得我们可以轻松地指出一个算法的性能级别，也令学术交流变得简单。

大O记法解答的是这样的问题：当数据增长时，最大运算步数如何变化。常见的时间复杂度表示有以下五种。

O(1)：常数时间复杂度

表示算法无论面对多大的数据量，其查找步数都不变。

比如：从数组中获取指定索引的元素

int getElement(int arr[], int n, int index) 
{
    if (index >= 0 && index < n) 
    {
        return arr[index];  // 直接通过索引访问，时间固定
    }
    return -1;
}

  • 原理：数组在内存中连续存储，通过 <首地址+索引×元素大小> 直接计算地址，时间与数组长度无关。

  • 解释：访问 arr[1000] 和 arr[0] 的时间相同。

O(log N)：对数时间复杂度

其中log(N)实际上表示的是log_{m}N，表示算法的步数随输入规模N的增长呈对数级增长，即每次操作将问题规模扩大m倍，其步数仅增加1或者1的有限倍。

比如：在有序数组中的二分法查找

// 在有序数组中查找目标值的索引
int binarySearch(vector<int>& nums, int target) 
{
    int left = 0, right = nums.size() - 1;
    while (left <= right) 
    {
        int mid = left + (right - left) / 2;  // 计算中点
        if (nums[mid] == target) 
        {
            return mid;  // 找到目标值
        } 
        else if (nums[mid] < target) 
        {
            left = mid + 1;  // 目标在右半区
        } 
        else 
        {
            right = mid - 1;  // 目标在左半区
        }
    }
    return -1;  // 未找到
}

  • 原理：每次将搜索范围缩小一半，最多需要 log₂N 次迭代。当N=1024 时，只需 10 次迭代（2¹⁰=1024）。

  • 复杂度推导：问题规模每次变为 N/2，迭代次数满足 N/(2^k) = 1，解得 k = log₂N，故时间复杂度为 O(log N)。

O(N)：线性时间复杂度

表示算法所需的最大运算步数与输入规模 N 成正比，输入规模翻倍时，执行时间也近似翻倍。

比如：在链表中查找指定值的节点

ListNode* findNode(ListNode* head, int target) 
{
    ListNode* curr = head;
    int count = 0;
    while (curr != nullptr) 
    {  // 最多遍历N个节点
        if (curr->val == target) 
        {
            return curr;
        }
        curr = curr->next;
        count++;
    }
    return nullptr;
}

  • 原理：链表无法随机访问，需从表头逐个遍历到表尾，最坏情况下遍历所有 N 个节点。

  • 解释：当增加一个数据时，查找的步数也增加1，如果步数增加1的有限倍数，这个算法的复杂度也是O(N)。

O(N²)：平方时间复杂度

表示最大运算步数与输入规模N的平方近似成正比，常见于包含双重嵌套循环的场景。

经典的冒泡排序

// 冒泡排序（升序）
void bubbleSort(vector<int>& nums) 
{
    int n = nums.size();
    for (int i = 0; i < n - 1; i++) 
    {  // 外层循环：N-1轮
        for (int j = 0; j < n - i - 1; j++) 
        {  // 内层循环：每轮比较N-i-1次
            if (nums[j] > nums[j + 1]) 
            {
                swap(nums[j], nums[j + 1]);  // 交换相邻元素
            }
        }
    }
}

  • 原理：外层循环遍历数组 N-1 次，内层循环每次将未排序部分的最大元素 “冒泡” 到末尾。

  • 复杂度推导：总比较次数为 (N-1) + (N-2) + ... + 1 = N(N-1)/2，忽略低阶项后为 O(N²)。

除此之外，本题的暴力枚举求解方法的时间复杂度也为O(N²)，具体代码实现如下：

暴力枚举解决“两数之和”问题

vector<int> Solution::twoSum(vector<int>& nums, int target)
{
    for (int i = 0; i < nums.size() - 1; i++)
    {
        for (int j = i - 1; j < nums.size(); j++)
        {
            if (nums[i] + nums[j] == target)
                return{ i,j };
        }
    }
    return{};
}

复杂度推导和冒泡排序相类似，不再赘述。

O(N!) :阶乘时间复杂度

表示算法执行步数随输入规模N的增长，与N的阶乘（N!=N×(N-1)×...×1）成正比，效率极低。

比如：全排列生成算法

//交换vector数组中的两个元素
void swap(vector<int>& arr, int i, int j)
 {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

//递归调用完成全排列，一开始传入的start是0，一直递归到start为arr.size()
void permute(vector<int>& arr, int start, vector<vector<int>>& result) 
{
    if (start == arr.size()) 
    {
        result.push_back(arr);
        return;
    }
    for (int i = start; i < arr.size(); i++) 
    {
        swap(arr, start, i);
        permute(arr, start + 1, result);
        swap(arr, start, i); 
    }
}
  • 原理：递归算法，
  • 复杂度推导：对于N个元素，全排列总数为N!，每个排列需O(N)时间输出，总时间为 O (N × N!)，但忽略低阶项后为 O (N!)。
  • 算法解释：

在所有的时间复杂度中，O(N!)属于效率极低的一档。除了全排列算法外，O(N!)复杂度也常出现在解决旅行商TSP问题的暴力解法等递归算法中。

 时间复杂度中优越性关系如下：

高效：O(1)>O(log N)>O(N)>O(N log N)

中等及低效：O(N^2)>O(N^3)>O(2^n)>O(N!)>O(N^N)

不同时间复杂度对比图：

三、容器

面向类和对象是c++程序语言的一个重要特性，如果一个类的主要目的是保存一些对象，而且这些对象是相同类型的，那我们通常称这个抽象类为容器。比如我想保存一系列的电话簿信息，那就可以把这些内容以一定的排列方式放入标准库自带的或者自主编写的容器里，以便后续存取和查找。在c++标准库中有多种容器，初始化方法为：

容器名<数据类型> 变量名

vessel<type> name

比如：

vector<int> v{1, 2, 3};

list<double> l = {3.14, 2.71};

map<string, int> m = {{"a", 1}, {"b", 2}};

unordered_map<int, string> um = {{1, "one"}, {2, "two"}};

下面主要介绍常用的4种容器类型：

vector动态数组

vector可以说是c++中最有用的容器库，其本质是动态数组。一个vector就是一个给定类型元素的序列，元素在内存中是连续存储的，存储模式如图1所示。

对于内存的连续性主要通过以下两个机制实现：

1. 底层数组存储

vector 内部维护一个指向原生数组的指针（如 T* data），所有元素在该数组中连续存储，类似普通数组的内存布局。

2. 动态扩容策略

当元素数量超过当前容量时，vector 会重新分配更大的连续内存块，将旧数据拷贝到新空间，释放旧内存。具体来讲是在初始内存占满后先申请一块更大的连续内存（通常是原容量的 2 倍)，将旧数组中的元素逐个拷贝到新内存。最后释放旧数组的内存，并更新内部指针指向新内存。

这样，每次扩容需要重新分配内存和拷贝元素，时间复杂度为O(n)，但由于扩容是 “指数级增长”，多次扩容的均摊时间复杂度仍为 O (1)。为了减少扩容的时间开销，若已知数据量，可使用reserve(n)函数预分配容量，避免多次扩容。

vector容器较常使用的函数如下： 

功能分类 操作 函数 / 语法 说明
初始化与构造 空构造 vector<T> v; 创建空 vector，不含任何元素
指定大小 + 默认值 vector<T> v(n); 创建含 n 个元素的 vector，元素为 T 类型默认值（如 int 为 0 ）
指定大小 + 初始值 vector<T> v(n, val); 创建含 n 个元素的 vector，每个元素值为 val
列表初始化（C++11+） vector<T> v{val1, val2...}; 用初始化列表直接赋值元素
拷贝构造 vector<T> v(other_v); 复制另一个 vector 的内容
元素访问 下标访问 v[index]

直接通过下标访问元素，不检查越界

（越界行为未定义，可能崩溃）
安全下标访问 v.at(index) 访问下标元素，会检查越界，越界抛 out_of_range 异常
访问首元素 v.front()

返回第一个元素的引用

（vector 为空时调用，行为未定义）
访问尾元素 v.back()

返回最后一个元素的引用

（vector 为空时调用，行为未定义）
数据指针 v.data()

返回指向底层数组首元素的指针

（可用于兼容 C 风格数组操作）
增删操作 尾部添加 v.push_back(val); 在 vector 末尾添加元素，若容量不足会自动扩容
尾部构造添加（C++11+） v.emplace_back(args); 直接在尾部原地构造元素，避免拷贝 / 移动开销（比 push_back 更高效）
尾部删除 v.pop_back(); 删除最后一个元素（vector 为空时调用，行为未定义 ）
插入元素 v.insert(it, val); 在迭代器 it 位置前插入元素 val
插入多个元素 v.insert(it, n, val); 在迭代器 it 位置前插入 n 个 val
插入其他容器元素 v.insert(it, first, last); 在迭代器 it 位置前，插入区间 [first, last) 内的元素（可跨容器）
原地构造插入（C++11+） v.emplace(it, args); 在迭代器 it 位置前原地构造元素，避免拷贝
删除元素 v.erase(it); 删除迭代器 it 指向的元素，返回下一个元素的迭代器
删除区间元素 v.erase(first, last); 删除 [first, last) 区间内的元素，返回下一个元素的迭代器
清空容器 v.clear(); 删除所有元素，size() 变为 0，但容量 capacity() 可能保留
空间管理 获取元素个数 v.size(); 返回当前元素数量（类型 size_t ）
判断是否为空 v.empty(); 为空返回 true，否则 false（等价于 v.size() == 0 ）
获取容量 v.capacity();

返回当前已分配内存可容纳的元素数量

（size() ≤ capacity() ）
预留空间 v.reserve(n);

预先分配至少能存 n 个元素的空间

（仅当 n > capacity() 时扩容，不初始化元素 ）
调整大小 v.resize(n);

改变 vector 大小： 若 n < size()，删除多余元素； 

若 n > size()，新增元素用默认值填充
调整大小 + 指定值 v.resize(n, val); 改变大小，若 n > size()，新增元素用 val 填充
释放多余容量（C++11+） v.shrink_to_fit();

尝试将容量收缩到与 size() 匹配

（请求不一定被编译器采纳，但会尽量做 ）
迭代器操作 正向起始迭代器 v.begin(); 返回指向第一个元素的正向迭代器
正向末尾迭代器 v.end();

返回指向最后一个元素之后位置的正向迭代器

（不指向有效元素，标记结束 ）
反向起始迭代器（C++11+） v.rbegin();

返回指向最后一个元素的反向迭代器

（从后往前遍历的 “起始” ）
反向末尾迭代器（C++11+） v.rend(); 返回指向第一个元素之前位置的反向迭代器（标记反向遍历结束 ）
常量正向迭代器（只读） v.cbegin(); v.cend(); 类似 begin()/end()，但迭代器是 const，不能通过它修改元素
常量反向迭代器（只读） v.crbegin(); v.crend(); 类似 rbegin()/rend()，迭代器是 const，只读
其他常用操作 交换内容 v.swap(other_v); 交换两个 vector 的数据（高效，直接交换内部指针 ）
赋值操作（覆盖） v.assign(n, val); 用 n 个 val 替换当前内容
赋值区间（覆盖） v.assign(first, last); 用区间 [first, last) 内的元素替换当前内容
看到这里有必要介绍一下迭代器的概念。迭代器(Iterator)是C++中 抽象化容器元素访问方式的核心概念，它让我们能以统一的语法遍历不同类型的容器，而无需关心容器的底层实现细节。从本质上讲，迭代器是一种 行为类似于指针的对象，但是它的功能和实现比普通指针更灵活、更安全。

  1. 行为类似指针

    • 支持解引用（*it）获取元素。
    • 支持递增（++it）移动到下一个元素。
    • 支持比较（it1 == it2）判断是否指向同一位置。

  2. 但比指针更灵活

    • 可以适配不同容器的底层结构（如数组、链表、树等）。
    • 可以实现更复杂的行为（如反向遍历、只读访问等）。

list双向链表容器

双向列表（doubly linked list）是一种数据结构。它的每个元素（节点）除了存储数据外，还有两个指针，分别指向前一个节点和后一个节点。这使得双向列表支持双向遍历，能高效地在表头、表尾和中间插入或删除元素。不过，它不支持随机访问，要访问特定位置的元素，得从头或尾开始遍历。

添加数据（尾部 / 头部）

  • 尾部添加（push_back）：创建新节点后，若链表为空，直接让表头（head）和表尾（tail）都指向新节点；若链表非空，将新节点的prev指向原尾节点，原尾节点的next指向新节点，最后更新tail指向新节点。
  • 头部添加（push_front）：类似地，若链表为空，head和tail指向新节点；否则，新节点的next指向原头节点，原头节点的prev指向新节点，最后更新head指向新节点。

删除数据（尾部 / 头部 / 指定位置）

  • 尾部删除（pop_back）：保存原尾节点，将tail指向原尾节点的前一个节点（若存在），并将新tail的next设为nullptr，最后释放原尾节点的内存。若删除后链表为空，将head也设为nullptr。
  • 头部删除（pop_front）：保存原头节点，将head指向原头节点的下一个节点（若存在），并将新head的prev设为nullptr，最后释放原头节点的内存。若删除后链表为空，将tail也设为nullptr。
  • 指定位置删除（erase）：找到待删除节点的前一个节点A和后一个节点B，让A的next指向B，B的prev指向A，最后释放待删除节点的内存。若删除的是头节点或尾节点，还需更新head或tail。

插入数据（指定位置前）

创建新节点后，找到插入位置的节点B（新节点将插入到B之前）。若B是头节点，则新节点成为新头节点；否则，将新节点的prev指向B的前一个节点A，next指向B，然后让A的next和B的prev都指向新节点。如下图所示。

 list容器较常使用函数如下：

功能分类 操作 函数 / 语法 说明
初始化与构造 空构造 list<T> l; 创建空 list，不含任何元素。
指定大小 list<T> l(n);

创建含 n 个元素的 list，元素为 T 类型默认值

（如 int 为 0）。
指定大小 + 初始值 list<T> l(n, val); 创建含 n 个元素的 list，每个元素值为 val。
列表初始化 list<T> l{val1, val2...}; （C++11+）用初始化列表直接赋值元素。
拷贝构造 list<T> l(other_l); 复制另一个 list 的内容。
范围构造 list<T> l(first, last);

用迭代器 [first, last) 范围内的元素初始化 list。

（另一个list对象中的迭代器，如果T相同也可是vector等其他容器中的迭代器对象）
元素访问 访问首元素 l.front() 返回第一个元素的引用（list 为空时调用，行为未定义）。
访问尾元素 l.back()

返回最后一个元素的引用

（list 为空时调用，行为未定义）。
容量操作 检查是否为空 l.empty() 若 list 为空返回 true，否则返回 false。
获取元素数量 l.size() 返回 list 中元素的数量。
获取最大容量 l.max_size() 返回 list 可容纳的最大元素数（取决于系统限制）。
修改操作 在头部添加元素 l.push_front(val) 在 list 头部插入元素 val。
在尾部添加元素 l.push_back(val) 在 list 尾部插入元素 val。
在头部构造元素 l.emplace_front(args...)

（C++11+）在 list 头部直接构造元素。

（参数为构造函数参数，构造函数是元素类型T的）
在尾部构造元素 l.emplace_back(args...)

（C++11+）在 list 尾部直接构造元素。

（参数为构造函数参数）
删除头部元素 l.pop_front() 删除 list 的第一个元素（list 不能为空）。
删除尾部元素 l.pop_back() 删除 list 的最后一个元素（list 不能为空）。
在指定位置前插入 l.insert(pos, val) 在迭代器 pos 前插入元素 val，返回新元素的迭代器。
在指定位置前构造 l.emplace(pos, args...)

（C++11+）在迭代器 pos 前直接构造元素。

（参数为构造函数参数）
删除指定位置元素 l.erase(pos) 删除迭代器 pos 指向的元素，返回下一个元素的迭代器。
删除指定范围元素 l.erase(first, last) 删除迭代器 [first, last) 范围内的元素，返回下一个元素的迭代器。
清空元素 l.clear() 删除所有元素，list 变为空（size() 为 0）。
调整大小 l.resize(n) 调整 list 大小为 n，多出的元素用默认值填充，元素减少时会截断。
调整大小并指定值 l.resize(n, val) 调整 list 大小为 n，多出的元素用 val 填充。
交换内容 l.swap(other) 交换两个 list 的内容（常数时间复杂度）。
迭代器操作 获取首元素迭代器 l.begin() 返回指向第一个元素的迭代器。
获取尾后迭代器 l.end() 返回指向最后一个元素之后位置的迭代器。
获取反向首迭代器 l.rbegin()

（C++11+）返回指向最后一个元素的反向迭代器。

（支持反向遍历）
获取反向尾迭代器 l.rend() （C++11+）返回指向第一个元素之前位置的反向迭代器。
获取常量首迭代器 l.cbegin()

（C++11+）返回指向第一个元素的常量迭代器。

（不可修改元素）
获取常量尾后迭代器 l.cend() （C++11+）返回指向最后一个元素之后位置的常量迭代器。
特殊操作 转移元素 l.splice(pos, other) 将另一个 list 的所有元素转移到当前 list 的 pos 位置前，other 变为空。
转移单个元素 l.splice(pos, other, it) 将 other 中迭代器 it 指向的元素转移到当前 list 的 pos 位置前。
转移范围元素 l.splice(pos, other, first, last) 将 other 中 [first, last) 范围内的元素转移到当前 list 的 pos 位置前。
删除指定值的元素 l.remove(val) 删除所有值等于 val 的元素。
删除满足条件的元素 l.remove_if(pred)

删除所有满足谓词 pred 的元素。

（如 [](int x){ return x > 10; }）
去重 l.unique() 删除连续重复的元素（需先排序）。
合并已排序列表 l.merge(other)

将另一个已排序的 list 合并到当前 list 中，保持有序。

（默认升序）
排序 l.sort() 对 list 进行排序（默认升序）。
反转顺序 l.reverse() 反转 list 中元素的顺序。

map关联数组

std::map 是 C++ 标准库中的一种关联容器，用于存储键值对（Key-Value Pairs），并根据键的顺序自动排序。它基于红黑树实现，提供了高效的插入、查找和删除操作。std::map 的核心特点是将唯一的键（Key）映射到对应的值（Value），并按键的升序排列元素。map容器的每一个元素都是一个pair结构的数据。这种结构使得它特别适合需要快速查找和有序遍历的场景。与普通数组不同，map 可以使用任意可比较的类型作为键（如字符串、自定义对象等），而不仅限于整数索引。具体的存储结构示意图如下：

这里提到的红黑树是一种一种自平衡二叉搜索树，它是在有序二叉树的基础上，对树的每个节点添加颜色属性(黑/红），然后通过一系列的法则限制黑红颜色节点的排列，结合旋转操作可以使得二叉树近似平衡，从而减小有序数组存入二叉树后查找时的复杂度，保证其检索效率的稳定。

map容器常用的函数如下：

功能分类 操作 函数 / 语法 说明
初始化与构造 空构造 map<K, V> m; 创建空的 map，键类型为 K，值类型为 V。
范围构造 map<K, V> m(begin, end); 从迭代器范围 [begin, end) 复制键值对初始化（要求元素类型可转换为 pair<const K, V>）。
拷贝构造 map<K, V> m(other); 复制另一个 map 的内容。
移动构造 map<K, V> m (std::move(other)); 移动另一个 map 的内容（C++11+）。
初始化列表构造 map<K, V> m{{k1, v1}, {k2, v2}}; 使用初始化列表初始化（C++11+）。
指定比较函数 map<K, V, Compare> m; 使用自定义比较函数 Compare（默认 std::less<K>）。
元素访问 下标访问 m[key] 返回键为 key 的值的引用。若键不存在，会插入默认值并返回引用。
安全下标访问 m.at(key) 返回键为 key 的值的引用。若键不存在，抛出 std::out_of_range 异常。
查找元素 m.find(key) 返回指向键为 key 的元素的迭代器。若不存在，返回 m.end()。
检查键是否存在 m.count(key) 返回键为 key 的元素个数（0 或 1）。
下界查找 m.lower_bound(key) 返回首个键 ≥ key 的元素的迭代器。
上界查找 m.upper_bound(key) 返回首个键 > key 的元素的迭代器。
相等范围查找 m.equal_range(key) 返回包含所有键等于 key 的元素的范围 [lower, upper)（对 map 而言，范围长度最多为 1）。
插入与删除 插入键值对 m.insert({key, value}); 插入键值对，返回 pair<iterator, bool>，其中 bool 表示是否插入成功（若键已存在则失败）。

插入

(避免失败）

 m.emplace(key, value); 原地构造键值对（C++11+），若键已存在则不插入。
插入或赋值 m[key] = value; 若键不存在则插入，存在则覆盖原值。
插入范围 m.insert(begin, end); 从迭代器范围 [begin, end) 插入键值对(其他map对象的)。
删除元素 m.erase(key); 删除键为 key 的元素，返回删除的元素个数（0 或 1）。
删除迭代器位置 m.erase(iterator); 删除迭代器指向的元素，返回下一个元素的迭代器。
删除范围 m.erase(begin, end); 删除迭代器范围 [begin, end) 内的元素。
清空容器 m.clear(); 清空所有元素。
容量与状态 判断是否为空 m.empty() 若容器为空返回 true，否则返回 false。
获取元素个数 m.size() 返回容器中元素的数量。
获取最大容量 m.max_size() 返回容器可容纳的最大元素数（取决于系统）。
迭代器与遍历 首元素迭代器 m.begin() 返回指向首个元素的迭代器（按键升序）。
尾后迭代器 m.end() 返回指向尾后位置的迭代器（不指向有效元素）。
逆序首元素迭代器 m.rbegin() 返回逆序迭代器的首元素（按键降序）。
逆序尾后迭代器 m.rend() 返回逆序迭代器的尾后位置。
C++11 范围遍历 for (const auto& pair : m) { ... } 按键升序遍历所有元素（C++11+）。
其他操作 交换内容 m.swap(other); 交换两个 map 的内容。
获取比较函数 m.key_comp() 返回用于比较键的函数对象。
获取值比较函数 m.value_comp() 返回用于比较值的函数对象（对 map 而言，与键比较函数相同）。

unordered_map无序的键值对容器

unordered_map 是 C++ 标准库中的一个关联容器，用于存储键值对。与 map 不同，它不保证元素按键的顺序排列，而是根据键的哈希值进行组织，因此被称为 “无序”。但是其可以通过键的哈希值直接找到待查元素的索引位置，这使得它在平均情况下具有常数时间复杂度的查找、插入和删除操作，效率很高。

内部存储方式与数据结构：unordered_map 的核心是哈希表（Hash Table），其本质就是一个元素组成为pair <const KEY, T> 类型的可扩展的数组，只不过是通过哈希函数将键(key)映射到数组的特定位置，这个数组被称为桶（Bucket）或槽（Slot）。具体来说：

  • 哈希函数：将键转换为一个无符号整数（哈希值），通常是 size_t 类型。例如，对于字符串键，哈希函数可能会计算其字符的 ASCII 值之和或更复杂的算法，这个字符到数字的转换过程由编译器完成，选择变换关系的依据是在性能、分布均匀性和安全性之间取得平衡。

        常用的哈希函数有以下几种：  

除法哈希（Division Method）

  • 公式：h(k) = k mod m（k 是键，m 是桶数量，通常取质数）。
  • 优点：实现简单，适用于整数键。
  • 缺点：若 m 选择不当（如 2 的幂），易产生聚集。

乘法哈希（Multiplication Method）

  • 公式：h(k) = floor(m × (k × A mod 1))，其中 A 是常数（如 0.618）。
  • 优点：对 m 的选择不敏感，分布较均匀。

多项式哈希（Polynomial Hashing）

  • 公式：用于字符串，如 h(s) = (s[0]·aⁿ⁻¹ + s[1]·aⁿ⁻² + ... + s[n-1]) mod m。
  • 优点：保留字符串位置信息，支持快速子串查询

其他哈希函数

FNV 哈希（Fowler–Noll–Vo），MD5，SHA-3，MurmurHash等

其中C++标准库中针对不同的数据类型设定了MurmurHash、FNV、自定义多项式等哈希函数，满足用户对一般数据类型的key值的寻址需求。如果想要为自定义的数据类型key寻址，则要自己设计哈希函数，可以通过特化std::hash或者自定义哈希类来实现。

  • 桶数组：哈希表的主体是一个固定大小的数组，每个元素是一个桶。桶的数量通常是质数，以减少哈希冲突。

  • 冲突处理：当两个不同的键产生相同的哈希值时（哈希冲突），unordered_map 使用链地址法处理冲突。每个桶存储一个链表（或其他容器，如红黑树），所有哈希到同一位置的键值对都存储在这个链表中，根据先后依次向下排列。还有一种冲突处理的方法是开放定址法，如果在插入一个值的过程中发现冲突，就会探测其周边的数据，直到空闲位置将其存入。在查找时也是一样的逻辑，如果通过哈希函数直接计算出的地址存储的不是目标元素，则按照冲突处理法则继续查找，直到找到对应值；如果直到碰到空闲的地址仍然没有找到目标元素，则说明查找的目标元素不存在，因为存储的时候就是按照一样的逻辑进行的，要是元素存在的话按照相同方式一定可以找到。

    常见的开放定址法有：

    • 线性探测法：冲突后依次探测下一个位置，直至到空闲位置；表尾的下一个位置是表首。

    • 平方探测法：冲突时按照+1²，-1²，+2²，-2²，+3²，-3²，··· 的顺序进行探测(表尾的下一个位置是表首。在这种方法中为减少冲突，一般取表长=某个4k+3得出的质数(k\in N^+ )

  • 负载因子：定义为元素数量与桶数量的比值。当负载因子超过某个阈值（一般为0.75）时，容器会自动扩容并重新哈希，以保持高效性能。

如果搞不清楚，这里给出B站up主“蓝不过海呀”的视频链接，全网最详细：

https://www.bilibili.com/video/BV13NwveLE1D/?spm_id_from=333.337.search-card.all.click

(如有侵权请联系删除）

 unordered_map容器常用的函数如下：

功能分类 操作 函数 / 语法 说明
初始化与构造 空构造 unordered_map<K, V> m; 创建空的 unordered_map，不含任何元素。
列表初始化 unordered_map<K, V> m{{k1, v1}, ...}; 用初始化列表直接赋值键值对（C++11+）。
拷贝构造 unordered_map<K, V> m(other_m); 复制另一个 unordered_map 的所有元素。
移动构造 unordered_map<K, V> m(std::move(other_m)); 通过移动语义构造（原 other_m 被清空）。
范围构造 unordered_map<K, V> m(begin, end); 从迭代器范围 [begin, end) 复制键值对。
元素访问与修改 下标访问 m[key] 返回键 key 对应的值的引用。若键不存在，插入默认值并返回引用。
安全访问 m.at(key) 返回键 key 对应的值的引用。若键不存在，抛出 out_of_range 异常。
插入元素 m.insert({key, value}); 若键不存在，插入新键值对；若存在则不插入。
插入或赋值 m.emplace(key, value); 若键不存在，构造并插入新键值对；若存在则不插入。
插入或更新 m[key] = value; 若键存在，更新值；若不存在，插入新键值对。
批量插入 m.insert(begin, end); 从迭代器范围 [begin, end) 插入键值对。
删除元素 m.erase(key); 删除键为 key 的元素，返回删除的元素个数（0 或 1）。
删除迭代器位置 m.erase(iter); 删除迭代器 iter 指向的元素，返回下一个元素的迭代器。
删除范围 m.erase(begin, end); 删除迭代器范围 [begin, end) 内的元素。
清空容器 m.clear(); 清空所有元素，容器大小变为 0。
查找操作 判断键是否存在 m.count(key) 返回键 key 的元素个数（0 或 1），用于判断键是否存在。
查找键 m.find(key) 返回指向键 key 的迭代器；若不存在，返回 m.end()。
范围查找 m.equal_range(key) 返回 pair<iterator, iterator>，表示键 key 的元素范围。
容量与状态 判断是否为空 m.empty() 若容器为空，返回 true，否则返回 false。
元素个数 m.size() 返回当前元素数量。
最大容量 m.max_size() 返回容器理论上可容纳的最大元素数量。
负载因子 m.load_factor() 返回当前负载因子（元素数 / 桶数）。
最大负载因子 m.max_load_factor() 返回负载因子的阈值（默认 0.75）。
设置负载因子阈值 m.max_load_factor(new_factor); 修改负载因子阈值。
桶数量 m.bucket_count() 返回当前桶的数量。
键的哈希函数 m.hash_function() 返回用于计算键哈希值的函数对象。
迭代器 正向迭代器 m.begin() / m.end()

返回指向容器首的迭代器 / 容器末尾后之后位置的的迭代器。

（支持 ++ 遍历）
常量迭代器 m.cbegin() / m.cend() 返回常量迭代器，不允许修改元素。
高级操作 预留桶数量 m.reserve(n) 预先分配至少能容纳 n 个元素的桶数量。
调整桶数量 m.rehash(n) 调整桶数量为 n 或更大，并重新哈希所有元素。
交换内容 m.swap(other_m) 交换两个 unordered_map 的内容（常数时间复杂度）。

 

元素操作时间复杂度比较

随机访问

  • vector：O(1)，通过下标直接访问元素，时间复杂度恒定。
  • list：O(n)，需从头部或尾部遍历到目标位置，无法直接随机访问。
  • map：O(n)，元素按键有序存储，需通过迭代器遍历查找，二叉树中序遍历。
  • unordered_map：O(n)，元素无序，需通过键的哈希值查找。

头部插入 / 删除

  • vector：O(n)，插入删除头部元素时，需移动后续所有元素，时间复杂度与元素数量成正比。
  • list：O(1)，直接操作头节点，仅需调整指针，无需移动元素。
  • map：O(log n)，基于红黑树结构，插入/删除操作需维护树的平衡，时间复杂度为对数级别。
  • unordered_map：平均为O(1)，插入时通过哈希值定位桶，删除时直接操作链表节点；最坏情况下（哈希冲突严重）可能退化为 O(n)。

尾部插入 / 删除

  • vector：平均为O(1)，当预留空间足够时，直接在尾部操作；空间不足时需重新分配内存并复制元素，均摊时间复杂度接近常数。
  • list：O(1)，直接操作尾节点，调整指针即可。
  • map：O(log n)，插入/删除操作需保持红黑树平衡，时间复杂度为对数级别。
  • unordered_map：O(1)（平均），原理同头部插入 / 删除，平均时间复杂度恒定。

中间插入 / 删除

  • vector：O(n)，插入或删除中间元素时，需移动该位置之后的所有元素，时间复杂度与元素数量成正比。
  • list：O(n)（定位）+ O(1)（操作），需先通过迭代器遍历定位到目标位置（O(n)），插入/删除时仅调整指针（O(1)）。
  • map：O(log n)，基于红黑树通过键定位到目标位置（O(log n)），插入/删除操作需维护树平衡（O(log n)），整体时间复杂度仍为对数级别。
  • unordered_map：平均为O(1)，通过哈希值定位桶（O(1)），若桶内为链表，遍历链表定位元素（平均 O (1)，最坏 O (n)），插入 / 删除操作仅调整指针。

查找

  • vector：O(n)，使用std::find等算法时需遍历容器，时间复杂度与元素数量成正比。
  • list：O(n)，需从头或尾遍历容器查找元素。
  • map：O(log n)，基于红黑树的有序性，通过二叉搜索定位元素，时间复杂度为对数级别。
  • unordered_map：平均为O(1)，通过键的哈希值直接定位桶，冲突时遍历链表（平均情况下时间复杂度接近常数，哈希冲突最坏情况 O(n)）。

排序

  • vector：O(n log n)，使用std::sort等排序算法，基于快速排序（或归并排序、堆排序），时间复杂度为 O(n log n)。
  • list：O(n log n)，需使用std::list::sort()（归并排序），无法直接使用std::sort（不支持随机访问）。
  • map：无需手动排序，元素插入时自动按键有序排列（红黑树保证有序性）。
  • unordered_map：不支持排序，元素无序存储。
# c++ # 算法 # leetcode # 数据结构 # 链表 # 散列表
Logo
腾讯云开发者社区

腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。

更多推荐

终极指南：Flink SQL连接器版本管理从混乱到有序的升级之路

Apache Flink作为流处理领域的佼佼者，其SQL连接器的版本管理一直是开发者面临的核心挑战。本文将系统讲解Flink SQL连接器版本管理的最佳实践，帮助你轻松应对版本兼容性问题，实现从混乱到有序的升级之旅。## 连接器版本管理的常见痛点 😫在Flink应用开发中，连接器版本管理常常让开发者头疼不已。不同版本的连接器可能导致各种兼容性问题，例如API变更、功能差异甚至运行时错误。

avatar 腾讯云开发者社区

Elasticsearch复杂数据类型终极指南：从入门到精通

Elasticsearch作为功能强大的搜索引擎，支持多种复杂数据类型，让开发者能够灵活处理各种结构化和非结构化数据。本文将带你全面了解Elasticsearch中的复杂数据类型，从基础概念到实际应用，助你轻松掌握数据建模的核心技巧。## 内部对象：构建层级化数据结构在Elasticsearch中，对象类型（Object）是最基础的复杂数据类型之一，用于表示具有嵌套关系的数据。例如，我们可

avatar 腾讯云开发者社区

如何快速搭建Neon无服务器PostgreSQL：面向初学者的完整指南

Neon是一款革命性的无服务器PostgreSQL解决方案，它通过分离存储和计算层，实现了自动扩缩容、类代码式数据库分支以及零级扩展能力。本指南将帮助你从零开始搭建Neon开发环境，体验这款创新数据库的强大功能。## 准备工作：环境要求与依赖项在开始搭建Neon环境前，请确保你的系统满足以下要求：- Linux操作系统（推荐Ubuntu 20.04+或Debian 11+）- Git

avatar 腾讯云开发者社区