C++学习记录(1)：常用 STL 汇总

前言

最近因为刷题和实际业务的开发，在重新整理 C++ 的笔记。

发现 STL 这东西平时一直在用，但很多时候只是依赖 AI 或者自动补全，没有认真了解过他们的特性。

比如 vector 为什么默认这么常用，map 和 unordered_map 到底该怎么选，list 又为什么看起来很强但实际出场率不高，这些东西如果只是记住几个接口，过一阵子还是会混。

所以这篇文章干脆把我目前最常碰到的一批 STL 类型先汇总一下。本文不追求把每个类的所有接口都列完，而是重点整理：

• 它一般适合拿来干什么
• 平时该怎么初始化
• 最常用的方法有哪些
• 这些方法的复杂度大概是什么水平
• 遇到题目或者实际业务时，为什么会优先想到它

顺序上我没有按字母排，而是按“通常上手时比较容易理解的，和我觉得更常先学到的”来排。

string

介绍与使用场景

std::string 用来保存和处理字符串。严格来说它是 std::basic_string<char> 的常用别名，但平时基本直接把它当作字符串类型来用就行。

• 业务开发里，一般用它保存用户名、文件路径、配置项、日志文本和各种普通文本。相比手写字符数组，它会自动管理内存，省心很多。
• 算法题里，一般用它处理回文串、子串、字符统计、模拟题和各种字符串匹配问题。它支持随机访问，和 STL 算法也很好配合。
• 如果要在头部或中间频繁插入、删除字符，就要注意它后面的字符通常需要整体移动。

初始化方式

#include <string>
using namespace std;

string text;
string text1 = "hello";
string text2("hello");
string text3(5, 'a');
string text4(text1);
string text5(text1, 1, 3);
string text6(text1.begin(), text1.begin() + 3);

字符和字符串别写混：

char ch = 'a';
string text = "abc";

常用方法

设原字符串长度为 n，参与操作的新内容长度为 m：

• size()、length()、empty()：时间复杂度都是 O(1)。
• operator[]、at()、front()、back()：访问字符都是 O(1)。at() 会检查越界，operator[] 不会。
• push_back()：不重新分配内存时是 O(1)；连续追加时均摊 O(1)；单次最坏 O(n)。
• pop_back()：O(1)。
• append()、operator+=：至少要复制新增内容，最坏 O(n + m)。
• operator+：会创建新字符串并复制内容，时间复杂度是 O(n + m)。
• insert()：在中间插入通常需要移动后续字符，最坏 O(n + m)。
• erase(pos, count)：删除后可能需要搬移剩余字符，最坏 O(n)。
• find()、rfind()：如果是查找单个字符，最坏一般按 O(n) 理解；如果是查找长度为 m 的子串，标准最坏上界可按 O(nm) 理解，具体实现可能更快。
• substr(pos, count)：要构造新字符串，复杂度和实际复制的字符数成正比。
• clear()：通常按 O(n) 理解更安全，不要假设它一定是常数时间。
• c_str()、data()：取底层字符指针是 O(1)，但字符串内容一改，之前拿到的指针可能失效。

示例

拼接一个简单的问候语：

#include <iostream>
#include <string>
using namespace std;

int main() {
    string name = "小明";
    string message = "你好，";

    message += name;
    message.push_back('！');

    //  输出 "你好，小明"
    cout << message << '\n';
}

截取文件扩展名：

#include <iostream>
#include <string>
using namespace std;

int main() {
    string filename = "notes.md";
    string::size_type pos = filename.rfind('.');

    if (pos != string::npos) {
        string ext = filename.substr(pos + 1);
        cout << "扩展名：" << ext << '\n';
    }
}

substr() 很方便，但它会生成一个新字符串。

如果只是临时看一段内容，而且特别在意性能，后面可以再去了解 string_view。

pair

介绍与使用场景

pair 用来把两个值组合成一个整体。它不是完整容器，更像一个很轻量的“二元打包工具”。

• 业务开发里，一般用它临时表示“键和值”、“名字和编号”、“坐标和状态”这类成对数据。要是字段含义已经很稳定，通常还是自己写结构体更清楚。
• 算法题里，用得非常多。比如坐标、边权与节点、数值与下标、函数返回两个结果，这些都很适合用 pair。
• 它的优点是省事，缺点也很明显：first 和 second 的语义不如成员名直观。

初始化方式

#include <string>
#include <utility>

