C++笔记九（STL与泛型编程）

本周内容
（1）迭代器的分类（category）
（2）迭代器分类对算法的影响
（3）STL算法
（4）仿函数/函数对象
（5）Adapter
（6）binder2nd and not1
（7）bind
（8）reverse_iterator、inserter、ostream_iterator、istream_iterator

• 从语言层面讲：
  • 容器Container是个class template
  • 算法Algorithm是个function template
  • 迭代器Iterator是个class template
  • 仿函数Functor是个class template
  • 适配器Adapter是个class template
  • 分配器Allocator是个class template

Algorithm看不见Container，对其一无所知；所以，它所需要的一切信息都必须从Iterators取得，而Iterators（Containers供应）必须能够回答Algorithm的所有提问，才能搭配该Algorithm的所有操作。

一 迭代器的分类

//五种iterator category
struct input_iterator_tag{ };
struct output_iterator_tag{ };
struct forward_iterator_tag;public input_iterator_tag{ };
struct bidrectional_iterator_tag;public forward_iterator_tag{ };
struct random_access_iterator_tag;public bidrectional_iterator_tag{ };

五种iterator的关系如下：

iterator_category.png

• 每个容器的iterator_category分别为：
  • array： random_access_iterator
  • vector： random_access_iterator
  • list： bidrectional_iterator
  • forward_list： forward_iterator
  • deque： random_access_iterator
  • set： bidrectional_iterator
  • map： bidrectional_iterator
  • multiset： bidrectional_iterator
  • multimap： bidrectional_iterator
  • unordered_set： forward_iterator
  • unordered_map： forward_iterator
  • unordered_multiset： forward_iterator
  • unordered_multimap： forward_iterator
  • istream： input_iterator
  • ostream： output_iterator

二 迭代器分类对算法的影响

• 以copy为例，通过迭代器的分类和迭代器萃取机的分类，对于某些分类有特化版本，直接调用低阶动作函数速度极快，针对不同分类采取不同策略，这样对于代码效率提高是有好处的。

  
  iterator_category和type_traits对算法的影响.png

• 算法源码中对iterator_category的暗示：通过写出一些明显的类型名称如下红色部分

  
  算法源码中对iterator_category的暗示.png

三 算法

• qsort（快速排序）,bsearch(二分法搜寻）这是C的函数；count_if（返回在[first, last)范围内满足特定条件的元素的数目）,find（查找）,sort（排序）是C++标准库提供的算法。
  因为他们接口满足如下:

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

• accumulate：用来计算特定范围内（包括连续的部分和初始值）所有元素的和，除此之外，还可以用指定的二进制操作来计算特定范围内的元素结果。
• for_each：用于逐个遍历容器元素，它对迭代器区间[first，last)所指的每一个元素，执行由单参数函数对象f所定义的操作。

//range-based for statement since C++11
for( dec1:coll ) {
    statement
}
for( int i : {2,3,4,5,3,23,424,5} ){
    cout << i << endl;
}

• replace：所有容器适用
  replace： 范围内所有等同于old_value者都以new_value取代
  replace_if：范围内所有满足pred()为true之元素都以new_value取代
  replace_copy：范围内所有等同于old_value者都以new_value放至新区间

• count：用于统计某一值在一定范围内出现的次数
  count_if：返回在[first, last)范围内满足特定条件的元素的数目

  • 容器不带成员函数count()：array,vector,list,forward_list,deque
  • 容器带有成员函数count()：set/multiset，map/multimap，unordered_set/unordered_multiset,unordered_map/unordered_multimap

• find：返回区间[first，end）中第一个值等于value的元素位置；若未找到，返回end。函数返回的是迭代器或指针，即位置信息。
  find_if：返回区间[first，end)中使一元判断式pred为true的第一个元素位置；若未找到，返回end。

  • 容器不带成员函数find()：array,vector,list,forward_list,deque
  • 容器带有成员函数find()：set/multiset，map/multimap，unordered_set/unordered_multiset,unordered_map/unordered_multimap

• sort：对给定区间所有元素进行排序

  • 容器不带成员函数count()：array,vector,deque, set/multiset，map/multimap，unordered_set/unordered_multiset,unordered_map/unordered_multimap
  • 容器带有成员函数count()：list,forward_list

• reverse iterator是一种反向遍历容器的迭代器

  
  reverse iterator.png

• binary_search二分查找法，之前一定要先排序，调用的是lower_bound,与之相对应的有upper_bound,差别如下图：

  
  lower_bound and upper_bound.png

四 仿函数/函数对象

• 仿函数或者说函数对象就是里面对（）作重载的一种类。

• 仿函数functors的可适配条件是，继承unary_function或者binary_function：

  
  functors可适配条件.png

五 Adapters

• adapter需要回答算法提出的五个问题和仿函数提出的三个问题来确定参数类型，编译通过表示回答完毕。

  
  adapter.png

六 Binder2nd and not1

• bind2nd辅助函数的价值是它是一个函数模板，会帮使用者作参数推导，比直接使用binder2nd需要知道operator的类型要方便。
• 函数或者函数对象必须能够回答三个问题（上述已提），才能和adapter完美搭配。

• typename的作用是当编译器运行到operation::second_argument_type时犹豫不决不知道什么类型时让它通过。

  
  binder2nd.png
  

  not1和bind2nd类似：

  
  not1.png

七 新型适配器bind（since C++11）

std::bind可以绑定：
（1）functions
（2）function objects
（3）member functions，_1（占位符号）必须是某个object地址。
（4）data members，_1必须是某个object地址。
返回一个function object ret。调用ret相当于调用上述1,2,3，或相当于取出4。

新版本代替了很多旧版本的东西，如下图：

bind.png

八 reverse_iterator、inserter、ostream_iterator、istream_iterator

下面介绍几种典型的适配器，这些适配器类似得对算法（例如copy）作了符号重载，使得同一个函数能够有不同的解读，这非常巧妙。

• 下面两图是迭代器适配器：

  
  reverse_iterator.png

inserter.png

• 下面两图是X（未知类型）适配器，：

  
  ostream_iterator.png

istream_iterator.png

下图是istream_iterator另一个例子，当使用者打出例2的代码，因为其实第一行已经有输入了，若是在下一行写入提示代码（“请输入”），则这一行提示代码不会出现，使得使用者会大吃一惊，需要注意！

istream_iterator.png