Essential C++读书笔记- 泛型编程

3.1 指针的算术运算

容器
Vector - 连续的存储块
List - 双向链表构成的存储块

考虑要实现一种通用的查找容器的方法find

3.1.1 Step 1 我们要实现一个vector<int>容器的元素查找

很容易实现,find 函数中轮询vector里面所有元素,找到就返回

int* find(const vector<int> &vec, int value)
{
    for( int ix = 0 ; ix < vec.size(); ++ix)
    {
        if (vec[ ix ] == value)
        {
            return &vex[ ix ];
        }
    }

    return std::nullptr;
}

3.1.2 Step 2 实现任意类型的vector元素的查找

这个时候我们引入了模板函数

template<typename elemType>
elemType* find(const vector<elemType> &vec, 
                const elemType& value)
{
    for( int ix = 0 ; ix < vec.size() ; ++ix)
    {
        if ( vec[ix] == value)
        {
            return &vec[ix];
        }
    }

    return std::nullptr
}

你可以用这个函数查找任何诸如vector<float>之类的容器了

3.1.3 Step 3 我要用同一个函数来实现数组的查找,可行么?

这个时候vector要在find函数里面不可见,所以我们想到了指针

template<typename elemType>
elemType* find(const elemType *array, int size,
                const elemType& value)
{
    if ( ! array || size < 1 )
    {
        return 0;
    }

    for ( int ix = 0 ; ix < size ; ++ix )
    {
        if ( vec[ix] == value )
        {
            return &vec[ix]
        }
    }

    return std::nullptr;
}

如果是数组,我们只要传递数组的首地址即可;如果是vector,只要传递容器中数据的首地址也能做到

3.1.4 Step 4 如果我现在还要是先list的查找呢

那就有点困难了,因为list底层是一个链表结构,不是连续内存,find函数这个时候就失效了。

3.2 了解Iterator

简单来说Iterator也是一组类,但是却可以实现和指针相同的语法,也提供内置的运算符操作(*, !=, ++ )。
那么我们怎么样来定义这样的一个迭代器类型呢?我们可能有vector<xxx>,有list<xxx>,怎么来进行区分?
标准库中是这么来定义的,

std::vector<std::string> svec;
std::vector<std::string>::iterator iter = svec.begin();

这里的iter指向vector<string>容器的第一个元素,我们前面说了你可以把它当成指针来用,比如说取第一个string的内容:*iter;指向下一个元素;iter++
这样,看来我们就能解决前一节中的最后一个问题了

template<typename IteratorType, typename elemType >
IteratorType find(IteratorType first, IteratorType last, 
                const elemtType &value)
{
    for (; first != last; ++first)
    {
        if(*first == value)
        {
            return first;
        }
    }
    return last;
}

这个时候,如果你要查找的是一个数组你可以这么写

    const inst asize = 8;
    int ia[ asize ] = { 1, 1, 2, 3, 5, 8, 13, 21};

    int* pia = find( ia, ia+asize, 1024);

vector可以这样

    vector<int> ivec;
    vector<int>::iterator it(ia, ia + asize); 
    it = find(ivec.begin, ivec.end(), 1024);

list可以这样

    list<int> ilist;
    list<int>::iterator iter(ia, ia + asize);
    iter = find(ilist.begin(), ilist.end(), 1024);

看样子大功告成了。

常用的泛型算法

  • 搜索算法: find(), count(), etc;
  • 排序及次序整理算法:merge(), sort(), reverse(), etc;
  • 赋值、删除、替换算法:copy(), remove(), swap(), etc;
  • 关系算法:equal(), include();
  • 生成(generation)与质变(mutation)算法: fill(), for_each(), generate(), transform();
  • 数值算法:accumulate(), partial_sum();
  • 集合算法:set_union(), set_difference()

3.3 顺序型容器

容器 实现机制 优点 缺点 适用场景
vector 连续存储结构,类似于数组 随机访问效率高 随机位置插入或删除元素效率低 高效的随机存取,没有大量插入删除操作的场景
list 双向链表结构 高效的随机插入删除操作 随机访问效率低下,需要维护额外指针 有大量的插入和删除,不关心随机存取
deque 连续存储结构;不同于vector的是提供了两级数组结构,一级和vector一样,另一级维护容器首地址 随机访问方便;方便的插入和删除操作;两端进行push和pop 占用内存多 即需要随机存取,又关心两端数据的插入删除

3.5 设计一个泛型算法(Generic Algorithm)

