第十章：泛型算法

泛型算法

#include <vector>
#include <algorithm> //包含了基本的泛型算法
#include <numeric>	// 包含一些数值算法，比如accumulate用作累积
#include <ranges>	// C++20 新引入

int main() {
	std::vector<int> x(100);
    int x[100];// 也可以传入这个，传给sort int*
    // 把迭代器传给 sort 即可实现排序
	std::sort(std::begin(x), std::end(x));
    // 泛型体现在：std::sort 支持多种类型
}

// 迭代器 ：是一个模拟的指针，目的：模拟数组的相关操作：递增、解引用。因此用迭代器作为容器与算法间的桥梁
// 泛型算法通常来说都不复杂，但优化足够好

//一些泛型算法与方法同名，实现功能类似，此时建议调用方法而非算法
//	std::find V.S. std::map::find


////////////////////////////////////////
// 读算法
// accumulate
template<class InputIt, class T>
constexpr // since C++20
T accumulate(InputIt first, InputIt last, T init)
{
    for (; first != last; ++first)
        init = std::move(init) + *first; // std::move since C++20
 
    return init;
}
////////////////////////////////////////
// find
template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );
(until C++20)
////////////////////////////////////////
// count
template< class InputIt, class T >
typename iterator_traits<InputIt>::difference_type
    count( InputIt first, InputIt last, const T& value );
(until C++20)

////////////////////////////////////////
// 写算法
// fill
template< class ForwardIt, class T >
void fill( ForwardIt first, ForwardIt last, const T& value );
(until C++20)


// Possible implementation
template< class ForwardIt, class T >
void fill(ForwardIt first, ForwardIt last, const T& value)
{
    for (; first != last; ++first) {
        *first = value;
    }
}

// fill_n，给开头元素，个数，写入的值
template< class OutputIt, class Size, class T >
OutputIt fill_n( OutputIt first, Size count, const T& value );

// Possible implementation
template<class OutputIt, class Size, class T>
OutputIt fill_n(OutputIt first, Size count, const T& value)
{
    for (Size i = 0; i < count; i++) {
        *first++ = value;
    }
    return first;
}
////////////////////////////////////////
// transform
template< class InputIt, class OutputIt, class UnaryOperation >
// InputIt 区间用来读，OutputIt d_first 表示写入区间开头位置
// unary_op 一元操作符
OutputIt transform( InputIt first1, InputIt last1,
                    OutputIt d_first, UnaryOperation unary_op );
(until C++20)


First version
template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1,
                   OutputIt d_first, UnaryOperation unary_op)
{
    while (first1 != last1)
        *d_first++ = unary_op(*first1++);// 先对区间解引用
    	// 获取到的值放入unary_op计算，同时把当前迭代器向下移动一位
    return d_first;
}

////////////////////////////////////////
// copy
template< class InputIt, class OutputIt >
OutputIt copy( InputIt first, InputIt last, OutputIt d_first );

////////////////////////////////////////
// fill_n
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> x(10);
    std::fill_n(x.begin(), 100, 3);// 危险，内存访问越界
    
    // 有动态拓展的算法
}
////////////////////////////////////////
// sort
template< class RandomIt > // 传入的元素需要支持><判断
void sort( RandomIt first, RandomIt last );
////////////////////////////////////////
// unique
// 返回一个迭代器，迭代器指向做完unique之后所有无重复元素的下一个位置，通常，需要调用erase把后面的元素删除
#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    // a vector containing several duplicate elements
    std::vector<int> v{1, 2, 1, 1, 3, 3, 3, 4, 5, 4};
    auto print = [&] (int id)
    {
        std::cout << "@" << id << ": ";
        for (int i : v)
            std::cout << i << ' ';
        std::cout << '\n';
    };
    print(1);
 
    // remove consecutive (adjacent) duplicates
    auto last = std::unique(v.begin(), v.end());
    // v now holds {1 2 1 3 4 5 4 x x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    print(2);
 
    // sort followed by unique, to remove all duplicates
    std::sort(v.begin(), v.end()); // {1 1 2 3 4 4 5}
    print(3);
 
    last = std::unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    print(4);
}

Output:

@1: 1 2 1 1 3 3 3 4 5 4 
@2: 1 2 1 3 4 5 4 	// 没有进行sort，因此只删除连续的相同元素
@3: 1 1 2 3 4 4 5 
@4: 1 2 3 4 5  
    
