下面是c++提高编程部分，可以深化对c++的理解

需要本页pdf版点击下载：https://kblog.ink?download=212&tmstv=1764311294

模板

模板是 C++ 为了解决同一逻辑需要为不同类型重复写函数的问题而提供的泛型技术。通过模板，可以让代码在编译阶段根据不同的数据类型生成相应的函数或类，从而减少冗余。

模板的概念

在没有模板之前，如果我们要交换不同类型的变量，需要写多份函数：

void mySwap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

void mySwap(double &a, double &b)
{
    double temp = a;
    a = b;
    b = temp;
}

void mySwap(char &a, char &b)
{
    char temp = a;
    a = b;
    b = temp;
}

逻辑完全一样，却必须为每种类型重新写一份。

模板的作用是解决这种重复劳动，让函数适用于任意类型。

函数模板

函数模板语法：

template<typename T>
void 函数名(参数列表)

示例：

template<typename T>
void mySwap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
}

调用方式可以自动推导：

mySwap(a, b);

也可以显式指定类型：

mySwap<int>(a, b);

函数模板的要点：

类型必须能够推导为同一种类型 T
模板不能自动执行隐式类型转换
若要强制类型，可用 mySwap<int>()
模板是在编译阶段生成代码

函数模板案例说明

假设有一个 Person 类型，也一样可以使用模板：

template<typename T>
void mySwap(T &a, T &b)
{
    T temp = a;
    a = b;
    b = temp;
}

模板对于自定义类型同样有效。

普通函数与模板函数的调用规则

当普通函数和函数模板都能匹配时：

普通函数优先于模板函数。

例如：

void func(int a)
{
    cout << "普通函数" << endl;
}

template<typename T>
void func(T a)
{
    cout << "模板函数" << endl;
}

func(10);       // 调用普通函数
func<>(10);     // 强制调用模板函数
func(3.14);     // 调用模板函数

模板的局限性

模板不是完全万能，有以下限制：

不能自动执行类型转换
类型必须一致（除非显式指定类型）
错误信息复杂，很难读
模板代码必须写在头文件中，不能分离编译
模板实例化过多会导致代码体积膨胀

模板注意点总结

普通函数优先于模板
模板不能进行自动隐式类型转换
需要时可以强制指定模板参数
模板必须在头文件中定义

类模板

类模板允许类支持多种数据类型。

基本语法：

template<typename T>
class 类名
{
};

示例：

template<class T>
class Person
{
public:
    T m_Name;
    T m_Age;

    Person(T name, T age)
    {
        m_Name = name;
        m_Age = age;
    }
};

创建对象时必须指定类型：

Person<string> p("张三", "18");

区别于函数模板：

函数模板可自动推导类型
类模板必须显式指定类型

类模板成员函数的实例化时机

类模板的成员函数不会全部立即生成。

原则：

只有被调用的成员函数才会实例化。

示例中若未调用某成员函数，则该成员函数不会被生成。

类模板对象作为函数参数

三种写法：

传递具体化类型：

void printPerson(Person<string> &p)

使用模板的模板参数：

template<typename T>
void printPerson(Person<T> &p)

整个函数模板化：

template<typename T>
void print(T &p)

三种方式均有效。

类模板与继承

类模板可作为父类或子类。

如果继承一个类模板：

template<typename T>
class Base
{
public:
    T m;
};

class Child : public Base<int>
{
};

如果子类仍然是模板：

template<typename T1, typename T2>
class Child : public Base<T2>
{
};

要点：
继承模板类时必须指定类型，除非子类也是模板。

类模板的类外实现

类外实现成员函数必须写成：

template<typename T>
返回值 类名<T>::函数名(参数)
{
}

示例：

template<typename T>
class Test
{
public:
    T m;
    void show();
};

template<typename T>
void Test<T>::show()
{
    cout << m << endl;
}

必须写 “<T>”，否则编译器不知道该函数属于模板类的成员。

类模板案例

示例两个模板参数：

template<typename T1, typename T2>
class Person
{
public:
    T1 name;
    T2 age;

    Person(T1 name, T2 age)
    {
        this->name = name;
        this->age = age;
    }
};

使用方式：

Person<string, int> p("张三", 18);

STL 初识

STL（Standard Template Library）是标准模板库，是 C++ 的核心内容之一。
STL 是基于模板技术实现的，并提供了大量可复用的容器和算法，让程序员可以用较少代码完成数据结构与算法操作。

STL 是泛型编程思想的典型体现。
所谓泛型编程，就是编写与类型无关的代码。

C++ STL 按照功能分为六大组件：

容器
算法
迭代器
仿函数
适配器
空间配置器

六大组件之间最核心、最紧密的关系是：
容器通过迭代器提供元素访问接口
算法依赖迭代器对容器进行操作

通过迭代器的统一访问方式，算法与容器完全分离，从而实现了完美的复用与组合。

STL 的六大组件介绍

容器

各种数据结构的模板类，例如 vector、deque、list、set、map 等。

算法

各种对容器进行操作的函数模板，例如 sort、find、for_each、count 等。

迭代器

连接算法与容器的桥梁，本质上类似于一个“指针对象”。

仿函数

重载 () 的类，用于让算法支持用户自定义的策略，例如比较规则。

适配器

对容器或函数对象进行改造，使其表现为另一种形态，例如 stack、queue。

空间配置器

负责内存管理，是 STL 底层实现的重要组件。

STL 的整体设计思想

STL 最大的特点是：
数据结构与算法分离，让最优算法无需依赖具体容器。

算法只要依赖迭代器，不关心容器类型
容器只提供迭代器，具体存储结构不用对算法公开
仿函数、适配器提供策略与接口层面的扩展

整个系统通过模板连接在一起。

因此 STL 有以下优点：

代码复用度极高
通用性强
效率高
可维护性强

STL 三大支柱

尽管 STL 有六大组件，但核心组件是三个：

容器
算法
迭代器

容器负责存储
迭代器负责遍历
算法负责操作

三者之间关系紧密但又互不耦合，这是 STL 的精髓。

容器分类概述

STL 中的容器按存储结构大致分为三类：

顺序容器（Sequence Containers）
关联容器（Associative Containers）
无序容器（Unordered Containers，C++11）

其中 PDF 本章重点讲解的是以下两大类：

顺序容器
关联容器

顺序容器包括：
vector
deque
list
string
以及适配器 stack、queue、priority_queue

关联容器包括：
set
multiset
map
multimap

这些容器均基于红黑树实现，自动排序。

迭代器的分类

不同容器支持不同类型的迭代器：