3.5.1 从问题开始

Step1, 我需要设计一个算法,输入是一个vector<int>,输出是一个新的vector,包含了原vector中所有小于10的值。
很容易做到,

std::vector<int> less_than(std::vector<int>& vec, int level)
{
    std::vector<int> nvec;
    for( int ix = 0; ix < vec.size(); ++ix)
    {
        if(vec[ix] < level)
        {
            nvec.push_back(vec[ix]);
        }
    }
    return nvec;
}

Step 2, 现在我们增加一些难度,允许用户指定不同的操作,比如说过滤大于一个值的元素,或者过滤等于一个值的元素。
一种解决的办法就是,增加第三个参数,一个函数指针,这第三个入参就是用户可以指定的操作,

vector<int> filter_ver1(const vector<int>& vec, 
                    int filter_value,
                    bool (*pred)( int, int))
{
    vector<int> nvec;

    for( int ix = 0 ; ix < vec.size(); ix++)
    {
        if(pred(vec[ix], filter_value))
        {
            nvec.push_back(vec[ix]);
        }
    }

    return nvec;
}

这个时候用户可以自己定义小于操作

bool less_than(int a, int b)
{
  return a < b ? true : false;
}

3.5.2 函数对象

函数对象实际上是某种类的实例对象,这种对象对函数调用运算符()进行了重载操作,而这个时候运算符()重载函数通常是inline的,从效率上来说要优于函数指针。
标准库定义了很多函数对象

对象分类 具体运算
算术运算 plus<type>, minus<type>, negate<type>, multiplies<type>, divides<type>, modules<type>
关系运算 less<type>, less_equal<type>, greater<type>, greater_equal<type>, equal_to<type>, not_equal_to<type>
逻辑运算 分别对应||, &&, !操作,logical_and<type>, logical_or<type>, logical_not<type>

我们来看一个使用这些运算符的例子,加入说我要对一个vector里的元素以降序排序,我们可以这么来写

#include <functional>
sort( vec.begin(), vec.end(), greater<int>());
  • 前两个参数标记范围;
  • 第三个参数告知操作;

3.5.3 函数对象适配器(Function Object Adapter)

我们再回到我们要实现这个泛型算法filter,我们可以使用标准库中使用的这些函数对象了,
Step 3, 使用标准库提供的函数对象less<int>来作为filter的第三个入参,
除此之外我们还希望用函数find_if来替代原来用for循环遍历整个vector的方式,但是我们知道find_if的第三个入参(用来作为查找条件的)应该是一个一元操作函数对象,只接受一个输入参数;但我们这里的sort函数是一个二元操作函数对象,那我们该怎么实现?


