C++笔记-泛型编程

2017-04-05

　　STL是一种泛型编程.面向对象编程关注的是程序的数据方面,而泛型编程关注的是算法.泛型编程旨在编写独立于数据类型的代码.在C艹中通常使用的工具是模板,模板是的能够按照泛型定义函数和类,而STL通过通用算法更近了一步.

为何使用迭代器

　　模板使得算法独立于存储类型,而迭代器使算法独立于使用的容器类型.所以他们都是STL通用方法的组成部分.

　　如果在一个double数组中搜索特定值可以这样写:

double * find_ar(double * ar, int n, const double & val)
{
    for(int i = 0; i < n; i++)
    if(ar[i] == val)
        return &ar[i];//如果在数组中找到val则返回val在数组中的地址;
    return nullptr;   //否则返回一个空指针
}

　　在这里我们基于了特定的数据结构(数组)可以使用模板来将这种算法推广到包含==运算符的任意类型的数组.
　　不过我们也可以使用链表:

struct Node
{
    double item;
    Node * p_next;
}

　　假设有一个指向链表第一个节点的指针,每个节点的p_next都指向下一个节点,链表最后一个节点的p_next被设置为nullptr…则可以这么写:

Node * find_ll(Node * head,const double & val)
{
    Node * start;
    for(start= head; start!=nullptr; start = start->p_next)
        if(start->item == val)
            return start;
    return nullptr;
}

　　他俩一个使用数组,一个将start重置为start->p_next,广义上他们都一样:将值于容器中的值比较,直到找到匹配为止.但在这里我们基于了特定的数据结构(链表)
　　而泛型编程旨在使用同一个find函数来处理数组,链表,或其他容器类型.函数不仅独立于容器中储存的类型,而且独立于容器本身的数据结构.模板为我们提供了存储在容器中的数据类型的通用表达,所以我们还需要遍历容器中的值的通用表达.而迭代器正好是干这活的…
　　要实现find函数,我们的迭代器应该具备以下特征: 　　

应能够对迭代器执行解引用操作,一边能够访问他引用的值,即如果p是个迭代器,则能对*p进行定义;
应能够将一个迭代器赋值给另一个.即如果p和q是迭代器.则能够对p=q进行定义;
应能够使用迭代器遍历容器中的所有元素,这可以为迭代器定义++p和p++来实现;
应能够将一个迭代器和另一个迭代器进行比较,看他们是否相等.即如果p和q都是迭代器则能对p==q和p!=q进行定义

　　对于find函数来讲,有上述功能就够了,STL按照功能的强弱定义了不同等级的迭代器.另外常规指针就能满足迭代器的要求,可以使之接受两个指示区间的指针参数,其中一个指向数组的起始位置另一个指向数组的超尾;并且如果我们的函数没找到指定的值,那么让他返回尾指针,因此可以这样重写find_ar():

typedef double * iterator;
iterator find_ar(iterator begin,iterator end,const double & val)
{
    iterator ar;
    for(ar = begin; ar!=end; ar++)
        if(*ar == val)
            return ar;
    return end;
}

　　对于find_ll()函数,可以定义一个迭代器类,其中定义了运算符*和++;

struct Node{
    double item;
    Node * p_next;
}
class iterator {
    Node * pt;
public:
    iterator() : pt(nullptr){}
    iterator(Node * p) : pt(p){}
    double operatror*(){return pt->p_next;}
    iterator & operator++(){ //++pt
        pt = pt->p_next;
        return *this;
    }
    iterator & operator++(int){ //int表示后缀版++运算符,该int参数永远不会用到只做区分
        iterator temp = *this;
        pt = pt->p_next;
        return temp;
    }
    //你就假装我这里重载了==和!=
}

　　废了这么大劲之后,我们的find函数改就可以这样写:

iterator find_ll(iterator head, const double & val)
{
    iterator start;
    for(start = head; head!=0; ++start)
        if(*start = val)
            return start;
        return nullptr;
}

　　机智的你一定发现了我这不学好的一天净扯淡: 这踏马不废话么这俩玩意(函数)一毛一样啊,差别就是find_ar用了超尾.find_ll返回的是nullptr啊..其实我们还可以让链表的最后一个元素后面还有个空白元素..这样链表也有了超尾.他们俩就成了真·一个(功能的)算法;

