• 课堂笔记| 第九章：泛型算法

    本节课要点：

    • 容器
    • 迭代器
    • 概念（concept）
    • 泛型算法
    • 完美转发
    • 析取类型
    • 特性（traits）

    一、模仿Python做一个range

    1. //range.h
    2. #pragma once
    3.  
    4. template <typename value_t = int>
    5. class range { // range 类似于 generator 生成器
    6. public:
    7.     using value_type = value_t;
    8.     using reference = value_type&;
    9.  
    10. private:
    11.     //TODO;
    12.     value_type b, e, s; //起始、终止、步长
    13.  
    14.  
    15. public:
    16.     //TODO
    17.     range(value_type _b, value_type _e, value_type _s = 1) noexcept : b(_b), e(_e), s(_s) {}
    18.  
    19.     class iterator {
    20.     public:
    21.         using value_type = range::value_type;
    22.         using reference = range::reference; 
    23.     
    24.     private:
    25.         //TODO
    26.         value_type n, s;
    27.  
    28.     public:
    29.         //TODO
    30.         iterator(value_type _n, value_type _s) : n(_n), s(_s) {}
    31.  
    32.         bool operator!=(const iterator & iter) {
    33.             return n != iter.n;
    34.         }
    35.  
    36.         iterator & operator++() {
    37.             n += s;
    38.             return *this;
    39.         }
    40.  
    41.         reference operator*() {
    42.             return n;
    43.         }
    44.     };
    45.  
    46.     auto begin() {
    47.         return iterator(b, s);
    48.     }
    49.  
    50.     auto end() {
    51.         return iterator(e + s, s);
    52.     }
    53. };

    二、泛型算法 

    - algo.h 第一版

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. namespace myalgo {
    6.  
    7.     template <typename T>
    8.     //concept 概念名 = requires {这个类型必须要含有一个iterator类;};
    9.     //concept 将在编译期间判断是否满足要求，如果满足则返回真，编译器将会放过它
    10.     concept iterable = requires {typename T::iterator;};
    11.  
    12.     template 
    13.     void print_c(container& c) {
    14.         for (auto &v : c)
    15.             std::cout << '(' << v << ')';
    16.         std::cout << std::endl;
    17.     }
    18.  
    19.     template <typename ...types>
    20.     void print(types &&...args) {
    21.         (std::cout << ... << args);
    22.         std::cout << std::endl;
    23.     }
    24.  
    25.     //----------------------------------------------------------------
    26.  
    27.     //TODO
    28.     template  //用概念名替代 typename，现在 container 受到了概念的限制
    29.     void rand_fill(container& c, size_t n, 
    30.         typename container::value_type min, decltype(min) max) { //auto?
    31.         //随机数发生引擎
    32.         std::default_random_engine generator(time(NULL));
    33.         //均匀分布的整型生成器；如果min和max给成了int以外的类型，则会发生类型提升且可能报错
    34.         std::uniform_int_distribution<decltype(min)> dis(min, max);
    35.  
    36.         for (size_t i = 0; i < n; ++i)
    37.             //把随机数 dis(generator) 插入到 c.begin() + i
    38.             c.emplace(c.begin() + i, dis(generator));
    39.     }
    40.     //rand_fill 不需要了解类型，是一种泛型算法
    41.  
    42.     //TODO
    43.     template <typename iterator> //采用前向迭代器
    44.     auto count(iterator first, iterator last) {
    45.         size_t c = 0;
    46.         for (auto iter = first; iter != last; ++iter)
    47.             ++c;
    48.         return c;
    49.     }
    50.  
    51.     //TODO
    52.     template <typename iterator>
    53.     void test_algo(iterator first, iterator last) {
    54.         print("count: ", myalgo::count(first, last));
    55.     }
    56.  
    57. };

    因为我们是在粗劣地模仿 C++ 原生的容器，为了避免与 C++ 原生的方法产生冲突，所以设置名字空间 myalgo，以指定方法作用域。

    1. concept 概念

    1. template <typename T>
    2. //concept 概念名 = requires {这个类型必须要含有一个iterator类;};
    3. //concept 将在编译期间判断是否满足要求，如果满足则返回真，编译器将会放过它
    4. concept iterable = requires {typename T::iterator;};

    这里的要求是类型 T 必须含有 iterator 迭代器类，我们称之为 iterable 可迭代的。

    2. 保证与容器元素类型一致 

    我们需要 min 和 max 的类型与元素类型一致： 

    1. typename container::value_type min
    2. decltype(min) max

    对于 min，我们直接析取容器元素类型；对于 max，我们让它与 min 保持一致即可。

    存在的问题：对于数组，其迭代器采用的是原生指针的别名，即伪迭代器。而原生指针内部没有再包含类型，因此将导致编译错误。

    - algo.h 第二版 

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. namespace myalgo {
    6.  
    7.     template <typename T>
    8.     concept iterable = requires {typename T::iterator;};
    9.  
    10.     template 
    11.     void print_c(container& c) {
    12.         for (auto &v : c)
    13.             std::cout << '(' << v << ')';
    14.         std::cout << std::endl;
    15.     }
    16.  
    17.     template <typename ...types>
    18.     void print(types &&...args) {
    19.         (std::cout << ... << args);
    20.         std::cout << std::endl;
    21.     }
    22.  
    23.     //----------------------------------------------------------------
    24.  
    25.     template 
    26.     void rand_fill(container& c, size_t n, 
    27.         typename container::value_type min, decltype(min) max) {
    28.         std::default_random_engine generator(time(NULL));
    29.         std::uniform_int_distribution<decltype(min)> dis(min, max);
    30.  
    31.         for (size_t i = 0; i < n; ++i)
    32.             c.emplace(c.begin() + i, dis(generator));
    33.     }
    34.  
    35.     template <typename iterator>
    36.     auto count(iterator first, iterator last) {
    37.         size_t c = 0;
    38.         for (auto iter = first; iter != last; ++iter)
    39.             ++c;
    40.  
    41.         return c;
    42.     }
    43.  
    44.     //TODO
    45.     template <typename iterator, typename predicate>
    46.     auto count_if(iterator first, iterator last, predicate && pred) {
    47.         size_t c = 0;
    48.         for (auto iter = first; iter != last; ++iter)
    49.             if (pred(*iter))
    50.                 ++c;
    51.         return c;
    52.     }
    53.  
    54.     //TODO
    55.     template <typename iterator, typename predicate>
    56.     void test_algo(iterator first, iterator last, predicate && pred) {
    57.         print("count: ", myalgo::count(first, last));
    58.         print("count_if: ", myalgo::count_if(first, last, pred));
    59.     }
    60. };

    1. 新增 count_if

    作为一种过滤器（filter），帮助我们按需求进行计数。我们使用谓词来帮助过滤，谓词即返回值为 bool 类型的回调函数。 

    1. //TODO
    2. template <typename iterator, typename predicate>
    3. auto count_if(iterator first, iterator last, predicate && pred) {
    4.     size_t c = 0;
    5.     for (auto iter = first; iter != last; ++iter)
    6.         if (pred(*iter))
    7.             ++c;
    8.     return c;
    9. }

    回顾可调用对象：

    全局函数、类的成员函数、lambda表达式、重载了()运算符的类对象。

    相应的 test_algo 改为：

    1. //TODO
    2. template <typename iterator, typename predicate>
    3. void test_algo(iterator first, iterator last, predicate && pred) {
    4.     print("count: ", myalgo::count(first, last));
    5.     print("count_if: ", myalgo::count_if(first, last, pred));
    6. }

    2. 完美转发 

    谓词的参数是 *iter，其类型是容器元素类型。为了避免类型折叠，我们使用完美转发：

    predicate && pred

    - algo.h 第三版 

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. namespace myalgo {
    6.  
    7.     template <typename T>
    8.     concept iterable = requires {typename T::iterator;};
    9.  
    10.     template 
    11.     void print_c(container& c) {
    12.         for (auto &v : c)
    13.             std::cout << '(' << v << ')';
    14.         std::cout << std::endl;
    15.     }
    16.  
    17.     template <typename ...types>
    18.     void print(types &&...args) {
    19.         (std::cout << ... << args);
    20.         std::cout << std::endl;
    21.     }
    22.  
    23.     //----------------------------------------------------------------
    24.  
    25.     template 
    26.     void rand_fill(container& c, size_t n, 
    27.         typename container::value_type min, decltype(min) max) {
    28.         std::default_random_engine generator(time(NULL));
    29.         std::uniform_int_distribution<decltype(min)> dis(min, max);
    30.  
    31.         for (size_t i = 0; i < n; ++i)
    32.             c.emplace(c.begin() + i, dis(generator));
    33.     }
    34.  
    35.     template <typename iterator>
    36.     auto count(iterator first, iterator last) {
    37.         size_t c = 0;
    38.         for (auto iter = first; iter != last; ++iter)
    39.             ++c;
    40.         return c;
    41.     }
    42.  
    43.     template <typename iterator, typename predicate>
    44.     auto count_if(iterator first, iterator last, predicate && pred) {
    45.         size_t c = 0;
    46.         for (auto iter = first; iter != last; ++iter)
    47.             if (pred(*iter))
    48.                 ++c;
    49.         return c;
    50.     }
    51.  
    52.     //TODO
    53.     template <typename iterator, typename T>
    54.     auto accumulate(iterator first, iterator last, T init) {
    55.         auto sum = init;
    56.         for (auto iter = first; iter != last; ++iter)
    57.             sum += *iter;
    58.         return sum;
    59.     }
    60.  
    61.     //TODO
    62.     template <typename iterator, typename predicate, typename T>
    63.     void test_algo(iterator first, iterator last, predicate && pred, T t) {
    64.         print("count: ", myalgo::count(first, last));
    65.         print("count_if: ", myalgo::count_if(first, last, pred));
    66.         print("accumulate: ", myalgo::accumulate(first, last, init));
    67.     }
    68. };

    1. 新增 accumulate 

    分析累加操作知，我们需要一个累加起点。对于数值，起点为0；对于字符串，起点为空串；对于字符，由于其累加无意义，因此我们不作考虑。

    1. //main.cpp
    2. #include 
    3. #include 
    4.  
    5. #include "../dlist8/dlist.h"
    6. #include "../array3/array.h"
    7. #include "algo.h"
    8.  
    9. int main() {
    10.     dlist<int> l;
    11.     myalgo::rand_fill(l, 10, 1000, 9999);
    12.     myalgo::print_c(l);
    13.     myalgo::test_algo(l.begin(), l.end(), 
    14.     [](int v) {return v > 5000;}, 0);
    15.  
    16.     array<char, 20> a;
    17.     myalgo::rand_fill(a, 20, 'A', 'Z');
    18.     myalgo::print_c(a);
    19.     myalgo::test_algo(a.begin(), a.end(), 
    20.     [](char c) {return c < 'O';}, '\0');
    21.  
    22.     std::vector v{"a", " quick", " fox", 
    23.     " jumps over ", "a", " lazy dog"};
    24.     myalgo::print_c(v);
    25.     myalgo::test_algo(v.begin(), v.end(), 
    26.     [](std::string s) {return s == "a";}, std::string(""));
    27.  
    28.     return 0;
    29. }

    说明："" 的类型是 const char *，加运算符不能作用在 const char * 上。因此，我们采用以下形式创建我们希望得到的空串：

    std::string("")

    “和”的类型肯定与容器存储的对象的类型是相同的，因此我们需要使用迭代器指向（容器元素的）类型。由于该类型对算法来说是未知的，因此，我们容易想到的一个解决问题的方法是用附加的类型参数明确的给出。

    1. //TODO
    2. template <typename iterator, typename T>
    3. auto accumulate(iterator first, iterator last, T init) {
    4.     auto sum = init;
    5.     for (auto iter = first; iter != last; ++iter)
    6.         sum += *iter;
    7.     return sum;
    8. }
    9.  
    10. //TODO
    11. template <typename iterator, typename predicate, typename T>
    12. void test_algo(iterator first, iterator last, predicate && pred, T init) {
    13.     print("count: ", myalgo::count(first, last));
    14.     print("count_if: ", myalgo::count_if(first, last, pred));
    15.     print("accumulate: ", myalgo::accumulate(first, last, init));
    16. }

    accumulate 返回值采用 auto 关键字，让编译器去自动推导类型，不仅可以确保类型的正确性，还可以使代码更加精简。 

    2. 优化：确保 init 类型与容器元素类型一致 

    1. //TODO
    2. template <typename iterator>
    3. auto accumulate(iterator first, iterator last, 
    4. typename iterator::value_type init) {
    5.     auto sum = init;
    6.     for (auto iter = first; iter != last; ++iter)
    7.         sum += *iter;
    8.     return sum;
    9. }
    10.  
    11. //TODO
    12. template <typename iterator, typename predicate>
    13. void test_algo(iterator first, iterator last, predicate && pred, 
    14. typename iterator::value_type init) {
    15.     print("count: ", myalgo::count(first, last));
    16.     print("count_if: ", myalgo::count_if(first, last, pred));
    17.     print("accumulate: ", myalgo::accumulate(first, last, init));
    18. }

    即采用：

    typename iterator::value_type init

    存在问题：对于数组，其迭代器（伪迭代器）是原生指针的别名。而原生指针是一种简单类型，它不可能有内嵌的其它类型，因此将导致编译错误。 

    - algo.h 第四版 

    使用特性（traits）解决上述问题。

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. namespace myalgo {
    6.  
    7.     template <typename T>
    8.     concept iterable = requires {typename T::iterator;};
    9.  
    10.     //traits 用于析取内部类型
    11.     template <typename T>
    12.     struct iterator_traits {
    13.         using value_type = typename T::value_type;
    14.     };
    15.  
    16.     //traits 专门针对于指针类型
    17.     template <typename T>
    18.     struct iterator_traits {
    19.         using value_type = T;
    20.     };
    21.  
    22.     template 
    23.     void print_c(container& c) {
    24.         for (auto &v : c)
    25.             std::cout << '(' << v << ')';
    26.         std::cout << std::endl;
    27.     }
    28.  
    29.     template <typename ...types>
    30.     void print(types &&...args) {
    31.         (std::cout << ... << args);
    32.         std::cout << std::endl;
    33.     }
    34.  
    35.     //----------------------------------------------------------------
    36.  
    37.     template 
    38.     void rand_fill(container& c, size_t n, 
    39.         typename container::value_type min, decltype(min) max) {
    40.         std::default_random_engine generator(time(NULL));
    41.         std::uniform_int_distribution<decltype(min)> dis(min, max);
    42.  
    43.         for (size_t i = 0; i < n; ++i)
    44.             c.emplace(c.begin() + i, dis(generator));
    45.     }
    46.  
    47.     template <typename iterator>
    48.     auto count(iterator first, iterator last) {
    49.         size_t c = 0;
    50.         for (auto iter = first; iter != last; ++iter)
    51.             ++c;
    52.         return c;
    53.     }
    54.  
    55.     template <typename iterator, typename predicate>
    56.     auto count_if(iterator first, iterator last, predicate && pred) {
    57.         size_t c = 0;
    58.         for (auto iter = first; iter != last; ++iter)
    59.             if (pred(*iter))
    60.                 ++c;
    61.         return c;
    62.     }
    63.  
    64.     //TODO
    65.     template <typename iterator>
    66.     auto accumulate(iterator first, iterator last, 
    67.     typename iterator_traits::value_type init) {
    68.         auto sum = init;
    69.         for (auto iter = first; iter != last; ++iter)
    70.             sum += *iter;
    71.         return sum;
    72.     }
    73.  
    74.     //TODO
    75.     template <typename iterator, typename predicate>
    76.     void test_algo(iterator first, iterator last, predicate && pred, 
    77.     typename iterator_traits::value_type init) {
    78.         print("count: ", myalgo::count(first, last));
    79.         print("count_if: ", myalgo::count_if(first, last, pred));
    80.         print("accumulate: ", myalgo::accumulate(first, last, init));
    81.     }
    82. };

    1. 新增 iterator_traits

    使用 traits 技术，设计一个 iterator_traits 类模板，用它来析取常规迭代器中的元素类型；再定义一个针对原生指针类型的特化版本。

    1. //traits 用于析取内部类型
    2. template <typename T>
    3. struct iterator_traits {
    4.     using value_type = typename T::value_type;
    5. };
    6.  
    7. //traits 专门针对于指针类型
    8. template <typename T>
    9. struct iterator_traits {
    10.     using value_type = T;
    11. };

    对于一般迭代器，直接析取其内部类型；对于数组的迭代器，采用其所指元素的类型。

    这里的模板参数是 T，而特化参数类型是 T*，我们称之为部分特化或偏特化。 

    2. 相应的改动 

    1. //TODO
    2. template <typename iterator>
    3. auto accumulate(iterator first, iterator last, 
    4. typename iterator_traits::value_type init) {
    5.     auto sum = init;
    6.     for (auto iter = first; iter != last; ++iter)
    7.         sum += *iter;
    8.     return sum;
    9. }
    10.  
    11. //TODO
    12. template <typename iterator, typename predicate>
    13. void test_algo(iterator first, iterator last, predicate && pred, 
    14. typename iterator_traits::value_type init) {
    15.     print("count: ", myalgo::count(first, last));
    16.     print("count_if: ", myalgo::count_if(first, last, pred));
    17.     print("accumulate: ", myalgo::accumulate(first, last, init));
    18. }
  • 相关阅读:
    C/C++语言标准
    Python开发环境搭建
    一文知晓Linux文件权限
    Debian Linux安装minikube&kubectl
    【C语言基础】近期所学到的函数以及关键字（函数memset、scanf、关键字staric、 inline、volatile）
    二叉树正传 - 二叉树的基本操作及构建
    布隆过滤器浅析
    Web jQuery 事件与其他
    win10如何清除ftp自动保存的账户密码
    C++初阶 | [三] 类和对象（中）
  • 原文地址：https://blog.csdn.net/m0_64140451/article/details/127801133