第六十五讲 细说vector(1)

vector,他字面意思叫向量,但是在C++里,他不只是叫向量,他表示一种容器,又因为他本身叫向量的原因,所以这种容器又叫序列容器(当然这是我妄加猜测的),那么为什么要用vector来作为STL的开篇呢?因为在所用容器里,可以说vector是用得最多的,当然这和他强大的功能分不开,如同大家的体会一样,我们会发现不论是vector,还是list,又或者是queue等等,他们有很多相似的操作方式,如果在末端插入元素,从末端取出元素,又好比他们都通过begine或者是end取得相关的迭代器,我们会不会这么认为,所有的标准容器都是从同一个基类派生出来的呢?要不他们为什么会有这么多相似之处?

当然,STL里面所有的容器都是绝对独立的,他们都有自己的独立界面,而且可以这么说,他们都设置为不可以派生的,因为他们的析构函数都是非虚的,当然这和他们是不是从同一基类派生的毫无关系。

vector,我想我们对他印象最为深刻的就是他能够创建动态数组了,所以,当他们想要数组的时候更多的选择会是vector,就像当我们想要字符串的时候,我们一定会选择string,而不是char*,说到这里,我们心里也该是有底了,在迭代器那一章里面,我们就说说过类似的功能,所以,现在大家都不难明白,在vector里面有一个默认参数是用来分配内存的,而且他给出了一大堆的标准类型名:
——————————-
template<typename T,typaname A=allocator<T>>
class vector{
public:

//标准类型名,下面的typedef是为了统一标准库的名称

typedef T value_type;



typedef A allocator_type;



typedef typename A::size_type size_type;



typedef typyname A::difference_type difference_type;

typedef implementation_dependent1 iterator;



typedef implementation_dependent2 const_iterator;



typedef reverse_iterator<iterator>reverse_iterator;



typedef reverse_iterator<const_iterator>const_reverse_iterator;

typedef typename A::pointer pointer;



typedef typename A::const_pointer const_pointer;



typedef typename A::refrence refrence;



typedef typename A::const_refrence const_refrence;



//…………
};


——————————–

这些typedef是每个标准库都会定义的,目的就是为什么实现名字统一,这里有一个重点得说说,那就是typename这个词,在这里之前,我们都认为typename如同class一样,而且我们也常常说这两个词可以互换,但是这里,我们终于遇到他们不可以互换的情况了:
———————————-
typedef typename A::size_type size_type;


———————————-

在这一句里,typename不再可以用class来替代,而且这里的typename不可以省略,来看看,如果我们没有这个typename会是什么情况:
——————————
A::iterator* pointer;


——————————
从模板哪里,我们可以知道A是一个类型,但是我们不知道iterator是不是类型,如果恰巧A里面有个iterator的静态成员呢?上面这句代码就要重新理解了,我们原本是想要声明一个pointer,让他指向A里面的iterator的,所以如果没有typename这个词的话,就会产生二义性,他不但可以有我们想要的结果,还会把他解释为相乘,所以这个typename是不可缺少的,那么为什么不能换成class呢?我不清楚,也不要再刨根究底了,既然C++是这么定义的,那么我们遵守就好,如果我们有什么想法,等我们能够自己搭建编译器的时候再来讨论吧。
—————————
int f(vector<int>&

c){

int sum=0;


vector<int>::iterator p=c.begin();


while(p != c.end()){

sum += *p;


++p;


}

return sum;


}
—————————–
上面的函数是计算出一个容器中所有元素的和,这是我们最常用的方法了,那么要实现上面的功能,所以我们知道vector里面要有如下的方法:
———————————
template<typename T,typaname A=allocator<T>>
class vector{
public:

//

//

iterator begin();



const_iterator begin();



iterator end();



const_iterator end();

reverse_itertor rbegin();



const_reverse_iterator rbegin();



reverse_iterator rend();



const_reverse_iterator rend();



//

//
};
——————————–
当然,这些函数的实现都不难,就比如:
——————–
iterator begin(){

return &

T[0];


}
——————–

如同前面我们所说的,iterator说到底就是一般指针的泛化,从内置指针到对象操作的转型,所以,begin其实就是返回第一个元素的地址,当我们对iterator解引用就自然得到了这个地址里面储存的数值。

对于iterator大家都不会陌生,和他一起的就是reverse_iterator了,C++叫他反向迭代器,值得注意的是他和iterator不是同一种类型,关于他们的区别,我们用实例来说明:
—————————
int main()
{

int b[] ={5,8,7,6,5,8,9,1,4,3,7 };



vector<int>a(b,b+11);



vector<int>::iterator p=a.begin();


int
sum = 0;



while(p!=a.end()){

cout<<*p<<endl;


sum += *p++;


}

cout<<"

sum = "

<<sum<<endl;



vector<int>::reverse_iterator rp = a.rbegin();


int sum2 = 0;



while(rp!=a.rend()){

cout<<*rp<<endl;


sum2 += *rp++;


}

cout<<"

sum2 = "

<<sum2<<endl;


return 0;


}
————————–

通过打印出来的结果,可以得出iterator和reverse_iterator的区别,在我们第一个循环里,我们使用的是iterator,所以我们打印出来的结果是按照我们声明的b顺序的,而第二循环中,我们用的是reverse_iterator,所以打印出来的顺序是反向的,所以这两个迭代器很好区别。

bebin()得到的是指向第一个元素的指针的,end()得到的是指向最后一个元素的下一个位置的指针(我这里说是下一个位置,并没有说他是元素,所以希望大家能够明白,end()返回的迭代器是没有明确定义的),所以这个迭代器我们不能够使用,同样,rbegin()返回的是指向最后一个元素的位置,而rend()返回的是第一个元素的前一个位置。
有了这两个迭代器,我们就可以对vector使用很多算法,如果查找,插入等等,比如,如果我们要在一个容器里面查找一个值,我们可以使用find()函数:
——————————
template<typename T>
typename vector<T>::iterator my_find(vector<T>&

c,const T val){

vector<T>::iterator p=c.begin();


while(p!=c.end()){

if(*p == val)

return p;


p++;


}

return c.end();


}
——————————

当然,我们可以用反向迭代器来实现这个算法:
——————————-
template<typename T>
typename vector<T>::iterator my_find(vector<T>&

c,const T val){

vector<T>::reverse_iterator rp=c.rbegin();


while(rp!=c.rend()){

if(*rp == val){

typename vector<T>::iterator p

= rp.base();


return –p;


}

rp++;


}

return c.end();

//还是用超尾迭代器来表示没有找到吧。
}
——————————-
从上面的两个算法中,我们可以看到,其实iterator和reverse_iterator都是完整的迭代器,只是他们是不同的类型,不过大家也看到了,这两种迭代器是可以转换的,当然是从reverse_iterator转为iterator(rp.base()),base()返回一个iterator,不过是指向rp的后面一个位置的元素,所以当我们用iterator来表示reverse_iterator的时候就得记得要-1,才得到reverse_iterator真正的位置。

vector的内容不少,今天就先说到这里吧。
============================
回复D直接查看目录

原文始发于微信公众号(

C/C++的编程教室

):第六十五讲 细说vector(1)

|

发表评论