输入迭代器
输出迭代器
前向迭代器
双向迭代器
随机访问迭代器

其中：

vector 和 deque 支持随机访问
list 仅支持双向迭代
set 与 map 的迭代器属于双向迭代器

随机访问迭代器可以执行：

it + 1
it – 1
it[n]

双向迭代器只能执行：

++it
–it

迭代器能力越强，可使用的算法越多。

STL 与模板的关系

STL 基于模板技术构建：
容器是类模板
算法是函数模板
迭代器是类模板

借助模板，STL 可以让同一个算法适配不同类型的容器，真正实现代码的复用性和泛型编程。

STL 使用的基本模式

典型的 STL 使用模式是“三件套”：

容器
迭代器
算法

示例：

vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);

for_each(v.begin(), v.end(), print);

容器负责存储
迭代器负责遍历
算法 for_each 负责操作元素

这是 STL 的基本使用方法，也是所有 STL 内容的核心。

vector 容器

vector 是一个动态数组，能够在运行时自动调整存储空间。
其底层实现为连续的线性存储空间，因此与普通数组具有相同的随机访问性能。
vector 在尾部插入和删除元素效率很高，但在中间插入删除会导致大量元素移动，效率较低。

使用 vector 需要包含头文件：

#include <vector>

vector 是 STL 中最常用的容器。

vector 的构造方式

vector 提供多种构造方法。

默认构造：

vector<int> v;

指定大小构造：

vector<int> v(10);

指定大小并初始化所有元素：

vector<int> v(10, 100);

根据迭代器区间构造：

vector<int> v2(v.begin(), v.end());

拷贝构造：

vector<int> v2(v1);

所有这些构造方式都最终会生成一段连续内存。

vector 的赋值方式

使用 operator=：

vector<int> v2 = v1;

assign 区间赋值：

v2.assign(v1.begin(), v1.end());

assign 指定数量与初始值：

v2.assign(10, 100);

交换两个 vector 的内容：

v1.swap(v2);

swap 操作时间复杂度为常数级，不是元素逐个拷贝。

vector 的容量与大小操作

获取当前元素数量：

v.size();

判断是否为空：

v.empty();

获取容量（capacity）：

v.capacity();

调整 size：

v.resize(20);       // 不足补 0，多余截断
v.resize(20, 100);  // 不足补 100

预留容量（reserve）：

v.reserve(1000);

reserve 用于提前申请空间，避免多次扩容，提高性能。
扩容通常会导致一次新的内存分配，并且将原有数据移动过去，因此迭代器会失效。

vector 的插入与删除操作

尾部插入元素：

v.push_back(100);

尾部删除元素：

v.pop_back();

插入元素到指定位置：

v.insert(v.begin(), 200);

删除指定位置：

v.erase(v.begin());

删除指定区间：

v.erase(v.begin(), v.begin() + 3);

清空所有元素：

v.clear();

remove 和 erase 不同：

clear 不释放容量
erase 会删除元素并保持连续性

要真正缩小容量，可以用 swap 技巧：

vector<int>(v).swap(v);

vector 的数据访问操作

使用下标访问元素：

v[0];

使用 at 访问元素（带范围检查）：

v.at(0);

访问第一个元素：

v.front();

访问最后一个元素：

v.back();

vector 支持随机访问，是其重要特性。

vector 遍历方式

使用迭代器：

for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
    cout << *it << endl;
}

使用反向迭代器：

for (vector<int>::reverse_iterator rit = v.rbegin(); rit != v.rend(); rit++)
{
    cout << *rit << endl;
}

使用范围 for（C++11）：

for (int x : v)
{
    cout << x << endl;
}

使用 for_each 算法：

for_each(v.begin(), v.end(), print);

vector 的迭代器失效问题

扩容后：

整个存储区可能重新分配
所有迭代器、指针、引用全部失效

插入元素后：

插入点之后的迭代器会失效

删除元素后：

删除点之后的迭代器会失效

这是 vector 使用中必须注意的问题。

vector 的内存管理特点

vector 的 capacity 通常比 size 大
当空间不足时，vector 会自动扩大容量
扩容通常以 1.5~2 倍增长（依编译器实现）
扩容会导致内存重新分配
因此 vector 不适合频繁在中间位置插入

vector 容器的小结

底层为连续数组，支持随机访问
尾插与尾删效率高
中间插入和删除效率低
扩容会导致迭代器失效
reserve 可以减少扩容次数
适用于需要快速访问和尾部操作的场景

deque 容器

deque（double-ended queue）称为双端队列，是一种可以在头部和尾部快速插入和删除元素的顺序容器。
与 vector 不同，deque 并不是连续存储，它使用分段连续的结构，因此没有 capacity；但它依然提供快速的随机访问能力。

使用 deque 需要包含头文件：

#include <deque>

deque 的设计目标是兼顾：

能够像 vector 一样随机访问
能够像 list 一样在头尾快速插入删除

因此它内部采用分段数组结构（由多个缓冲区组成），并由一个中心控制器管理。

deque 的构造方式

默认构造：

deque<int> d;

指定大小构造：

deque<int> d(10);

指定大小并初始化所有元素：

deque<int> d(10, 100);

区间构造：

deque<int> d2(d.begin(), d.end());

拷贝构造：

deque<int> d2(d1);

这些构造方式与 vector 类似。

deque 的赋值方式

直接赋值：

d2 = d1;

assign 区间赋值：

d2.assign(d1.begin(), d1.end());

assign 指定数量和值：

d2.assign(10, 100);

交换两个 deque：

d.swap(d2);

swap 时间复杂度为常数级。

deque 的大小操作

获取当前元素数量：

d.size();

判断是否为空：

d.empty();

改变容器大小：

d.resize(20);        // 不足补 0，多余截断
d.resize(20, 100);   // 不足补 100

deque 不像 vector 那样有 capacity，因此没有 capacity() 和 reserve() 函数。

deque 的插入与删除操作

头部插入：

d.push_front(100);

尾部插入：

d.push_back(200);

头部删除：

d.pop_front();

尾部删除：

d.pop_back();

在中间插入：

d.insert(d.begin(), 300);

删除指定位置：

d.erase(d.begin());

删除指定区间：

d.erase(d.begin(), d.begin() + 3);

清空：

d.clear();

deque 的 push_front 和 push_back 都具有高效率，这是它区别于 vector 的重要特性。

deque 的数据访问操作

随机访问：

d[0];

带边界检查访问：

d.at(0);

获取第一个元素：

d.front();

获取最后一个元素：

d.back();

deque 提供随机访问迭代器，因此可用于 sort 算法。

