C++ 系统第三阶段：STL 容器、迭代器、Lambda 与算法

前言

在掌握对象生命周期、RAII、智能指针、移动语义和异常安全之后，C++ 学习会逐渐从“如何正确管理一个对象”转向“如何管理大量对象”。

第三阶段的核心问题是：

当程序中存在一组数据时，应该使用什么容器保存？如何查找、筛选、统计、排序和删除？容器发生变化后，迭代器、指针和引用是否仍然有效？

这一阶段主要学习以下内容：

  • 序列式容器：vector、list、deque
  • 容器适配器：stack、queue、priority_queue
  • 关联式容器：map、set
  • 哈希容器：unordered_map、unordered_set
  • 迭代器与迭代器失效
  • Lambda 表达式
  • 常用 STL 算法
  • 容器与算法的综合使用
  • LogManager 日志管理项目

本文先系统讲解知识点，最后通过一个单线程内存日志管理器将这些内容串联起来。

一、STL 的整体结构

STL 是 Standard Template Library，即标准模板库。

它主要包含：

容器
迭代器
算法
函数对象
容器适配器

可以简单理解为：

容器：负责保存数据
迭代器：负责访问数据
算法：负责处理数据
Lambda：负责描述处理条件

例如：

std::vector<int> values{3, 1, 2};

std::sort(values.begin(), values.end());

其中：

  • std::vector 保存数据；
  • begin() 和 end() 提供迭代器区间；
  • std::sort 对区间排序。

STL 的一个核心思想是：

算法通常不直接依赖具体容器，而是操作迭代器区间。

二、序列式容器

序列式容器按照元素的位置组织数据。

常见的序列式容器包括：

std::vector
std::list
std::deque

2.1 std::vector

vector 可以理解为能够自动扩容的动态数组。

它的主要特点是：

  • 元素通常存储在连续内存中；
  • 支持随机访问；
  • 尾部插入通常效率较高；
  • 中间插入和删除需要移动后续元素；
  • 容量不足时会重新分配内存；
  • 非常适合遍历和排序。

定义：

std::vector<int> values;

添加：

values.push_back(10);
values.push_back(20);

访问：

std::cout << values[0];
std::cout << values.at(1);

operator[] 不检查越界，at() 会检查越界并在错误时抛出异常。

2.2 size() 与 capacity()

size() 表示当前真实存在的元素数量。

values.size();

capacity() 表示当前已经分配的空间最多可以容纳多少个元素。

values.capacity();

例如：

std::vector<int> values;
values.reserve(10);

此时通常是：

size     = 0
capacity >= 10

因为 reserve() 只预留内存，不会创建元素。

2.3 reserve() 与 resize()

reserve()

values.reserve(10);

只改变容量，不改变元素数量。适合提前知道大概会插入多少元素的场景，可以减少扩容次数。

resize()

values.resize(10);

会让容器中真正存在 10 个元素。

因此：

reserve 改变 capacity
resize 改变 size

2.4 push_back() 与 emplace_back()

push_back() 把一个已经存在的对象复制或移动进容器：

LogItem item;

logs.push_back(item);
logs.push_back(std::move(item));

emplace_back() 使用参数直接在容器尾部构造对象：

logs.emplace_back(/* 构造参数 */);

如果已经有一个完整对象，使用：

logs.push_back(std::move(item));

通常已经足够清晰。

2.5 vector 扩容过程

当：

size == capacity

并继续添加元素时，vector 通常会：

  1. 申请更大的连续内存；
  2. 把原来的元素复制或移动到新内存；
  3. 销毁旧内存中的元素；
  4. 释放旧内存；
  5. 插入新元素。

因为元素地址发生变化，所以扩容后：

原来的所有迭代器失效
原来的所有指针失效
原来的所有引用失效

2.6 vector 删除后的失效规则

假设原数据为：

A B C D

删除 B 后：

A C D

C 和 D 会向前移动。

因此：

删除位置以及删除位置后面的迭代器、指针和引用失效。

删除位置之前的通常仍然有效。

2.7 为什么日志管理适合使用 vector

日志管理通常具有以下操作特点：

  • 经常从尾部添加；
  • 经常遍历所有日志；
  • 经常按条件筛选；
  • 需要排序；
  • 需要与 STL 算法配合。

因此：

std::vector<LogItem> m_logs;

是一个合理的第一版设计。

需要注意，按 ID 查找仍然是 O(n)，这不是 vector 的优势。

选择 vector 的主要原因是：

尾插方便
遍历效率高
连续内存
缓存局部性好
支持 std::sort
适合练习和使用 STL 算法

