(Boolan) STL与泛型编程第四周笔记(下)

1.C++标准库的算法,是什么东西?

从语言的层面讲,STL的算法都长下面两个样子:

template

Algorithm(Iterator itr1, Iterator itr2)

{

  //...

}

template

Algorithm(Iterator itr1, Iterator itr2, Cmp comp)

{

  //...

}

上面这两个东西是Function template(函数模板),一般情况算法都有两个版本,一个是两个参数的,一个是有三个参数的版本。 前面两个参数是两个迭代器,用来让算法知道需要操作的对象的范围,第三个参数是为了增加算法的弹性,用户可以在其中加上自己的准则,比如:sort函数,默认是从小到大排序,如果加上第三个参数(指定从大到小), 那么sort就会将数据按照指定的方式操作。

算法是看不见容器的,对其一无所知,一切信息都是从iterator中得到。 iterator就是算法和容器之间的桥梁。

1.1各种容器的iterators的iterator_category

STL中有五中iterator_category分别是:

struct input_iterator_tag{};

struct output_iterator_tag{};

struct forward_iterator_tag: public input_iterator_tag{};

struct bidirectional_iterator_tag: public forward_iterator_tag{};

struct random_access_iterator_tag: public bidirectional_iterator_tag{};

Array,Vector,Deque这三种容器支持随机访问,是连续空间(deque模仿出连续的假象),使用的是random_access_iterator_tag

list, set,map,multiset,multimap,都是关联性容器,不支持随机访问,使用的是bidirectional_iterator_tag

forward_list,unordered_set, unordered_map,unordered_multiset,unordered_multimap是单向连续性空间,不支持随机访问,使用的是forward_iterator_tag

istream ,ostream分别使用的是input_iterator_tag,output_inerator_tag

注:typeid(iter).name(),可以直接得到对象的类型名称

1.2iterator_category对算法的影响

使用distance函数求得一个容器begin和end之间的距离

template

inline iterator_traits::difference_type

distance(InputIterator first, InputIterator last)

{

  typedef typename iterator_traits::iterator_category category;

  return __distance(first, last, category);

}

当传入vector.begin()和vector.end()函数,通过萃取机iterator_traits得到他的iterator_category类型,然后去调用:

template

inline iterator_traits::difference_type

__distance(RandomAccessIterator first, RandomAccessIterator last, input_iterator_tag)

{

  return last - first;

}

因为连续空间的容器,所以直接首尾相减,就能得到距离,速度非常快

当传入的是list.begin()和list.end()函数,通过萃取机iterator_traits得到他的iterator_category类型,然后去调用:

template

inline iterator_traits::difference_type

__distance(InputIterator first, InputIterator last, input_iterator_tag)

{

  iterator_traits::difference_type n = 0;

    while(first != last)

    {

      ++first;

      ++n;

    }

  return n;

}

因为是非连续空间容器,所以只能通过迭代的方式,一个一个向后偏移得到距离。 速度很慢。

由此可以想象,不同的iterator_category对算法的影响是非常大的。 在算法中,会做非常多的检查,让算法使用正确的最快的迭代器分类去操作容器,使用STL其实是一件非常幸福的事情(想想c程序员。。。 )

2.仿函数

仿函数其实是一个类重载了()运算符,在STL中如下:

template

struct plus: public binary_function

{

  T operator () (const T& x, const T& y)

  {

    return x+y;

  }

}

在使用STL的算法时,可以使用函数来指定第三参数,也可以用仿函数指定,例如:

// 使用函数指定

bool myfunc(int i, int j)

{

  return i < j;

}

sort(myvec.begin(), myvec.end(), myfunc);

// 使用仿函数指定

template

struct less: public binary_function

{

  bool operator () (const T& x, const T& y) const

  {

    return x < y;

  }

}

sort(myvec.begin(), myvec.end(), less());

less()是一个临时对象,将其传入sort之后,sort会自动调用class less里头的operator (),就像调用函数一样(仿函数比函数更有弹性),因为仿函数可以被适配器修改。

如果我们自己写了一个仿函数,需要继承STL的两个类:

``

// 一个操作数继承

unary_functiontemplate < class Arg, class Result>

struct unary_function

{

typedef Arg argument_type;

typedef Result result_type;

};

// 两个操作数继承

binary_functiontemplate

struct binary_ function

{

typedef Arg1 fist_argument_type;

typedef Arg2 second_argument_type;

typedef Result result_type;

};

STL规定每一个Adaptable Function都要挑选适当的来继承,因为Function Adapter将会提问问题,例如:

