C / C++ / 系统课时

用算法完成筛选统计和去重

用算法完成筛选统计和去重

商品数据进入内存后,常见任务不是手写循环,而是把“查找、统计、过滤、排序、去重”拆给 STL 算法。本文用一组商品记录串起 find_if、count_if、remove_if、sort 和 unique,并说明每一步对容器真正做了什么。

学习目标

  • 用谓词组合 find_if 与 count_if 完成条件查找和统计
  • 正确使用 erase-remove 与 sort-unique 完成删除和按键去重
  • 判断算法执行顺序,以及迭代器区间变化对后续操作的影响

把需求拆成算法

假设内存中保存若干商品,需要完成四件事:找到第一个高价商品、统计仍可销售且有库存的记录、删除停用或零库存商品,再按商品 ID 去重。这里每个动作都能对应一个标准算法,而不必把所有条件塞进一个长循环。

find_if 返回第一个满足谓词的迭代器;count_if 返回满足谓词的元素数量。它们都只读取区间,不改变元素顺序。remove_if 和 unique 则不同:它们只把“应该保留”的元素移动到区间前部,并返回新的逻辑末尾,容器的物理大小并不会自动缩小。

用一条处理链完成整理

下面的程序使用 C++17。排序时除了商品 ID,还用名称作为次级条件,这样重复 ID 的保留结果是确定的;随后 unique 只比较 ID,因此每个 ID 最终只保留一条。

cpp
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Product {
    int id;
    std::string name;
    int price;
    int stock;
    bool active;
};

int main() {
    std::vector<Product> products{
        {1003, "Keyboard", 259, 12, true},
        {1001, "Mouse", 129, 0, true},
        {1002, "SSD", 499, 5, true},
        {1004, "Old Cable", 19, 30, false},
        {1002, "SSD Copy", 499, 5, true}
    };

    auto expensive = std::find_if(
        products.begin(), products.end(),
        [](const Product& p) { return p.price >= 400; }
    );

    if (expensive != products.end()) {
        std::cout << "first expensive: "
                  << expensive->id << ' ' << expensive->name << '\n';
    }

    auto sellableCount = std::count_if(
        products.begin(), products.end(),
        [](const Product& p) { return p.active && p.stock > 0; }
    );
    std::cout << "sellable count: " << sellableCount << '\n';

    // remove_if 只返回新的逻辑末尾,必须配合 erase 才真正缩短 vector。
    products.erase(
        std::remove_if(
            products.begin(), products.end(),
            [](const Product& p) { return !p.active || p.stock == 0; }
        ),
        products.end()
    );

    std::sort(
        products.begin(), products.end(),
        [](const Product& a, const Product& b) {
            if (a.id != b.id) {
                return a.id < b.id;
            }
            return a.name < b.name;
        }
    );

    // unique 只能合并相邻重复项,因此必须先按去重键排序。
    products.erase(
        std::unique(
            products.begin(), products.end(),
            [](const Product& a, const Product& b) {
                return a.id == b.id;
            }
        ),
        products.end()
    );

    for (const auto& p : products) {
        std::cout << p.id << ' ' << p.name << '\n';
    }
}

预期输出

text
first expensive: 1002 SSD
sellable count: 3
1002 SSD
1003 Keyboard

实际商品数据可以变化,但在这组固定输入下输出应与上面一致。

为什么顺序不能随便换

remove_if 应先清掉停用和零库存记录,否则这些无效项也会参与后续排序和去重。unique 前必须先让相同 ID 相邻,因此通常先 sort 再 unique。如果直接在未排序的序列上调用 unique,它只能去掉连续重复项,散落在其他位置的重复 ID 仍会保留。

复杂度与边界

对含 nn 个商品的 vector,find_if、count_if、remove_if 和 unique 都是线性扫描,时间复杂度为 O(n)O(n);sort 通常为 O(nlog⁡n)O(n \log n),因此整条处理链主要由排序决定。

若“重复”的业务含义不是商品 ID 相同,而是 SKU、名称加规格等组合键相同,应把排序键和 unique 的等价条件一起调整。两者必须描述同一个去重规则,否则相同业务键可能没有排到一起,或者错误地合并本来不同的商品。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用算法完成筛选统计和去重

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通