deque 的遍历方式

迭代器遍历：

for (deque<int>::iterator it = d.begin(); it != d.end(); it++)
{
    cout << *it << endl;
}

反向迭代器遍历：

for (deque<int>::reverse_iterator rit = d.rbegin(); rit != d.rend(); rit++)
{
    cout << *rit << endl;
}

范围 for：

for (int x : d)
{
    cout << x << endl;
}

使用 STL 算法：

for_each(d.begin(), d.end(), print);

deque 的内部结构

deque 的底层结构不是连续存储，而是：

多段缓冲区（blocks）
一个中央控制器（map），记录各段缓冲区的指针

访问时通过 map 和偏移量来找到实际存储位置。
因此：

deque 的随机访问速度接近 vector，但略慢
中间插入比 vector 快，但比 list 慢

由于结构分段，deque 不需要像 vector 那样大幅扩容，也可以快速头尾操作。

deque 的使用注意点

deque 不提供 capacity
deque 可以在头尾快速插入删除
deque 的中间插入删除比 vector 更快
deque 支持随机访问，因此可以使用 sort
在大量使用 push_front 时，deque 优于 vector
迭代器在插入删除行为后可能会失效（特别是多段扩张时）

deque 的适用场景

适用于以下情况：

需要随机访问
需要频繁头尾插入删除
不需要严格的连续存储

典型用途：

模拟队列结构
双端缓冲处理
需要频繁从头部读取数据的算法

list 容器

list 是一个双向链表容器。
与 vector 和 deque 不同，list 的底层结构不是连续存储，而是典型的链式结构：

每个节点包含：

数据域
前驱指针
后继指针

因为结构的原因：

list 不支持随机访问
迭代器不支持 +1、-1 运算符
在任意位置插入和删除效率很高
适用于大量插入删除操作的场景

使用 list 需要包含头文件：

#include <list>

list 的构造方式

默认构造：

list<int> l;

指定大小构造：

list<int> l(10);

指定大小与初始值：

list<int> l(10, 100);

区间构造：

list<int> l2(l.begin(), l.end());

拷贝构造：

list<int> l2(l1);

list 的构造形式与其他容器保持一致。

list 的赋值操作

直接赋值：

l2 = l1;

assign 区间赋值：

l.assign(l1.begin(), l1.end());

assign 指定数量与初始值：

l.assign(10, 100);

交换两个 list：

l.swap(l2);

swap 操作为常数时间，因为只是交换内部指针。

list 的大小与容量

获取元素个数：

l.size();

判断是否为空：

l.empty();

调整大小：

l.resize(20);
l.resize(20, 100);

由于 list 是链表，没有 capacity 的概念。

size 操作对于 list 的实现是常数时间复杂度。

list 的插入与删除操作

尾部插入：

l.push_back(100);

尾部删除：

l.pop_back();

头部插入：

l.push_front(200);

头部删除：

l.pop_front();

在指定位置插入：

l.insert(it, 300);

删除指定位置：

l.erase(it);

删除某个值：

l.remove(100);

remove 会删除所有等于该值的节点。

清空：

l.clear();

list 在任何位置插入和删除效率极高，这是链表的最大特点。

list 的数据访问

访问第一个元素：

l.front();

访问最后一个元素：

l.back();

list 不支持下标访问，也不支持 at，因为底层为链式结构，不具备随机访问能力。

list 的遍历方式

普通迭代器遍历：

for (list<int>::iterator it = l.begin(); it != l.end(); it++)
{
    cout << *it << endl;
}

反向迭代器：

for (list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); rit++)
{
    cout << *rit << endl;
}

范围 for：

for (int x : l)
{
    cout << x << endl;
}

list 的迭代器不能使用：

it + 1
it[n]

因为链表不支持随机访问。

list 特有的排序与反转操作

由于 list 不支持随机访问，无法使用 sort 算法。
STL 为 list 提供内置成员函数：

排序：

l.sort();

支持自定义排序规则：

l.sort(MyCompare());

反转：

l.reverse();

这些操作都是链表特有的，针对其结构设计的高效算法。

list 的链表特性总结

插入与删除高效
不支持随机访问
迭代器稳定
节点分散存储
sort 与 reverse 是成员函数
适合大量数据插入删除

list 容器通常用于以下场景：

需要频繁在中间位置插入或删除元素
需要稳定迭代器
不关心随机访问性能

stack 容器

stack 是一种后进先出（LIFO）的容器适配器。
它并不是独立容器，而是依赖其他容器实现其功能。
默认情况下，stack 底层使用 deque 作为其存储结构，也可以指定为 vector。

使用 stack 需要包含头文件：

#include <stack>

stack 的特点：

只能访问栈顶元素
只能从栈顶插入和删除
遵循后进先出的规则

stack 不提供遍历功能，不支持随机访问。

stack 的常用接口

创建 stack：

stack<int> s;

向栈顶压入元素：

s.push(10);

弹出栈顶元素：

s.pop();

访问栈顶元素：

s.top();

判断是否为空：

s.empty();

获取元素数量：

s.size();

stack 的接口非常简单，不允许直接访问除栈顶以外的任何元素。

stack 的使用示例

stack<int> s;

s.push(10);
s.push(20);
s.push(30);

while (!s.empty())
{
    cout << s.top() << endl;
    s.pop();
}

输出顺序为：30、20、10（后进先出）。

stack 的底层结构说明

stack 并非独立容器，而是一种适配器。
其底层可以使用：

deque（默认）
vector
list（较少使用）

实际声明底层类型的语法：

stack<int, vector<int>> s;     // 用 vector 做底层
stack<int, deque<int>> s2;     // 用 deque 做底层

由于 stack 只允许访问栈顶，因此底层容器必须支持：

push_back
pop_back
back

这些特性使得 deque 和 vector 最适合作为底层。

stack 的限制

不允许遍历
不允许随机访问
只能操作栈顶元素
无法检查栈中第二个、第三个等位置

它适用于严格遵循 LIFO 结构的场景，例如：

函数调用管理
表达式求值
括号匹配
追踪某些操作历史

queue 容器

queue 是一种先进先出（FIFO）的容器适配器。
与 stack 类似，queue 不是独立容器，而是对底层容器的一种“行为封装”。

queue 的特点：

只能从队尾入队（push）
只能从队头出队（pop）
不能访问除队头、队尾外的其他元素
遵循严格的先进先出规则

需要包含头文件：

#include <queue>

默认底层容器为 deque，也可以指定为 list 等其他支持 push_back / pop_front 的容器。

queue 的常用接口

创建 queue：