template

class binder2nd: public unary_function

{

protected: Operation op;

// 这里就是function adapter在问问题

typename Operation::second_argument_type value;

public:

// ....

};

typename Operation::second_argument_type value;

这一句就是在问仿函数问题,你的第二个参数类型是什么,如果这一句可以编译通过,那么函数适配器就得到了仿函数的第二个参数类型,仿函数就可以被改造。

一个仿函数想要能被STL中的适配器改造,就需要继承适当的类融入STL。

3. Adapter

STL的算法可以让用户提供第三参数,用于给用户自定义算法处理数据的方式,上面讲述了可以使用仿函数作为第三参数,仿函数可以被适配器改造,下面就来看一下适配器是如何改造仿函数的。

3.1 bind2nd

以泛型算法count_if为例:

模板 < 类 InputIterator, 类谓词 > 类型 iterator_traits < InputIterator >::d ifference_type count_if (InputIterator 第一, InputIterator 最后, 谓词 pred) {类型

iterator_traits < InputIterator >::d ifference_type n = 0;for (; 首先是最后一个; + + 第一个) {if (pred (* 第一)) {+ n;}

} 返回 n;

} 在使用count_if时如下:

count_if (vi. 开始 (), vi. 结束 (), bind2nd (较少 < int > (), 40));bind2nd就是一个适配器,用于将仿函数less的第二参数绑定为40.

bind2nd源码如下:

模板 < 类操作, 类 T > 内联 binder2nd < 操作 > bind2nd (const 操作 & op, 常量 T & x) {typedef 类型操作:: second_argument_type arg2_type; 返回

binder2nd < 操作 > (op, arg2_type (x));}

在bind2nd中返回的是一个binder2nd类型的临时对象,bind2nd函数其实是一个中间层,因为binder2nd类模板不可以自动推导类型参数,只有模板函数可以,所以使用中间层给类模板指定模板参数Operation。

class binder2nd源码如下:

模板 < 类操作 > 类 binder2nd: 公共 unary_function < 类型操作:: first_argument_type, 类型操作:: result_type > {保护:

操作 op;类型操作:: second_argument_type 值;

public: binder2nd (const 操作 & x, 常量类型操作:: second_argument_type & y): op (x), 值 (y) {} 类型操作:: result_type 运算符 () (const

类型操作:: first_argument_type & x) 常量 {返回 op (x, 值);}

} 当在count_if中传入第三参数bind2nd (较少 < int > (), 40) 后, 先会调用bind2nd函数, 函数确定Operation 和 T的类型函数变成如下:

内嵌 binder2nd < 更少 < int > > bind2nd (恒少 < 国际 > & op, const int & x) {typedef 更少的 < int >:: second_argument_type arg2_type; 返回 binder2nd < 少 < 国际 > > (op, arg2 _

类型 (x));} 然后先让class binder2nd确定模板参数

类 binder2nd: 公共 unary_function < 较少 < int >:: fist_argument_type, 更少 < 国际 >:: result_type > {保护: 更少的 < 国际 > op; 更少的 < 国际 >:: second_argument_

类型值;公共: binder2nd (常量较少 < int > & x, 常量较少 < int >:: second_argument_type & y): op (x)、值 (y) {} 更少 < int >:: result_type 运算符 () (不小于 < int >:

: first_argument_type & x) 常量 {返回 op (x, 值);}

}

再在函数内部调用class binder2nd的构造函数,实例化一个binder2nd类型的临时对象,将less()和40分别记录在op和value里头。

最后count_if的第三个参数就得到一个binder2nd类型的临时对象,其中包涵了less和40,count_if函数变成如下:

加上vi是容器list的实例化 ptrdiff_t count_if (列表 < int >:: 迭代器第一, 列表 < int >:: 迭代最后, binder2nd pred) {ptrdiff_t n = 0; for (; 首先! = 尾页; + + 第一个) {if (pred (*

第一)) {+ + n;}

} 返回 n;

}

在count_if中调用pred这个仿函数时(pred就是binder2nd类型的临时对象的别名),会触发class binder2nd中的 operator(),在operator()中

op(x, 40);

40就被绑定到less()的第二参数上

这就是仿函数适配器的工作原理(真的非常的巧妙)。

3.2 inserter

当我们想用copy函数进行容器间的拷贝动作时,一种是提前将空间预留

int myints[] = {10, 20, 30, 40, 50, 60, 70};

vector myvec(7);

copy(myints, myints+7, myvec.begin());

