泛型编程与STL(三):容器

一.何为容器

二.为什么容器

三.如何使用容器

四.深入容器

一.何为容器

       在STL中。算法，迭代器，容器是三个紧密联系的组件。容器提供保存数据的地方，迭代器提供对容器访问操作的通用接口，而算法利用迭代器访问数据提供对数据的操作。容器作为数据的存储组件，同时也为存储的数据提供了访问，修改操作的接口。而STL为它的容器规定了一组通用接口的规范，这使得STL的容器的接口具有了一致性。例如vector,list它们都有push_back方法，虽然它们的实现方法不同，但是push_back的作用确是相同的。

1.1 容器的concept.

       要理解各类STL容器的特点，就必须先理解STL是怎么定义各类容器的concept的。concept是一组requirement的集合，而STL的容器都会是满足一个或多个concept的model，所以理解了各类concept的requirement就理解了容器的特点。        容器的concept有一定的层次结构，大致结构如下所示，其中箭头表示两个concept之间的refine关系：

       container这个concept是容器最基本的concept，其他所有的concept都是这个concept的refine。        其中 中间这条主线的concept主要根据container所能提供的iterator来定义的。foward container的要求是容器能够提供forward iterator，reversible container要求容器能够提供bidredirection iterator............        sequence container 与 associate container 这两个concept的 主要区别在于： sequence container将单一类型元素聚集起来，然后根据位置来存储访问。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。associate contaqiner中的每个元素都有一个对应的键值，容器通过键值来存储和读取元素，元素在容器中的位置与元素对应的键值有关。         sequence container：sequence container中又精炼出了两个concept及front insert container与back insert container，这两个concept要求能够提供在最前端，最末尾处访问，删除，插入的接口。这两个refine的concept并不是互斥的，如deque及是front insert container的model，又是back insert container的model。而vector只是back insert container的model。        associate container：associate container中有三组refine的concept，并且每组内的concept是互斥的。 simple associate container 与pair associate container互斥，simple associate container要求元素以自身的值为键值，而pari associate container则要求为元素提供一个额外的键值。set就是一个simple associate container，而map则相反。 unique associate container与multiple associate container互斥，unique associate container要求存储的键值只有一个唯一的元素对应，有multiple associate container则允许一个键值可以对应多个元素。如map，sort是unique associate container，而multiset multimap则是multiple associate container。 sorted associate container与hashed associate container互斥，sorted associate container 按照键值的比较结果排序组织元素（想象二叉搜索树等结构，这与它们的存储方式类似），而hashed associate container则按照键值的hash table来组织元素。unordered_map是hashed associate container而map则是sorted associate container。最后总结下set是simple associate container ,unique associate container,sorted associate container的model。multimap是pair associate container，multiple associate container与sorted associate container的model。

1.2.容器容纳的元素

       容器对元素的存储有两点必须的掌握：        1. 容器对元素的存储是基于值语义的，而不是基于指针语义。这句话的意思是当我们传入一个值给容器存储时，容器会拷贝一份该元素的副本，而不是存储一个该元素的指针或者引用在容器内。也就是说传入一个值给容器容器会先缔造一份该元素的拷贝然后将拷贝存入容器。（即使我们存入的数据类型是指针，容器也会拷贝一份指针的副本存储）        2 .容器存储的元素的生命周期是不会超过容器本身的。当容器销毁时，容器内的指针也会被销毁掉。所以当你存储的是指针的时候要小心了，你必须在容器销毁之前把指针的值取出来然后销毁指针指向的对象，因为指针容器只会销毁指针本身，而不是指针指向的对象。        3. 容器一般都会使用默认的内存分配器，这点你不用担心，但是如果你想使用自己的内存管理器也可以进行定制然后通过模板参数传给容器。但是默认的内存分配器的特点造就了容器不支持多态。或许这么说不太好，举个例子，如果有两个类A与B，B继承A，然后当你有一个类B的对象，将其存入类A的容器内，那么将其取出的时候你会发现这个对象属于B的部分已经被切除了。

二.为什么容器

             为什么使用STL容器，主要有一下几点：        1.使用STL容器让你免于反复造轮子，一些得到多年检验的组件将为你提供高质的服务。你不用自己在去写什么动态数组，链表，红黑树什么的了。        2.使用STL容器可以享受配套的iterator与算法。买一送二何乐不为。        3.STL容器当然是跨平台的支持。

三.如何使用容器

 3.1STL容器对存储元素的要求

       在使用STL容器存储元素之前你得先明白，STL容器对于被存储的元素都有哪些要求，以及它为这些元素提供哪些保障。 容器对这种元素提供的功能除了受限于容器本身提供的接口外，还受限与元素本身提供的特性。理论来说一个什么操作都不支持的元素也可以使用容器，只是容器对这种元素几乎不提供任何接口而已。看下面例子：

class TestA
{
//我们屏蔽了默认提供的内置方法
private:
	TestA&  operator=(const TestA &b);
	TestA(const TestA& b);
	TestA();
	~TestA();
	TestA& operator*();
	const TestA& operator*() const;

};
int main(int argc,char* argv[])
{
//之所以用new而且不delete,是不让vector<TestA>的析构函数不被实例化
	vector<TestA>* a=new vector<TestA>();
}
           

