C++ Primer(四)_标准库_泛型算法

目录

• 泛型算法
  • 依赖
  • 根据行为分类——当然只是书上的出现的
  • 迭代器模板——<iterator>

泛型算法

算法永远不会改变容器大小——但是插入迭代器会产生这种行为，而算法是不知道的，仅通过迭代器操作数据

依赖

• 算法输入的是迭代器，不依赖与容器类型
• 但是依赖于所操作元素类型定义的操作——要么是==，要么是<

根据行为分类——当然只是书上的出现的

只读算法

都是左闭右开的区间 find(b, e, val) 找到的第一个val的迭代器；未找到返回e，依赖operator== count(b, e, val) operator== accumulate(b, e, val) val为求和初值，依赖元素的operator+；<numeric> 接受单一迭代器表示一个序列的都作了后一个序列比至少和前一个一样长的假设 equal(b1, e1, b2) 返回bool

写算法——大坑，写到普通迭代器且没分配空间，Boom

插入迭代器避免插没空间的，它的赋值操作被重载为容器的insert操作

获取方法auto back_it = back_inserter(b);

void fill(b, e, t) b到e的区间填充t fill_n(b, n, t) 向b开始写n个t 拷贝算法——向目的迭代器输出 多数改变原序列的算法都有拷贝版本 copy(b1, e1, b2) 返回拷贝的最后一个元素的后一个迭代器 replace(b, e, t1, t2) 区间内的t1全部用t2替换 replace_copy(b1, e1, b2, t1, t2) 原序列不变，替换结果拷贝到b2序列 unique_copy(b1, e1, b2) 记得unique是要同值元素相连的

重排算法

sort(b, e) 有sort(b, e, cmp)版本 unique(b, e) 返回最后一个不重复的值后一迭代器，并不删除元素，只是覆盖了；后面的值不确定是什么 stable_sort(b, e) 稳定排序 partition(b, e) true在前，false在后，返回最后一个true的后一迭代器

定制算法比较操作

• 函数指针

• lambda——解决谓词有限问题

• bind——占位符所在命名空间std::placeholders::

  using namespace std::palceholders;
  
  void f(a1, a2, a3, a4, a5);
  auto g = bind(f, a, b, _2, c, _1);    // 占位符表示的是在g里形参列表的位置    使用的拷贝
  // g(X, Y) 相当于 f(a, b, Y, c, X)

  当需要绑定的对象无法拷贝时，可以使用ref(), cref()获取可拷贝的对象，对象里保存着不可拷贝对象的引用

迭代器模板——<iterator>

插入迭代器——赋值操作被重载为插入行为

• 获取方式——一些函数

返回相应行为迭代器 返回值类型 back_inserter(container) 需要容器支持push_back back_inserter_iterator front_inserter(container) 支持push_front front_inserter_iterator inserter(container, p) p为插入位置 inserter_iterator

• 操作

  it为迭代器 it = t 根据迭代器类型，调用所绑定容器的.push_back, .push_front, .insert it ++ 以下操作无任何意义 it -- *it

流迭代器——>>和<<被重载为流上行为

输入流

懒惰求值：绑定后不立即取值，只保证第一次解引用肯定从流读取了

目的：避免迭代器没用或多个迭代器绑定流产生数据丢失或一些奇怪现象；

istream_iteratoe<T> in(is) 从cin流读取T类型元素 istream_iterator<T> end 不指定流，可做尾后位置用 in1 == in2 判断绑定的流是否相同；如果T不同直接不能过编译:?? in1 != in2 *in 从流取值 in++, ++in 元素类型定义的>>从流读取下一个值 in->mem 取T元素成员mem

输出流

ostream_iterator<T> out(os) ostream_iterator<T> out(os, str) str相当于分隔符，每写入一个T对象，就写一个str out = val 用<< 把val写入流，类型要相符（隐式类型转换是OK的） *out, out ++, ++ out 无意义操作，返回out

反向迭代器——++和--被重载为与普通迭代器相反的行为

很自然的，反向迭代器需要原容器或迭代器有--操作

• 获取方式
  • 直接从容器拿：.rbegin()……
  • 从支持--的迭代器初始化：reverse_iterator(it)
• 操作——和原来的迭代器一样，只是++和--反了
• 获取普通迭代器
  • .base()：得到普通迭代器++方向的下一个位置迭代器
• ！！！反向迭代和普通迭代的范围是不一样的，但仍形成一个rbegin闭，rend开的区间

移动迭代器——解引用返回的是右值引用

• 获取：make_move_iterator()
• 配合uninitialized_copy(b, e, f); // 提高“拷贝”效率