std::pair<int, std::string> p1;
std::pair<int, std::string> p2(1, "apple");
std::pair<int, std::string> p3{2, "banana"};
auto p4 = std::make_pair(3, std::string("orange"));

C++17 开始还可以让编译器推导模板参数：

std::pair p5{4, std::string("pear")};

常用方法

pair 就两个成员，所以很多操作都可以直接按常数时间理解：

• first、second：访问成员是 O(1)。
• std::make_pair(a, b)：构造一个 pair，结构本身可按 O(1) 理解，实际成本取决于成员构造或移动。
• swap(other)：交换两个成员，结构层面是 O(1)，具体成本取决于成员类型。
• 比较运算：按字典序比较，最多比较两个成员。若成员比较本身都是 O(1)，整体可按 O(1) 理解；如果成员本身是 string 这类对象，实际成本还要把成员比较开销算进去。

示例

用 pair 保存商品名和数量：

#include <iostream>
#include <string>
#include <utility>
using namespace std;

int main() {
    pair<string, int> item{"apple", 5};

    cout << "商品：" << item.first << '\n';
    cout << "数量：" << item.second << '\n';

    item.second += 2;
    cout << "更新后的数量：" << item.second << '\n';
}

如果数据语义已经比较复杂，pair 就会开始别扭：

struct Student {
    string name;
    int age;
};

这种时候通常不如直接写结构体。

array

介绍与使用场景

array 是对固定长度数组的封装，长度必须在编译期确定。

它和 C 风格的数组一样使用连续内存，但接口更现代一些。

• 业务开发里，一般适合长度固定、含义明确的数据，比如一周 7 天的统计值、固定数量的传感器数据、固定字段的协议内容。
• 算法题里，一般适合字母计数、方向数组、固定维度状态等场景。尤其是“长度就是 26、4、8、10 这种写死的值”时，它会比 vector 更直接。
• 如果元素数量需要运行时变化，就别用 array，该换 vector。

初始化方式

#include <array>
using namespace std;

array<int, 5> nums{};
array<int, 5> nums1{1, 2, 3, 4, 5};
array<int, 5> nums2{1, 2};
array nums3{1, 2, 3};  // C++17 起可推导

要注意，长度是类型的一部分：

array<int, 3> a{};
array<int, 5> b{};

这两个不是同一种类型。

常用方法

设数组长度为 N：

• size()、empty()：O(1)。
• operator[]、at()、front()、back()：访问元素都是 O(1)。
• data()：返回底层连续内存指针，O(1)。
• begin()、end()：取迭代器，O(1)。
• fill(value)：把所有元素改成同一个值，O(N)。
• swap(other)：逐个交换元素，O(N)。
• array 不提供 push_back()、pop_back()、resize()，因为长度根本不能改。

示例

统计小写字母出现次数：

#include <array>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string text = "banana";
    array<int, 26> counts{};

    for (char ch : text) {
        ++counts[ch - 'a'];
    }

    cout << "a 出现了 " << counts['a' - 'a'] << " 次\n";
    cout << "b 出现了 " << counts['b' - 'a'] << " 次\n";
    cout << "n 出现了 " << counts['n' - 'a'] << " 次\n";
}

这个场景里，字符种类固定就是 26 个，用 array<int, 26> 会比 vector<int>(26) 更能体现“长度不会变”。

vector

介绍与使用场景

vector 是动态数组，我觉得它应该是用得最多的 STL 容器之一。

它的元素放在连续内存里，支持下标访问，也能在运行时动态扩容。

终于不用纠结怎么实现动态数组了！你说是吧， C 语言？

• 业务开发里，一般适合保存数量会变、又经常需要遍历或随机访问的数据。因为连续内存对缓存友好，所以很多时候性能表现也不错。
• 算法题里，几乎到处都能见到它。输入数组、邻接表、动态规划状态、离散化后的结果，很多都用 vector。
• 它不适合频繁在头部或中间插入、删除元素，因为这往往需要整体搬移后面的元素。

初始化方式

#include <vector>
using namespace std;

vector<int> nums;
vector<int> nums1(5);
vector<int> nums2(5, 10);
vector<int> nums3{1, 2, 3, 4, 5};
vector<int> nums4(nums3);
vector<int> nums5(nums3.begin(), nums3.begin() + 3);

下面两种写法一定要分清：

