`
fuerbosi
  • 浏览: 461160 次
文章分类
社区版块
存档分类
最新评论

暑假c++复习6之顺序容器

 
阅读更多

容器类共享公共的接口,这使标准库更容易学习,只要学会其中一种类型就能运用令一种类型,每种容器类型提供一种不同的时间和功能折中方案,通常不需要修改代码,只需

改变类型声明,用一种容器类型代替另一容器类型就可以优化程序的性能。

容器容纳特定类型对象的集合,它将单一类型元素聚集起来成为容器。然后根据位置来存储和访问这些元素,这就是顺序容器。

标准库定义 了三种顺序容器类型vector,list和deque(双端队列),他们的差别在于访问元素的方式,以及添加或删除元素相关操作的运行代价。标准库还提供了三种容器适配器,实际上适配器是根据原始的容器类型所提供的操作,通过定义性操作接口,来适应基础的容器类型,顺序容器适配器包括stack,queue,和priority类型。

顺序容器类型:

vector 支持快速随即访问

list 支持快速插入或删除

deque 双端队列

顺序容器适配器:

stack 后进先出栈

queue 先进先出队列

priority_queue 有优先级管理的队列

容器只定义了少量的操作,大多数额外操作则有算法库提供

容器的构造函数:

C<T>c;//创建一个空容器;;适用于所有容器

C<T>c( c2)创建c2的副本c,c和c2必须是同一类型,并存放相同类型的元素;;使用与所有的容器

C<T>c(b,e);创建c,其元素师迭代器b和e指示的范围内元素的副本,使用与所有容器。

C<T>c(n,t)创建c,c中有n个t,值适用于顺序容器

C<T>c(n)创建c,c有n个值初始化,值适用于顺序容器

//用svec中的所有元素初始化slist

list<string>slist(svec.begin(),svec.end());

vector<string>::iterator mid =svec.begin()+svec.size()/2;

deque<string>front (svec.begin(),mid);//用svec中的前半部分初始化front

deque<string>back(mid,svec.end());//用svec中的后半部分初始化back

亦可这样:

char *word[]={"it","is","beutiful","flower"};

size_t size=sizeof(word)/sizeof(char*);

list<string>word2(word,word+size);


c++中,大多数类型都可用作容器的元素类型,容器元素类型必须免租一下两个约束:

1,元素类型必须支持复制运算

2,元素类型的对象必须可以复制,

引用不支持一般意义的赋值运算,因此没有元素是引用类型的容器。io库类型不支持复制或赋值,因此,不能创建存放io类型的容器。


支持复制和赋值功能是容器元素类型的最低要求。

迭代器为所有标准库容器所提供的运算:

*iter

iter->num//对iter进行解引用,获取指定元素中名为num 的成员。等效于(*iter).num

++iter;

iter++

--iter

iter--

iter1==iter2

iter1!=iter2

vector和deque容器的迭代器提供额外的元素:

iter+n

iter-n

iter1+=Iter2

iter1-=iter2

iter1-iter2只有这两种容器

<,>=,<,>=只有这两种容器


1,当first和last相等时,迭代器范围为空

2,当first和last不相等时,迭代器范围内至少有一个元素。而且first指向该区间中的第一个元素,此外通过若干次自增运算可以使first的值不断增大,直到与last相等。

begin和end操作产生指向容器内第一个元素和最后一个元素的下一个为位置的迭代器。

c.begin()指向容器的第一个元素

c.end()指向容器的最后一个元素

c.rbegin()指向容器的最后一个元素

c.rend()指向容器的第一个元素

上述每个操作都有两个不同版本,一个是const成员,另一个是非const成员。这些操作返回什么类型取决于容器是否为const,如果容器不是const,则这些操作返回iterator

或reverse_iterator,如果容器是const则返回类型要加上const_前缀,也就是const_iterator。

push_back函数会在容器的尾部创建一个新元素,并使容器的长度加1;

在顺序容器中添加元素的操作:

c.push_back(t)//在容器尾部插入新元素,返回void

c.push_front(t)//在容器c的前端添加值为t的元素,返回void,只是用于list和deque容器类型

c.insert(p,t)//在迭代器p所指向的元素前面插入值为t的新元素,返回指向新添加元素的迭代器

c.insert(p,n,t)//在迭代器p所指向的元素插入n个值为t的新元素。返回void

c.insert(p,b,e);//在迭代器p所指向的元素前面插入由迭代器b和e标志范围内的元素,返回指向新添加元素的迭代器

在容器中添加元素时,系统是将元素值赋值到容器里,类似地,使用一段元素初始化新容器时,新容器存放的时原始元素的副本。

list<string> lst;
list<string>::iterator iter=lst.begin();
while(cin>>word)
   iter=lst.insert(iter,word);
上述循环等效于push_front;

访问元素:

c.back()//返回最后一个元素的引用

c.front()//返回第一个元素的引用

c[n]//返回下标为n的元素的引用。如果下标越界则该操作未定义,只使用vector和deque

c.at(n)//返回下标为n的元素的引用。如果下标越界则该操作未定义,只使用vector和deque

删除顺序容器内元素的操作

c.erase(p)//删除p所指向的元素,返回删除元素的下一个元素

c.erase(b,e)//删除b,e所指向段的所有元素,返回被删除元素段后面的元素。

c.clear()//删除容器c内的所有元素,返回void

c.pop_back()//删除容器c的最后一个元素,返回void

c.pop_front()'//删除c的第一个元素,返回void,只是用与list和deque。


顺序容器的赋值操作:

c1=c2;//删除容器c1的所有元素,然后将c2的元素复制给c1,c1和c2的类型必须相同

c1.swap(c2);//交换内容,调用完该函数后,c1中存放的是c2原来的元素,c2中存放的则是c1原来的元素,c1和c2的类型必须相同,该函数的执行速度通常要bii将c2的元素复制 给c1要快。

c.assign(b,e);//重新设置c的元素:将迭代器b和e标记的范围内所有的元素复制到c中,b和c必须不是只想c中必须不是指向c中元素的迭代器。

c.assign(n,t);//将容器c中心设置为存储n个值为t的元素。

除了swap外都可以用erase和insert操作替代。

下面列举了一些选择容器类型的法则:

1)如果程序要求随即访问元素,则应使用vector或deque

2)如果程序必须在容器的中间位置插入或删除元素,则应采用list容器。

3)如果程序不是在容器的中间位置而是在容器首部或尾部插入或删除元素则应采用deque容器

4)如果只需子读取输入时在容器的中间位置插入元素然后需要随机访问元素。则可考虑在输入时将元素读入到一个list容器中,接着对此容器重新排序,然后使其适合顺序访问,然后将排列后的list容器复制到一个vector容器


容器适配器:

适配器是使一事物的行为类似于另一事物的行为的一种机制,容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。例如,stack(栈)适配器可使任何一种顺序容器以栈的方式工作。

适配器通用的操作和类型:

size_type//一种类型,足以存储适配器类型最大对象的长度

value_type//元素的类型

container_type//基础容器的类型,适配器在此容器上实现。

A a;创建一个空适配器,命名为a

A a(c)创建一个名为a的新适配器,初始化为容器c的副本

关系操作符//所有适配器都支持全部关系操作符

使用适配器时,必须包含相关的头文件:

#include<stack>

#include<queue>

适配器的初始化:

所有的适配器都定义了两个构造函数:默认构造函数用于创建空对象,而嗲一个容器参数的构造函数将参数容器的副本作为其基础值。假如dep是deque<int>的容器;则可用deq初始化一个新栈。

stack<int> stk(deq);

stack栈可以建立在vector,list或deque之上,而queue适配器要求其干练的基础容器必须提供push_front运算,因此只能建立在list容器上,而不能建立在vector上,priority_queue适配器要求提供随机访问功能,因此可建立在vector或deque容器上。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics