Chapter25 其他工具函数和算法

Chapter25 其他工具函数和算法

C++17提供了很多新的工具函数和算法，将在这一章中讲述。

25.1 `size()`、`empty()`、`data()`

为了让泛型代码更加灵活，C++标准库提供了三个新的辅助函数：size()、empty()、data()。

这三个辅助函数和另外几个用来迭代范围或集合的泛型全局辅助函数：std::begin()、 std::end()、std::advance()一样，都定义在头文件<iterator>中。

25.1.1 泛型`size()`函数

泛型size()函数允许我们查询任何范围的大小，前提是它有迭代器接口或者它是原生数组。通过使用这个函数你可以写出类似于下面的代码：

#ifndef LAST5_HPP
#define LAST5_HPP
#include <iterator>
#include <iostream>
template<typename T>
void printLast5(const T& coll)
{
    // 计算大小：
    auto size{std::size(coll)};
    // 把迭代器递增到倒数第五个元素处
    std::cout << size << " elems: ";
    auto pos{std::begin(coll)};
    if (size > 5) {
        std::advance(pos, size - 5);
        std::cout << "... ";
    }
    // 打印出剩余的元素：
    for (; pos != std::end(coll); ++pos) {
        std::cout << *pos << ' ';
    }
    std::cout << '\n';
}
#endif  // LAST5_HPP

这里通过

auto size{std::size(coll)};

我们用传入的集合的大小初始化了size，std::size()调用可能会映射到 coll.size()，如果参数是原生数组的话会映射到其长度。因此，如果我们调用：

std::array arr{27, 3, 5, 8, 7, 12, 22, 0, 55};
std::vector v{0.0, 8.8, 15.15};
std::initializer_list<std::string> il{"just", "five", "small", "string", "literals"};
printLast5(arr);
printLast5(v);
printLast5(il);

输出将是：

9 elems: ... 7 12 22 0 55
3 elems: 0 8.8 15.15
5 elems: just five small string literals

另外因为std::size()还支持原生C数组，所以我们也可以调用：

printLast5("hello world");

这会打印出：

12 elems: ... o r l d

注意这个函数模板计算数组大小时不是使用通常的方法，而是使用countof或者如下定义的ARRAYSIZE:

#define ARRAYSIZE(a) (sizeof(a)/sizeof(*(a)))

注意你不能向printLast5<>()传递隐式的初值列。这是因为模板参数不能推导为std::initializer_ list()。因此，如果你想传递隐式的初值列，那么你必须像下面这样重载printLast5()：

template<typename T>
void printLast5(const std::initializer_list<T>& coll)

最后，注意这段代码不能用于forward_list<>，因为单向链表没有成员函数size()。因此，如果你只是想检查集合是否为空的话，更推荐使用std::empty()，下面即将讨论它。

25.1.2 泛型`empty()`函数

类似于新的全局size()，新的泛型std::empty()可以帮助我们检查是否一个容器、一个原生C数组或者一个std::initializer_list<>为空。

一个类似于上面的例子是，你可以检查一个传入的集合是否为空：

if (std::empty(coll)) {
    return;
}

相比于std::size()，std::empty()还支持单向链表。

注意，根据语言规则原生C数组的大小不能为0。因此，std::empty()对C数组总是返回false。

25.1.3 泛型`data()`函数

最后，新的泛型std::data()函数允许我们访问集合（有data()成员的容器、原生C数组、 std::initializer_list<>都可以）的原始数据。例如，下面的代码会打印出集合内索引为偶数的元素：

#ifndef DATA_HPP
#define DATA_HPP
#include <iterator>
#include <iostream>
template<typename T>
void printData(const T& coll)
{
    // 打印出索引为偶数的元素：
    for (std::size_t idx{0}; idx < std::size(coll); ++idx) {
        if (idx % 2 == 0) {
            std::cout << std::data(coll)[idx] < ' ';
        }
    }
    std::cout << '\n';
}
#endif // DATA_HPP

因此，如果我们调用：