////////////////////////////////////////
// distance
template< class InputIt > // 接收输入迭代器
typename std::iterator_traits<InputIt>::difference_type distance( InputIt first, InputIt last );
(constexpr since C++17)
// implementation via tag dispatch, available in C++98 with constexpr removed
namespace detail {
 
template<class It>
constexpr // required since C++17
typename std::iterator_traits<It>::difference_type 
    do_distance(It first, It last, std::input_iterator_tag)// 根据迭代器类别不同引入重载
    // 输入迭代器重载
{
    typename std::iterator_traits<It>::difference_type result = 0;
    while (first != last) {
        // 对输入元素而言，求两个迭代器之间的距离，加到相等为止；返回加的次数
        ++first;
        ++result;
    }
    return result;
}
 
template<class It>
constexpr // required since C++17
typename std::iterator_traits<It>::difference_type 
    do_distance(It first, It last, std::random_access_iterator_tag)
    // 随机访问迭代器重载
{
    // 对于随机访问迭代器而言，之间相减即可；随机访问器支持的功能（两个迭代器相减）
    return last - first;
}
 
} // namespace detail
 
template<class It>
constexpr // since C++17
typename std::iterator_traits<It>::difference_type 
    distance(It first, It last)
{
    // 传给了do_distance
    return detail::do_distance(first, last,
                               typename std::iterator_traits<It>::iterator_category());// 获取迭代器类别
}

特殊的迭代器

插入迭代器

////////////////////////////////////////
// back_insert_iterator
// 写算法一定要保证目标区间足够大，但有些时候没法保证，因此引入back_insert_iterator
// std::back_insert_iterator<Container>::operator=
// inserts an object into the associated container
// 1.不支持insert, 向容器结尾来查找
// 2.调用容器的push_back来插入
#include <iostream>
#include <iterator>
#include <deque>
 
int main()
{
    std::deque<int> q;
    std::back_insert_iterator< std::deque<int> > it(q);
 
    for (int i=0; i<10; ++i)
        it = i; // calls q.push_back(i) 相当于调用这个
 
    for (auto& elem : q) std::cout << elem << ' ';
}
Output:
	1 2 3 4 5 6 7 8 9 10
        
int main() 
{
   std::vector<int> x;
   // std::fill_n(x.begin(), 10 , 3);// 会报错，内存溢出
   // 利用 back_insert_iterator 插入的特性
   std::fill_n(std::back_insert_iterator<std::vector<int>>(x), 10 , 3);
        // 打印出 10 个 3
        // 用插入迭代器作为fill_n的第一个参数，在fill_n内部循环了10次，相当于调用了10次push_back
   // 为了方便调用，C++简化，可使用 back_inserter
   std::fill_n(std::back_inserter(x), 10 , 3);
   for (auto i : x)
   {
       std::cout << i << ' ';
   }
}    
////////////////////////////////////////
// front_insert_iterator    
// 同上类似，调用 push_front 实现
// 同样，有 front_inserter
// 注意：想使用插入迭代器时，需要确保底层的容器支持相应的操作
#include <list>
int main() 
{
   std::list<int> x;// 支持 push_front
    //  std::vector<int> x; 不行，因为不支持 push_front
   std::fill_n(std::front_inserter(x), 10 , 3);
   for (auto i : x)
   {
       std::cout << i << ' ';
   }
}
////////////////////////////////////////
// insert_iterator
// 需要提供一个容器和这个容器的迭代器
// 对它赋值时会调用容器的 insert
template< class Container >
class insert_iterator : public std::iterator< std::output_iterator_tag,
                                              void,void,void,void >
                                                  
// std::inserter      
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <set>
 
int main()
{
    std::multiset<int> s {1, 2, 3};
 
    // std::inserter is commonly used with multi-sets
    std::fill_n(std::inserter(s, s.end()), 5, 2);
 
    for (int n : s)
        std::cout << n << ' ';
    std::cout << '\n';
 
    std::vector<int> d {100, 200, 300};
    std::vector<int> v {1, 2, 3, 4, 5};
 
    // when inserting in a sequence container, insertion point advances
    // because each std::insert_iterator::operator= updates the target iterator
    std::copy(d.begin(), d.end(), std::inserter(v, std::next(v.begin())));
 
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}
Output:
    1 2 2 2 2 2 2 3 
    1 100 200 300 2 3 4 5

流迭代器 istream_iterator / ostream_iterator

// istream_iterator 
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <list>
#include <sstream>
#include <numeric> // accumulate

int main() 
{
   std::istringstream str("1 2 3 4 5");
    // istream_iterator( istream_type& stream ); 构造
   std::istream_iterator<int> x(str);
   // 迭代器通常可用*解引用
   std::cout << *x << std::endl;// int tmp; str >> tmp
   std::cout << *x << std::endl;// int tmp; str >> tmp
   
   ++x;						  // str >> tmp
   std::cout << *x << std::endl;
}