提前预留空间是因为copy函数只是单纯的移动迭代器,向迭代器所指的地方插入数据,源码如下:

模板 < 类 InputIterator, 类 OutputIterator > OutputIterator 复制 (InputIterator 首先, InputIterator 最后, OutputIterator 结果) {而 (第一个! 最后一个) {结果 = * 第一;

++ 结果;首先为 ++;

} 返回结果;

}

假设我们的容器其中本来就有数据,没有预留空间,那么直接使用copy函数会造成一颗定时炸弹(越界访问),在这种时候就需要使用适配器来改造拷贝动作。

将copy的第三参数改写成迭代适配器:

copy(myints, myints+7, inserter(myvec, iter)); //iter为迭代器,指向容器内任意地方

inserter源码如下:

模板 < 类容器, 类迭代器 > 内联 insert_iterator < 容器 > 插入 (容器 & x, 迭代器 i) {类型容器: 迭代器 iter; 返回 insert_

迭代器 < 容器 > (x, iter (i));} inserter与bind2nd一样,也是一个辅助函数,帮助class insert_iterator确定模板参数.

类 insert_iterator源码如下:

模板 < 类容器 > 类 insert_iterator {保护: 容器 * 容器; 类型容器:: 迭代器 iter; public: typedef output_iterator_tag

iterator_category;

insert_iterator(Container& x, typename Container::iterator i)

    :container(&x), iter(i)

{ }

insert_iterator&

operator = (const typename Container::value_type& value)

{

    iter = container->insert(iter, value);

    return *this;

}

typename Container::iterator& operator ++ ()

{

    return ++iter;

}

};

inserter函数返回一个insert_iterator类型的临时对象,在这个临时对象中,容器myvec被记录到了容器指针container中,myvec的迭代器iter被记录到了临时对象中的的iter里,当copy函数在执行:

result = *first;

++result;

以上两个操作的时候,会触发class insert_iterator里的两个操作符重载函数。

这样copy函数从原来一个傻傻的,只会一个一个拷贝的底层函数,摇身一变成了一个智能的插入拷贝函数(C++技术相当奇妙,这就是操作符重载的好处)。

4. iostream iterator

标准库定义有提供给输入输出使用的 iostream iterator,称为istream_iterator 和 ostream_iterator,他们分别支持单个元素的读取和写入。

使用这两个迭代器需要包涵#include

4.1 ostream_iterator

ostream_iterator的使用方法如下:

将out_it绑定到cout输出设备 ostream_iterator < int > out_it (cout);

//将out_it绑定到cout输出设备, 并且在输出元素后加上一个字符串 ostream_iterator < int > out_it (cout, ",");

包括 < iostream >

包括 < 向量 >

包括 < 算法 >

包括 < 迭代器 >

使用命名空间性病;

int main () {向量 < int > vec; (int i = 0; 我 < 10; + + i) {vec. push_back (i);}

ostream_iterator < int > outit (cout, ",");

复制 (vec, 开始 (), vec. end (), outit);

返回 0;

}

4.2 istream_iterator

使用方法如下:

// 定义一个指向输入流结束位置的迭代器

istream_iterator eos;

// 定义一个指向标准输入的迭代器

istream_iterator iit(cin)

当 iit = eos时,说明流中的数据已经全部读取结束,操作iit让其加一,可以让迭代器指向下一个流中的数据

包括 < iostream >

包括 < 迭代器 >

using namespace std;

int main()

{

double value1, value2;

cout << "please insert two value: ";

istream_iterator eos;

istream_iterator iit(cin);

if(iit != eos)

{

    value1 = *iit;

}

++iit;

if(iit != eos)

{

    value2 = *iit;

}

cout << value1 << ' ' << value2 << endl;

return 0;

}

这里值得注意的是,当我们把

cout << "please insert two value: ";

写到

istream_iterator iit(cin);

后面

在执行程序的时候,我们发现,当输入第一个数字之后,cout这句输出才会被打印出来,造成这样的原因是,当定义了iit之后,其构造函数已经对iit加一,读取已经开始,所以cout的输出被放在后面。

注:

ifstream infile("./test/01.cpp");

istream_iterator eos;

istream_iterator iit(infile);

ofstream outfile("./2.cpp");

ostream_iterator out_it(outfile, " ")

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,393评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,790评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,391评论 0 330
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,703评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,613评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,003评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,507评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,158评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,300评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,256评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,274评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,984评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,569评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,662评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,899评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,268评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,840评论 2 339

推荐阅读更多精彩内容