第8.6章: 典型算法

概述

ranges 库提供了大量用于日常任务的算法：查找、计数、变换和删除元素。本章介绍其中最常用的那些。

你将学到：

std::ranges::find 用来查找特定的值。


::fast_io::vector<int> v{3, 1, 4, 1, 5};

auto it = ::std::ranges::find(v, 4);

if (it != v.end()) {
    print("found: ", *it, "\n");
}

如果没有找到该值，返回的迭代器等于 v.end()。

find_if 用一个谓词进行查找：


auto it = ::std::ranges::find_if(v, [](int x) {
    return x % 2 == 0;   // find first even number
});

谓词接收每个元素，命中时返回 true。

count 统计完全相等的元素个数：


auto c = ::std::ranges::count(v, 1);
print("count of 1 = ", c, "\n");

count_if 按条件统计：


auto evens = ::std::ranges::count_if(v, [](int x) {
    return x % 2 == 0;
});

transform 对每个元素应用一个函数，并把结果写到输出 range 中。


::fast_io::vector<int> out(v.size());

::std::ranges::transform(v, out.begin(), [](int x) {
    return x * 2;
});

输入保持不变，输出中包含变换后的值。

remove 和 remove_if 并不真正删除元素。它们把“保留下来”的元素前移，并返回指向新的逻辑末尾的迭代器。


auto new_end = ::std::ranges::remove(v, 1).begin();

要真正删掉元素，需要在容器上调用 erase：


v.erase(new_end, v.end());

这种写法被称为“erase–remove 惯用法”。

很多算法都接受投影。假设我们有：


struct Item {
    int key;
    int value;
};

::fast_io::vector<Item> items{
    {3, 100},
    {1, 200},
    {2, 300}
};

我们可以统计有多少个元素的 key 是偶数：


auto c = ::std::ranges::count_if(items, [](Item const& x) {
    return x.key % 2 == 0;
});

也可以直接使用投影：


auto c = ::std::ranges::count_if(items, [](int k) {
    return k % 2 == 0;
}, &Item::key);

投影 &Item::key 在谓词看到元素之前先取出 key 成员。

本章介绍了最常用的一批算法。C++ 标准库里还有更多算法，完整列表可以在下面这个地址浏览：