2.8 std::list

list 是双向链表。

特点：

  • 节点内存通常不连续；
  • 不支持随机访问；
  • 已知位置后插入和删除方便；
  • 插入其他节点时，大部分已有迭代器仍有效；
  • 缓存局部性通常不如 vector；
  • 每个节点还需要额外保存前后指针。

不能简单地认为：

删除多就一定使用 list

因为找到删除位置本身也可能需要线性遍历。

2.9 std::deque

deque 是双端队列。

特点：

  • 头部和尾部插入效率较高；
  • 支持随机访问；
  • 内存通常不是完全连续的；
  • 不提供 reserve() 和 capacity()；
  • 迭代器失效规则比 vector 更复杂。

适合：

  • 双端队列；
  • 滑动窗口；
  • 频繁从头尾插入删除的场景。

三、容器适配器

常见容器适配器包括：

std::stack
std::queue
std::priority_queue

3.1 std::stack

stack 是后进先出：

Last In First Out

常用接口：

push
pop
top
empty
size

3.2 std::queue

queue 是先进先出：

First In First Out

常用接口：

push
pop
front
back
empty
size

3.3 std::priority_queue

priority_queue 会让优先级最高的元素位于顶部。

默认是大顶堆：

std::priority_queue<int> values;

最大的元素优先取出。也可以通过自定义比较器改变优先级规则。

四、关联式容器

关联式容器按照键组织元素，而不是按照位置组织元素。

常见容器包括：

std::map
std::set
std::multimap
std::multiset

4.1 二叉搜索树与平衡树

普通二叉搜索树满足：

左子树的元素小于根节点
右子树的元素大于根节点

如果插入数据本身已经有序，普通二叉搜索树可能退化成链表，查找效率会从接近 O(log n) 退化到 O(n)。

因此，map 和 set 通常基于平衡搜索树实现，例如红黑树。

这一阶段需要理解：

  • 为什么需要控制树高；
  • 为什么平衡树的查找、插入、删除通常是 O(log n)；
  • 为什么不要求立即完整手写红黑树。

4.2 std::map

map 保存键值对：

std::map<std::string, int> scores;

插入：

scores["Tom"] = 90;

查找：

auto it = scores.find("Tom");

特点：

  • 键唯一；
  • 元素按照键有序；
  • 查找、插入、删除通常是 O(log n)；
  • 支持范围查询。

operator[] 的副作用

使用：

scores["Jack"]

如果 "Jack" 不存在，map 会自动插入一个新元素。

纯查询时更适合使用：

find
at
contains

其中 contains 是 C++20 接口。

4.3 std::set

set 只保存键：

std::set<int> values;

特点：

  • 元素唯一；
  • 元素有序；
  • 元素本身就是键；
  • 元素不能被随意修改，否则可能破坏树的顺序。

4.4 multimap 与 multiset

它们允许重复键。

范围查询常用：

lower_bound
upper_bound
equal_range

五、哈希容器

常见哈希容器包括：

std::unordered_map
std::unordered_set

unordered_map 通常使用哈希表实现。

特点：

  • 元素无序；
  • 平均查找、插入、删除接近 O(1)；
  • 最坏情况可能退化到 O(n)；
  • 需要哈希函数；
  • 可能发生哈希冲突。

5.1 哈希冲突

不同的键可能计算出相同的桶位置：

key1 → bucket 3
key2 → bucket 3

这就是哈希冲突。

常见处理方式之一是链地址法。

5.2 负载因子与 rehash

负载因子可以理解为：

元素数量 ÷ 桶数量

负载因子过高时，冲突会增加。

容器可能重新申请更多桶并重新计算元素位置，这个过程称为 rehash。rehash 后，原来的迭代器通常会失效。

5.3 map 与 unordered_map 的选择

需要保持键有序或范围查询时，优先考虑 map。

只关心快速按键查找、不关心顺序时，优先考虑 unordered_map。

数据量较小且主要顺序遍历时，vector 也可能更合适。

容器选择不能只看理论复杂度，还需要考虑：

  • 数据量；
  • 内存占用；
  • 遍历性能；
  • 是否要求有序；
  • 是否要求范围查询；
  • 哈希函数成本；
  • 缓存局部性。

六、迭代器

迭代器是连接容器与算法的桥梁，可以理解为一种类似指针的对象。

auto it = values.begin();

std::cout << *it;
++it;

6.1 begin() 与 end()

begin() 指向第一个元素。

end() 指向最后一个元素后面的尾后位置。

注意：

end() 不是最后一个元素，不能解引用。