//我是第一个分割线↓

　　前面的废话都是为了下面的废话做铺垫的:

　　STL其实就是遵循上面的方法.首先每个容器类(vector, list等)定义了相同的迭代器类型,对于其中的某个类,迭代器可能是指针;但对于另一个类,迭代器可能是对象.但他们都将提供列如 * 和++等这样的操作.其次每个容器类都有个超尾标记,当迭代器递增到容器最后一个值的后面的时候把这个值赋值给迭代器.每个容器类都有begin()和end()方法,begin返回指向第一个元素的迭代器,end返回一个指向超尾的迭代器.每个容器类都有++操作用来遍历容器 ~~尽是废话~~

　　使用迭代器的时候不用管他是咋实现的..知道咋用就成(~~如果你碰到需要自己定义迭代器的情况当我放屁~~):~~观众: 你智障吧废话谁踏马不会用这玩意~~
　　哎呦你咋知道的…没错我就是智障.在知道了迭代器大概是咋构造的之后的我们可以更加自信满满的~~并没有~~雄赳赳气昂昂跨..啊不..写出迭代器:

1
2
3

vector<double>::iterator pr; //这玩意是输出vector<double>里的元素
for(pr = sco.begin(); pr != sco.end(); pr++)
    cout << *pr << endl;

这里本萌妹使用了C艹11,做一个炫酷的紧跟潮流个屁的智障:

1 2	for(auto pr = sco.begin(); pr != sco.end(); pr++) cout << *pr << endl;

作为一种编程风格,最好直接使用STL函数来处理细节,如for_each(),或C艹11的迷之基于范围的for循环:

1	for(auto x: sco) cout << x << endl;

迭代器类型

　　STL定义了五中迭代器,分别是: 输入迭代器,输出迭代器,正向迭代器,双向迭代器,随机访问迭代器;他们都可以执行解引用操作

输入迭代器：

　　从程序的角度来说,即来自容器内部的讯息被视为输入,因此输入迭代器可被程序用来读取容器中的信息,但不一定能让程序修改容器里的值.
　　输入迭代器必须能访问容器中所有的值(废话),可以通过++运算符来实现(废话).但输入迭代器并不保证第二次遍历容器时顺序不变,另外当迭代器被递增后,也不保证先前的值可以被解引用.基于输入迭代器的算法都应该是单通行(single-pass)的,输入迭代器是单项迭代器,可以递增,但不能递减.

输出迭代器:

　　输出指的是将信息从程序传输给迭代器,因此程序的输出就是容器的输入,和输入迭代器差不多,他只能够解引用让程序能修改容器的值,也就是只能写,而不能读.
　　对于单通行,只读算法可以使用输入迭代器,对于单通行,只写算法,则可以使用输出迭代器. 　　

正向迭代器:

　　正向迭代器与输入输出迭代器不同的是,他总是按照相同的顺序遍历一系列值.另外正向迭代器递增后仍可以怼前面的迭代器值解引用,并得到相同的值.
　　既可以读写又可以只读:

1 2	int * pirw; //读写 const int * pir;//只读

双向迭代器:

具有正向迭代器全部特征,并且支持(前后缀)递减运算符;

随机迭代器:

具有全部双向迭代器的特征,并且能够根据要求直接跳到容器中任何一个元素;

概念,改进和模型(完全不知道书上在说啥)

~~下面是咬文嚼字时间~~

　　迭代器是一系列要求,而不是类型.STL算法可以使用任何满足要求的迭代器所实现,STL术语叫概念(concept)来描述一系列要求.概念可以具有继承的关系,例如双向迭代器继承了正向迭代器的功能,然而不能将继承机制用于迭代器: 假设我们将双向迭代器实现为一个常规指针,而指针属于C++内置类型,不能从派生而来.但从概念上将他确实能够继承.所以有些STL文献使用术语改进(refinement)来表示这种概念上的继承.so,双向迭代器是正向迭代器概念的一种改进.而概念的具体实现叫做模型(model).

将指针用于迭代器

　　迭代器是广义指针,指针满足所有迭代器要求,因此STL算法可以使用指针来对基于指针的非STL同期进行操作其实就是可以将STL用于数组…..

1
2
3

const int SIZE = 100;
double Rec[SIZE];
sort(Rec,Rec+100);

