STL

STL 是 C++ 标准程序库的核心。STL 内的所有组件都由模板构成,因此元素可以是任意型别。

STL六部分为:容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)。

容器(containers)

用于管理某一类对象的集合。

Sequence Containers(序列容器)

向量(vector):连续存储数据,在当前空间不够时,从新分配当前2倍的空间,并把数据进行拷贝(因此,插入数据可能导致迭代器失效)。

      erase删除元素时,会把后面数据都向前移动,因此耗时且可能让迭代器失效。

列表(list):有节点构成的双向链表。空间运用绝对精准不浪费。不支持随机访问。

双向对列(deque):存储连续的指向不同元素的指针构成的数组。可向前或向后扩展。

        实质是分段连续的,由中控器map维持其整体连续的假象,每段由vector实现。

栈(stack):先进后出的排列。基于deque。

队列(queue):先进先出的排列。基于deque。

 优先队列(priority_queue):元素按照某种次序的队列。

Associative Containers(关联容器)

集合(set):节点构成红黑树,节点按照某种方式排序,且任意两个节点数据不同。不能直接改变元素值,之能删除再插入。

多重集合(multset):与set区别为允许存在两个相同元素的集合。

映射(map):由键值对组成的集合,内部有序。

多重映射(multimap):与map区别为允许相同键存在的映射,可以通过lower_bound与upper_bound找到某个key下所有value。

 Unordered Containers(无序容器)

无序集合(Unordered Set):采用HashTable Separate Chaining 实现

unordered_multiset:Hash组织的map,关键字可以重复。

无序映射(Unordered Map):采用HashTable Separate Chaining 实现

unordered_multimap:Hash组织的map,关键字可以重复。

迭代器(iterators)

用于遍历容器的元素集合。

常说,迭代器在STL中用来将算法和容器联系起来,起着一种黏和剂的作用。

迭代器分为:iterator,const_iterator(只能读)

前向迭代器(Forward iterator) :只能够以自增方式 向前迭代。

双向迭代器(Bidirectional iterator) :迭代器只能自增自减。如:set,map等。

随机访问迭代器(Random-access iterator):可以进行,迭代器+=n。如:vector,deque。

输入型迭代器(Input iterator):向前选代时能够读取value。即按顺序依次读取。

输出型迭代器(Output iterator): 向前迭代时能够涂写value。即按顺序依次写入。

空间配置器(allocator)

负责空间分配与管理。

第一级配置器直接采用malloc和free进行空间分配。

第二级配置器采用策略避免过多内存碎片。

对于超过128字节,采用一级配置器。对于空间消耗采用8的整数倍,维护一个16个free-list存储小块未使用空间,分别用来存储8,16,24,....的小块空间。若free-list没有空间则申请128字节并放入free-list。

配接器(adapters)

算法(algorithms)

作用于容器,如对容器的初始化,排序等操作。

仿函数(functors)

相关推荐