数据结构 03：用 STL 完成查找、去重与安全修改

拿到 [7,-1,3,7,2,-5]，先过滤无效读数，再统计、去重、查询：这比依次背诵 vector、set、map 的成员函数更接近真实工作。这篇把同一批数据串成流水线，每一步都说明容器里实际还剩什么，以及迭代器能否继续使用。

专题目录 · 前置：存储布局与结构选择 · 后续：查找与排序

1. 容器、迭代器、算法如何分工

容器拥有元素，迭代器描述位置，算法处理迭代器定义的范围。对于 [first,last)，first 指向第一项，last 指向不包含在范围内的终点；begin()==end() 就是空范围。end() 可以比较，但不能解引用。

[7] [-1] [3] [7] [2] [-5] | 尾后位置
 ↑ begin()                 ↑ end()
算法处理左闭右开范围 [begin(), end())

迭代器不一定是裸指针，不同迭代器支持的操作也不同。因此，“任何算法都能用于任何容器”是错误的。

std::sort 不能拿 list 的迭代器直接排序，set 的键也不能通过迭代器就地改写。标准库的容器种类不止旧资料中的“七种”；C++17 已有 array、forward_list、无序关联容器等。先学操作要求，比死记一个历史数量有用。

2. 过滤：remove 为什么没有真的缩短容器

约定读数小于 0 无效，0 是有效读数。原数据为 [7,-1,3,7,2,-5]，目标得到 [7,3,7,2]。

remove_if 只有两个迭代器，不拥有容器，因此不能更改容器的 size。它把保留项按原有相对顺序移动到前面，返回有效前缀的新终点。后面的对象仍存在，但值处于有效而未指定的状态，不能把图中尾部的 ? 当成必然保留的原值。

std::vector<int> readings{7, -1, 3, 7, 2, -5};
auto new_end = std::remove_if(readings.begin(), readings.end(),
                              [](int x) { return x < 0; });
// size 仍是 6；[begin,new_end) 的内容是 7,3,7,2
readings.erase(new_end, readings.end());
// size 变成 4；内容是 7,3,7,2

这就是 C++17 的 erase-remove 写法；时间为 O(n)。逐项 vector.erase 每次都可能移动后缀，批量删除时最坏达到 O(n²)。标准草案：remove 算法

操作不变量： 扫描过的输入中，所有应该保留的项都在输出前缀里，顺序不变。自己手写过滤算法时，这就是读指针、写指针为什么能只向前移动的依据。

空数组或全负数在过滤后为空；[0,-1,0] 过滤后保留两个 0。完整源码对这些边界都有断言。

3. 去重：排序去重与保序去重不是同一需求

允许重排：sort → unique → erase

对 [7,3,7,2] 排序得到 [2,3,7,7]，相同值相邻后，unique 才能把每一组相邻重复压缩为一项。

std::sort(readings.begin(), readings.end());
auto unique_end = std::unique(readings.begin(), readings.end());
readings.erase(unique_end, readings.end());
// 2,3,7

unique 不会搜索整个序列中所有重复项，且本身不改变 size。例如 [7,3,7] 的相邻元素均不相同，直接 unique 仍保留三个元素。排序后去重的总复杂度为 O(n log n)，这也改变了顺序。标准草案：unique

必须保留第一次出现的顺序

保序去重的目标是 [7,3,2]。让 unordered_set 负责“以前见过吗”，让 vector 负责结果顺序：

std::unordered_set<int> seen;
std::vector<int> ordered;
for (int x : readings_before_sort) {
    if (seen.insert(x).second) ordered.push_back(x);
}

insert 的 second 表示这次是否真的插入了新键。平均总时间 O(n)，额外空间 O(n)，哈希冲突严重时最坏可能 O(n²)。输出顺序来自遍历原数组和追加结果，不能从哈希表的遍历顺序推断。

如果每个读数带有时间戳，“相同”的定义也要先说清：是数值相同、时间戳相同，还是整条记录相同？排序比较器与 unique 的等价判断必须服务于同一个去重目标。

4. 查找：有序前提不能省略

无序数据使用线性查找；排序后可以二分查找，但先排序的成本仍要计算。

auto found = std::find(raw.begin(), raw.end(), 7);
if (found != raw.end()) {
    // 可以解引用 *found
}

// readings 已按升序排列
int target = 3;
auto position = std::lower_bound(readings.begin(), readings.end(), target);
bool exists = position != readings.end() && *position == target;

lower_bound 找第一个不小于目标的位置，可能是 end()；它不是“找到相等值才返回”的接口。对 vector 的二分查找比较次数和位置移动均为 O(log n)。对只有前向/双向迭代器的范围，比较次数可以仍是对数，但迭代器移动可能线性。因此查 map/set 应优先用成员 lower_bound，以使用其树索引。