std::vector<int> filter(std::std::vector<int>& vec, int val, less<int>& lt)
{
    std::vector<int> nvec;
    
    std::vector<int>::const_iterator iter = vec.begin();
    while(( iter = 
                find_if(iter, vec.end(), 
                    bind2nd(lt, value)) != vec.end())
    {
        nvec.push_back(*iter);
        iter++;
    }
    return nvec;
}

这个时候就引出了本节所要介绍的一个新东西了,叫函数对象适配器,这个适配器会对普通的函数对象进行修改,来满足用户所需。
比如说这个例子里用到的绑定适配器(binder adapter)可以将函数对象的参数绑定到一些特定值,这样我们的二元操作符sort就可以变成我们所需的一元的了。

NOTE: C++11以后引入了std::bind函数,使得适配器操作起来更加灵活

Step4, 消除filter()与vector的元素类型,让我们的泛型算法更加通用
使用模板函数,

template<typename InputIterator, typename OutputIterator
        typename ElemType, typename Comp>
OutputIterator filter(InputIterator first, InputIterator last, 
                OutputIterator at, ElemType& val, Comp pred)
{
    while((first = find_if(first, last, bind2nd(pred,val))) != last)
    {
        *at++ = *first++;
    }
    return at;
}
  • 首先,要消除filter的返回值类型vector<int>,如前所述的,我们只能返回迭代器;这里定义了返回值迭代器类型OutputIterator;
  • 然后,消除第一个入参的类型vector<int>,也使用迭代器来标记过滤的范围;
  • 之后,加一个参数at,标记filter的结果保存的目的地址;
  • 接着是查找对象以及区别算法的定义。

NOTE: 后面章节中有另一种解决方法,叫做插入迭代器适配器(insert iterator adapter)

这里还要介绍另外一种迭代器,交租哦negator,它会对函数对象的true/false值取反。

3.9 如何使用Iterator Inserter

3.9.1 笨一点的调用泛型算法filter的方法

我们再回到3.5节中最后实现的filter函数,用户使用这个函数的时候,可以这么来做,

void main()
{
    int ia[5] = {1, 4, 2, 0, 9, 8};
    std::vector<int> ivec( ia, ia+5 );

    std::vector<int> ovec(5);

    filter(ivec.begin(), ivec.end(), ovec.begin(), 3, greater<int>());
}

上述的程序中,由于filter函数内部是直接给目标容器的迭代器进行赋值操作,所以调用的时候,需要满足如下的这些条件

  • 预先定义目标容器必须足够大,这样才足以填充filter函数中的每个过滤出来的结果;
    也就是说我们可能需要定义一个和源容器一样大的目的容器,预留足够的空间,这个显然是会带来内存空间的浪费的。

那么我们可不可以定义一个空的容器呢?我们知道,进行赋值操作(assignment)的时候,容器并不会自动扩容,也就是空的容器会一直保持为空,这样调用的时候必然会报错;
那么我们可不可以使用类似push_back这样的操作来替换赋值操作呢?这样的话,我们就不需要定义一个固定大小的目标容器了,答案是有的,这就是所谓的迭代器插入适配器(insertion adapter),

Insertion adapter 目的 入参 使用方法
back_inserter() 以容器的push_back替换赋值操作 目标容器 unique_copy ( ivec.begin, ivec.end, back_inserter(result_vec) )
inserter() 以容器的inserter函数替换赋值操作函数 一个是目标容器,一个是迭代器指向要插入的起点 unique_copy ( ivec.begin, ivec.end, inserter(vec, vec.end()) )
front_inserter() 以容器的push_front()函数替换赋值操作 目标容器 只适用list和deque,copy(ilist.begin(), ilist.end(), front_inserter( ilist_clone ))

3.9.2 借助Iterator Inserter之后的聪明方法

借助back_inserter,

filter(ivec.begin(), ivec.end(), back_inserter(ovec), 3, greater<int>());

3.10 使用iostream iterator

这节首先我们考虑要实现一个新的问题,

  • 从标准输入读取字符,保存到一个vector容器中;
  • 然后进行排序;
  • 然后通过标准输出到设备上;

3.10.1 首先还是笨点的办法

很容易理解,标准输入都进来,写入text,然后排序,然后写出去,

int main()
{
    std::string word;
    std::vector<std::string> text;

    while (std::cin >> word)
    {
        text.push_back(word);
    }

    std::sort(text.begin(), text.end());

    for (int ix = 0; ix < text.size(); ix++)
    {
        std::cout << text[ix] << std::endl;
    }
}

3.10.2 借助标准库的iostream迭代器的聪明方法

这里用到了iostream迭代器

  • 首先我们考虑使用copy算法,源是cin,目的是text;
  • copy算法也有三个入参,前两个是源的范围(类似指针的范围);最后一个是text,这里我们借助back_inserter来把copy内部的赋值操作转换成了push_back操作;
  • 然后是输出,定义一个ostream_iterator,用于作为copy的目的;
int main()
{
    std::istream_iterator<std::string> is(std::cin);
    std::istream_iterator<std::string> eof;

    std::vector<std::string> text;
    std::copy(is, eof, std::back_inserter(text));

    std::sort(text.begin(), text.end());

    std::ostream_iterator<std::string> os(std::cout, " ");
    std::copy(text.begin(), text.end(), os);
}

3.10.3 来看看上述第二种方法带来的妙用吧

假如说这个时候我又有新的需求,不再从标准输入读入,从标准输出写出;而是要从文件读入,文件写出,该怎么做?
很简单,只要做到如下两点

  • istream_iterator绑定到ifstream对象
  • ostream_iterator绑定到ofstream对象
    这就大功告成了
int main()
{
    std::ifstream in_file("in.txt");           // 新建ifstream和ofstream
    std::ofstream out_file("out.txt");

    std::istream_iterator<std::string> is(in_file);   // in_file替换std::cin
    std::istream_iterator<std::string> eof;

    std::vector<std::string> text;
    std::copy(is, eof, std::back_inserter(text));

    std::sort(text.begin(), text.end());

    std::ostream_iterator<std::string> os(out_file, " ");  // out_file替换std::cout
    std::copy(text.begin(), text.end(), os);
}

这就是泛型带来的优势,一套代码,满足你各种需求。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念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

推荐阅读更多精彩内容