STL组件（components）之容器(container)

青旅半醒 2021-06-24 15:56 550阅读 0赞

容器的分类：序列式容器（sequence container）和关联式容器（association container）。其中，序列式容器又称可序（ordered）群集，每个元素的位置取决于插入时机和地点与元素值没有关系，STL中提供了三个这样的容器：vector、deque和list；关联式容器又称为已序群集，元素位置取决于特定的排序准则，默认情况下排序准则是operater<,每个元素的位置取决于元素值，和插入次序无关，STL中提供了两对这样的容器：set/multiset、map/multimap.

一下是对容器的理解，未必一定正确，仅供自己参考和学习，如有错误，还望指正，谢谢。

总结一：list和set不支持下表操作符operater\[\];因此对于list的遍历可采用以下两种途径：a、采用循环输出（list.front()）并删除(list.pop\_front())第一个元素的方法;b、直接利用迭代器进行遍历；支持下表操作operator\[\]和直接存取container::at()的容器有：vector、deque、string和map。

总结二：在关联容器中，所有元素都按照排序准则而有序，在内存中按照二叉树存储，即每个元素（节点）都有一个父节点和两个子节点，其中左节点比右节点“小”。

以set为例：

\#include<set>  
int array\[5\]=\{ 12, 34, 10, 98, 3\};  
const size\_t array\_size=sizeof(array)/sizeof(array\[0\]);  
std::set<int> set;  
for(size\_t i=0; i<array\_size; \++i)  
\{   
        //把数据插入集合，数据自动排序  
        set.insert(array\[i\]);  
\}  
//此时已经排序了，下面依次输出  
std::set<int>::const\_iterator b=set.begin();  
for(; b!=set.end(); \++b)  
\{   
        std::cout << \*b << '**\\n**';  
\}

总结三：vector、list、deque均支持push\_back()操作，但由于在vector的前端无法进行插入操作（如果可以的话，需要消耗很大的代价），故只有list和deque支持push\_front()操作；对于关联容器没有push\_\*()操作而是用insert()来代替。同时注意区分container::front()与container::back(),这两者返回的是容器里面的元素而不是迭代器，其中，支持这种的容器有：vector、deque、list。

总结四：foreach的实现：

template<typename Iterator,typyname Operater>

Operater foreach(Iterator beg,Iterator end,Operater op)

while(beg!=end)

op(\*beg);

++beg;

return op;

总结五：list的特殊成员函数

1、void list：：unique（）或list：：unique（BinaryPrediction BP）；

移除list之内相邻而重复的元素，使每一个元素都不同于下一个元素。

2、void list：：splice（iterator pos,list&source）

将source的所有元素移动到\*this，并安插到迭代器pos所指位置，调用之后，source清空，此时注意如果\*this和source相同的话，会导致未定义的行为发生；

void list：：splice（iterator pos,list&source，iterator sourcepos）

从source list中，将位于sourcepos位置上的元素移动至\*this，并安插于迭代器pos所指位置，\*this和source可以相同，此时在内部移动；

void list：：splice（iterator pos,list&source，iterator sourcebeg,iterator sourceend）

从source list中，将位于\[sourcebeg,end\]位置上的所有元素移动至\*this，并安插于迭代器pos所指位置，\*this和source可以相同。

3、void list：：sort（）

void list：：sort（CompFunc op）

4、void list：：merge（）

void list：：merge（list&source，CompFunc op）

将source内的所有元素并入\*this，并清空source。

#                     STL容器 #

## 顺序容器 ##

顺序容器将单一类型的元素聚集起来，然后根据位置来存储和访问这些元素。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。

STL中最常用的顺序容器是vector、list、deque。在这里，我不打算介绍如何使用这些容器类的基本函数，这将作为课后作业。我把篇幅放在如何选择使用这三种容器上。

### vector<> ###

vector被称为动态数组，原始的静态数组一旦越界可能会悄无声息的修改掉不该修改的内存，而vector会立即出错，抛出异常。vector具备动态增长的能力，如果空间不够，vector会创建一块更大的连续空间，然后将原来的数据搬迁到新的空间中。vector保证了元素在内存空间上的连续性，所以如果你碰到一个旧式的函数需要接受char\*作为参数，你可以使用下面的代码进行转换：

char\* p=&v\[0\];

f(p);

vector还有的好处是自动释放内存，因此你不需要担心使用char\*的时候由于疏忽造成的内存泄漏。vector的operator\[\]和at函数能够接受元素的索引，在常数时间内访问到需要的元素。

但是由于vector内存自增长的策略，如果频繁的调用push\_back函数往vector里面放入数据，就可能会发生多次的内存重新分配、内存拷贝等操作，在这种情况下，我们可以考虑使用deque或者list.

无论如何，使用stl容器，避免使用原始数组，我本人就已经几年没有使用原始数组了。

### deque<> ###

deque是一个数组，但是内存空间上是不连续的，所以不能像vector那样对C风格的char\*兼容。deque的意思是双向开口的线性容器。