vector<int> a(5);  // 5 个元素：0 0 0 0 0
vector<int> b{5};  // 1 个元素：5

常用方法

设当前元素数量为 n：

• size()、empty()：O(1)。
• operator[]、at()、front()、back()：访问元素都是 O(1)。
• push_back()、emplace_back()：连续使用时均摊 O(1)；单次扩容时最坏 O(n)。
• pop_back()：O(1)。
• insert()、emplace()：末尾追加可参考 push_back()；头部或中间插入通常最坏 O(n)。
• erase()：删除中间或头部元素通常最坏 O(n)，因为后面的元素要前移。
• clear()：销毁全部元素，O(n)。
• reserve()：如果触发重新分配，需要搬移已有元素，O(n)。
• capacity()：查看当前容量，O(1)。
• resize()：缩小要销毁元素，增大要补新元素，还可能触发重分配；最坏可按 O(n + k) 理解，k 是新增元素数。

示例

保存一组成绩并求总分：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> scores{80, 92, 75};

    scores.push_back(88);
    scores.push_back(95);

    int total = 0;
    for (int score : scores) {
        total += score;
    }

    cout << "人数：" << scores.size() << '\n';
    cout << "总分：" << total << '\n';
}

如果已知大概要塞很多元素，先 reserve() 往往更舒服：

vector<int> nums;
nums.reserve(1000);

for (int i = 0; i < 1000; ++i) {
    nums.push_back(i);
}

反过来，如果一直从头删元素，vector 就不太合适：

while (!nums.empty()) {
    nums.erase(nums.begin());
}

这种写法每次都可能移动大量元素，需要频繁操作两端时通常更适合 deque。

deque

介绍与使用场景

deque 是双端队列，可以在头部和尾部都高效地插入、删除，同时也支持下标访问。

• 业务开发里，一般适合两端都可能进出数据的场景，比如任务缓冲、消息缓冲、窗口数据维护。
• 算法题里，很常见于 BFS、单调队列、滑动窗口最大值、0-1 BFS 这类题。
• 它和 vector 最大的区别之一，就是头部操作更自然；但它通常不是一整段连续内存，所以缓存局部性一般不如 vector。

初始化方式

#include <deque>
using namespace std;

deque<int> nums;
deque<int> nums1(5);
deque<int> nums2(5, 10);
deque<int> nums3{1, 2, 3, 4, 5};
deque<int> nums4(nums3);
deque<int> nums5(nums3.begin(), nums3.begin() + 3);

常用方法

设当前元素数量为 n：

• size()、empty()：O(1)。
• operator[]、at()、front()、back()：访问元素都是 O(1)。
• push_front()、emplace_front()、push_back()、emplace_back()：O(1)。
• pop_front()、pop_back()：O(1)。
• insert()、emplace()：中间插入通常最坏 O(n)。
• erase()：中间删除通常最坏 O(n)；删两端元素时更建议直接用 pop_front() 或 pop_back()。
• clear()：O(n)。
• deque 不适合拿来当“一整块连续数组”使用，因为它不保证所有元素排在同一段连续内存里。

示例

模拟一个两端都可能来人的队伍：

#include <deque>
#include <iostream>
#include <string>
using namespace std;

int main() {
    deque<string> passengers;

    passengers.push_back("小明");
    passengers.push_back("小红");
    passengers.push_front("工作人员");

    cout << "队首：" << passengers.front() << '\n';
    cout << "队尾：" << passengers.back() << '\n';

    passengers.pop_front();
    cout << "工作人员离开后，队首是：" << passengers.front() << '\n';
}

在 BFS 这类场景里，pop_front() 的优势也很明显：

deque<int> nodes;
nodes.push_back(0);

while (!nodes.empty()) {
    int current = nodes.front();
    nodes.pop_front();

    // 处理 current，并把下一批节点塞到队尾
}

如果你只是想从头删元素，又顺手用了 vector::erase(begin())，那大概率就是该换 deque 了。

queue

介绍与使用场景

queue 是队列容器适配器，遵循先进先出，也就是 FIFO。

• 业务开发里，一般用它保存等待处理的任务、消息或请求，让它们按进入顺序依次处理。
• 算法题里，一般用它做 BFS、层序遍历、模拟排队过程。
• 它默认底层通常是 deque，但平时更关心的是它暴露出来的队列接口，而不是底层细节。

初始化方式

#include <deque>
#include <list>
#include <queue>