int main() {
    std::istringstream str("1 2 3 4 5");
    std::istream_iterator<int> x(str);
    // 缺省构造 constexpr istream_iterator();
    std::istream_iterator<int> y{};// C++规定，缺省为流迭代器结尾位置
    // y() 是一个函数声明，y{}是类对象定义
    // std::istream_iterator<int> y; 也可以
    /*
    for (; x != y; ++x) {
        std::cout << *x << std::endl;
    }*/
    
    // 应用在一些算法上
    int res = std::accumulate(x, y, 0);
    std::cout << res << std::endl;// 输出 15
    // 用输入流迭代器标识了一个区间，区间为 1 2 3 4 5
}


//  ostream_iterator
#include <algorithm>
#include <numeric>

int main() {
    std::ostream_iterator<char> oo {std::cout};
    std::ostream_iterator<int> i1 {std::cout, ", "};
    std::fill_n(i1, 5, -1);
    *oo++ = '\n';
    
    std::ostream_iterator<double> i2 {std::cout, "; "};
    *i2++ = 3.14;
    *i2++ = 2.71;
    *oo++ = '\n';
}

// Output:
-1, -1, -1, -1, -1,
3.14; 2.71;

#include <iostream>
#include <sstream>
#include <iterator>
#include <numeric>
int main()
{
    std::istringstream str("0.1 0.2 0.3 0.4");
    std::partial_sum(std::istream_iterator<double>(str),
                      std::istream_iterator<double>(),
                      std::ostream_iterator<double>(std::cout, " "));
}

反向迭代器

#include <iostream>
#include <vector>
#include <iterator>
#include <array>

int main() {
    std::vector<int> x{1, 2, 3, 4, 5};
    std:;copy(x.begin(), x.end(), std::ostream_iterator<int>(std::cout, " "));
    // 反向迭代器
    std:;copy(x.rbegin(), x.rend(), std::ostream_iterator<int>(std::cout, " "));
    // x.rbegin() x.begin() 不能混用
}

移动迭代器 move_iterator

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <iterator>
#include <numeric>
#include <string>
 
int main()
{
    std::vector<std::string> v{"this", "_", "is", "_", "an", "_", "example"};
 
    auto print_v = [&](auto const rem) {
        std::cout << rem;
        for (const auto& s : v)
            std::cout << std::quoted(s) << ' ';
        std::cout << '\n';
    };
 
    print_v("Old contents of the vector: ");
 
    std::string concat = std::accumulate(std::make_move_iterator(v.begin()),
                                         std::make_move_iterator(v.end()),
                                         std::string());
 
    // An alternative that uses std::move_iterator directly could be:
    // using moviter_t = std::move_iterator<std::vector<std::string>::iterator>;
    // std::string concat = std::accumulate(moviter_t(v.begin()),
    //                                      moviter_t(v.end()),
    //                                      std::string());
 
    // Starting from C++17, which introduced class template argument deduction,
    // the constructor of std::move_iterator can be used directly without
    // template parameters in most cases:
    // std::string concat = std::accumulate(std::move_iterator(v.begin()),
    //                                      std::move_iterator(v.end()),
    //                                      std::string());
 
    print_v("New contents of the vector: ");
 
    std::cout << "Concatenated as string: " << quoted(concat) << '\n';
}

// Output:
Old contents of the vector: "this" "_" "is" "_" "an" "_" "example"
New contents of the vector: "this" "_" "is" "_" "an" "_" "example"
Concatenated as string: "this_is_an_example"
    
    
////////////////////////////////////////
int main() {
    std::string x = "abc";
    auto y = x;
    std::cout << x << std::endl;
    auto z = std::move(x);
    std::cout << x << std::endl;// x 的值被移动给了 z，因此 x 空
}

迭代器与哨兵（ Sentinel ）

要求：两个迭代器描述两个对象，其中一个迭代器不断变化后能变成另一个对象，在判等时能够相等；

哨兵：标识区间结尾

并发算法（ C++17 / ）

std::execution::seq

顺序执行
std::execution::par

并发执行
std::execution::par_unseq

并发（多线程）非顺序（SIMD）执行

SIMD（单指令多数据）
std::execution::unseq

SIMD单线程执行

一条指令处理多组数据，一般是硬件提供的支持

#include <iostream>
#include <vector>
#include <execution>
#include <random>
#include <ratio>
#include <chrono>