deque允许以常数时间内对头部进行元素的插入和删除操作，vector如果对头部进行这种操作就意味着需要移动后续的所有元素，因此效率极差。

而且deque的内存是多段连续空间组合而成，不存在vector的那种空间不够需要重新分配的代价。

你需要具有以下特性的序列容器吗：（选自<<Effective STL>>）

1）可以使用随机访问迭代器；

2）只要没有删除而且插入只发生在容器结尾，指针和引用的数据就不会失效？这个一个非常特殊的情况，但如果你遇到这种情况，deque就是你梦想的容器。（有趣的是，当插入只在容器结尾时，deque的迭代器也可能会失效，deque是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。）

但是deque也有缺点，因为设计较为复杂，所以用索引访问某个元素或者使用迭代器访问的性能都比vector差。

选择vector还是deque？如果有太多的元素要插入到vector中，并且不能在一开始就预计元素的数目，那么使用deque是有道理的。不过要算笔账，如果通过索引或者迭代器访问元素的操作很频繁，这部分付出的性能代价超过了因为使用deque而节约的初始化容器的时间，还不如使用vector。大多数书籍都推荐使用vector作为默认选项。

要是能事先预料到容器需要容纳多少个元素就太好了，可以使用vector::reserve来预先申请足够的空间，避免了内存再分配。

### list<> ###

list不浪费空间，通常vector总是预先分配一块比实际需要的大的空间，而deque也需要额外的数据结构，list对于空间的利用非常的节约。插入和删除操作及其高效。根据位置访问元素性能不高，基本上是从头到尾的线性访问。

## 迭代器 ##

迭代器的理论依据是iterator 模式。经典著作《设计模式》对迭代器模式的作用如下解释：提供一种方法顺序访问一个聚合对象中各个元素，而又不需要暴露该对象内部表示。

这非常符合STL的设计思想：将数据容器和算法分开，彼此独立设计，最后再用粘合剂将它们撮合在一起。iterator就是这种粘合剂。

比如查找算法函数

template<class InputIterator, class Type>

InputIterator find(InputIterator \_First, InputIterator \_Last, const Type& \_Val);

find函数不关心容器是什么类型，拥有哪些内在结构，他只需要用户将容器提供的表示前后范围的iterator对象作为参数传递进来，然后在这个范围内查找值等于\_Val的元素，并返回用来表示找到的元素位置的iterator对象。

我们来看看下面简单的例子：

\#include <iostream>

\#include <vector>

\#include <algorithm>

using namespace std;

int \_tmain(int argc, \_TCHAR\* argv\[\])

vector<int> v;

v.reserve(1000);//申请1000个int变量的空间

for(int i=0;i<1000;++i)//插入1000个int变量

v.push\_back(i);

//查找值等于5的元素

vector<int>::iterator itor=find(v.begin(),v.end(),5);

if(itor!=v.end())

cout<<\*itor<<endl;//打印找到的元素的值

return 0;

iterator由每个容器自己提供，所以你看到我写代码时使用了vector<int>::iterator，不存在一个全局的iterator类型。每个容器提供的iterator虽然类型可能有区别，但是基本接口都一样，这就是find函数的实现者可以不管容器类型的原因，他只需要调用iterator的方法。

根据移动特性和提供的操作，iterator被分为5类：

1.  input iterator 只读
2.  output iterator 只写
3.  forward iterator 只能向前移动，同时可读可写
4.  bidirectional iterator 可双向移动，同时可读可写
5.  random access iterator 可以跳过n个元素移动，可双向移动，可读写

使用iterator需要小心的是它可能失效。比如：

int \_tmain(int argc, \_TCHAR\* argv\[\])

vector<int> v;

for(int i=0;i<10;++i)

v.push\_back(i);

vector<int>::iterator itor;

for(itor=v.begin();itor!=v.end();++itor)

if(\*itor==5)

v.erase(itor);

return 0;

最后一个循环遍历整个容器，删除值为5的元素，但是这是错误的用法。因为当第一次删除了值为5的元素后，指向该元素的itor变量变为无效，但是循环将执行itor!=v.end()，这句话没什么问题，尽管itor无效，但是它依然不等于v.end(),判断成立。后面的\++itor这个语句不能执行在无效的itor变量上，所以程序崩溃。

问题的关键在于我们不能让itor失效，一种浅陋的做法如下：

int \_tmain(int argc, \_TCHAR\* argv\[\])

vector<int> v;

for(int i=0;i<10;++i)

v.push\_back(i);

vector<int>::iterator itor;

int distance=0;

for(itor=v.begin();itor!=v.end();++itor,++distance)

if(\*itor==5)

v.erase(itor);

itor=v.begin()+distance;

return 0;

这种做法很繁琐，并且没有使用stl强大的算法函数，所以浅陋。高效的做法如下：

int \_tmain(int argc, \_TCHAR\* argv\[\])

vector<int> v;

for(int i=0;i<10;++i)

v.push\_back(i);

v.erase(remove(v.begin(),v.end(),5));