std::queue<int> q1;
std::queue<int, std::list<int>> q2;

std::deque<int> data{10, 20, 30};
std::queue<int> q3(data);

它不能直接像顺序容器那样写成初始化列表形式。

常用方法

以下复杂度按默认底层容器 deque 来理解：

• push(value)：O(1)。
• emplace(args...)：O(1)。
• pop()：O(1)，没有返回值，通常先 front() 再 pop()。
• front()：访问队首，O(1)。
• back()：访问队尾，O(1)。
• empty()、size()：O(1)。

如果你改了底层容器，复杂度要跟着底层容器的对应操作一起看。

示例

按进入顺序处理任务：

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    queue<string> tasks;

    tasks.push("读取配置");
    tasks.push("连接服务器");
    tasks.push("加载数据");

    while (!tasks.empty()) {
        cout << "正在处理：" << tasks.front() << '\n';
        tasks.pop();
    }
}

queue 的优势是语义非常直接，但限制也明显：它不能随机访问中间元素。要是你还想按下标看内容，那就该考虑 deque 或 vector。

stack

介绍与使用场景

stack 是栈容器适配器，遵循后进先出，也就是 LIFO。

• 业务开发里，一般用来保存撤销记录、页面返回路径、表达式解析过程、需要倒着处理的临时状态。
• 算法题里，常见于括号匹配、单调栈、模拟递归、深度优先搜索。
• 它默认底层通常也是 deque，但使用时一般只通过 push、pop、top 这些栈接口来操作。

初始化方式

#include <deque>
#include <stack>
#include <vector>

std::stack<int> s1;
std::stack<int, std::vector<int>> s2;

std::deque<int> data{1, 2, 3};
std::stack<int> s3(data);

和 queue 一样，它也不支持直接写初始化列表。

常用方法

以下复杂度按默认底层容器 deque 来理解：

• push(value)：O(1)。
• emplace(args...)：O(1)。
• pop()：O(1)，没有返回值，通常先 top() 再 pop()。
• top()：访问栈顶，O(1)。
• empty()、size()：O(1)。

如果换了底层容器，复杂度还是要跟着底层容器走。

示例

用栈判断括号是否匹配：

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isValid(const string& str) {
    stack<char> brackets;

    for (char ch : str) {
        if (ch == '(' || ch == '[' || ch == '{') {
            brackets.push(ch);
            continue;
        }

        if (ch != ')' && ch != ']' && ch != '}') {
            continue;
        }

        if (brackets.empty()) {
            return false;
        }

        char left = brackets.top();
        brackets.pop();

        if ((ch == ')' && left != '(') ||
            (ch == ']' && left != '[') ||
            (ch == '}' && left != '{')) {
            return false;
        }
    }

    return brackets.empty();
}

int main() {
    cout << boolalpha;
    cout << isValid("{[()]}") << '\n';
    cout << isValid("{[(])}") << '\n';
}

这里最关键的地方就是：遇到右括号时，要优先处理最近那个还没配对的左括号，这正好就是栈擅长的顺序。

map

介绍与使用场景

map 用来保存键值对，键不能重复，并且会自动按键排序。它通常可以理解成一棵平衡搜索树。

• 业务开发里，一般用它做“键到值”的映射，而且还希望最终遍历时是有序的，比如按编号输出数据。
• 算法题里，常用来统计频率、记录状态、维护动态有序映射，或者查找某个键附近的位置。
• 如果你完全不关心顺序，只关心查找快不快，那通常还得再和 unordered_map 比一比。

初始化方式

#include <map>
#include <string>
#include <utility>
#include <vector>

std::map<std::string, int> m1;
std::map<std::string, int> m2{
    {"apple", 3},
    {"banana", 5}
};

std::vector<std::pair<std::string, int>> items{
    {"pen", 2},
    {"book", 4}
};
std::map<std::string, int> m3(items.begin(), items.end());

也可以指定比较规则：

#include <functional>
#include <map>

std::map<int, int, std::greater<int>> m{
    {1, 10},
    {3, 30},
    {2, 20}
};

常用方法

设容器里有 n 组键值对：