这个程序能编译通过，也能运行。为什么？主要是因为我们除了使用了vector的默认构造函数之外，没有使用vector的任何函数，所以我们提供的元素本身也不需要提供任何额外的功能。 template member function只有在我们调用了它之后它才会在编译时实例化（虽然不够准确，但是重点不在这里），这里我们只是调用了vector默认构造函数，而它对元素本身没有任何要求所以能通过编译。但是如果我们调用了vector其他的member function 比如push_back，这时候编译时push_back会实例化，push_back实例化之后编译器便会对push_back型别推导，这时候因为我们的元素没有提供任何push_back要求的功能，所以型别推导会失败。        上述例子只是为了说明，STL容器能提供使用的接口并不是默认所有都可以使用的，只有当我们提供的存储元素满足了某些条件之后我们才能使用STL容器的相应功能。        总的来说对于sequence container容器我们需要提供以下的三个方法才能“正常”的使用，copy construction,copy assignment以及析构函数。而要使用如下面这种功能我们则需要提供一个默认构造函数。

vector<Foo> ok(10);//在容器内以默认构造函数构造10个Foo对象
           

       而对于associate container容器元素我们除了要提供sequence container所需要的三个方法之外，我们还需要让associate 元素的键值有一个相关比较函数。默认情况下associate container会为我们生成一个STL预置的less<T>函数对象，像下面这样：

template < class T,                       
           class Compare = less<T>,        // 如果我们自己不提供key的函数比较对象,则STL为我们提供一个，并在内部调用key的<进行比较
           class Alloc = allocator<T> >    
           > class set
           

less<T>这个函数对象会被container调用来比较我们的两个键值大小，less<T>内部默认使用的键值的<符号进行比较。我们只要为元素的键值提供<操作就可以使用associate container的默认的less<T>函数对象进行比较。或者我们也可以提供一个我们自己的函数对象，对key进行比较。注意这里提供的函数对象必须是Predicate binary function object的model(提供两个传入参数，返回结果是bool型别的函数对象)。 严格若排序       associate container 元素的键值之间的比较必须满足 严格若排序。这个概念简单的理解就是满足下面这个的条件：        1.X<X始终不成立.        2.不可能X<Y成立 而Y<X也成立.        3.X<Y，Y<Z，则X<Z

照例举个例子吧，假设我有一个类A有两个变量value1,value2。我想以value1的顺序进行排序，如果两个对象的value1相等则用value2进行排序。当我们改写<的时候我们就应该这么做

//编译器默认为我们提供的copy assignment与copy construction足够了
//如果你的value不是内置的型别你应该小心的对待他们的拷贝动作。
class A
{
public:
	A(int var1,int var2):value1_(var1),value2_(var2){}
	int value1_;
	int value2_;
	bool operator<(const A& a) const
	{
		//value1的值相等我们用value2的值来比较
		if(value1_!=a.value1_)
			return value1_<a.value1_;
		else
			return value2_<a.value2_;
	}

};
int main(int argc,char* argv[])
{
	set<A> seta;
	seta.insert(A(2,9));
	seta.insert(A(2,1));
	seta.insert(A(3,2));
	seta.insert(A(1,1));
	seta.insert(A(1,2));
	seta.insert(A(2,3));
	for(set<A>::iterator it=seta.begin();it!=seta.end();it++)
	{
		printf("%d,%d\n",it->value1_,it->value2_);
	}
}
           

输出结果： 1，1 1，2 2，1 2，3 2，9 3，2

3.2 容器适配器

       目前STL提供了三种针对sequence container的适配器，分别是stack,queue,priority_queue。下面是三种适配器对被适配的底层容器的要求： stack：

• back()
• push_back()
• pop_back()

queue：

• front()
• back()
• push_back()
• pop_front()

priority_queue：

• front()
• push_back()
• pop_back()
• random_access concept的container

在STL容器中满足所有的sequence container都能满足stack的要求，而只有list,dequeue可以满足queue的要求，vector，deque则可以满足priority_queue的要求。               在没有没有提供适配容器的情况下调用这些adaptor的话它们会选用默认的container进行适配，stack默认选择的deque作为其适配容器，queue默认选择也选择deque,而priority_queue则默认选择了vector。以下是这些适配器的声明：

template < class T, class Container = vector<T>,
           class Compare = less<typename Container::value_type> > class priority_queue;

template < class T, class Container = deque<T> > class queue;

template < class T, class Container = deque<T> > class stack;
           

不得不提到的一点是priority_queue中元素的优先级比较默认是使用的预制的binary predicate function的model“less<T>”来进行的，而这个function object默认则会使用元素的"<"符号进行比较所以，我们需要为存储在priority_queue中的提供"<"比较符，如果我们希望使用默认的function object的话。同样的提供的"<"也必须满足strict weak ordering。

四：深入容器

这个主题留待下节吧