C++笔记-泛型编程(续

2017-04-11

容器种类

　　STL具有容器概念和容器类型.概念是具有名称的通用类别,容器类型是可用于创建具体对象的模板.

容器概念

　　容器概念描述了所有STL容器都需要满足的一些要求.他是个概念化的抽象基类,说他是一个概念化的抽象基类,是因为容器类不真正使用继承机制.
所有的容器都提供某种特定的特征和操作,下表对一些通用特征进行了总结:

　上表中的复杂度表示执行操作所需的时间,从快到慢依次为:
　○ 编译时间
　○ 固定时间
　○ 线性时间
　如果复杂度为编译时间,则操作将在编译时执行,执行时间为0;固定复杂度意味着操作发生在运行阶段,但独立于对象中的元素数目;线性复杂度意味着时间与元素数目成正比;

C++11新增的容器要求

　　下表列出了C++11新增的通用容器要求,其中rv表示类型为X的非常量右值,如函数返回值,另外要求X::iterator满足正向迭代器的要:
;

序列(sequence)

　　序列概念增加了迭代器至少是正向迭代器的要求,并且要求元素按严格的线形顺序排列,即存在第一个元素,最后一个元素,除了端点的俩元素外,每个元素前后都分别有一个元素,且不会在两次迭代之间发生变化.这7个STL容器类型都是序列: deque,forward_list,list,queue,priority_queue,stack,vector;
　　
　　下表表示了序列所需要的操作,t表示类型为T(存在容器中的值的类型)的值,n表示整数,p,q,i,j表示迭代器:
　　
　　
　　因为模板deque,list,queue,priority_queue,stack和vector都是序列的概念模型,所以他们中的一些还可以使用下表所列出的操作:
　　

详细介绍

　　vector:　

　　　　前面说过了,不做赘述

　　deque:　

　　　　deque模板类表示双端队列,实现类似vector,他支持随机访问,但不同的是:从deque对象的开始位置插入和删除元素的时间是固定的,而vector是在结尾处提供了固定时间的插入和删除,在而别的地方都是线性时间,但vector的速度似乎快一点..

　　list:

　　　　list模板类表示双向链表.除了第一个和最后一个元素外,每个元素都与前后的元素相连接.他和vector的区别在于,list在链表中任意位置插入和删除的时间是固定的(废话).list擅长的是元素的快速插入和删除.但他不支持数组表示法和随机访问.从容器中管插入或删除元素后,链表迭代器指向的位置不变,但数据不同.然后插入新元素并不会移动已有元素,只是修改链接信息.
　　　　list的成员函数,Alloc有默认值:
　　　　　　○ void merge(list & x) //将链表x与调用链表合并.两个链表必须排序,合并后的链表在调用链表中,x为空.这个函数复杂度为线性时间;
　　　　　　○ void remove(const T & val) //从链表中删除val的所有实例,复杂度为线性时间;
　　　　　　○ void sort() //使用<运算符排序,复杂度为NlogN;
　　　　　　○ void splice(iterator pos, list x) //将链表x的内容插入到pos的前面,x为空,复杂度为固定时间;
　　　　　　○ void unique() //将连续的相同元素压缩为单个元素(删除重复元素),复杂度为线性时间
　　　　　　list的示例代码

　　　　insert()和splice()之间的区别在于:insert()将原始区间的副本插入到目标地址,而splice()则将原始区间移动到目标地址,且splice()方法执行后,迭代器指向的元素不变.

　　forward_list(C++11):

　　　　　forward_list容器类实现了单链表.也就是每个节点都只连接到下一个节点,而没有连接到前一个节点.所以他只需要正向迭代器,并且是不可反转容器;

　　queue:

　　　　　queue模板类是个适配器类.他让底层类(默认为deque)展示典型的队列接口.但他限制比deque多,不允许随机访问队列,不允许遍历队列,他可以:
　　　　　○ bool empty()const //如果队列为空,返回true,否则返回false
　　　　　○ size_type size()const //返回队列中元素的数目
　　　　　○ T& front() //返回指向队首元素的引用
　　　　　○ T& back() //返回指向队尾元素的引用
　　　　　○ void push(const T& x) //在队尾插入x
　　　　　○ void pop() //删除队首元素

　　priority_queue:

　　　　该类是另一个适配器,支持的操作和queue一样,区别是在priority_queue中最大的元素会被移动到队首;
　　　　构造函数参数:

1 2	priority_queue<int> pql; priority_queue<int> pq2(greater<int>)

　　stack:

　　　　该类也是个适配器,和queue相似,他给底层类(默认是vector)提供了典型的栈接口;但他不允许随机访问栈元素,不允许遍历栈,只能用一些栈的基本操作,如压入,弹出,查看栈顶值,检查元素数目,测试栈是否为空,他还可以:
　　　　○ bool empty() const //如果栈为空则返回true,否则返回false
　　　　○ size_type size() const //返回栈中元素数目
　　　　○ T& top() //返回指向栈顶元素的引用
　　　　○ void push(const T& x) //在顶部插入x
　　　　○ void pop() //删除栈顶元素

　　array(C++11):

　　　　非SLT容器,其长度为固定,所以也就没有调整容器大小的操作(如push_back(),insert()),但定义了一些成员函数如operator [] ()和at().可将很多STL算法用于他(如copy(),for_each());

关联容器(associative container)

　　关联容器是将值于键值关联在一起,并使用键来查找值.表达式X::key_type指出了键的类型.他们提供了对元素的快速访问(查找).STL提供了四种关联容器: set, mulitiset,map,multimap. 前两种在文件set.h中,后两者在map.h中定义.
　　最简单的关联容器是set,其值类型与键值相同,键是唯一的,对于set来说值就是键; multiset类似set,只是可以有多个键值相同,比如: 如果建和值的类型为int,则multiset对象包含的内容可以有1,2,2,2,3,5等.而在map中,值于键的类型不同,键和值是一一对应的;而multimap和map差不多,只是一个键可以与多个值相关联; 　　

　　set示例:

　　const int N = 6;
　　string s1[N] = {"ass","we"."can","booy","next","can"};
　　set<string> A(s1,s1+N);
　　ostream_iteratior<string,char> out(cout," ");
　　copy(A.begin(),A.end(),out);

　　和别的容器相似set也使用模板来制定要储存的值类型,与其他容器相似,set也有一个将迭代器区间作为参数的构造函数.上述代码片段输出表明键是唯一的,虽然数组里有俩for,但如果两个集合包含相同的值,则这个值将在并集中只出现一次,所以for在集合中只出现了一次,这是因为set的键值是唯一的,且集合是经过排序的:cout: ass booy can next we
　　set_union()函数接受五个迭代器参数,前两个迭代器定义了第一个集合的区间,接下来的两个参数定义了第二个集合的区间,最后一个参数是输出迭代器,指出将结果集合复制到什么位置.举个栗子,要显示集合A,B的并集可以:

1	set_union(A.begin(),A.end(),B.begin(),B.end(),ostream_iterator<string,char> out(cout," "));

假设要将记过放到C集合中,而不是现实他,则最后一个参数应该是个匿名insert_iterator,将信息复制给C:

1	set_union(A.begin(),A.end(),B.begin(),B.end(),insert_iterator<set<string>>(C,C.begin()));

　　方法lower_bound()将键作为参数并返回一个迭代器,迭代器指向集合中的第一个不小于键参数的成员,upper_boun()将键作为参数并返回一个指向集合中第一个大于键参数的成员.函数set_intersection()和set_difference()粉蝶查找交集和获得两个集合的差,参数与set_union()相同;

　　multimap示例:

　　基本的multimap声明使用模板参数指定键的类型和存储的值类型.他一个键可以与多个键值相关联.下面声明创建一个multimap对象,键类型为int,值类型为string,第三个模板参数是可选的,用于对键排序,默认使用less<>:

1	multimap<int,string> codes;

　　如果要用区号作为键来存城市名字,一种方法是创建个pair,再将它插入:

pair<const int, string> item(213,"Los Angeles");
codes.insert(item);
//或创建匿名pair对象:
codes.insert(pair<const int, string> (213,"Los Angeles");)

　　对于pair对象,可以使用first和second访问其两个部分:

1 2	pair<const int, string> item(213,"Los Angeles"); cout << item.first << item.second << endl;

　　成员函数count()接受键作为参数,返回具有该键的元素数数目.lower_bound()和upper_bound()将键作为参数,并分别返回集合中第一个不小于键参数的成员和第一个大于键参数的成员;equal_range()用键做参数,返回两个迭代器,表示的区间与该键匹配.

　　无序关联容器

　　无需关联容器也是将值与键关联起来,并用键找值,但底层差别在于关联容器基于树形结构,而无序关联容器基于哈希表,速度奇快.比如unordered_set,unordered_map,unordered_multiset,unordered_multimap;