• insert({key, value})、emplace(key, value)：O(log n)。
• insert_or_assign(key, value)：插入或覆盖，O(log n)，需要 C++17。
• find(key)、count(key)、contains(key)：O(log n)。contains() 需要 C++20。
• at(key)：按键访问，O(log n)；键不存在会抛异常。
• operator[](key)：O(log n)；键不存在时会直接插入一个默认值。
• erase(key)：按键删除，O(log n)。
• erase(iterator)：删单个已知位置的节点，均摊 O(1)。
• lower_bound(key)、upper_bound(key)：O(log n)。
• size()、empty()：O(1)。
• clear()：O(n)。

map 里负责排序的是键，所以键本身不能直接改；值是可以改的。

示例

统计单词出现次数：

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> words{
        "apple", "banana", "apple", "orange", "banana", "apple"
    };

    map<string, int> counts;
    for (const string& word : words) {
        ++counts[word];
    }

    for (const auto& [word, count] : counts) {
        cout << word << ": " << count << '\n';
    }
}

这个写法很顺手，但也要记得：operator[] 会在键不存在时自动插入。如果你只是想查一下有没有，不想顺手把键塞进去，更适合用 find()、contains() 或 at()。

set

介绍与使用场景

set 用来保存不重复元素，并且会自动排序。可以把它看成“只有键、没有值的有序集合”。

• 业务开发里，一般适合需要去重、又希望最终结果保持有序的数据。
• 算法题里，常用来维护动态有序集合。除了判重，还能顺手做 lower_bound()、upper_bound() 这类“找附近元素”的操作。
• 如果你只需要去重和快速查询，不需要有序性，那也常常会拿它和 unordered_set 做选择。

初始化方式

#include <set>
#include <vector>

std::set<int> s1;
std::set<int> s2{3, 1, 2, 2};

std::vector<int> nums{4, 2, 5, 2};
std::set<int> s3(nums.begin(), nums.end());

指定降序比较：

#include <functional>
#include <set>

std::set<int, std::greater<int>> s{1, 3, 2};

常用方法

设集合里有 n 个元素：

• insert(value)、emplace(args...)：O(log n)。
• find(value)、count(value)、contains(value)：O(log n)。contains() 需要 C++20。
• erase(value)：O(log n)。
• erase(iterator)：删单个已知位置节点，均摊 O(1)。
• lower_bound(value)、upper_bound(value)：O(log n)。
• begin()、end()：取迭代器本身是 O(1)，遍历时元素天然有序。
• size()、empty()：O(1)。
• clear()：O(n)。

需要注意，set 里的元素本身就是排序关键字，所以不能直接改值。真要改，只能删了再插。

示例

先去重，再按从小到大输出：

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> nums{4, 2, 4, 1, 3, 2};
    set<int> uniqueNums(nums.begin(), nums.end());

    for (int num : uniqueNums) {
        cout << num << ' ';
    }
}

查找第一个不小于目标值的元素：

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> scores{60, 70, 85, 90};

    auto it = scores.lower_bound(80);
    if (it != scores.end()) {
        cout << *it << '\n';
    }
}

unordered_map

介绍与使用场景

unordered_map 用哈希表保存键值对，不按键排序，遍历顺序也不该依赖。

• 业务开发里，一般适合通过某个键高频查值，比如通过用户 ID 找用户信息、通过配置名找配置内容。
• 算法题里，更是常客。频率统计、记录下标、缓存结果、做哈希判定，很多题第一反应就是它。
• 它平均复杂度很好，但不是稳定的最坏复杂度保证；要是你还需要有序遍历或者范围查询，就该回去考虑 map。

初始化方式

#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

std::unordered_map<std::string, int> m1;
std::unordered_map<std::string, int> m2{
    {"apple", 3},
    {"banana", 5}
};

std::vector<std::pair<std::string, int>> items{
    {"pen", 2},
    {"book", 4}
};
std::unordered_map<std::string, int> m3(items.begin(), items.end());

如果键是自定义类型，还得自己提供相等比较和哈希函数。

常用方法

设容器里有 n 组键值对：

• insert({key, value})、emplace(key, value)：平均 O(1)，最坏 O(n)。
• insert_or_assign(key, value)：平均 O(1)，最坏 O(n)，需要 C++17。
• find(key)、count(key)、contains(key)：平均 O(1)，最坏 O(n)。contains() 需要 C++20。
• at(key)：平均 O(1)，最坏 O(n)；键不存在会抛异常。
• operator[](key)：平均 O(1)，最坏 O(n)；键不存在会插入默认值。
• erase(key)：平均 O(1)，最坏 O(n)。
• erase(iterator)：平均 O(1)，最坏 O(n)。
• reserve(count)：通常用来提前留桶位，减少重哈希次数；如果触发重哈希，平均复杂度可按 O(n) 理解，最坏可能到 O(n^2)。
• load_factor()：O(1)。
• size()、empty()：O(1)。
• clear()：O(n)。

