首页 > 代码库 > c++顺序容器

c++顺序容器

    1. 定义和初始化
      #include<vector>
      #include<list>
      #inlcude<deque>
      初始化:
       C<T> c; 空容器,如vector<int> ivec;
       C c(c2); 创建容器c2的副本c
       C c(b,e); 由迭代器b,e标识的范围内的元素的副本,如list<int> ilist(ivec.begin(),ivec.end());
       C c(n,t); 用n个值为t 的元素创建容器c
       C c(n); 创建有n个值初始化元元素的容器

      string strings[]={"abc","def",ghi"};
      deque<string> sdeq(strings,strings+sizeof(strings)/sizeof(string));

      容器元素类型必须满足以下两个条件:
      元素类型必须支持赋值运算;
      元素类型的对象必须可以复制;

        除了引用类型外,所有的内置类型或复合类型都可以用做元素类型。(引用不支持一般意义上的赋值运算),另外,IO类型不支持复制或赋值,故不能创建存放IO类型对象的容器。

      容器存放的是复本,对于由其它容器或对象初始化的容器来说,更改其值不会影响被复制的原值。
      容器的容器:
      vector<vector<string> > lines;
      >>中间要使用空格:
      vector<vector<string>> lines;//error

    2. 迭代器
      迭代器为所有标准库容器类型所提供的运算:
      *iter  iter->item  ++iter iter1==iter2  iter1!=iter2
      vector和deque容器的迭代器提供的额外运算:(迭代器算术运算)
      iter + n
      iter - n
      iter1+=iter2
      >,>=,<,<=
      上述只用于vector和deque容器,因为只有这两种容器为其元素提供快速,随机的访问。

    3. 容器操作
      容器定义的类型别名:
       size_type UL,最大可能长度,作为索引的类型
       iterator 此容器类型的迭代器类型
       const_iterator 只读迭代器
       reverse_iterator 按逆序寻址元素的迭代器
       const_reverse_iterator 只读逆序迭代器
       difference_type 足够存储两个迭代器差值的有符号整型,可负
       value_type 元素类型
       reference 元素左值类型,是value_type&的同义词
       const_reference 元素常量左值类型,等效于const value_type&

      关系操作符:
      所有容器都支持关系操作符来实现来个容器的比较。比较的容器必须要有相同的容器类型,且元素类型也要相同。容器的比较是基于容器内元素的比较,故元素应要支持关系操作。

      容器大小操作:
      c.size()//当前大小
      c.max_size()//可容纳最大数
      c.empty()
      c.resize(n)//调整大小为n,若n>c.size(),添加值采用初始化方法,否则删除多余值
      c.resize(n,t)//调整大小为n,若n>c.size(),添加值为t,否则删除多余值

      元素访问:
      如果容器非空,则front和back成员将返回容器内第一个或最后一个元素引用:
      if(!ilist.empty())
      {
        list<int>::reference val=*ilist.begin();//引用
        list<int>::reference val2=ilist.front();//和val相同 
        list<int>::reference last=*--ilist.end();
        list<int>::reference last2=ilist.back();
      }
      汇总:
      c.back()
      c.front()
      c[n]      //only vector and deque suported ,no list
      c.at(n)   //only vector and deque suported ,no list


      删除元素:
       c.erase(p) 删除迭代器指向的元素,返回指向删除元素的下个元素的迭代器,若p为c.end()则函数未定义
       c.erase(b,e) 删除迭代器b和e范围内的元素,返回指向删除元素段的下个元素的迭代器,若e为c.end(),则返回c.end()
       c.clear() 删除c中所有元素,返回void
       c.pop_back() 删除最后一个元素,返回void,若c为空,则函数未定义
       c.pop_front() 删除第一个元素,返回void,若c为空,则函数未定义,只适用于list或deque
      一般来说,需要先找到要删除的元素后才能使用erase方法,寻找一个指定元素最简单的方法是使用标准库里的find方法。<algorithm>
      string searchValue("Quasimodo");
      list<string>::iterator iter=find(slist.begin(),slist.end(),searchValue);
      if(iter!=slist.end())
        slist.erase(iter);

      赋值与swap
       c1=c2 删除c1中所有内容,将c2的元素复制给c1。c1和c2的类型必须相同
       c1.swap(c2) 交换内容:类型要相同。执行速度通常比将c2的元素复制到c1的操作快
       c.assign(b,e) 重设c的元素:将迭代器b和e标记的范围内的元素复制到c中。b和e不能指向c中的元素
       c.assign(n,t) 将c重设为存储n个值为t 的元素

          当在不同或相同的容器中,元素类型不相同但是相互兼容,则其不能用=进行赋值,要用assign赋值。
      swap:容器类型相同,元素类型相同。
         c1.swap(c2);
      swap操作没有移动元素,因此迭代器没有失效。比如在交换前,一个迭代器指向c1[2],实现交换后,该迭代器指向c2[2],指向的仍是同一个对象。
         
    4. 容器自增长
      为了使vector容器实现快速的内存分配,vector容器预留了额外的存储区用于存放新加的元素。

      由于vector是在内存中连续存放的,vector容器处理内存分配的细节是其实现的一部分,该部分是由vector的接口去持的。vector类提供了两个成员函数:capacity和reserve,使程序员可与vector容内存分配的实现部分的交互工作。capacity操作获取在容器需要分配更多的存储空间之前能够存储的元素总数,而reserve操作告诉vector容器应该预留多少个元素的存储空间。
       size是指容器当前拥有的元数总数,而capacity是指容器在必须分配新的存储空间之前可以存储的元素总数。
       vector<int> ivec;
       cout<<"ivec:size: "<<ivec.size()<<endl;   //0
       cout<<"ivec:capacity:"<<ivec.capacity()<<endl; //0
      //加入24个元素后
      size:24
      capacity:32

      ivec.reserve(64);
      size:24
      capacity:64
      //再加入24个元素后
      size:48
      capacity:64 //使用了预留的容量,不分配空间
      //再加入24个元素
      size:7
      capacity:128//重新分配存储空间,以加倍当前容量的分配策略分配(依编译器变化)

    5. 容器选择
        Vector Deque List
       随机访问 快速 快速 不支持
       insert/erase 效率低 效率最低 快速
       push_front() 不支持 快速 快速
       push_back() 快速 快速 快速
       pop_front() 不支持 快速 快速
       pop_back() 快速 快速 快速

      list不支持随机元素访问:

      ilist.at(0);//error
      ilist[0];//error
      vector不支持push_front(val)和pop_front()操作。
      选择容器的提示:
      A.如果程序要求随机访问元素,则应使用vector或deque容器。
      B.如果程序必须要在中间位置插入或删除元素则应采用list容器。
      C.如果不需要在中间插入或删除元素,而是在首或尾部插入或删除元素,则应采用deque容器。
      D.如果只需在读取输入时在容器的中间位置插入元素,然后需要随机访问元素,则可考虑在输入时将元素读入到一个list容器中,接着对此容器重新排序,使其适合顺序访问,然后将排序后的list容器复制到vector中。
      E.如果程序既需要随机访问又必须在容器的中间位置插入或删除元素,此时选择何种容器取决于下面两种操作的代价:随机访问list的代价,在vector或deque容器中插入/删除元素时复制元素的代价。

    6. string和容器
      string类型支持大多数顺序操作,在某些方面可将string类型视为字符容器。与vector容器不同的是,它不支持以栈方式操纵容器:在string类型中不能使用front,back和pop_back操作。

       
      string 不支持的容器操作:
      C<T> c(n) 初始化
      push_front(e)
      back,front
      pop_back() pop_front()
      关于string的具体介绍请参阅:《关于C++标准库中的 string》一文
    7. 容器适配器
      除了顺序容器,标准库还提供了三种顺序容器适配器:queue,priority_queue和stack。
      适配器支持的通用操作有:
       size_type,value_type, container_type, A a; A a(c); 关系运算符
      #include<stack>
      #include<queue>
      初始化:
      两种方式:默认构造函数,空对象;带一个容器参数的构造函数将参数容器的副本作为其基础值。
      例:假如deq是deque<int>类型的容器,则可用deq初始化一个新stack: stack<int> stk(deq);
      覆盖基础容器类型:
      默认的stack和queue都基于deque容器上实现,而priority_queue则在vector容器上实现。在创建适配器时,通过将一个顺序容器指定为适配器的第二个类型参数,可覆盖其关联的基础容器类型:
      stack< string, vector<string> > str_stk; //implemented on top of vector
      stack<string, vector<string> > str_stk(svec);//holds a copy of svec
      stack 适配器要要所关联的容器可以是任意一种顺序容器,故可建立在vector,list或deuqe上。
      queue适配器要求其关联的基础容器必须提供push_front运算,故只能建立在list容器上,不能建立在vector上。
      priority_queue适配器要求提供随机访问的功能, 故可建立在vector或deque容器上,不能建立在list容器上。

      栈适配器:
      s.empty(),s.size(),s.pop(),s.top() ,s.push(item)
      队列:FIFO queue
      q.empty(),q.size(),q.pop(),q.front(),q.back(),q.push(item)

c++顺序容器