小实验： 对 [2,3,7] 查 1,3,5,9，返回位置依次为下标 0,1,2,3；其中只有 3 确实存在。完整算法推导见查找与排序笔记。

5. 计数与字典：一次读取为什么增加了元素

如果想统计每个值出现几次，要在去重之前统计；否则重复次数已经丢失。

std::map<int, int> frequency;
for (int x : std::vector<int>{7, 3, 7, 2}) ++frequency[x];
// 按键遍历：2→1，3→1，7→2

这里使用 operator[] 很合适：不存在的键会先插入一个值初始化的 int，即 0，然后自增。可是读取配置时同样的写法可能是错误的：

std::map<std::string, int> limits{{"imu", 100}};
auto before = limits.size();
auto it = limits.find("camera"); // 未找到时是 end()，size 不变
if (it != limits.end()) {
    int configured = it->second;
}
// limits["camera"] 会新增 camera→0，不能当作无副作用的读取。
// limits.at("camera") 则在不存在时抛出 out_of_range。

要明确覆盖可用 insert_or_assign；希望仅在键不存在时插入可用 try_emplace。两者均在 C++17 中可用。标准草案：map 元素访问

set 的相等不一定是对象所有字段相等

如果 set<Person> 只比较年龄，那么两个姓名不同但年龄相同的人会被视为等价键，只保留一个。比较器必须满足严格弱序，不能写成 <=。也不强制必须重载 operator<，可以传入独立比较器。

struct Person { std::string name; int age; };
struct PersonLess {
    bool operator()(const Person& a, const Person& b) const {
        return std::tie(a.age, a.name) < std::tie(b.age, b.name);
    }
};
std::set<Person, PersonLess> people;

这里按年龄再按姓名排序，只有这两个字段都等价才去重；若业务身份是 ID，就应按 ID 定义唯一性，而不是碰巧使用某个展示字段。

6. 修改：删除后接住新的迭代器

按迭代器删除之后，不能继续对原来的失效迭代器执行 ++it。使用返回的下一个位置：

for (auto it = frequency.begin(); it != frequency.end(); ) {
    if (it->second < 2) {
        it = frequency.erase(it);
    } else {
        ++it;
    }
}
// 剩下 7→2

对 map、set、list，删除只使被删元素的迭代器和引用失效。对 vector，删除点及其后的迭代器、引用都会失效；即使容器没有重新分配，也不能继续拿旧位置当作原元素。

表并非所有容器操作的完整规则，尤其不能从 list 推断 deque。标准的具体失效边界见 vector 修改规则与无序容器规则。

rehash 后重新查找，而不是继续使用旧迭代器

std::unordered_map<int, std::string> names{{1, "imu"}};
auto old_position = names.find(1);
std::string& saved_value = old_position->second;
names.rehash(names.bucket_count() * 2 + 1);
// 此处不得解引用 old_position；saved_value 仍引用同一存活元素。
auto new_position = names.find(1);

插入、reserve、rehash 都需要结合是否重建桶来判断。reserve 有助于预估容量，但不是对所有后续修改的一次性安全承诺。

7. 两类任务：范围输出与按优先级处理

有序 map 做范围查询

std::map<int, std::string> events{
    {10, "start"}, {20, "sample"}, {25, "warning"}, {40, "stop"}
};
for (auto it = events.lower_bound(15);
     it != events.end() && it->first < 30; ++it) {
    // 依次处理 20、25，对应左闭右开的区间 [15,30)
}

找起点 O(log n)，输出 k 个结果再花 O(k)。如果同一时间点允许多条记录，可以用 multimap，或把映射值改为一组记录；数据模型要先决定。

priority_queue 做当前最优任务

std::priority_queue<int> priorities;
for (int p : {3, 9, 1}) priorities.push(p);
while (!priorities.empty()) {
    int p = priorities.top();
    priorities.pop();
    // 依次取出 9、3、1
}

堆顶有保证，其余位置并未完全排序；同优先级任务也不保证先进先出。如果需要稳定次序，把序号作为第二排序条件。普通 FIFO 任务队列用 queue 即可，回溯或撤销历史则使用 stack。

8. 配套 C++17 示例与输出

下载 stl_operations.cpp。它不是孤立 API 拼盘：包括过滤与去重、保留首次出现顺序、词频删除、范围查询、比较器身份、rehash 后的引用检查。对应统一编译命令见专题学习路线。

源码中的输入与结果如下：

容器选择也取决于数据语义：按数值去重与“每个传感器只保留最新读数”是不同需求。后者还需要传感器 ID 和时间戳，不能直接复用仅按读数排序去重的代码。