算法的形式

Cmp通常是个比大小的准则，是Functor。
算法所需的信息通常指迭代器如何移动

迭代器的分类

array，vector，deque它们是连续的，它们的迭代器是Random Access Iterator/随机访问迭代器
list的迭代器是Bidirectional Iterator/双向迭代器
forward_list的迭代器是Forward Iterator/前向迭代器
基于红黑树的set/multiset, map/multimap它们都是Bidirectional Iterator
基于hashtable的unordered_set, unordered_multiset, unordered_map, unordered_multimap的迭代器是双向的（Bidirectional Iterator）还是单向的（Forward Iterator），要看bucket对应的链表具体是双向链表还是单向链表。具体到STL应该是forward_iterator

根据分类自己打印各容器的迭代器类型字符串

利用c++本身typeid打印出迭代器类型

父类没有数据和函数，只有typedef。目的是为了让子类拥有这些别名，方便写代码

迭代器分类对算法的影响

distance：知道两个指针的距离，相当于两个指针相减。如果无法相减，只能循环

typename 的使用是为了指定 iterator_traits<_InputIterator>::difference_type 表示一个类型。iterator_traits<_InputIterator>::difference_type 是迭代器 _InputIterator 的差值类型（表示两个迭代器之间的距离），而 typename 在这里是为了明确告诉编译器这是一个类型而不是其他类型的标 识符

advance函数会根据iterator_category(__i)的类型选择调用不同的__advance的实现

容器迭代器的分类是基于对象（存在继承关系），而不是基于enum（枚举类型）

迭代器虽然有5种，但根据继承关系(子类is a 父类)，只要实现了父类，不需要5种都实现

copy会不断地做检查，检查是否为某种迭代器，决定copy是否要做某些操作来加速
traits区分赋值拷贝重不重要，如复数类，没有指针不重要

destroy和前面类似，不断细分类型。traits区分析构函数重不重要


unique_copy例子

算法是模板函数，可以接收任意类型的参数，语法没法指定传入的参数类型
因此在定义模板参数名称的时候，会命名（暗示）它想要接收的类型，比如下图，distance函数想要接收的是input iterator，而sort想要接收的是random access iterator，rotate函数想要接收forward iterator等等

算法源码剖析

C++标准库提供的algorithm需要符合如下接口

template<typename Iterator>
std::Algorithm(Iterator itr1, Iterator itr2, ...)
{
    ...
}

一般函数都有两个版本，第二个版本一般是允许增加一种原则或者操作，从而应用的更广泛

myobj是个函数对象，是myclass类，重载了()

for_each让范围里的所有元素都依次做同一件事情

replace：范围内的所有等于 old_value 的，都被 new_value 取代
replace_if：范围内所有满足 pred() 为 true 的元素都被 new_value 取代
replace_copy：范围内的元素全部 copy 到新地方，其中所有等于 old_value 的，都被替代为 new_value

count：在范围中计数值等于 value 的个数
count_if：在范围中计数满足条件 pred() 的个数
所有关联式容器自带成员函数 count()

find：在范围内找到值等于 value 的元素
find_if：在范围内找到满足 pred() 的元素
所有关联式容器自带成员函数 find()

所有关联式容器（（本身就排好序了）没有成员函数 sort()，array，vector，deque也没有
list、forward_list无法跳跃,因此只能使用自带sort

逆向迭代器，rbegin()使用end()，然后套用一个reverse_iterator适配器

二分查找是否存在目标元素（并不给予位置），使用前必须先排序；主要使用 lower_bound() 来找到能放入 val 的最低位置，再判断该元素是否存在

仿函数和函数对象

仿函数只为算法服务，提供一些特殊准则


GC++独有的仿函数

sort仿函数

STL中的每个仿函数都继承了binary_function<T, T, bool>,表示有两个操作数的操作，共3个模版参数，对应的还有unary_function，表示有1个操作数的操作（如否定）

如果希望自己写的仿函数可以修改，适配，融入stl，就需要继承上述两个结构之一因为adpat可能向functors提问上述三个别名

仿函数就是一个class里头的重载小括号，这样的class创建的对象就是函数对象/仿函数，因为做出来的是一个对象但像一个函数

存在多种Adapter

迭代器适配器（Iterator Adapters）：用于在不同迭代器之间进行转换或提供额外功能的适配器。例如，std::back_inserter、std::front_inserter、std::inserter 等。
函数适配器（Function Adapters）：用于在函数对象之间进行转换或提供额外功能的适配器。例如，std::bind、std::function 等。
容器适配器（Container Adapters）：提供不同接口的容器，例如，std::stack、std::queue、std::priority_queue 等

改造例子：stack 中将 deque 的 push_back 改名为 push

函数适配器

binder2nd

binder2nd是函数适配器之一，用于将一个二元操作函数（_Operation）和一个固定的值（__y）绑定在一起 —— 绑定第二参数

binder2nd类继承自unary_function，表示其为一元函数对象，其operator()用于执行绑定的操作

not1

bind

占位符 placeholders：
using namespace std::placeholders;
提供了 _1，_2，_3，·······
上面的的 _1 指的是被绑函数中的第一个参数

// functions
double my_divide(double x, double y)
{
	return x/y;
}

// function objects 测试与functions同理
// divides<double> my_divide;

struct MyPair
{
    // data members
	double a, b;
    // member functions
	double multiply()
	{
		return a*b;
	}
};

auto fn_five = bind(my_divide, 10, 2);
cout << fn_five() << endl; // 5.0

auto fn_half = bind(my_divide, _1, 2);
cout << fn_half(10) << endl; // 5.0

auto fn_invert = bind(my_divide, _2, _1);
cout << fn_invert(10, 2) << endl; // 0.2

//将 my_divide 的返回类型变为 int，即 int(x/y)
auto fn_rounding = bind<int>(my_divide, _1, _2); 
cout << fn_rounding(10, 3) << endl; // 3

MyPair ten_two {10, 2};  //定义一个实例ten_two
//绑定 member functions，由于成员函数有 this，所以 _1 就相当于 this，即 x.multiply()
auto bound_memfn = bind(&MyPair::multiply, _1);
cout << bound_memfn(ten_two) << endl; // 20

//把实例 ten_two 绑定到 a，即 ten_two.a
auto bound_memdata = bind(&MyPair::a, ten_two);
cout << bound_memdata() << endl; // 10

auto bound_member_data2 = bind(&MyPair::b, _1);
cout << bound_member_data2(ten_two) << endl;

迭代器适配器

reverse_iterator

对逆向迭代器取值，就是取其所指正向迭代器的前一个位置

inserter

对于 copy(InputIterator first, InputIterator last, OutputIterator result)，其会不管 OutputIterator 后是否有充裕空间，对 result 开始依次赋值
因此对=操作符重载，将iterator的赋值操作改变为insert操作，如上图下面部分

ostream_iterator

ostream适配器，因为是为了改造basic_ostream
用于将数据输出到输出流（ostream）。它是一个模板类，通常用于将容器中的元素输出到输出流，或者将其他可输出的数据类型输出到流中

将 copy 变为一个输出工具，分隔符是 ,
其核心依然是操作符重载，这样就相当于 cout<<*first; cout<<“,”;

istream_iterator

用于从输入流（istream）中读取数据。它是一个模板类，通常用于从输入流中读取数据到容器中，或者直接读取输入流中的数据
在创建 iit 的时候就已经把所有的键盘输入读进去了，之后就是一个一个取出来赋值给 value 的操作
++iit; 语句用于使 istream_iterator 前进到输入流的下一个元素。

copy和istream iterator适配器，对操作符进行重载，实现和cin的同步