哈希容器最要命的一点就是：平均很快，但别把“平均 O(1)”误记成“永远 O(1)”。

示例

经典的“两数之和”：

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    vector<int> nums{2, 7, 11, 15};
    int target = 9;
    unordered_map<int, int> positions;

    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int needed = target - nums[i];
        auto it = positions.find(needed);

        if (it != positions.end()) {
            cout << "下标：" << it->second << " 和 " << i << '\n';
            break;
        }

        positions[nums[i]] = i;
    }
}

这个例子不需要有序性，只需要快速查有没有，因此 unordered_map 就很顺手。

unordered_set

介绍与使用场景

unordered_set 是哈希版的集合，用来保存不重复元素，但不保证有序。

• 业务开发里，一般适合保存“只需要去重和判断是否存在”的数据，比如已处理请求 ID、黑名单用户、访问过的资源。
• 算法题里，经常用它做快速判重、访问标记、哈希去重。
• 如果你后面还得按顺序遍历，或者做区间/邻近查找，那通常还是 set 更合适。

初始化方式

#include <unordered_set>
#include <vector>

std::unordered_set<int> s1;
std::unordered_set<int> s2{3, 1, 2, 2};

std::vector<int> nums{4, 2, 5, 2};
std::unordered_set<int> s3(nums.begin(), nums.end());

自定义类型做键时，也一样需要自己准备比较和哈希逻辑。

常用方法

设集合里有 n 个元素：

• insert(value)、emplace(args...)：平均 O(1)，最坏 O(n)。
• find(value)、count(value)、contains(value)：平均 O(1)，最坏 O(n)。contains() 需要 C++20。
• erase(value)：平均 O(1)，最坏 O(n)。
• erase(iterator)：平均 O(1)，最坏 O(n)。
• reserve(count)：作用是减少后续重复扩桶；如果触发重哈希，平均复杂度可按 O(n) 理解，最坏可能到 O(n^2)。
• load_factor()：O(1)。
• size()、empty()：O(1)。
• clear()：O(n)。

和 unordered_map 一样，它的“快”也是平均意义上的快，不是最坏情况保证。

示例

判断数组里有没有重复元素：

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    vector<int> nums{1, 4, 2, 3, 4};
    unordered_set<int> seen;

    for (int num : nums) {
        if (seen.find(num) != seen.end()) {
            cout << "发现重复元素：" << num << '\n';
            break;
        }

        seen.insert(num);
    }
}

这个问题只关心“有没有出现过”，完全不关心顺序，所以 unordered_set 很合适。

tuple

介绍与使用场景

tuple 可以把多个不同类型的值打包在一起。你可以把它理解成 pair 的“多元素版本”。

• 业务开发里，一般用它让函数一次返回多个结果，或者临时传递几项不同类型但彼此相关的数据。要是这些字段有长期业务含义，还是定义结构体更清楚。
• 算法题里，常用它组合状态、排序关键字、优先队列里的复合元素，比如“距离、点编号、父节点”这种东西。
• 它方便是方便，但一旦层数深、元素多，可读性会掉得很快。

初始化方式

#include <string>
#include <tuple>
using namespace std;

tuple<int, string, double> a{1, "Alice", 95.5};
tuple<int, string, double> b = make_tuple(2, "Bob", 88.0);

int id = 3;
string name = "Carol";
auto c = tie(id, name);

结构化绑定也很常用：

auto [userId, userName, score] = a;

如果想直接引用原对象，可以写引用绑定：

auto& [refId, refName, refScore] = a;

常用方法

• get<I>(t)：按编译期下标访问元素，通常按 O(1) 理解。
• get<T>(t)：按类型访问元素，前提是这个类型在 tuple 里只出现一次，通常按 O(1) 理解。
• make_tuple(...)：创建 tuple，结构层面可按 O(1) 理解，具体成本看元素构造。
• tie(...)：创建引用形式的 tuple，常用来接收多个返回值，通常按 O(1) 理解。
• tuple_size<T>::value、tuple_element<I, T>::type：编译期信息，不涉及运行时遍历。
• 比较运算：按字典序逐项比较，若把元素个数记作 k，最多比较 k 个成员；如果各成员比较本身都是 O(1)，整体可按 O(k) 理解，否则还要把成员自己的比较成本算进去。
• swap：逐项交换。若把元素个数记作 k，最坏 O(k)，具体还看每个元素的交换成本。