queue<int> q;

入队（加入队尾）：

q.push(10);

出队（删除队头）：

q.pop();

访问队头元素：

q.front();

访问队尾元素：

q.back();

判断是否为空：

q.empty();

获取元素个数：

q.size();

queue 不支持遍历，不支持随机访问，也不允许访问中间元素。

queue 的使用示例

queue<int> q;

q.push(10);
q.push(20);
q.push(30);

while (!q.empty())
{
    cout << q.front() << endl;  // 打印队头
    q.pop();                    // 出队
}

输出顺序为：10、20、30（先进先出）。

queue 的底层结构说明

queue 的默认底层结构为 deque。
deque 支持：

push_back
pop_front
front
back

因此非常适合作为 queue 的底层。
也可以手动指定底层容器：

queue<int, list<int>> q2;  // 使用 list 作为底层

底层容器必须支持以下操作：

push_back
pop_front
front
back

vector 不能作为 queue 的底层，因为 vector 不支持 pop_front。

queue 的限制

不能随机访问
不能遍历
不能查看中间数据
只能操作队头和队尾

queue 用于严格遵循先进先出的场景，例如：

任务调度
消息队列
排队系统
数据流缓冲

priority_queue 容器

priority_queue 是一个优先级队列容器适配器。
它不保证先进先出，而是保证“队头永远是最大（或最小）优先级的元素”。
priority_queue 底层通常使用堆（heap）结构实现，默认是最大堆。

使用 priority_queue 必须包含头文件：

#include <queue>

priority_queue 与 queue 和 stack 一样，是容器适配器，不是独立容器。

其底层默认结构是：

vector（作为底层容器）
以及 heap（作为排序规则）

priority_queue 的基本特点

队头元素永远是当前队列中优先级最高的元素
默认情况下，priority_queue 是大顶堆（最大值在队头）
不支持遍历
不支持随机访问
只能访问队头元素

适用于需要动态获取最大元素或最小元素的场景。

priority_queue 的基本用法

声明一个默认的优先级队列（大顶堆）：

priority_queue<int> pq;

向队列中插入元素：

pq.push(10);
pq.push(30);
pq.push(20);

访问队头元素（优先级最高）：

pq.top();

删除队头元素：

pq.pop();

判断是否为空：

pq.empty();

获取元素数量：

pq.size();

priority_queue 的默认行为示例

priority_queue<int> pq;

pq.push(10);
pq.push(30);
pq.push(20);

cout << pq.top();   // 输出 30

输出为 30，因为默认规则是最大堆。

每次 pop 都会删除当前最大元素：

30
20
10

priority_queue 的底层结构说明

priority_queue 默认使用如下结构：

vector 作为底层容器
greater 或 less 作为比较规则
内部使用 make_heap、push_heap、pop_heap 来维护堆结构

默认情况：

priority_queue<int, vector<int>, less<int>>   // 大顶堆（默认）

其中 less 表示元素按从大到小排序。

priority_queue 实现小顶堆

若要实现小顶堆（最小值优先），需要指定 greater 比较器：

priority_queue<int, vector<int>, greater<int>> pq;

示例：

priority_queue<int, vector<int>, greater<int>> pq;

pq.push(10);
pq.push(30);
pq.push(20);

cout << pq.top();    // 输出 10

priority_queue 存放自定义类型

priority_queue 可以存放自定义类型，需要自定义比较器。

示例：

struct Person
{
    string name;
    int age;
};

struct ComparePerson
{
    bool operator()(const Person& a, const Person& b) const
    {
        return a.age < b.age;    // 年龄大的优先
    }
};

priority_queue<Person, vector<Person>, ComparePerson> pq;

插入元素后，pq.top() 永远是年龄最大的 Person。

priority_queue 的限制

不能遍历队列
不能访问中间元素
不能修改元素值（修改元素会破坏堆结构）
适合频繁取最大值或最小值的场景

priority_queue 典型用途：

任务调度
排行榜
动态获取最大或最小数据
事件优先级管理

set 容器

set 是一个关联式容器，底层采用红黑树（平衡二叉树）结构实现。
set 中的所有元素自动按照一定规则进行排序，并且每个元素都必须独一无二。

set 的主要特点：

所有元素自动排序
元素不可重复
底层为红黑树结构
查找、插入、删除效率为对数级
只存 key，不存 key-value 结构

使用 set 需要包含头文件：

#include <set>

set 的构造方式

默认构造：

set<int> s;

区间构造：

set<int> s2(s.begin(), s.end());

拷贝构造：

set<int> s2(s1);

set 构造方式和其他 STL 容器一致，只是内部结构不同。

set 的赋值操作

直接使用 =：

s2 = s1;

assign 区间赋值：

s.assign(s1.begin(), s1.end());

交换两个 set 的内容：

s.swap(s2);

swap 操作复杂度为常数级（只交换树根指针）。

set 的大小和容量操作

判断是否为空：

s.empty();

获取元素数量：

s.size();

set 不提供 capacity，因为它不是连续存储结构。

清空：

s.clear();

set 的插入和删除操作

插入元素：

s.insert(10);

由于 set 不允许重复，如果插入一个已存在的元素，将失败。

insert 返回值为 pair：

pair<set<int>::iterator, bool> ret = s.insert(10);

其中：

iterator 表示插入位置
bool 表示是否插入成功（true 为成功，false 为失败）

删除元素：

s.erase(it);

删除指定值：

s.erase(10);

清空：

s.clear();

set 的迭代器遍历

正向遍历：

for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
{
    cout << *it << endl;
}

反向遍历：

for (set<int>::reverse_iterator rit = s.rbegin(); rit != s.rend(); ++rit)
{
    cout << *rit << endl;
}

由于底层为红黑树，遍历得到的顺序为默认升序。

set 的查找操作

查找某元素：

set<int>::iterator it = s.find(20);

如果存在，find 返回对应迭代器；
如果不存在，返回 s.end()。

统计某值出现次数：

s.count(20);

因为 set 不允许重复，返回值要么是 1，要么是 0。

set 的自动排序与比较规则

set 默认按升序排列（使用 less<T>）：

set<int> s;  // 默认从小到大

如需自定义排序规则，例如降序，需要自定义仿函数：

struct MyCompare
{
    bool operator()(int a, int b) const
    {
        return a > b;    // 从大到小排序
    }
};

set<int, MyCompare> s;

通过比较器，set 可以实现任意自定义排序规则。

set 存储自定义数据类型

set 存储自定义类型时，必须提供排序规则，否则编译失败。

示例：

struct Person
{
    string name;
    int age;
};

