C++

C++顺序容器

TheHuPost newsletter上线了, 欢迎大家订阅! 
对C++, Java,JavaScript,Python等编程语言有兴趣的,也可以看看编程语言. 
也欢迎大家来论坛与我讨论

C++顺序容器

C++顺序容器内的元素按照其位置存储和访问,元素的排列次序由元素添加到容器里的次序决定.

    标准库定义了vector,list,deque 三种顺序容器,以及stack,queue,priority_queue三种顺序容器适配器;

容器构造函数

   C<T> c    // 创建一个空容器c, T是元素类型,适用于所有容器

   C c(c2)     //创建容器c2 的副本c, c和c2 需有相同的容器类型和相同的元素类型,适用于所有容器

   C  c(b,e)    //创建c ,其元素是迭代器b 和e 表示范围内元素的副本,适于所有容器

   C c(n,t)       //创建c,  其元素为n 个t ,   适于顺序容器

    C c(n)        //创建有n个值初始化元素的c , 适于顺序容器

容器内元素的类型约束

  •    1. 元素类型必须支持赋值运算;
  •     2. 元素类型的对象必须可以复制

   引用不支持一般意义上的赋值,引用不能为容器的元素类型; IO库类型不支持赋值或复制,因此不能创建存放IO对象的容器

迭代器所提供的运算

  *iter

      iter->mem

     ++iiter / iter++

     --iter/iter--

    iter1 == iter2

     iter1 != iter2

只有vector 和deque 支持迭代器的算术运算和关系运算:

 iter+n/iter-n

    iter1 +=iter2

   iter1 -= iter2

    iter1-iter2

   >,>=,<,<=

迭代器范围使用左闭合区间

   即begin ,end 两迭代器之间包含的元素为 [begin,end)    ,或者说begin 指向容器的起始元素,end指向容器最末元素的下一元素;

   要形成左闭合区间,迭代器有如下要求:

  •     1.    begin ,end 指向同一容器的元素或超出末端的下一位置;
  •      2.    begin 不能位于end之前

 

使用左闭合区间的优点:

  •     1.   begin == end 时, 判断迭代器范围为空
  •      2.   begin !=   end 时,迭代器范围内至少有一个元素,且begin 指向第一个元素

迭代器失效

一些容器操作会导致迭代器失效,产生类似于悬垂指针的问题

   如erase 操作删除了元素,则原先指向该元素的迭代器就会失效

   如添加元素时,原先保持的end迭代器就会失效,需要重新获得end ,所以避免保持end 返回的迭代器

顺序容器的操作

顺序容器的定义的相关类型

size_type

   iterator

   const_iterator

    reverse_iterator

   const_reverse_iterator

    difference_type

    value_type

    reference

    const_reference

begin 和end 操作

c.begin()/c.end()   // 返回指向第一个元素和最后元素下一位置的iterator

c.rbegin()/c.rend()  // 返回指向最后元素和指向第一元素前面位置的reverse_iterator

添加元素

c.push_back(t)   // 在容器c 的尾部添加值为t 的元素,返回void类型, 适于所有容器类型;

  c.push_front(t)   // 在容器前段添加元素,只适于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标示的范围内元素,返回void

关系比较

  支持容器类型的关系比较, 比较的容器需有相同的容器类型和元素类型

       容器的比较是基于容器内元素的比较, 类型string类型的比较,取决于第一个不同元素的比较

大小操作

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

   c.maxsize()   // 返回c可容纳的最多元素个数

   c.empty()        //  是否为空的bool值

   c.resize(n)    // 调整容器大小为n,  若n < c.size() ,则删除多的元素

   c.resize(n,t)     // 调整容器大小为n ,新增元素都为t

访问元素

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()               //删除所有元素,返回void

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

   c.pop_front()      //删除第一个元素,     只适于list,deque

赋值与swap

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

   c1.swap(c2)    // 交换后c1中存放c2原来元素, c2 中存放c1 中元素 ,c1 和c2 类型徐相同, 执行速度一般比复制和赋值快

   c.assign(b,e)   // 删除c中所有元素,再见b,e间元素赋值到c

    c.assign(n,t)    // 删除c中所有元素,将c重置为n个t

vector的自增长

    元素连续存放,可以提供高效的随机访问,  但插入,删除操作会非常慢(开辟新空间,将元素拷贝到新的空间,释放老的空间)

    元素不练习存储,可以提供高效的插入,删除操作,但随机访问会非常慢(需要遍历整个链表)

    vector通过分配比所需空间更多的连续空间来提供快速的随机访问,同时尽量插入,删除时的开销.

   具体内容见下一篇”vector 的自增长以及顺序容器的选择”

容器适配器

顺序容器适配器

  顺序容器适配器: queue,stack,priority_queue

   适配器包括容器适配器,迭代器适配器,函数适配器.

  适配器是使一事物的行为类似另一事物的行为的一种机制,容器适配器让一种已存在的容器以另一种不同的抽象方式工作.

适配器的操作和类型

 size_type

   value_type

  container_type

 A  a; 

 A a(c)

关系操作符

适配器头文件

  适配器需包含头文件

#include<queue>

#include<stack>

stack & queue, priority

默认stack ,queue 基于deque实现, priority基于vector实现

可以在创建适配器时,将一个顺序容器指定为第二个类型实参,覆盖其关联的基础容器类型

stack< string,   vector<string> >str_stk;

stack 操作

s.empty()    //stack 为空返回true

   s.size()      // stack 中元素个数

   s.pop()      //删除stack 顶部元素

   s.top()       //返回stack 顶部元素的值

   s.push(item)     //在stack顶压入新元素

queue  and priority_queue

q.empty()

 q.size()

q.pop()

q.front()     // 返回队列首元素的值,只适于queue

q.back()     // 返回队列尾元素的值,只适于queue

q.top()   //  返回优先级最高的元素值,只适于priority_queue

q.push(item)      //对于queue ,在尾部压入新元素;  对于priority_queue ,放在比其优先级低的元素的前面 

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top