　　sort()函数接受指向容器第一个元素的迭代器和指向超尾的迭代器作为参数.Rec或&Rec[0]是第一个元素的地址,Rec+SIZE是最后一个元素后面的元素的地址;由于指针是迭代器,而算法是基于迭代器的,所以可将STL算法用于常规数组.
　　假设要把信息输出到显示器上,可以使用一个表示输出的迭代器则可以使用copy();STL有一个ostream_iterator模板是输出迭代器的一个概念模型:

1
2
3

#include <iterator>
...
ostream_iterator<int,char> out_iter(cout," "); //注意这双引号里有个空格

　　out_iter是个接口,能够使用cout来显示信息,第一个模板参数指出被发送给输出流的数据类型,第二个参数(car)值出了输出流使用的字符串类型;
　　将copy()用于迭代器:

copy(dice.begin(),dice.end(),out_iter);
//这意味着将dice容器整个区间复制到输出流中,即显示容器里的内容
//也可以直接构建个匿名的迭代器:
copy(dice.begin(),dice.end(), osteram_iterator<int,char>(cout," "));

　　这样用表示将由15和空格组成的字符串发送到cout的输出流中:

1	*cout_iter++ = 15; // 和 cout << 15 << " "; 一样

　　有输出就有输入,可以用俩isteram_iterator模板对象来定义copy()的输入范围,如下,isteram_iterator的第一个参数(int)是指出要读取的数据类型,第二个参数指出输入流使用的字符串类型(char),构造函数参数cin意味着使用由cin管理的输入流,构造函数参数为空则表示输入失败:

1 2	copy(istream_iterator<int,char>(cin), istream_iterator<int,char>(), dice.begin() ); //从输入流中读取,直到失败;

下面的代码演示了如何使用copy和istream迭代器以及反向迭代器:

#include<iostream>
#include<iterator>
#include<vector>
using namespace std;
int main()
{
    using namespace std;
    
    int casts[10] = {6,7,2,9,4,11,8,7,10,5};
    vector<int> dice(10);
    copy(casts,casts+10,dice.begin());
    cout << "原始数据: " << endl;
    ostream_iterator<int,char> out_iter(cout," ");
    copy(dice.begin(),dice.end(),out_iter);
    cout << endl;
    cout << "使用了反向迭代器重新输出:" << endl;
    copy(dice.rbegin(),dice.rend(),out_iter);
    cout << endl;
    cout << "使用了vector类的reverse_iterator: " << endl;
    vector<int>::reverse_iterator ri;
    for(ri = dice.rbegin(); ri != dice.rend(); ++ri)
        cout << *ri << ' ';
    cout << endl;
return 0;
}

　　但是上述代码是在其已知了dice的大小的情况下进行的,如果不知道容器的大小呢?,并且还是向容器中刚添加元素(而不是像上述代码覆盖已有内容),这种情况下咋整?有三种插入迭代器可以将复制转为插入解决问题,他们使用动态内存分配插入新元素:
　　
　　back_insert_iterator; //将元素插入到容器尾,但只能用于允许在尾部快速插入的容器; (vector符合)
　　front_insert_iterator; //将元素插入到容器前面,但只能用于允许在起始位置做时间固定插入的容器;
　　insert_iterator; //将元素插入到insert_iterator构造函数的参数指定位置之前;
　　这些迭代器将容器类型作为模板参数,将模板名作为构造函数参数:

1	back_insert_iterator<vector<int>>back_iter(dice); //为名为dice的vector<int>容器创建个back_insert_iterator

　　下列程序演示了两种迭代器的使用方法,并且使用for_each()输出:

#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <algorithm>
using namespace std;
void output(const string & s){cout << s << " ";}
int main()
{
    string s1[4] = {"F","A","♂","Q"};
    string s2[2] = {"B","L"};
    string s3[2] = {"M","J"};
    vector<string> words(4);
    copy(s1,s1+4,words.begin());//words地方够,可以复制进来
    for_each(words.begin(), words.end(), output);
    cout << endl;
    copy(s2,s2+2,back_insert_iterator<vector<string>>(words));//从后面插♂入
    for_each(words.begin(),words.end(), output);
    cout << endl;
    copy(s3,s3+2,insert_iterator<vector<string>>(words,words.begin())); //插♂前面
    for_each(words.begin(),words.end(), output);
    cout << endl;
    return 0;
}