int main() {
    std::random_device rd;// 产生随机数
    
    std::vector<double> vals(10000000);
    for (auto& d : vals) {
        d = static_cast<double>(rd());
    }// 构造包含10000000个double型数据的数组，且随机排布
    
    for (int i = 0; i < 5; ++i)
    {
        using namespace std::chrono;
        std::vector<double> sorted(vals);// 复制到sorted数组中
        const auto startTime = high_resolution_clock::now();// 获取当前时间
        // std::sort(sorted.begin(), sorted.end());// 对 sorted 进行排序
        // 使用并行算法：std::execution::unseq
        std::sort(std::execution::unseq,sorted.begin(), sorted.end());// 对 sorted 进行排序
        // 尝试其他并行算法par,建立多线程
        std::sort(std::execution::par,sorted.begin(), sorted.end());\
        
        const auto endTime = high_resolution_clock::now();
        std::cout << "Latency: "
                  << duration_cast<duration<double, std::milli>>(endTime - startTime).count()// 计算 sort 计算时间
                  << std::endl;
    }
}
// 注意加速时，需要加入一些编译的链接和选项  -O3 -ltbb，不同编译环境不一样

bind与lambda表达式

基于泛型算法引入

很多算法允许通过可调用对象自定义计算逻辑的细节 transform / copy_if / sort…

// transform
template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1,//获取元素
                   OutputIt d_first, UnaryOperation unary_op)
{
    while (first1 != last1)
        *d_first++ = unary_op(*first1++);//对每个元素调用unary_op，获取相应的结果
    // 因此可以通过定义不同的UnaryOperation来实现不同的功能
 
    return d_first;
}

// copy_if
template<class InputIt, class OutputIt, class UnaryPredicate>
OutputIt copy_if(InputIt first, InputIt last,
                 OutputIt d_first, UnaryPredicate pred)// 有一个谓词
{
    for (; first != last; ++first)
    {
        if (pred(*first)) // 输入一个元素，返回布尔值表示这个元素是真是假
        { // pred(*first) 语法形式很像函数，因此将pred称为可调用对象
            // 函数、函数指针--典型的可调用对象
            *d_first = *first; // 真则写入
            ++d_first;
        }
    }
 
    return d_first;
}
// sort
template< class RandomIt, class Compare >
constexpr void sort( RandomIt first, RandomIt last, Compare comp );
// 自定义Compare comp比较方法进行排序

可调用对象

#include <iostream>
#include <vector>
#include <functional>

// 函数指针，不能在函数内部定义函数
bool MyPredict(int val) {
    return val > 3;
}