struct MyCompare
{
    bool operator()(const Person& p1, const Person& p2) const
    {
        return p1.age < p2.age;
    }
};

set<Person, MyCompare> s;

要点：

自定义类型必须提供可比较方式
通过比较器决定插入顺序和唯一性判断

set 的应用特性总结

自动排序
元素不可重复
查找效率高
适合去重场景
适合需要保持有序的数据集合
底层为红黑树，所有操作为对数复杂度

典型用途包括：

从数据中去重
维护自动排序的数据集合
快速查找和删除键值

multiset 容器

multiset 与 set 的主要区别是：

set 中的元素不允许重复
multiset 中的元素允许重复出现

除了允许重复之外，multiset 的其他行为（自动排序、底层红黑树、迭代器规则等）与 set 完全一致。

使用 multiset 需要包含头文件：

#include <set>

multiset 的底层仍然是红黑树，因此所有元素按指定规则自动排序。

multiset 的构造方式

默认构造：

multiset<int> ms;

区间构造：

multiset<int> ms2(ms.begin(), ms.end());

拷贝构造：

multiset<int> ms2(ms1);

所有构造方式与 set 相同。

multiset 的赋值操作

直接赋值：

ms2 = ms1;

assign 区间赋值：

ms.assign(ms1.begin(), ms1.end());

交换内容：

ms.swap(ms2);

这些操作与 set 完全一致。

multiset 的插入元素

插入元素：

ms.insert(10);
ms.insert(10);   // 允许重复

与 set 不同，multiset 插入时不会失败，因此 insert 返回值没有布尔标识。

返回值类型：

multiset<int>::iterator it = ms.insert(10);

由于 multiset 不会阻止重复，因此不需要用 pair 返回插入是否成功。

multiset 的删除操作

删除指定位置：

ms.erase(it);

删除所有等于某值的元素：

ms.erase(10);

由于 multiset 允许多个重复值，因此 erase(10) 会删除所有为 10 的节点。

删除区间：

ms.erase(ms.begin(), ms.end());

清空容器：

ms.clear();

multiset 的查找和统计

查找某值的任意一个位置：

multiset<int>::iterator it = ms.find(10);

统计某值出现次数：

ms.count(10);   // 有可能返回多个

由于 multiset 允许重复，count 可能返回 0, 1, 2, 3…

查找某值的全部区间：

pair<multiset<int>::iterator, multiset<int>::iterator> range;
range = ms.equal_range(10);

equal_range 返回：
第一个迭代器是等于 10 的第一个位置
第二个迭代器是第一个大于 10 的位置

要遍历所有等于 10 的元素：

for (multiset<int>::iterator it = range.first; it != range.second; ++it)
{
    cout << *it << endl;
}

multiset 的排序规则

multiset 默认按升序排序：

multiset<int> ms;

如果需要自定义排序规则，如降序，可以传入比较器：

struct MyCompare
{
    bool operator()(int a, int b) const
    {
        return a > b;   // 降序
    }
};

multiset<int, MyCompare> ms;

multiset 将根据比较器自动进行排序。

multiset 的自定义类型存储

与 set 相同，存放自定义类型时必须提供比较规则：

struct Person
{
    string name;
    int age;
};

struct MyCompare
{
    bool operator()(const Person& p1, const Person& p2) const
    {
        return p1.age < p2.age;
    }
};

multiset<Person, MyCompare> ms;

由于允许重复，多个 Age 相同的 Person 也可以存入 multiset。

multiset 的特性总结

允许重复元素
插入永远成功
自动排序
底层红黑树
可通过 count 统计重复次数
可通过 equal_range 获取重复元素区间
适合需要有序且允许重复的场景

典型用途：

从大量数据中获取排序结果
统计重复元素
构建有序集合且不需要去重

map 容器

map 是关联式容器，用来存储 key-value（键值对）结构的数据。
其底层实现仍然是红黑树，因此 map 中的所有元素都会根据 key 自动排序。

map 的主要特点：

数据以键值对形式存储（pair<const Key, T>）
通过 key 自动排序
key 不允许重复
查找、插入、删除效率为对数级
通过 key 可以快速访问 value

包含头文件：

#include <map>

map 的迭代器遍历出来的顺序为 key 的升序。

map 的构造方式

默认构造：

map<int, string> m;

区间构造：

map<int, string> m2(m.begin(), m.end());

拷贝构造：

map<int, string> m2(m1);

map 的构造方式与 set 非常类似，但内容为键值对。

map 的赋值操作

直接赋值：

m2 = m1;

使用 swap 交换内容：

m.swap(m2);

map 不支持 assign，因为 key-value 与 assign 语义不一致。

map 的插入操作

map 的插入方式有多种：

通过 pair 插入：

m.insert(pair<int, string>(1, "apple"));

通过 make_pair：

m.insert(make_pair(2, "banana"));

通过 value_type：

m.insert(map<int, string>::value_type(3, "orange"));

通过下标操作符 []：

m[4] = "pear";

注意：
使用 [] 访问不存在的 key 会自动创建该 key，并将 value 默认构造出来。

例如：

cout << m[10];   // key 10 被自动创建，value 默认为空字符串

这与 insert 的行为不同。

map 的插入返回值

使用 insert 时，返回值是一个 pair：

pair<map<int, string>::iterator, bool> ret = m.insert(make_pair(1, "apple"));

其中：

iterator 表示插入位置
bool 表示是否插入成功

当 key 重复时：

bool 为 false
iterator 指向已存在的元素

map 的删除操作

删除指定位置：

m.erase(it);

删除指定 key：

m.erase(1);

删除区间：

m.erase(m.begin(), m.end());

清空：

m.clear();

map 的查找与访问

查找 key：

map<int, string>::iterator it = m.find(2);

如果存在，返回指向元素的迭代器；
如果不存在，返回 m.end()。

统计某 key 出现次数：

m.count(2);   // 对 map 来说，只可能是 0 或 1

由于 map 的 key 不允许重复，所以 count 只能返回 0 或 1。

通过下标访问：

m[3];

注意：这会自动创建 key 为 3 的元素，即使它原本不存在。

更安全的是使用 at（C++11）：

m.at(3);

at 如果 key 不存在，会抛出异常。

map 的遍历

遍历 map：

for (map<int, string>::iterator it = m.begin(); it != m.end(); ++it)
{
    cout << it->first << " " << it->second << endl;
}

first 表示 key
second 表示 value

由于 map 是按照 key 自动排序的，因此遍历顺序为 key 的升序。

map 的自定义排序

默认排序规则为 less<Key>（升序）。