return 0;

std::remove将在指定的范围内，标记删除值等于5的元素，然后返回第一个被标记删除的元素的迭代器。remove会把不需要删除的元素移动到容器的前面，而将需要删除的元素移动到容器的后面。

vector<int>::erase将接受一个iterator参数，真正从容器中删除该iterator指定的元素。

注意：关联容器不该这样用，而应该使用容器自己提供的erase算法，list提供了性能更好的remove成员函数。

## 关联容器 ##

### 基本介绍 ###

基本的关联式容器是map和set。map通过key-value成对的形式组织，key作为索引，而value作为数据。set仅包含一个key，并有效地支持查询某个key是否存在的操作。

multimap和map的区别在于容器可以存储多个相同的key。multiset和set的区别也是一样。

C++标准并没有规定map,set的内部结构。典型情况下，map,Multimap,set,Multiset都是内部使用的平衡二叉树的数据结构，因此查找速度都差不多,存储的元素都需要排序。

标准C++提供了模板类pair<T1,T2>来将key和value组织在一起。你可以使用构造函数创建，也可以使用内联模板函数make\_pair创建：

template<class first, class second>

inline pair<first,second> make\_pair(const first& \_X,const second& \_Y)

pair拥有公有成员变量first(代表key)和last（代表value），你可以直接访问。

举例如下：

\#include <iostream>

\#include <sstream>

\#include <map>

\#include <algorithm>

using namespace std;

int \_tmain(int argc, \_TCHAR\* argv\[\])

std::map<int,string> map;

for(int i=0;i<10;i++)

stringstream stream;

stream<<i;

map.insert(make\_pair(i,stream.str()));

std::map<int,string>::iterator itor=map.find(5);

if(itor!=map.end())

cout<<itor->second<<endl;

return 0;

set的使用这里不再举例。

### std::find和find成员区别 ###

当我们使用std::find在关联式容器中查找一个元素的时候，它总是通过迭代器获得元素的引用并且调用operator==来判断是否等于我们要查找的那个元素，我们称之为相等查找。

但是当我们使用map::find函数完成同样的功能的时候，它总是通过如下表达式：

!Compare(key1,key2) && !Compare(key2,key1)。Compare是用户提供的函数对象，默认是std::less，我们可以自己提供，但是由于为了保证元素的顺序，我们要提供符合operator <操作父语义的函数对象。我们称上面红色的表达式为等价判断。

由于std::find和成员函数find判断依据不一样，就有可能会出现不一致的情况。

比如map的key如果类型为std::string，string是区分大小写的，因此用operator==来判断string(“A”)和string(“a”)是不相等的。但是假如我们提供的Compare函数对象提供的operator()实现忽略大小写，则两者的行为将发生差别。

无论如何，既然我们自己提供了Compare函数对象，我们当然希望后续的各种操作符合我们定义的语义，所以这就引出一条STL基本使用规则：优先使用成员函数而不是全局的函数，假如两个函数执行相同功能的话。

### 标准之外的关联式容器 ###

在标准之外，常常有基于hash算法的容器类，SGI提供了hash\_map,hash\_set等。这些类是无序的关联式容器，内部使用了哈希表数据结构，下一个版本的c++09标准将提供。由于哈希表的平均查找时间是常数O(1)，所以比较适合需要频繁查找操作的容器。

但是hash表操作的最坏执行效率可能非常差，可能是线性的N，在有些情况下就会这样。但那些基于平衡二叉树的容器始终保持在O（logN)。注意，这里的平衡一词不可少，应为如果一棵树退化成类似链表形式，查找效率也将变成O(N)。

所以如果一个服务程序响应客户的请求，进行少数次数的查找，选择STL的基于平衡二叉树的容器能够保证最坏情况下不会让客户大失所望，但是如果面对的是要进行成千上万次的查找操作已完成某个功能，hash表才是不二的选择。

常用的hash算法使用一个hash函数负责根据传入的key计算存放元素的hash表的索引。这里要求hash函数能够快速的算出尽可能不重复的索引，考虑到元素可能非常的多，快速是第一位的，有时候无法避免产生重复的索引，那就需要依赖hash表来解决这个冲突。一种常用的hash表采用了如下结构：

有一个一维数组（称为桶子），每个数组元素实际上都是一个链表，链表中存放的就是要保存的元素。如果有两个key被hash函数计算出了相同的索引，可能是5，那么他们就存放在一个链表中，该链表有两个元素，通过key区分，然后桶中的第五个元素指向该链表。

参考：[http://hi.baidu.com/guoerguoerguoer/blog/item/0d4f8a7bd64b8fe62f73b300.html][http_hi.baidu.com_guoerguoerguoer_blog_item_0d4f8a7bd64b8fe62f73b300.html]

[http_hi.baidu.com_guoerguoerguoer_blog_item_0d4f8a7bd64b8fe62f73b300.html]: http://hi.baidu.com/guoerguoerguoer/blog/item/0d4f8a7bd64b8fe62f73b300.html