6.2 左闭右开区间

STL 算法通常操作：

[first, last)

含义是包含 first，不包含 last。

6.3 begin() 与 cbegin()

cbegin() 明确返回只读迭代器。

只读查询函数可以使用：

m_logs.cbegin()
m_logs.cend()

6.4 迭代器类别

常见迭代器类别包括：

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

vector 提供随机访问迭代器，list 只提供双向迭代器。

不能对 list 迭代器直接执行：

it + 3

需要使用：

std::advance
std::next
std::prev

6.5 范围 for

推荐：

for (const auto& item : result)
{
    std::cout << item.id;
}

使用 const auto& 可以避免复制元素，并保证只读。

七、Lambda 表达式

Lambda 是匿名函数。

基本形式：

[capture](parameters)
{
    body
}

例如：

[id](const LogItem& item)
{
    return item.id == id;
}

7.1 捕获方式

[]          // 不捕获
[value]     // 值捕获
[&value]    // 引用捕获
[=]         // 默认值捕获
[&]         // 默认引用捕获
[this]      // 捕获当前对象

7.2 值捕获与引用捕获

值捕获保存一份副本；引用捕获操作原变量。

引用捕获必须特别注意生命周期，避免 Lambda 中保存悬空引用。

7.3 mutable

值捕获变量默认不能在 Lambda 内修改。

[value]() mutable
{
    ++value;
}

这里只修改 Lambda 内部保存的副本。

7.4 泛型 Lambda

C++14 支持：

[](const auto& left, const auto& right)
{
    return left < right;
}

八、常用 STL 算法

STL 算法通常定义在：

#include <algorithm>

8.1 find_if

auto it = std::find_if(
    logs.cbegin(),
    logs.cend(),
    [id](const LogItem& item)
    {
        return item.id == id;
    }
);

找到时返回指向第一个匹配元素的迭代器；没找到时返回结束迭代器。

8.2 count_if

return std::count_if(
    logs.cbegin(),
    logs.cend(),
    [level](const LogItem& item)
    {
        return item.level == level;
    }
);

只返回数量，不复制日志。

8.3 any_of

return std::any_of(
    logs.cbegin(),
    logs.cend(),
    [](const LogItem& item)
    {
        return item.level == LogLevel::Error;
    }
);

找到第一条匹配日志后即可停止。

8.4 copy_if

std::copy_if(
    m_logs.cbegin(),
    m_logs.cend(),
    std::back_inserter(result),
    [level](const LogItem& item)
    {
        return item.level == level;
    }
);

为什么需要 back_inserter

reserve() 只增加容量，不增加元素数量。

空 vector 中没有已经构造好的元素可供覆盖，所以需要 back_inserter 通过 push_back() 追加结果。

8.5 sort

std::sort(
    logs.begin(),
    logs.end(),
    [](const LogItem& left, const LogItem& right)
    {
        return left.timestamp < right.timestamp;
    }
);

为什么不能使用 <=

比较器必须满足严格弱序，一个元素不能被判断为小于自己。

因此相等时必须返回 false，应该使用 <，不能使用 <=。

8.6 remove_if

remove_if 只会把保留元素移动到前面，并返回新的逻辑末尾，不会缩小容器。

auto newEnd = std::remove_if(
    values.begin(),
    values.end(),
    condition
);

values.erase(newEnd, values.end());

这称为 erase-remove 惯用法。

8.7 其他常用算法

std::all_of
std::none_of
std::for_each
std::transform
std::unique
std::min_element
std::max_element
std::accumulate

其中 accumulate 定义在：

#include <numeric>

九、LogManager 综合项目

LogManager 是一个单线程、内存中的日志管理器。

它负责：

添加日志
按 ID 查找
按 ID 删除
按级别筛选
按级别统计
判断是否存在错误
按时间排序
按级别和时间排序
删除空日志

第一版暂时不处理：

  • 多线程；
  • 自动写文件；
  • 日志滚动；
  • 网络上传；
  • 数据库；
  • 单例模式。

9.1 日志数据

enum class LogLevel
{
    Debug,
    Info,
    Warning,
    Error
};

struct LogItem
{
    int id = 0;
    LogLevel level = LogLevel::Info;
    std::string message;
    std::int64_t timestamp = 0;
};

9.2 类不变量

LogManager 需要保证：

所有日志 id 必须大于 0
所有日志 id 必须唯一
timestamp 不能小于 0
message 暂时允许为空
timestamp 允许重复
m_logs 不保证始终有序
所有修改必须通过公开接口完成
操作失败时原有状态保持不变