如果需要自定义排序规则，例如降序，可以使用仿函数：

struct MyCompare
{
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};

map<int, string, MyCompare> m;

map 会根据比较器对 key 进行排序。

map 存储自定义类型

当 key 为自定义类型时，必须提供比较规则，否则编译失败。

示例：

struct Person
{
    string name;
    int age;
};

struct ComparePerson
{
    bool operator()(const Person& p1, const Person& p2) const
    {
        return p1.age < p2.age;
    }
};

map<Person, string, ComparePerson> m;

value 不需要可比较，但 key 必须可比较。

map 的特性总结

键值对结构
key 自动排序
key 不允许重复
使用 [] 会自动创建元素
查找、删除效率高
底层为红黑树

适用于：

通过 key 快速查找 value 的场景
需要自动排序的映射结构
需要保持 key 的唯一性

multimap 容器

multimap 与 map 的主要区别是：

map 的 key 不允许重复
multimap 的 key 允许重复

除此之外，multimap 与 map 在结构、迭代器、性能特征上都几乎一致。
底层仍然是红黑树，所有元素按照 key 自动排序。

使用 multimap 需要包含头文件：

#include <map>

multimap 按 key 自动排序，并允许多个键指向不同 value。

multimap 的构造方式

默认构造：

multimap<int, string> mm;

区间构造：

multimap<int, string> mm2(mm.begin(), mm.end());

拷贝构造：

multimap<int, string> mm2(mm1);

multimap 的构造方式与 map 完全一致。

multimap 的赋值操作

直接赋值：

mm2 = mm1;

交换内容：

mm.swap(mm2);

和 map 一样，multimap 不支持 assign。

multimap 的插入操作

插入键值对：

mm.insert(make_pair(1, "Tom"));
mm.insert(make_pair(1, "Jack"));
mm.insert(make_pair(2, "Lucy"));

因为 multimap 允许重复 key，insert 永远不会失败：

multimap<int, string>::iterator it = mm.insert(make_pair(1, "Alice"));

不会返回 bool，因为不存在“插入失败”。

multimap 的删除操作

删除指定位置：

mm.erase(it);

删除指定 key（会删除所有等于该 key 的键值对）：

mm.erase(1);

删除区间：

mm.erase(mm.begin(), mm.end());

清空：

mm.clear();

multimap 的查找与统计

查找某 key 的一个位置：

multimap<int, string>::iterator it = mm.find(1);

统计某 key 的数量：

mm.count(1);   // 返回 key=1 的所有数量

查找等于某 key 的所有区间：

pair<multimap<int, string>::iterator, multimap<int, string>::iterator> range;
range = mm.equal_range(1);

遍历所有 key=1 的元素：

for (multimap<int, string>::iterator it = range.first; it != range.second; ++it)
{
    cout << it->first << " " << it->second << endl;
}

equal_range 是 multimap 中最重要的查询方式之一，可以一次性获取所有重复键。

multimap 的遍历方式

常规遍历：

for (multimap<int, string>::iterator it = mm.begin(); it != mm.end(); ++it)
{
    cout << it->first << " " << it->second << endl;
}

遍历得到的结果按 key 的升序。

由于 key 可以重复，输出可能包含连续的相同 key。

multimap 的排序规则

默认使用升序排序规则：

multimap<int, string> mm;

可自定义排序规则：

struct MyCompare
{
    bool operator()(int a, int b) const
    {
        return a > b;
    }
};

multimap<int, string, MyCompare> mm;

自定义比较对象必须能比较 key。

multimap 的自定义类型存储

若 key 为自定义类型，必须提供比较器：

struct Person
{
    string name;
    int age;
};

struct ComparePerson
{
    bool operator()(const Person& p1, const Person& p2) const
    {
        return p1.age < p2.age;
    }
};

multimap<Person, string, ComparePerson> mm;

value 不需要比较规则，但 key 必须能比较。

multimap 的主要特性总结

key 可以重复
自动排序
底层为红黑树
不会因为重复 key 而插入失败
count 和 equal_range 是核心操作
适合“一对多”的映射关系
用于需要根据 key 分类存储多个 value 的场景

典型用途：

分类管理多个对象
建立多对一或一对多关系
按 key 自动排序并保存重复信息

STL 算法

STL 中的算法是非常重要的一部分。算法大多以函数模板的形式提供，专门用于操作各种 STL 容器。
算法的分类大致为：

遍历算法
查找算法
排序算法
拷贝与替换类算法
删除类算法
数值算法
集合算法

算法的使用方式：

算法通过迭代器访问容器元素，因此适用于几乎所有容器。
算法与容器完全解耦，迭代器是连接两者的桥梁。

使用算法需要包含头文件：

#include <algorithm>
#include <functional>

部分数值类算法需要包含：

#include <numeric>

遍历算法

遍历算法主要用于对容器中的每个元素执行某些操作。

for_each
该算法对区间内每一个元素执行给定的函数对象。

语法：

for_each(开始迭代器, 结束迭代器, 函数对象);

示例：

for_each(v.begin(), v.end(), print);

print 可以是函数或者仿函数。

常用遍历算法

for_each：对每个元素执行某操作
transform：将旧区间的元素加工后放到新的区间中

transform 示例：

transform(v.begin(), v.end(), v2.begin(), negate<int>());

注意 transform 第四个参数要求是仿函数或可调用对象。

transform 不会改变原容器，除非原容器作为输出区间。

查找算法

find
查找等于某值的元素，返回迭代器。

find(v.begin(), v.end(), 10);

find_if
根据条件查找，条件由谓词（返回 bool 的函数或仿函数）决定。

find_if(v.begin(), v.end(), GreaterFive());

greaterFive 是一个谓词，判断元素是否大于 5。

adjacent_find
查找相邻的重复元素。

adjacent_find(v.begin(), v.end());

binary_search
二分查找，要求容器必须是有序的。

binary_search(v.begin(), v.end(), 20);

count
统计区间中等于某值的元素数量。

count_if
按条件统计元素数量。

排序算法

sort
快速排序算法，支持随机访问迭代器（vector、deque）。

sort(v.begin(), v.end());

自定义排序：

sort(v.begin(), v.end(), greater<int>());

stable_sort
稳定排序，排序后相同元素保持原有相对顺序。

random_shuffle
随机打乱容器元素。

reverse
将区间元素反转。

拷贝与替换算法

copy
复制区间元素到另一处：

copy(v.begin(), v.end(), v2.begin());

replace
将区间内等于某值的元素替换为新值：

replace(v.begin(), v.end(), oldValue, newValue);

