设为首页 加入收藏

TOP

C++标准库容器总结(一)
2013-02-08 14:31:14 】 浏览:1371
Tags:标准 容器 总结

  C 标准库顺序容器

  所有的标准库容器都是类模板,用以存储单一类型元素的集合.顺序容器按元素位置存储访问,关联容器按键存储访问.

  1 顺序容器

  将单一类型的元素按顺序存储,以下标来访问元素.标准库定义了三种顺序容器:vector,list及deque.vector支持快速随机访问;list支持快速插入删除;deque是双端队列.

  a)容器初始化:

  C<T> c; 创建一个名为c的容器,容器类型为C,如vector或list,T为容器内元素类型.适用于所有容器;

  C c1(c); 创建容器c的副本,c1和c必须具有相同的容器类型和元素类型,适用于所有容器;

  C c(b,e); 创建容器c,元素是迭代器b,e标示范围内的副本,适用于所有容器;

  C c(n,t); 创建容器c,元素为n个值为t的值,t的类型必须是容器C的元素类型或者可以转换为该类型,只适用于顺序容器;

  C c(n); 创建具有n个值初始化元素的容器c,元素类型为值n的类型,只适用于顺序容器;

  注:* 在使用迭代器复制元素时,不要求双方容器类型相同,容器内元素类型也可以不同,只要元素类型可以相互转换即可;

  * 迭代器范围[b,e)是左闭右开区间,即e所指的元素并未被复制,e只是提供了停止复制的条件;

  b)元素类型约束:

  元素类型必须满足:

  元素类型必须支持赋值;

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

  关联容器的键类型必须且只要实现<操作符即可.

  注:*大多数类型都能满足上述最低限制的约束.例外,引用不支持一般意义上的赋值,IO库类型不支持复制或赋值,所以两者以及auto_ptr类型都不能作为容器的元素类型.

  2 迭代器

  一种数据类型,用于遍历容器内元素,标准库容器都有自己的迭代器,配合算法使用.迭代器是标准库容器类型的配套设施.

  a)迭代器范围是一个左闭右开的区间,即[b,e);

  b)一些容器操作会使指向容器元素的迭代器失效,要特别注意.

  c)const_iterator迭代器和const迭代器的区别;

  注:*迭代器往往和容器及泛型算法结合使用,本节仅简单描述,后面会有详尽的介绍.

  3 顺序容器的操作

  a)begin和end操作:

  c.begin(),c.end(),c.rbegin(),c.rend();

  非const版本:vector<string>::iterator = c.begin();

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

  const版本:  vector<string>::const_iterator = c.begin();

  vector<string>::const_reverse_iterator = c.rbegin();

  b)添加操作:

  c.push_back();在容器尾部添加值为t的元素,返回void;

  c.push_front();在容器头部添加值为t的元素,返回void,

  只适用于list和deque;

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

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

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

  注:*添加元素可能会使迭代器失效,所以每次操作之后都应该及时更新迭代器;

  c)容器大小:

  c.size();返回容器内元素个数,返回类型为c::size_type;

  c.max_size();返回容器内最多可容纳的元素个数,返回类型为c::size_type;

  c.empty();测试容器内是否有元素;

  c.resize(n);调整容器大小,使其能容纳n个元素;

  c.resize(n,t);调整容器大小,使其能容纳n个元素,新添加元素以t初始化;

  注:*c.resize(n)中,当n < c.size(),删除多出来的元素;否则,采用值初始化添加新元素;

  *c.reserve(n);仅调整c的最大容量,并不初始化元素;

  *c.resize(n)和c.resize(n,t)可能会使迭代器失效;

  d)访问元素:

  c.front();返回容器内第一个元素的引用,如果c为空,该操作未定义;

  c.back();返回容器内最后一个元素的引用,如果c为空,该操作未定义;

  c[n];和c.at(n);返回下标为n的元素的引用,n越界时,该操作未定义,只用于vector和deque;

  e)删除元素:

  c.erase(p);删除迭代器p指向的元素,返回一个指向被删除元素后面的元素的迭代器;

  c.erase(b,e);删除迭代器b和e标记范围内的所有元素,返回一个指向被删除元素段后面的元素的迭代器;

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

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

  c.pop_front();删除容器的第一个元素,返回void,只适用于list和deque;

  注:*删除元素可能会使迭代器失效,所以每次操作之后都应该及时更新迭代器;

  f)赋值操作:

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

  cl.swap(c2);交换c1和c2中的所有元素,c1和c2的容器类型及元素类型必须相同;

  c.assign(b,e);重新给c赋值,内容为b和e所标记范围内的元素,b和e必须不是指向c中的元素的迭代器;

  c.assign(n,t);将c中的元素重新设置为n个值为t的元素;

  注:*赋值和assign操作会使左操作数中的迭代器失效,但是swap操作后,迭代器仍然指向相同的元素;

  *swap操作在常量时间内完成,没有移动任何元素;

  4 vector容器的自增长

  vector预留了额外的存储区,用于存放新添加的元素,当现有的空间用完之后再自动重新分配存储空间.capacity()和reserve()使程序员可以和vector的内存分配的实现部分交互工作.

  a)c.capacity();获取c在要分配更多的存储空间之前所能容纳的元素总数;

  b)c.reserve(n);c应该预留n个元素的存储空间;

  注:*c.resize(n);和c.reserve(n);的区别很微妙,前者对多出来的新元素进行值初始化;后者仅仅调整存储空间,而不进行任何初始化.

  *c.max_size();和c.capacity();的区别也很微妙.简单的说,c.max_size();是c.capacity();的最大值,前者是一个常量,值取决于操作系统或C 库的实现,而后者则是一个变量.

  www.cplusplus.com/reference/stl/vector/max_size/有例子程序.

  *c.size(); <= c.capacity(); <= c.max_size();

  5 顺序容器的选用

  a)顺序容器的特点:

  vector容器可以实现高效的随机访问,但是除了容器尾部外,在其他任何位置添加和删除元素却很低效;

  list容器可以实现高效的添加删除,但是随机访问的效率却很低;

  deque容器支持对所有元素的随机访问,在容器的首部和尾部可以高效地添加删除元素,但是在中间位置添加删除元素却又很低效.

  注:*应用中占优势的操作将决定使用哪种类型的容器.

  6 容器适配器

  适配器概念的定义:是一种标准库类型,函数或迭代器,使一种标准库类型,函数或迭代器的行为类似于另一种标准库类型,函数或迭代器.本质上,适配器是使一种事物的行为类似于另一种事物行为的机制.容器适配器在其基础容器上定义一个新的接口,使基础容器拥有另一种不同容器的工作方式.

  顺序容器适配器:stack(栈),queue(队列),priority_queue(优先级队列).

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

  size_type 一种类型,存储此适配器类型最大对象的长度;

  value_type 元素类型;

  container_type 基础容器的类型;

  A a;创建一个新的容器适配器;

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

  关系操作符:==,!=,<,<=,>,>=.

  b)适配器的初始化:

  deque<int> deq;

  stack<int> stk();

  stack<int> stk(deq);

  注:*stack适配器和queue适配器的基础容器默认为deque,priority_queue的基础容器默认为vector.

  c)覆盖基础容器类型:

  deque<int> deq;

  stack<int,vector<int> > stk(deq);

  注:*stack适配器关联的基础容器可以是任意一种顺序容器类型;

  *queue适配器要求基础容器必须提供push_front操作,只能建立在list容器上;

  *priority_queue适配器要求提供随机访问操作,只能建立在vector或deque容器上;

  d)栈适配器的操作:

  s.empty();返回栈是否为空;

  s.size();返回栈中的元素个数;

  s.pop();删除栈顶元素,返回void;

  s.top();返回栈顶元素,但不删除该元素;

  s.push(item);在栈顶压入新元素;

  注:*程序员不能直接使用栈适配器所关联的基础容器的操作.

  e)队列和优先级队列的操作:

  q.empty();返回队列是否为空;

  q.size();返回队列中的元素个数;

  q.pop();删除队首元素,返回void;

  q.front();返回队首元素,但不删除元素,只适用于队列;

  q.back();返回队尾元素,但不删除元素,只适用于队列;

  q.top();返回具有最高优先级的元素,但不删除该元素,只适用于优先级队列;

  q.push(item);对于queue,在队尾压入一个元素;对于priority_queue,在基于优先级的适当位置插入一个元素.

   

首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇将integer的bit位翻转 下一篇C/C++ 数组的初始化

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目