9.3 为什么 m_logs 必须为 private

private:
    std::vector<LogItem> m_logs;

这样可以防止外部绕过 AddItem() 的检查，直接插入非法数据。

十、核心功能实现

10.1 按 ID 查找

const LogItem* LogManager::FindById(int id) const
{
    auto it = std::find_if(
        m_logs.cbegin(),
        m_logs.cend(),
        [id](const LogItem& item)
        {
            return item.id == id;
        }
    );

    if (it == m_logs.cend())
    {
        return nullptr;
    }

    return &(*it);
}

返回的是 vector 内部元素地址。扩容、删除和排序后，该指针可能失效，因此不应长期保存。

10.2 添加日志

bool LogManager::AddItem(LogItem item)
{
    if (item.id <= 0 || item.timestamp < 0)
    {
        return false;
    }

    if (FindById(item.id) != nullptr)
    {
        return false;
    }

    m_logs.push_back(std::move(item));
    return true;
}

所有检查都在修改容器之前完成，失败时不会改变原状态。

10.3 查询数量和空状态

std::size_t LogManager::ItemSize() const noexcept
{
    return m_logs.size();
}

bool LogManager::IsEmpty() const noexcept
{
    return m_logs.empty();
}

10.4 按 ID 删除

bool LogManager::EraseItem(int id)
{
    auto it = std::find_if(
        m_logs.cbegin(),
        m_logs.cend(),
        [id](const LogItem& item)
        {
            return item.id == id;
        }
    );

    if (it == m_logs.cend())
    {
        return false;
    }

    m_logs.erase(it);
    return true;
}

10.5 按级别筛选

std::vector<LogItem>
LogManager::FindByLevel(LogLevel level) const
{
    std::vector<LogItem> result;

    result.reserve(m_logs.size());

    std::copy_if(
        m_logs.cbegin(),
        m_logs.cend(),
        std::back_inserter(result),
        [level](const LogItem& item)
        {
            return item.level == level;
        }
    );

    return result;
}

10.6 按级别统计

std::size_t
LogManager::CountByLevel(LogLevel level) const
{
    return std::count_if(
        m_logs.cbegin(),
        m_logs.cend(),
        [level](const LogItem& item)
        {
            return item.level == level;
        }
    );
}

不应通过 FindByLevel(level).size() 统计，否则会产生不必要的对象复制。

十一、剩余核心功能

11.1 判断是否存在错误日志

bool LogManager::HasError() const
{
    return std::any_of(
        m_logs.cbegin(),
        m_logs.cend(),
        [](const LogItem& item)
        {
            return item.level == LogLevel::Error;
        }
    );
}

11.2 按时间排序

void LogManager::SortByTime()
{
    std::sort(
        m_logs.begin(),
        m_logs.end(),
        [](const LogItem& left, const LogItem& right)
        {
            return left.timestamp < right.timestamp;
        }
    );
}

11.3 按级别和时间排序

int LogManager::GetLevelPriority(LogLevel level) noexcept
{
    switch (level)
    {
    case LogLevel::Error:
        return 4;

    case LogLevel::Warning:
        return 3;

    case LogLevel::Info:
        return 2;

    case LogLevel::Debug:
        return 1;
    }

    return 0;
}

void LogManager::SortByLevelAndTime()
{
    std::sort(
        m_logs.begin(),
        m_logs.end(),
        [](const LogItem& left, const LogItem& right)
        {
            const int leftPriority =
                GetLevelPriority(left.level);

            const int rightPriority =
                GetLevelPriority(right.level);

            if (leftPriority != rightPriority)
            {
                return leftPriority > rightPriority;
            }

            return left.timestamp < right.timestamp;
        }
    );
}

11.4 删除空消息

std::size_t LogManager::RemoveEmptyMessages()
{
    const std::size_t oldSize = m_logs.size();

    auto newEnd = std::remove_if(
        m_logs.begin(),
        m_logs.end(),
        [](const LogItem& item)
        {
            return item.message.empty();
        }
    );

    m_logs.erase(newEnd, m_logs.end());

    return oldSize - m_logs.size();
}

十二、推荐的完整接口

class LogManager
{
public:
    const LogItem* FindById(int id) const;

    bool AddItem(LogItem item);

    bool EraseItem(int id);

    std::size_t ItemSize() const noexcept;

    bool IsEmpty() const noexcept;

    std::vector<LogItem>
        FindByLevel(LogLevel level) const;

    std::size_t
        CountByLevel(LogLevel level) const;

    bool HasError() const;

    void SortByTime();

    void SortByLevelAndTime();

    std::size_t RemoveEmptyMessages();

private:
    static int
        GetLevelPriority(LogLevel level) noexcept;

private:
    std::vector<LogItem> m_logs;
};

十三、测试要求

测试数据应覆盖：

多个不同 ID
多个不同日志级别
不同时间戳
重复 ID
非法 ID
负时间戳
空 message

推荐测试：

  1. 初始状态为空；
  2. 合法日志添加成功；
  3. 重复 ID 添加失败；
  4. 非法 ID 添加失败；
  5. 负时间戳添加失败；
  6. 查询存在和不存在的 ID；
  7. 删除存在和不存在的 ID；
  8. 按级别筛选；
  9. 按级别统计；
  10. 判断是否存在错误日志；
  11. 按时间排序；
  12. 按级别和时间排序；
  13. 删除空消息；
  14. 失败操作不会改变日志数量。

十四、第三阶段必须掌握的问题

为什么使用 vector 保存日志

因为日志主要进行尾部添加、顺序遍历、筛选和排序，vector 连续内存、遍历效率高，并支持 std::sort。

find_if 返回什么

返回指向第一个满足条件元素的迭代器；没有找到时返回结束迭代器。

为什么找不到时等于 end()

因为算法操作 [first, last) 区间，遍历到尾后位置仍未找到时，就返回 last。

为什么 FindById 返回的指针可能失效

因为它指向 vector 内部元素，扩容、删除和排序都可能改变元素地址或位置。

为什么 copy_if 配合 back_inserter

因为结果容器一开始没有元素，back_inserter 会通过 push_back() 把匹配结果追加到容器尾部。

为什么 reserve() 不改变 size()

因为 reserve() 只申请容量，不构造元素。size() 表示真实存在的元素数量。

为什么 remove_if 不能真正删除元素

因为算法只整理迭代器区间，不改变容器大小。它返回新的逻辑末尾，真正删除还需要调用 erase()。

为什么排序比较器不能使用 <=

因为比较器必须满足严格弱序，相等元素比较时必须返回 false。

Lambda 值捕获与引用捕获有什么区别

值捕获保存副本，引用捕获操作原变量。引用捕获必须注意生命周期。

vector 删除和扩容后哪些迭代器失效

扩容后所有迭代器、指针和引用失效；删除后，删除位置及其后面的迭代器、指针和引用失效。

十五、阶段总结

第三阶段的重点不是背诵接口，而是形成解决数据管理问题的方法：

分析数据特征
    ↓
选择合适容器
    ↓
使用迭代器描述区间
    ↓
使用 Lambda 描述条件
    ↓
使用 STL 算法处理数据
    ↓
理解容器修改后的失效规则

LogManager 将第三阶段知识串联起来：

功能使用的知识
保存日志vector
添加日志push_back、移动语义
按 ID 查找find_if
删除指定日志find_if、erase
按级别筛选copy_if、back_inserter
按级别统计count_if
判断错误日志any_of
按时间排序sort
多条件排序比较器、严格弱序
删除空消息remove_if + erase
保护内部数据private、类不变量
只读查询const 正确性

完成这一阶段后，可以进入第四阶段：

继承
多态
虚函数
虚析构
抽象接口
对象切片
虚函数表
RTTI

届时可以继续改造日志项目，将输出部分抽象为：

ILogSink
ConsoleLogSink
FileLogSink
MemoryLogSink

让 LogManager 只负责管理日志，不同输出组件负责将日志写入不同目标。

# c++ # 算法 # 开发语言
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

基于STM32的全屋环境智能监测与预警终端设计

avatar 亚马逊云科技技术品牌专区

Keras：面向人类的深度学习库

Keras3支持多后端（TensorFlow、PyTorch、JAX），通过设置环境变量切换，兼容指定版本。pip安装后可用Sequential API快速构建CNN模型，如MNIST分类示例，实

avatar 亚马逊云科技技术品牌专区

AI行业日报｜2026-09-25：5个热点事件

本期行业动态聚焦于端侧算力重构、自主智能体工作流、开发工具经济模型、网络隔离架构设计与公共部门合规审查。以下结合一线技术场景进行结构化梳理，供 AI 研究员与软件工程团队参考。 PrismML 正将其轻量级语言模型适配至搭载高通处理器的智能眼镜终端 1 。该平台的核心战略指向开源权重模型的本地化运行，旨在最大化挖掘穿戴设备现有算力的利用效率 1 。对于嵌入式与边缘计算开发者而言，此类微型模型向低功

avatar 亚马逊云科技技术品牌专区