std::array arr{27, 3, 5, 8, 7, 12, 22, 0, 55};
std::vector v{0.0, 8.8, 15.15};
std::initializer_list<std::string> il{"just", "five", "small", "string", "literals"};
printData(arr);
printData(v);
printData(il);
printData("hello world");

输出将是：

27 5 7 22 55
0 15.15
just small literals
h l o w r d

25.2 `as_const()`

新的辅助函数std::as_const()可以在不使用static_cast<>或者add_const_t<>类型特征的情况下把值转换为相应的const类型。

这允许我们用非常量对象强制调用常量版本的重载函数：

std::vector<std::string> coll;
foo(coll);                  // 非常量版本的重载优先级更高
foo(std::as_const(coll));   // 强制调用常量版本的重载

如果foo()是一个函数模板，这将强制模板参数被实例化为常量类型，而不是原本的非常量类型。

25.2.1 以常量引用捕获

as_const()的一个应用就是以常量引用方式捕获lambda的参数。例如：

std::vector<int> coll{8, 15, 7, 42};
auto printColl = [&coll = std::as_const(coll)] {
                     std::cout << "coll: ";
                     for (int elem : coll) {
                         std::cout << elem << ' ';
                     }
                     std::cout << '\n';
                 };

现在，调用

printColl();

将会打印出coll当前的状态，并且没有意外修改coll的值的危险。

25.3 `clamp()`

C++17提供了一个新的工具函数clamp()，它可以找出三个值中大小居中的那个。它其实是min()和max() 的组合。例如：

#include <iostream>
#include <algorithm>    // for clamp()
int main()
{
    for (int i : {-7, 0, 8, 15}) {
        std::cout << std::clamp(i, 5, 13) << '\n';
    }
}

这里的clamp(i, 5, 13)等价于std::min(std::max(i, 5), 13)，其输出如下：

类似于min()和max()，clamp()的所有参数也都是同一个类型T的const的引用：

namespace std {
    template<typename T>
    constexpr const T& clamp(const T& value, const T& min, const T& max);
}

返回值也是const引用，并且是输入参数之一。

如果你传递了不同类型的参数，你可以显式指明模板参数T：

double d{4.3};
int max{13};
...
std::clamp(d, 0, max);          // 编译期 ERROR
std::clamp<double>(d, 0, max);  // OK

你也可以传递浮点数，只要它们的值不是NaN。

就像min()和max()一样，你也可以传递一个谓词函数来进行比较操作。例如：

for (int i : {-7, 0, 8, 15}) {
    std::cout << std::clamp(i, 5, 13, [] (auto a, auto b) {
                                          return std::abs(a) < std::abs(b);
                                      })
              << '\n';
}

将会有如下输出：

因为-7的绝对值介于5和13的绝对值之间，所以clamp()第一次调用会返回-7。

clamp()没有接受初值列参数的重载版本（min()和max()有）。

25.4 `sample()`

C++17提供了sample()算法来从一个给定的范围（总体）内提取出一个随机的子集（样本）。有时这也被称为 水塘抽样 或者 选择抽样 。

考虑下面的示例程序：

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>    // for sample()
#include <random>       // for default_random_engine
int main()
{
    // 初始化一个有10,000个字符串的vector：
    std::vector<std::string> coll;
    for (int i = 0; i < 10000; ++i) {
        coll.push_back("value" + std::to_string(i));
    }
    // 打印10个从集合中随机抽取的元素：
    std::sample(coll.begin(), coll.end(),
                std::ostream_iterator<std::string>{std::cout, "\n"},
                10,
                std::default_random_engine{});
}

我们首先初始化了一个有足够多字符串（value0, value1, ...）的vector，之后我们使用了sample()来提取出这些字符串的一个随机的子集：

// 打印10个从集合中随机抽取的元素：
std::sample(coll.begin(), coll.end(),
            std::ostream_iterator<std::string>{std::cout, "\n"},
            10,
            std::default_random_engine{});

我们传递了以下参数：

总体范围的起点和终点
一个用来写入提取出的值的迭代器（这里使用了输出迭代器把提取出的字符串写入到标准输出）
要提取的元素数量的上限（如果总体范围小于指定数量则无法达到上限）
用来计算随机子集的随机数引擎

