侯捷STL学习(11)--算仿+仿函数+适配器

layout: post

title: 侯捷STL学习（十一）

date: 2017-07-24

tag: 侯捷STL

第三讲 标准库内核分析-算法

• 标准库算法形式

iterator分类

• 不同容器iterator类型不同
• 测试iterator类型

#include <iostream>     // std::cout
#include <iterator>     // std::iterator_traits
#include <typeinfo>     // typeid
namespace jj33
{
void _display_category(random_access_iterator_tag)
{   cout << "random_access_iterator" << endl; }
void _display_category(bidirectional_iterator_tag)
{   cout << "bidirectional_iterator" << endl; }
void _display_category(forward_iterator_tag)
{   cout << "forward_iterator" << endl;  }
void _display_category(output_iterator_tag)
{   cout << "output_iterator" << endl;   }
void _display_category(input_iterator_tag)
{   cout << "input_iterator" << endl;    }

template<typename I>
void display_category(I itr)
{
   typename iterator_traits<I>::iterator_category cagy;
   _display_category(cagy);
   
   cout << "typeid(itr).name()= " << typeid(itr).name() << endl << endl;   
       //The output depends on library implementation.
       //The particular representation pointed by the  
	   //returned valueis implementation-defined, 
	   //and may or may not be different for different types.   
}
	
void test_iterator_category()
{
	cout << "\ntest_iterator_category().......... \n";
  	
  	display_category(array<int,10>::iterator());
  	display_category(vector<int>::iterator());
  	display_category(list<int>::iterator());	
  	display_category(forward_list<int>::iterator());  
  	display_category(deque<int>::iterator());

  	display_category(set<int>::iterator());
  	display_category(map<int,int>::iterator());
  	display_category(multiset<int>::iterator());
  	display_category(multimap<int,int>::iterator());
  	display_category(unordered_set<int>::iterator());
  	display_category(unordered_map<int,int>::iterator());
  	display_category(unordered_multiset<int>::iterator());
  	display_category(unordered_multimap<int,int>::iterator());	  
	    	
  	display_category(istream_iterator<int>());
  	display_category(ostream_iterator<int>(cout,""));
}															 
}

           

• istream_iterator,ostream_iterator的iterator_category

iterator_category对算法效率的影响

• distance函数实现
• 对于连续空间直接相减，不连续空间需要重新计算
• type traits对算法的影响
• traits为萃取机，将iterator和type放进去，然后回答一些属性问题？
• 输入迭代器可读，输出迭代器可写。
• 算法模板参数输入名称，有时候暗示该算法输入的迭代器类型

算法源码剖析例子

• sort算法，区分C函数和STL库函数
• 本身遍历容器iterator就是有序的
• 算法accumulate
• 算法for_each
• 算法replace,replace_if,replace_copy
• 算法count,count_if
• 全局函数和成员函数的区别
• 算法find,find_if
• reverse iterator:rbegin(),rend()
• 算法binary_search
• 有序查找，红黑树是怎么查找的？

仿函数functions

• 仿函数只为算法服务
• GNU C++独有的，非标准；identity在set容器中取data
• 没有继承就没有融入STL体系
• 仿函数可适配的条件：继承
• STL规定每个adaptable function都挑选适当着继承
• 仿函数是个函数对象，用小括号创建临时对象，实现的是函数功能，但是封装为class;方便adater去修饰调整

适配器Adapter

• 改造器
• A用B的方法，两种方式：继承B或者内涵B
• adapter内涵仿函数，迭代器，容器实现
• 容器适配器
• stack,queue严格的是adapter;改造就是将一些函数重新封装，换名称
• 函数适配器：binder2nd
• 要问函数内部的参数类型及其返回值类型，就需要函数本身继承的calss回答，Operation::second_agrument 就由less内部继承的父类回答
• 已经更新用bind替换binder2nd；
• 函数适配器not1

新型适配器bind

• bind应用
• 迭代器适配器
• reverse_iterator适配器
• inserter适配器
• 不必担心目的地址是否有足够空间
• copy函数已经写好了，通过操作符重载实现安全的赋值操作
• ostream_iterator
• istream_iterator
• 实际当创建istream_iterator<>对象时已经再读入都一个数据了，这个时候就要求cin输入操作

C/C++基本语法学习

STL

C++ primer