replace_if
按条件替换：

replace_if(v.begin(), v.end(), 谓词, newValue);

swap
交换两个容器内容：

swap(v1, v2);

删除类算法

remove
删除区间内等于某值的元素，但不改变容器大小，只是将要删除的元素“覆盖掉”。

remove(v.begin(), v.end(), 10);

remove_if
按条件删除。

真正要删除元素，需要配合容器的 erase：

v.erase(remove(v.begin(), v.end(), 10), v.end());

unique
去除相邻重复元素（非全局去重，需要先排序）。

数值算法（numeric 头文件）

accumulate
计算区间和：

accumulate(v.begin(), v.end(), 初始值);

inner_product
计算两个区间的内积。

inner_product(v1.begin(), v1.end(), v2.begin(), 初值);

partial_sum
计算前缀和：

partial_sum(v.begin(), v.end(), v2.begin());

adjacent_difference
计算相邻元素差值。

集合算法（针对有序容器）

set_intersection
求交集。

set_union
求并集。

set_difference
求差集。

这些算法要求区间必须是有序的。

函数对象（仿函数）

函数对象是重载了 () 的类，可以像函数一样使用。

示例：

struct Print
{
    void operator()(int v)
    {
        cout << v << endl;
    }
};

使用：

for_each(v.begin(), v.end(), Print());

谓词

谓词是返回 bool 的函数或仿函数。

一元谓词：判断单个元素
二元谓词：判断两个元素的关系（如 sort 自定义规则）

示例：

struct GreaterFive
{
    bool operator()(int v)
    {
        return v > 5;
    }
};

常见内置仿函数

算术仿函数：plus minus multiplies divides 等
关系仿函数：greater less equal_to 等
逻辑仿函数：logical_and logical_or logical_not

例如：

sort(v.begin(), v.end(), greater<int>());

string 容器

string 是 C++ 提供的专门操作字符串的类，属于 STL 的顺序容器之一。
与 C 风格字符串相比，string 更安全、使用更方便，并且支持动态扩容。

使用 string 需要包含头文件：

#include <string>

string 底层采用动态数组结构，支持随机访问、自动扩容、比较、拼接等操作。

string 的构造方式

创建空字符串：

string s;

使用 C 字符串初始化：

string s("hello");

复制构造：

string s2(s1);

重复某字符构造：

string s(10, 'a');   // "aaaaaaaaaa"

使用区间构造（迭代器）：

string s(str.begin(), str.end());

string 的赋值操作

使用 =：

string s;
s = "hello";
s = s2;

assign 区间赋值：

s.assign(s2.begin(), s2.end());

assign 指定数量和字符：

s.assign(5, 'x');    // "xxxxx"

assign 使用 C 字符串：

s.assign("world");

string 的拼接操作

使用 += 拼接字符串：

s += "abc";

使用 append：

s.append("def");

拼接单个字符：

s.push_back('X');

拼接多个字符：

s.append(5, 'y');   // "yyyyy"

string 的拼接操作会自动扩容。

string 的查找与替换

查找子串：

s.find("abc");

查找字符：

s.find('x');

查找最后一次出现的位置：

s.rfind("abc");

替换指定区间：

s.replace(pos, len, "newtext");

string 的比较

string 支持直接使用 ==、!=、<、> 等比较。

也支持 compare 函数：

s.compare(s2);

compare 返回：

0：相等

0：大于
<0：小于

比较规则基于字典序。

string 的字符访问

使用下标访问：

s[0];

范围检查访问：

s.at(0);

访问第一个字符：

s.front();

访问最后一个字符：

s.back();

在末尾添加字符：

s.push_back('a');

删除末尾字符：

s.pop_back();

string 的插入和删除

插入操作：

s.insert(0, "hello");

插入单字符：

s.insert(pos, 3, 'x');   // 插入 3 个 'x'

删除操作：

s.erase(0, 3);   // 删除前 3 个字符

清空：

s.clear();

string 的子串操作

获取子串：

s.substr(pos);

获取指定区间子串：

s.substr(pos, len);

子串会返回一个新的 string 对象。

string 与 C 字符串转换

获取 C 风格字符串指针：

s.c_str();

注意：c_str() 返回 const char*，不可修改。

将 C 字符串赋值给 string：

s = "hello";

将 string 转为 char 数组，需要手动拷贝。

string 的长度与容量

获取字符串长度：

s.length();

等价于：

s.size();

改变长度：

s.resize(20);         // 不足补 '\0'
s.resize(20, 'x');    // 不足补 'x'

string 内部也有 capacity，用于管理动态扩容：

s.capacity();

string 会根据需要自动扩容。

string 容器小结

支持动态增长
支持随机访问
支持拼接、查找、替换等高级操作
自动管理内存，无需考虑 ‘\0’ 结尾
比 C 字符串安全许多

string 是实际开发中最常用的字符串结构。

评委打分案例

这个案例用于综合练习 vector、deque、algorithm、函数对象等 STL 技术，同时贯穿面向对象的实践。

案例背景：

某比赛有 5 名评委对选手打分
每名评委的打分范围为 0～100
选手最终得分为去除最高分、最低分后的 3 个分数平均值

该案例分为几个步骤：

创建选手类
让 5 名评委打分
使用容器存储每位评委的分数
对分数进行处理（排序、去掉最高和最低、求平均）
输出最终得分

创建选手类

定义一个选手结构体，包含姓名与分数：

class Person
{
public:
    string name;
    int score;
};

score 最终保存处理后的平均分。

创建选手并放入容器

使用 vector 存储选手对象：

void createPerson(vector<Person>& v)
{
    string nameSeed = "ABCDE";
    for (int i = 0; i < 5; i++)
    {
        Person p;
        p.name = "选手";
        p.name += nameSeed[i];
        p.score = 0;
        v.push_back(p);
    }
}

最终容器中存放五个 Person 对象。

评委打分

使用随机数模拟每名评委对选手的打分。

每个选手的分数由一个 deque 容器存储：

for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
{
    deque<int> d;
    for (int i = 0; i < 5; i++)
    {
        int score = rand() % 41 + 60;  // 60~100 分
        d.push_back(score);
    }
}

使用 deque 的原因：

支持快速头尾插入删除
便于操作分数（例如删除最高分最低分）

对打分结果排序

将选手分数排序，以便去掉最高分和最低分：

sort(d.begin(), d.end());

排序后：

d.front() 是最低分
d.back() 是最高分

去掉最高分和最低分

使用 pop_front 和 pop_back：

d.pop_front();   // 去最低分
d.pop_back();    // 去最高分