int main() {
    std::vector<int> x{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> y;
    // copy_if 输入区间包含x的所有元素，输出的迭代器是back_inserter，每次往y里面push_back
    std::copy_if(x.begin(), x.end(), std::back_inserter(y), MyPredict);
    // MyPredict 是谓词,给定任意数据返回是真是假，只有返回真是y中才会写入
    // MyPredict 如上，即 > 3 时写入
    for (auto p : y) {
        std::cout << p << ' ';
    }
    std::cout << std::endl;
}

bind：通过绑定的方式修改可调用对象的调用方式

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional> // bind

bool MyPredict2(int val1, int val2) {
    return val1 > val2;
}

int main() {
    std::vector<int> x{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> y;
    // 利用bind2nd
    std::copy_if(x.begin(), x.end(), std::back_inserter(y), std::bind2nd(std::greater<int>(), 3));
    // std::greater 接收两个参数，这里把bind2nd第二个参数固定成 3，因此只接收第一个参数。因此得到类似的结果
    //constexpr bool operator()(const T &lhs, const T &rhs) const {
    //return lhs > rhs; }
    
    // 利用bind1st
    std::copy_if(x.begin(), x.end(), std::back_inserter(y), std::bind2nd(std::greater<int>(), 3));
    // 此处会打印出比 3 小
    // 这是因为 bind1st 把第一个参数绑定成 3
    
    
    // bind1st使用场景有限
    std::copy_if(x.begin(), x.end(), std::back_inserter(y), std::bind2nd(MyPredict2, 3));
    // 无法完成绑定，即只有部分对象才可以使用bind1st和bind2nd
    
    for (auto p : y) {
        std::cout << p << ' ';
    }
    std::cout << std::endl;
}
////////////////////////////////////////
//bind
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional> // bind
#include <memory> 

bool MyPredict2(int val1, int val2) {
    return val1 > val2;
}

int main() {
    using namespace std::placeholders; // 用bind需要这个名字空间
    
    std::vector<int> x{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> y;
    // bind
    std::copy_if(x.begin(), x.end(), std::back_inserter(y), std::bind(MyPredict2, _1, 3));
    
    for (auto p : y) {
        std::cout << p << ' ';
    }
    std::cout << std::endl;
}

bool MyAnd(bool val1, bool val2) {
    return val1 && val2;
}

void MyProc(int* ptr) {
    
}
// 使用智能指针
void MyProc2(std::shared_ptr<int> ptr) {
    
}

auto fun() {
    int x;
    return std::bind(MyProc, &x);
}

auto fun2() {
    std::shared_ptr<int> x(new int());// 在堆上分配一块内存
    return std::bind(MyProc2, x);
}

int main() {
    using namespace std::placeholders;
    
    auto x = std::bind(MyPredict2, _1, 3);
    x(50);// 会用50来调用MyPredict2，作为其第一个参数，_1
    // _1 定义在名字空间 std::placeholders
    std::cout << x(50);
    std::bind(MyPredict2, 3, _1)// 这里3对应val1，_1对应val2;
    // _1指的是传入的x(50)的第1个参数
        
    auto x = std::bind(MyPredict2, _2, 3);
    std::cout << x("hello", 50);//hello对应_1，50对应_2
    
    auto x = std::bind(MyPredict2, _2, _1);
    std::cout << x(3, 4);// 3 -> _1 -> val2; 4 -> _2 -> val1
    // 4 > 3 -> True
    
    // bind 组合 通过绑定的方式修改可调用对象的调用方式
    // 调用 std::bind 时，传入的参数会被复制，这可能会产生一些调用风险
    auto x1 = std::bind(MyPredict2, _1, 3);	 //  5 > 3
    //x1 要包含MyPredict2、3等信息，其中3是被复制进去的
    auto x2 = std::bind(MyPredict2, 10, _1); // 10 > 5
    auto x3 = std::bind(MyAnd, x1, x2);		// 1 && 1
    std::cout << x3(5);// x3的值会尝试传递给x1, x2
    
    auto x4 = std::bind(MyPredict2, _1, _1);
    std::cout << x4(2);
    
    // 返回可调用对象，是 bind 的构造的一个可调用对象，其内部包含了int* 指针，并指向了局部的对象；局部的指针会被复制到band的对象中
    auto ptr = fun();
    ptr();// 该行为即未定义，因为x地址是被复制进去的，但x已经不存在
    // 这种情况可以尝试使用智能指针,较为安全
    auto ptr = fun2();
    ptr();
}


void Proc(int& x) {
    ++x;
}
int main() {
    int x = 0;
    auto b = std::bind(Proc, x); // 构造 bind 时 x 会被拷贝给 b 这个对象的数据成员中，接下来再用 Proc 用的是拷贝的 x，即 b 内部的 x 被修改了
    // 而 x 不会被修改
    b();
    std::cout << x << std::endl;// 打印出0
    
    // 如果真的要修改这里的 x ，可以使用 std::ref 或 std::cref 避免复制的行为
    auto b = std::bind(Proc, std::ref(x));//std::ref会构成一个对象，并会被拷贝复制给b；但是这个对象内部会包含一个引用，引用这个x，因此在调用Proc时会修改x的值，即传引用
    auto b = std::bind(Proc, std::cref(x));//传常量引用也可以避免拷贝
    b();// 这里有点问题..报错
    std::cout << x << std::endl;// 打印出1
    
    
    // std::bind_front （ C++20 引入） 绑定第一个
    auto y = std::bind_front(MyPredict2, 3);
    std::cout << y(2);
}
// 用bind实现比较复杂的功能会很麻烦

lambda 表达式，C++11开始

新引入的一套语法《C++ Lambda Story》

lambda 表达式会被编译器翻译成类进行处理

#include <iostream>
#include <algorithm>
#include <vector>

// lambda 表达式的基本组成部分
int main() {
    auto x = [](int val) { return val > 3; }; // lambda表达式
    // 形参列表: ()
    // 函数体:   {}   其中每一条语句都要以 ; 结尾，并在括号外加 ; 
    // 函数体 描述了 x 赋值的具体的语句
    std::cout << x(5) << std::endl;
    
    auto x = [](int val)
    {
        return (val > 3) && (val  < 10);// 返回bool值
    };// 相比bind操作简单清晰
}
////////////////////////////////////////
// C++ insight
int main()
{
    // 定义了一个类
  class __lambda_4_14
  {
    public: // 定义了一个operator()(int val)
    inline /*constexpr */ bool operator()(int val) const
    {
      return (val > 3) && (val < 10);// return的逻辑
    }
    
    using retType_4_14 = bool (*)(int);
    inline constexpr operator retType_4_14 () const noexcept
    {
      return __invoke;
    };
    
    private: 
    static inline /*constexpr */ bool __invoke(int val)
    {
      return __lambda_4_14{}.operator()(val);
    }
    
    // 可见类复杂，lambda表达式简洁
  };
  
  __lambda_4_14 x = __lambda_4_14{};
  return 0;
}
////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory>

int main() {
    auto x = [](int val)  -> float  // 指定返回类型
    {
        if (val > 3) {
            return 3.0; // 返回的数据类型需要相同，告诉编译器这是什么类型
        }
        else {
            return 1.5;
            // return 1.5f 会报错，因为3.0是double类型，1.5f是float，系统无法判断最后给x什么类型，可以显式得给x规定返回数据类型
        }
    };
    std::cout << x(5) << std::endl;
}

////////////////////////////////////////////
// 捕获

int main()
{
    int y = 10; // 局部自动对象
    // static int y = 10; //此时为局部静态对象，不需要/不能捕获它，直接[]即可，全局/静态对象都不用捕获
    auto x = [](int val)
    {
        return val > y; // 无法编译成功，lambda表达式内部不知道y
    };
    std::cout << x(5) << std::endl;
    ///////中括号是用来捕获的///////
    auto x = [y](int val)
    {
        return val > y; // 这样可以
    };
}
////////////////////////////////////////////

int main()
{
    int y = 10;
    auto x = [y] (int val) mutable  // 需要加一个mutable
    {
        ++y; // 不会传递到 lambda表达式外部
        // 原因是这里采用了y的值捕获，即y被赋值到lambda表达式内部
        // 对内部的'y'操作
        return val > y;
    };
    std::cout << x(5) << std::endl;
    std::cout << y << std::endl; // 打印出 10
}

// 引用捕获
int main()
{
    int y = 10;
    int z = 3;
    auto x = [&y,z] (int val) // 引用捕获,[]捕获列表，可以包含多种捕获，即混合捕获
    {
        ++y; // 内部的'y'是外部的y的别名
        return val > z;
    };
    std::cout << x(5) << std::endl;
    std::cout << y << std::endl; // 打印出 11
}

int main()
{
    int y = 10;
    int z = 3;
    auto x = [=] (int val) 
    // [=] 编译器会分析内部使用了哪些局部自动对象，且没有显式出现在[]捕获列表，值捕获会把这个局部自动对象捕获下来
    {
        return val > z;
    };
    std::cout << x(5) << std::endl;
}
// 注意看c++insight中的实现
int main()
{
    int y = 10;
    int z = 3;
    auto x = [&] (int val) 
    // [&] 内部使用了局部自动对象，没有显式出现在[]捕获列表，此时用引用的方式对其捕获
    {
        return val > z;
    };
    std::cout << x(5) << std::endl;
    
    /////// 
    auto x = [&, z] (int val) //通常采用引用捕获，但 z 是例外
    {
        ++y;
        return val > z;
    };
    
    auto x = [=, &y] (int val) //通常采用值捕获，但 y 是引用捕获
    {
        ++y;
        return val > z;
    };
}

//////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <memory>

// this 捕获
// 关键字 this：如果构造Str对象，对其调用fun()函数，this是一个指向Str的指针
struct Str
{
    auto fun()
    {
        int val = 3;	// 局部自动对象
        auto lam = [val,this] () //只有this才能捕获对象x，相当于传了指针
        {
            return val > x;
            // return val > __this->x; // -> 成员访问
        };
        return lam();
    }
    int x; // 不在fun()中定义，不是局部自动对象；同时不是静态/全局对象，无法直接对其捕获
};

int main()
{
    Str s;
    s.fun(); // this 对应的是 s 的地址
}


// 初始化捕获
int main()
{
    int x = 3;
    auto lam = [y = x](int val) // C++14中引入，初始化捕获，构造自动对象y，并将x值赋予y，y可在lambda表达式内部使用
    {
        return val > y;
    };
    std::cout << lam(100) << std::endl;
}
int main()
{
    std::string a = "hello";
    auto lam = [y = std::move(a)]()
    {
        std::cout << y << std::endl;
    };
    std::cout << a << std::endl;// a 里面没有值了，构造lambda表达式时就已经空了
    lam();
}
int main() 
{
    int x = 3;
    int y = 10;
    auto lam = [z = x + y](int val) // lambda表达式构造的时候执行了一次，仅保存z，不需要后续重复计算x+y
    {
        return val > z;
    };
    
    auto lam = [x = x](int val) // 构造对象x，此对象用于lambda表达式，并用x初始化
    {
        return val > x;
    }
}

//////////////////////////////////
// *this 捕获（ C++17 ）
struct Str
{
    auto fun()
    {
        int val = 3;
        auto lam = [val, this] ()
        auto lam = [val, *this] ()
            // *this是一个解引用，此时会把其指向的对象copy到lambda表达式中，此时会较安全，缺点是进行了一个复制，较耗费资源
        {
            return val > x;
        };
        return lam;
    }
    int x;
};

auto wrapper() // 返回的是lambda表达式
    // 捕获了局部自动对象 val；会用值的方式保存在lambda表达式内部
    // 还捕获了一个this，一个指向Str对象的指针，指向s，调用结束后s会被销毁，此时即为一个悬挂指针，其行为未定义
{
    Str s;
    return s.fun();
}

int main()
{
    auto lam = wrapper();
    lam();// this指向一个已被销毁的对象
}

说明符

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <memory>
#include <string>

int main()
{
    int y = 3;
    // lam 表明类的对象，
    auto lam = [y](int val)
        // 调用()实现可调用运算时，不应该对对象内部的东西产生任何改变
    auto lam = [y](int val) mutable //加入说明符 mutable，此时const小事
        // 此时可以对类中的内容改变
    {
      ++y;// 与 const 矛盾
      return val > y;  
    };
    
    // C++ insight
    inline /*constexpr */ bool operator()(int val) const
    {
      return val > y;
    } 
}

// constexpr (C++17)
int main ()
{
    auto lam = [](int val) constexpr
        // 这个lambda可以在编译期进行调用
    {
      return val + 1;
    }; 
    
    constexpr int val = lam(100);
    std::cout << val << std::endl;
}

// consteval (C++20)
int main ()
{
    auto lam = [](int val) consteval
        // 这个lambda只能在编译期进行调用
    {
      return val + 1;
    }; 
    
    constexpr int val = lam(100);
    std::cout << val << std::endl;
}


// 模板形参 (C++20)
int main()
{
    auto lam = []<typename T>(T val) // 可以接收任意类型的数据
        // 编译器还是会主动优化，把输出在编译期确定了，如果要确保可以在运行期执行，就加 constexpr
    {
      return val + 1;  // 数据类型要支持 + 1 的操作
    };
    constexpr int val = lam(100);
    return val;
}

lambda 表达式的深入应用

#include <iostream>
#include <functional>

// 捕获时计算
int main()
{
    int x = 3;
    int y = 5;
    auto lam = [z = x + y]()
    {
      return z;  
    };
    lam();
}

// 即调用函数表达式
// ( Immediately-Invoked Function Expression, IIFE )
int main()
{
    int x = 3;
    int y = 5;
    auto lam = [z = x + y]()
    {
      return z;  
    }(); // 构造完lambda表达式后马上调用
    
    const auto val = [z = x + y]() 
        // 常量需要在初始化就给它值
        // 即调用函数表达式把它初始化了，不需要额外定义函数
    {
      return z;  
    }();
    std::cout << val << std::endl;
}

// 使用 auto 避免复制（ C++14 ）
int main()
{
    auto lam = [](auto x)
    {
      return x + 1;  
    };
    // C++ insights
    template<class type_parameter_0_0> // 可以接收任何类型的参数
    inline /*constexpr */ auto operator()(type_parameter_0_0 x) const
}

#include <map>
int main()
{
    std::map<int, int> m{{2, 3}};
    auto lam = [](const std::pair<int, int>& p) // const & 避免复制；但还是会复制
        // 解引用之后类型如果不完全匹配，还是会引入复制
    auto lam = [](const std::pair<const int, int>& p) // 这样才没复制
        // 因为std::map的value_type是std::pair<const Key, T>
        // 使用 auto 避免因为类型不匹配导致的复制
    auto lam = [](const auto&p) // 使用 auto 避免复制（ C++14 ）
    {
      return p.first + p.second;
    };
    std::cout << lam(*m.begin()) << std::endl; 
}


// Lifting （ C++14 ）
auto fun(int val)
{
    return val + 1;
}

auto fun(double val) // 函数重载
{
    return val + 1;
}

int main()
{
    auto b = std::bind(fun, 3);// 报错，fun对应两个可调用对象，编译器无法区分
    std::cout << b() << std::endl;
    
    // Lifting （ C++14 ）
    auto lam = [](auto x)
    {
        return fun(x); // Lifting
    };
    std::cout << lam(3) << std::endl; 
    std::cout << lam(3.5) << std::endl;
    // 使用了函数模板，根据参数具体类型调用具体的函数
}

// 递归调用（ C++14 ）
int factorial(int n)
{
    return n > 1 ? n * factorial(n - 1) : 1;
}

int main()
{
    auto factorial_lam = [](int n)
    { // 初始化 factorial_lam 的类型，但是不定
        return n > 1 ? n * factorial_lam(n - 1) : 1;
        // 解析过程又遇到factorial_lam，类型不定，括号中的行为不定
        // 1.表达式合法不确定，2.返回类型不确定
    };
    auto x = 3; // 根据表达式信息解析 x 的类型
    std::cout << factorial(5) << std::endl;
}
// 修改
int main()
{
    auto factorial_lam = [](int n)
    {
        auto f_impl = [](int n, const auto& impl) -> int // 代表f_impl会返回一个int型整数，要递归的话一定要把返回类型显式的标出来
        {
            return n > 1 ? n * impl(n - 1, impl) : 1;
        };
        return f_impl(n, f_impl);
    };
    std::cout << factorial_lam(5) << std::endl;
}

template<>
inline /*constexpr */ int operator()<__lambda_8_23>(int n, const __lambda_8_23 & impl) const
{
	return n > 1 ? n * impl.operator()(n - 1, impl) : 1;
}

int main()
{
    auto factorial_lam = [](int n)
    {
        auto f_impl = [](int n, const auto& impl) // 没有显式指定返回类型，被C++解析成了auto
        {
            return n > 1 ? n * impl(n - 1, impl) : 1;
        };
        return f_impl(n, f_impl);//n传入，f_impl传入；编译器需要确定auto返回类型，根据里面的return语句自动推导返回类型；又是一个鸡生蛋蛋生鸡的问题，就无法解析
    };
}
// factorial_lam 是lambda表达式，被C++翻译成一个随机的类型，会翻译成一个类， 但是类的名称由C++随机确定，我们无权干涉；因此无法解析出factorial_lam的具体类型
// 但是要确定 operator() 的返回类型，我们有权确定
// 编译器解析 -> int 即能推断出 f_impl 的返回类型
// 递归内层的lambda表达式的返回类型需要显式表达出来

泛型算法的改进——ranges

#include <iostream>
#include <algorithm>
#include <vector>
#include <ranges>

int main()
{
    std::vector<int> x{1, 2, 3, 4, 5};
    auto it = std::find(x.begin(), x.end(), 3);
    std::cout << *it << std::endl;
}
// ranges
// 可以使用容器而不是迭代器输入
	// 通过 std::ranges::dangling 避免返回无效的迭代器
// 引入迭代器的目的：区分一个区间
 
// 引入映射概念，简化代码编写
// 引入 view ，灵活组织程序逻辑
	// 1.对输入不是立即计算，需要时再计算
	// 既是算法也是容器
	// 2.灵活组织程序逻辑
int main()
{
    std::vector<int> x{1, 2, 3, 4, 5};
    auto it = std::ranges::find(x, 3);
    std::cout << *it << std::endl;
}

//  通过 std::ranges::dangling 避免返回无效的迭代器
auto fun()
{
    return std::vector<int>{1, 2, 3, 4, 5};
}
int main()
{
    std::vector<int> x{1, 2, 3, 4, 5};
    auto it = std::ranges::find(fun(), 3); //有问题
    // fun()返回了一个局部自动对象，返回之后该对象被销毁
    std::cout << *it << std::endl;// *it 指向的右值对象已被销毁
}

// 引入映射概念，简化代码编写
#include <map>

int main()
{
    std::map<int, int> m{{2,3}};
    // find需要用lambda表达式查找
    // ranges 使用proj映射
    auto it = std::ranges::find(m,3, &std::pair<const int, int>::second);
    std::cout << it->first << ' ' << it->second << std::endl;
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

10.第十章：泛型算法.md

10.第十章：泛型算法.md

第十章：泛型算法

泛型算法

特殊的迭代器

插入迭代器

流迭代器 istream_iterator / ostream_iterator

反向迭代器

移动迭代器 move_iterator

迭代器与哨兵（ Sentinel ）

并发算法（ C++17 / ）

std::execution::seq

std::execution::par

std::execution::par_unseq

std::execution::unseq

bind与lambda表达式

可调用对象

bind：通过绑定的方式修改可调用对象的调用方式

lambda 表达式，C++11开始

Files

10.第十章：泛型算法.md

Latest commit

History

10.第十章：泛型算法.md

File metadata and controls

第十章：泛型算法

泛型算法

特殊的迭代器

插入迭代器

流迭代器 istream_iterator / ostream_iterator

反向迭代器

移动迭代器 move_iterator

迭代器与哨兵（ Sentinel ）

并发算法（ C++17 / ）

std::execution::seq

std::execution::par

std::execution::par_unseq

std::execution::unseq

bind与lambda表达式

可调用对象

bind：通过绑定的方式修改可调用对象的调用方式

lambda 表达式，C++11开始