C++线性范围与STL算法的使用与优势

### C++ 线性范围与 STL 算法的使用与优势 #### 1. 线性范围的使用示例 借助基础函数、迭代器及其对应的 `type_traits`、范围类和 `make_linear_range` 便捷函数，我们能够轻松迭代一系列数字。以下是简单示例： ```cpp for(auto t: make_linear_range(0.0, 1.0, 4)) { std::cout << t << ", "; } // 输出: 0, 0.33, 0.66, 1.0, ``` 这里，`make_linear_range` 函数返回一个 `LinearRange` 类。当使用基于范围的 `for` 循环时，编译器内部生成的代码类似如下： ```cpp auto r = make_linear_range(0.0, 1.0, 4); // r 是 LinearRange<double> auto first = r.begin(); // first 是 LinearRangeIterator<double> auto last = r.end(); // last 是 LinearRangeIterator<double> for(auto it = first; it != last; ++it) { std::cout << (*it) << ", "; } ``` 这使得 `LinearRange` 的值就像显式存储这些值的容器一样被迭代，例如： ```cpp for(auto t: {0.0, 0.33, 0.66, 1.0}) { std::cout << t << ", "; } ``` 线性范围还可用于反向迭代数字： ```cpp for(auto t: make_linear_range(1.0, 0.0, 4)) { std::cout << t << ", "; } // 输出: 1.0, 0.66, 0.33, 0.0, ``` #### 2. STL 算法作为构建块 标准模板库（STL）包含了一系列数据类型、容器和算法。尽管我们日常频繁使用容器，但往往低估了 STL 算法的作用。实际上，复杂算法可以通过组合 STL 中的算法来实现，因此在手动编写算法之前，应优先考虑使用 STL。 ##### 2.1 STL 算法概念 为更好地理解 STL 算法，了解其概念和通用模式很有必要。 - **算法操作于迭代器**：STL 库中的算法仅对迭代器进行操作，而非容器（如 `std::vector`、`std::map` 等）。迭代器可被视为具有与普通 C 指针相同属性的对象，能移动到下一个元素并进行解引用（若指向有效地址）。尽管迭代器内部可能是遍历树状 `std::map` 的复杂对象，但算法仅使用指针允许的部分操作。 - **实现可用于任何容器的通用算法**：实现通用算法能让程序员轻松编写与任何容器兼容的自定义算法。例如，`contains()` 函数可用于任何容器： ```cpp template <typename Iterator, typename T> auto contains(Iterator begin, Iterator end, const T& v) { for (auto it = begin; it != end; ++it) { if (*it == v) { return true; } } return false; } ``` 反之，新容器若能暴露迭代器，也可使用所有算法。例如，实现一个二维 `Grid` 结构，将行作为迭代器对暴露： ```cpp struct Grid { Grid(size_t w, size_t h) : w_{w}, h_{h} { data_.resize(w*h); } auto get_row(size_t y) { auto l = data_.begin() + w_*y; auto r = l + w_; return std::make_pair(l, r); } std::vector<int> data_{}; size_t w_{}; size_t h_{}; }; ``` 表示行的迭代器对可被任何 STL 算法使用： ```cpp auto grid = Grid{10, 10}; auto y = 3; auto r = grid.get_row(y); std::generate(r.first, r.second, std::rand); auto num_fives = std::count(r.first, r.second, 5); ``` ##### 2.2 迭代器指向范围的第一个元素和最后一个元素之后 所有算法都接受一对迭代器，第一个指向范围的第一个元素，第二个指向范围最后一个元素之后的元素。例如： ```cpp auto vec = std::vector<std::string>{ "a", "b", "c", "d", "e", "f" }; auto first = vec.begin(); auto last = vec.end(); ``` 这里，`last` 迭代器指向 `"f"` 之后的假想元素。 ##### 2.3 算法不改变容器大小 STL 算法只能修改指定范围内的元素，不会向容器添加或移除元素。例如，`std::remove()` 或 `std::unique()` 实际上并不从容器中移除元素，而是重新排列元素，将移除的元素置于末尾，并返回指向移除元素第一个元素的迭代器。 ```cpp // 示例：std::remove auto vec = std::vector<int>{1, 1, 2, 2, 3, 3}; auto new_end = std::remove( vec.begin(), vec.end(), 2 ); vec.erase(new_end, vec.end()); // 示例：std::unique auto vec = std::vector<int>{1, 1, 2, 2, 3, 3}; auto new_end = std::unique( vec.begin(), vec.end() ); vec.erase(new_end, vec.end()); ``` ##### 2.4 有输出的算法需要已分配的数据 向输出迭代器写入数据的算法（如 `std::copy()` 或 `std::transform()`）需要为输出预留已分配的数据。由于算法仅使用迭代器作为参数，无法自行分配数据。若将指向空容器的迭代器传递给输出算法，程序将崩溃。例如： ```cpp auto vals = std::vector<int>{ 1, 2, 3, 4 }; auto squared = std::vector<int>{}; std::transform( vals.begin(), vals.end(), squared.begin(), [](int v) { return v * v; } ); ``` 为解决此问题，可采取以下两种方法： - **预分配结果容器所需的大小**： ```cpp auto square_func = [](int v) { return v * v; }; auto vals = std::vector<int>{1, 2, 3}; auto squared = std::vector<int>{}; squared.resize(vals.size()); auto dst = squared.begin(); std::transform(vals.begin(), vals.end(), dst, square_func); ``` - **使用插入迭代器**：插入迭代器在迭代时将元素插入容器。 ```cpp auto square_func = [](int v) { return v * v; }; auto c = std::vector<int>{1, 2, 3}; // 使用 std::back_inserter 插入向量末尾 auto squared_vec = std::vector<int>{}; auto dst_vec = std::back_inserter(squared_vec); std::transform(c.begin(), c.end(), dst_vec, square_func); // 使用 std::inserter 插入 std::set auto squared_set = std::set<int>{}; auto dst_set = std::inserter(squared_set, squared_set.end()); std::transform(c.begin(), c.end(), dst_set, square_func); ``` 若操作 `std::vector` 且知道结果容器的预期大小，可在执行算法前使用 `reserve()` 成员函数，以避免不必要的内存分配。 ##### 2.5 算法默认使用 `operator==` 和 `operator<` 算法在比较时依赖基本的 `==` 和 `<` 运算符，如整数比较。若要在算法中使用自定义类，类必须提供 `operator==` 和 `operator<`，或作为参数传递给算法。例如，在简单的 `Flower` 类中实现这些运算符： ```cpp struct Flower { // 相等操作，用于查找 auto operator==(const Flower& f) const { return height_ == f.height_; } // 小于操作，用于排序 auto operator<(const Flower& f) const { return height_ < f.height_; } int height_{}; }; aut ```