此时 deque 中剩余 3 个分数。

求平均分

遍历剩余分数求平均：

int sum = 0;
for (deque<int>::iterator it2 = d.begin(); it2 != d.end(); it2++)
{
    sum += *it2;
}
int avg = sum / d.size();

将平均分存入选手对象：

it->score = avg;

输出最终结果

遍历选手容器：

for (vector<Person>::iterator it = v.begin(); it != v.end(); it++)
{
    cout << "姓名：" << it->name << " 最终得分：" << it->score << endl;
}

输出每位选手名称与平均分。

评委打分案例小结

该案例综合使用：

vector 存储选手对象
deque 存储分数
algorithm 中的 sort 算法
随机数模拟
STL 容器的增删查改

展示了 STL 在实际业务中的应用方式。

员工分组案例

此案例演示了如何将自定义对象分类存储到 multimap 容器中，并实现部门分组。
案例主要使用以下 STL 内容：

vector
multimap
pair
随机数
容器遍历

案例目标：
公司有若干员工，需要根据部门（策划、研发、美术）将员工分组存放，然后打印输出每个分组的成员信息。

定义员工类

定义员工类，包含姓名和工资：

class Worker
{
public:
    string name;
    int salary;
};

工资将随机生成，用于模拟不同员工的薪资水平。

创建员工

通常有五名员工，使用 vector 存储所有员工：

void createWorker(vector<Worker>& v)
{
    string nameSeed = "ABCDEFGHIJ";
    for (int i = 0; i < 10; i++)
    {
        Worker w;
        w.name = "员工";
        w.name += nameSeed[i];
        w.salary = rand() % 10001 + 10000; // 10000~20000
        v.push_back(w);
    }
}

此时 vector 中存放十名员工。

设置部门编号

定义三个部门编号，便于分配员工：

#define DeptPlan 0
#define DeptDevelop 1
#define DeptArt 2

策划部
研发部
美术部

员工分组到 multimap 中

使用 multimap<int, Worker> 将员工按部门编号分类存储：

void setGroup(vector<Worker>& v, multimap<int, Worker>& m)
{
    for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++)
    {
        int deptId = rand() % 3;   // 随机分配到三个部门
        m.insert(make_pair(deptId, *it));
    }
}

multimap 的 key 为部门编号
value 为 Worker 对象

由于 multimap 允许相同 key，因此多个员工可以存入同一个部门。

分部门显示员工信息

遍历 multimap，通过 equal_range 获取某个部门的全部员工：

void showWorkerByGroup(multimap<int, Worker>& m)
{
    cout << "策划部门：" << endl;
    pair<multimap<int, Worker>::iterator, multimap<int, Worker>::iterator> pos
        = m.equal_range(DeptPlan);

    for (multimap<int, Worker>::iterator it = pos.first; it != pos.second; it++)
    {
        cout << "姓名：" << it->second.name << " 工资：" << it->second.salary << endl;
    }

    cout << "研发部门：" << endl;
    pos = m.equal_range(DeptDevelop);

    for (multimap<int, Worker>::iterator it = pos.first; it != pos.second; it++)
    {
        cout << "姓名：" << it->second.name << " 工资：" << it->second.salary << endl;
    }

    cout << "美术部门：" << endl;
    pos = m.equal_range(DeptArt);

    for (multimap<int, Worker>::iterator it = pos.first; it != pos.second; it++)
    {
        cout << "姓名：" << it->second.name << " 工资：" << it->second.salary << endl;
    }
}

每个部门使用 equal_range 自动获取：

key == 部门编号的所有员工区间
然后遍历输出该区间内容

员工分组案例小结

此案例综合使用：

vector 容器创建员工列表
multimap 存储部门与员工映射
make_pair 插入键值对
equal_range 实现多值查找
随机数模拟员工工资和部门分配

通过此案例展示 multimap 一对多映射的典型应用场景。

STL 总结

STL 是 C++ 中最重要的技术之一，主要由三大核心部分组成：

容器
算法
迭代器

容器用于存储数据结构
算法用于处理数据
迭代器负责在两者之间建立联系，使算法不依赖具体容器类型

STL 是泛型编程思想的高度体现，通过模板技术实现了算法和数据结构的高度复用性。

容器回顾

顺序容器：

vector
deque
list
string

容器适配器：

stack
queue
priority_queue

关联式容器：

set
multiset
map
multimap

这些容器各有特性，不同场景下选择不同容器才能获得最佳效率。

vector 适合频繁随机访问和尾部操作
deque 适合头尾高效插入删除
list 适合频繁的任意位置插入删除
set/map 适合需要自动排序的有序集合
multiset/multimap 适合允许重复键的分类结构

算法回顾

遍历类算法：

for_each
transform

查找类算法：

find
find_if
binary_search
count
count_if

排序类算法：

sort
stable_sort
random_shuffle
reverse

拷贝和替换类算法：

copy
replace
replace_if
swap

删除类算法：

remove
remove_if
unique

数值类算法（需 numeric）：

accumulate
inner_product
adjacent_difference
partial_sum

集合类算法：

set_intersection
set_union
set_difference

这些算法通过迭代器操作任何容器，使得算法与容器之间完全解耦。

函数对象与谓词回顾

函数对象（仿函数）是重载了函数调用运算符的类对象，常用于算法中作为策略或条件。

常用仿函数包括：

算术：plus、minus、multiplies
关系：equal_to、greater、less
逻辑：logical_and、logical_or、logical_not

谓词是返回 bool 的函数对象，可用于算法条件判断。

例如：

find_if(v.begin(), v.end(), GreaterFive());

谓词可自定义复杂逻辑，结合算法完成强大的数据处理。

迭代器回顾

迭代器是 STL 的核心：

容器通过 begin 和 end 提供迭代器
算法通过迭代器访问容器数据
迭代器将容器和算法连接起来

不同容器支持不同类型的迭代器：

随机访问迭代器：vector、deque
双向迭代器：list、set、map
前向迭代器、输入迭代器、输出迭代器用于特殊场景

迭代器的统一接口使算法可用于任意容器。

STL 的设计思想回顾

STL 的核心设计理念是：

算法与容器分离
使用迭代器作为中间层
通过模板实现泛型编程

容器专注存储结构
算法专注处理逻辑
迭代器专注访问机制

这种结构使得：

代码复用性极高
逻辑清晰
扩展性强
性能优秀

STL 的优点总结

通用性强
高效
灵活
代码可复用性强
可读性好
可组合性出色

STL 是现代 C++ 开发的基础，使用 STL 能更快速高效地构建复杂程序。