c++容器学习

转：http://blog.csdn.net/zhanghaodx082/article/details/17919401

1,using学习

   两种方式：第一，完全引入命名空间y，如，using namespace std; 以后要用std中定义的符号就方便了，如cin>> ;

                       第二，只引入要用的符号，如，using std::cin;

   注意：.h头文件中，最好不要只用第一种方式，因为.h文件在预处理时会完全复制到.cpp文件中，导致包含该.h的文件都引入了该命名空间。

2,各种容器

  1）string类型

  定义和初始化：string a;

                              string b(a);

                              string b("hello");

                              string b(5,‘m‘);

   string的输入：cin>>a; 输入时会忽略开头的空白字符（包括空格，换行符，制表符），读取字符时再次遇到空白字符时，读取终止; 如，输入“    hello”，则a为“hello”

    读入未知数目的string对象，while(cin>>a);

    另外，可以用getline(输入流对象，string对象)函数，如，while(cin,a) ，开头并不忽略空白字符。

    string操作：s.empty() （为空，则返回1） ; s.size() （返回string::size_type类型==unsigned）; s[n] ; s1+s2 ; s1 = s2 ;s1==s2 ; s1 != s2 ; s1>s2 ;s1>=s2 ; s1

    string单个字符的操作（包括char），在cctype头文件中定义。

  2）vector类型：类模板

    定义和初始化：vector v1;

                                vector v2(v1);

                                vector v2(n,i);

                                vector v2(n);

    操作：v.empty()

                v.size() （返回vector::size_type）

                v.push_back()

                v[n]

                v1=v2

                v1==v2 , v1!=v2,v1>v2,v1>=v2,v1

  3）bitset类型：类模板

    定义和初始化：bitset b;  b有n位，每位都为0;

                                bitset b(u); b是unsigned long型的u的一个副本; eg， bit a(0xffff); // bits0......15设为1 ;   bit a(0xffff);  //bits0.......15被设为1,16......31是0

                                bitset b(s); b是string对象a中含有的位串的副本;  eg，string a = "1100"; bitset b(a);  //b中，第2和3的位置是1,其余为0

                                bitset b(s,pos,n); b是s中从位置pos开始的n个位的副本。 eg，string str(111111110000000); bitset b(str,5,4);  //如果省略第三个参数，则表示从指 定  的开始位置一直到结束

    bitset对象上的操作：

   顺序容器：根据元素位置来存储和访问元素，包括：vector，list，deque ; 顺序容器适配器stack，queue，priority_queue

    1,几种顺序容器的异同点

    vector：

    内部数据结构：数组

    访问元素：随机访问每个元素，所需要的时间为常量。

    添加删除元素：在末尾增加或删除元素所需时间与元素数目无关，在中间或开头增加或删除元素所需时间随元素数目呈线性变化。

    迭代器：在内存重新分配后，迭代器会失效。当把超过capacity()-size()个元素插入vector中时，内存会重新分配，所有的迭代器都将失 效；否则，指向当前元素以后的任何元素的迭代器都将失效。当删除元素时，指向被删除元素以后的任何元素的迭代器都将失效。

    list：

   内部数据结构：双向循环链表

   访问元素：不能随机访问元素，所需时间与链表长度成线性关系

   添加删除元素：任何地方添加删除元素所需时间为常量

   迭代器：添加元素不会是迭代器失效 ; 删除元素，只会使被删除元素的迭代器失效，而其他迭代器不会失效。

    duque：

   内部数据结构：数组

   访问元素：随机访问每个元素，所需要的时间为常量

   添加删除元素：开头和结尾添加和删除元素与元素数目ti无关，其他位置添加和删除元素与元素数目成线性关系

   迭代器：增加元素，所有迭代器都失效 ; 删除头尾元素，只有对应迭代器失效，删除其他元素，全部迭代器失效。

   2,顺序容器介绍

     1）定义和初始化： C c;  

                                  C c(c1);

                                  C c(iter1,iter2);  //iter1是复制起始的迭代器，iter2是复制元素最后一个元素的下一个元素的迭代器;可以是同种容器的不同类型，甚至完全不同的容器类    型，也可以用指针

                                  C c(n,t);

                                  C c(n);

     容器内元素的类型约束：元素必须支持赋值元算，元素对象必须可以复制。引用不支持赋值，I/O库类型不支持复制和赋值，所以不能用作容器类型。

     迭代器：iterator

     iterator支持的操作：*iter,iter->mem , ++iter,--iter,iter++,iter-- , iter1==iter2,iter1!=iter2 ; vector和deque类型的迭代器还提供的额外操作：iter+n,iter-n , iter1+=iter2,iter1-iter2 , >,>=,

    2）顺序容器的操作：添加/删除元素，设置容器大小，获取容器的第一个和最后一个元素

     容器定义的类型别名：size_type , iterator , const_iterator , reverse_iterator , const_reverse_iterator , difference_type , value_type , reference , const_reference

     获取迭代器：c.begin() , c.end() , c.rebegin() , c.rend()  注：如果容器是const，则返回的迭代器为const类型，即const_iterator ; 如果不是const容器，则返回普通迭代器。

     容器中添加元素：c.push_back(k) ; c.insert(k) ; c.insert(iter,n,t) ; c.insert(iter,iter1,iter2) ;      c.push_front(k)（只是用于listhe deque）

     容器中删除元素：c.erase(p),c.erase(b,e),c.clear(),c.pop_back(),c.pop_front()

     容器关系操作符：前提是，1>容器类型完全相同 ; 2>容器元素类型支持关系操作，容器关系符操作本质上是容器元素关系符操作。

     容器大小的操作：c.size() , c.max_size() , c.resize(n) , c.resize(n,t) , c.empty()

     访问元素：c.back() （返回容器最后一个元素的引用）, c.front() （返回容器第一个元素的引用）, c[n] （返回下标为n的元素的引用，只适合vector，deque）, c.at(n) （返回下标为n的元素的引用，只适合vector和deque）

     赋值和swap：c1=c2 ; 删除c1中的元素，赋值c2中的元素到c1,c1和 c2容器类型和元素类型必须相同

                           c1.swap(c2) ; 不会插入和删除元素，效率较高，为时间常量；且操作后迭代器不会失效

                           c.assign(iter1,iter2) ;  删除c中元素，把迭代器iter1到iter2范围内的元素赋值给c；iter不能指向c，iter指向元素可以和c中元素不同

                           c.assign(n,t)

      vector内存分配：c.size()和c.capacity()： 前一个是容器内元素个数，后一个是容器空间大小，即最多可容纳元素个数

                                 c.resize()和c.reserve()：前一个是重新分配能容纳n和元素的空间，后一个是重新分配空间，包括额外预留空间

           上述vector内存分配问题，是因为vector原型是数组，元素必须在内存中连续存储，所以容器自增长时，必须删除原来元素，重新分配一个更大连续存 储空间，所以效率   较低，所以vector实现了一种机制，自动重新分配空间时，会预留一部分多于空间。而list没有这个问题，因为list原型是链表，不需要连续存储空 间。

    容器适配器，用现有容器初始化容器适配器，容器适配器提供一些特殊的操作。即容器适配器是特殊的容器。