示例

函数一次返回多个结果：

#include <iostream>
#include <string>
#include <tuple>
using namespace std;

tuple<int, string> findUser() {
    return {1001, "Alice"};
}

int main() {
    auto [id, name] = findUser();
    cout << id << ' ' << name << '\n';
}

保存一个复合状态：

#include <iostream>
#include <tuple>
using namespace std;

int main() {
    tuple<int, int, int> state{5, 2, 3};
    auto [distance, row, column] = state;

    cout << "距离：" << distance
         << "，位置：(" << row << ", " << column << ")\n";
}

list

介绍与使用场景

list 是双向链表。它最大的特点不是“快”，而是“已知位置时，插删节点很稳”，并且不会像 vector 那样因为搬移元素把整段数据挪来挪去。

• 业务开发里，一般适合需要长期保留迭代器、并且经常在已知位置插入或删除节点的场景。
• 算法题里，实际使用频率通常没有 vector、deque、queue 那么高，但在需要链表语义、稳定迭代器、节点级操作时还是有价值。
• 如果你只是需要头尾增删并且还想随机访问，通常 deque 更顺手；如果你只是普通顺序存储，通常 vector 还是首选。

初始化方式

#include <list>
using namespace std;

list<int> nums;
list<int> nums1(5);
list<int> nums2(5, 10);
list<int> nums3{1, 2, 3, 4, 5};
list<int> nums4(nums3);
list<int> nums5(nums3.begin(), nums3.end());

常用方法

设当前元素数量为 n：

• size()、empty()：O(1)。
• front()、back()：O(1)。
• push_front()、emplace_front()、push_back()、emplace_back()：O(1)。
• pop_front()、pop_back()：O(1)。
• insert(pos, value)、emplace(pos, ...)：如果已经有位置迭代器，插入单个元素是 O(1)。
• erase(pos)：如果已经有目标位置迭代器，删除单个元素是 O(1)。
• 查找某个值、走到第 i 个位置：都得沿链表慢慢走，最坏 O(n)。
• remove(value)：遍历并删除所有等于该值的节点，O(n)。
• reverse()：O(n)。
• sort()：O(n log n)。
• clear()：O(n)。

这里最容易记错的一点就是：list 的插删是 O(1)，前提是你已经拿到了正确位置的迭代器。如果你还得先遍历半天找到那个位置，整体就不便宜了。

示例

已知位置时在中间插入：

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> nums{10, 20, 30};

    auto pos = nums.begin();
    ++pos;

    nums.insert(pos, 15);

    for (int value : nums) {
        cout << value << ' ';
    }
}

输出会是：

10 15 20 30

但如果你每次都得先一路走过去找到位置：

auto pos = nums.begin();

for (int i = 0; i < 100; ++i) {
    ++pos;
}

那前面的查找本身就已经是 O(n) 了。所以大多数普通场景下，我反而会先考虑 vector 或 deque，而不是急着上 list。

总结

这一篇博客我记录了一下我刷 hot 100 中经常遇到的一些 STL 类。

我感觉其实最核心的不是把接口一个个硬背下来，而是先分清楚几个问题：

• 它的数据在内存里大概怎么放
• 它擅长的是随机访问、两端操作，还是按键查找
• 它的常见操作复杂度大概是什么水平
• 它为什么适合当前题目，而不是“也能用但不知道为什么要用”

如果只是给自己一个很粗的经验版结论，我目前会先这样记：

• 普通顺序存储，先想 vector
• 固定长度，先想 array
• 字符串处理，先想 string
• 两端都要高效操作，先想 deque
• 先进先出用 queue，后进先出用 stack
• 要有序映射/集合，看 map、set
• 只想平均意义上的快速查找，看 unordered_map、unordered_set
• 临时打包两个值用 pair，多个值用 tuple
• list 不少人刚学时觉得很厉害，但真正常规开发和算法题里，很多时候并不是第一选择

后续的话我大概会补充一下关于 priority_queue、multiset、multimap 之类的。

至于迭代器、算法库之类的我应该会单独再开一篇博客编写。那部分和这些容器放在一起看，感觉会更完整一些。

---

---