最后的结果是我们打印出了coll内的10个随机元素。输出的一个可能的示例是：

value132
value349
value796
value2902
value3267
value3553
value4226
value4820
value5509
value8931

如你所见，元素的顺序是稳定的（前后顺序和在coll里时一样）。然而，只有当传递的范围的迭代器至少是前向迭代器时才保证这一点。

该算法的声明如下：

namespace std {
    template<typename InputIterator, typename OutputIterator,
             typename Distance, typename UniformRandomBitGenerator>
    OutputIterator sample(InputIterator sourceBeg, InputIterator sourceEnd,
                          OutputIterator destBeg,
                          Distance num,
                          UniformRandomBitGenerator&& eng);
}

它有以下保证和约束：

源范围迭代器至少是输入迭代器，目标迭代器至少是输出迭代器。如果源迭代器连前向迭代器都不是，那么目标迭代器必须是随机访问迭代器。
像通常一样，如果目标区间大小不够又没有使用插入迭代器，那么写入目标迭代器可能会导致未定义行为。
算法返回最后一个被拷贝的元素的下一个位置。
目标迭代器指向的位置不能在源区间中。
num 可能是整数类型。如果源区间里的元素数量不足，将会提取出源区间里所有的元素。
只要源区间的迭代器不只是输入迭代器，那么被提取出的子集中元素的顺序将保持稳定。

这里还有一个演示sample()用法的例子：

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>    // for sample()
#include <random>       // for 随机数设备和随机数引擎
int main()
{
    // 初始化一个有10,000个string的vector：
    std::vector<std::string> coll;
    for (int i = 0; i < 10000; ++i) {
        coll.push_back("value" + std::to_string(i));
    }
    // 用一个随机数种子初始化一个Mersenne Twister引擎：
    std::random_device rd;      // 随机数种子（如果支持的话）
    std::mt19937 eng{rd()};     // Mersenne Twister引擎
    // 初始化目标区间（至少要能存放10个元素）：
    std::vector<std::string> subset;
    subset.resize(100);
    // 从源区间随机拷贝10个元素到目的区间：
    auto end = std::sample(coll.begin(), coll.end(),
                           subset.begin(),
                           10,
                           eng);
    // 打印被提取出的元素（使用返回值作为终点）：
    std::for_each(subset.begin(), end,
                  [] (const auto& s) {
                      std::cout << "random elem: " << s << '\n';
                  });
}

我们首先初始化了一个有足够多字符串（value0, value1, ...）的vector，然后用一个随机数种子初始化了一个随机数引擎:

// 用一个随机数种子初始化一个Mersenne Twister引擎：
std::random_device rd;      // 随机数种子（如果支持的话）
std::mt19937 eng{rd()};     // Mersenne Twister引擎

和一个目的区间：

// 初始化目标区间（至少要能存放10个元素）：
std::vector<std::string> subset;
subset.resize(100);

sample()调用会从源区间拷贝（最多）10个元素到目的区间：

// 从源区间随机拷贝10个元素到目的区间：
auto end = std::sample(coll.begin(), coll.end(),
                       subset.begin(),
                       10,
                       eng);

返回值end被初始化为目的区间中最后一个被拷贝的元素的下一个位置，所以可以用作打印的终点：

// 打印被提取出的元素（使用返回值作为终点）：
std::for_each(subset.begin(), end,
              [] (const auto& s) {
                  std::cout << "random elem: " << s << '\n';
              });

Chapter25 其他工具函数和算法

Chapter25 其他工具函数和算法

25.1 size()、empty()、data()

25.1.1 泛型size()函数

25.1.2 泛型empty()函数

25.1.3 泛型data()函数

25.2 as_const()

25.2.1 以常量引用捕获

25.3 clamp()

25.4 sample()

25.1 `size()`、`empty()`、`data()`

25.1.1 泛型`size()`函数

25.1.2 泛型`empty()`函数

25.1.3 泛型`data()`函数

25.2 `as_const()`

25.3 `clamp()`

25.4 `sample()`