`
ribishuangba
  • 浏览: 285265 次
文章分类
社区版块
存档分类
最新评论

十STL容器

 
阅读更多
<meta content="text/html; charset=utf-8" http-equiv="CONTENT-TYPE"> <meta content="OpenOffice.org 2.2 (Linux)" name="GENERATOR"> <meta content="freebird" name="AUTHOR"> <meta content="20070510;9550000" name="CREATED"> <meta content="root" name="CHANGEDBY"> <meta content="20070717;14010300" name="CHANGED"> <style type="text/css"> <!-- @page { size: 8.5in 11in; margin: 0.79in } H1 { margin-top: 0.24in; margin-bottom: 0.23in; line-height: 200%; page-break-inside: avoid } H1.western { font-family: "Liberation Serif", serif; font-size: 22pt } H1.cjk { font-family: "DejaVu Sans"; font-size: 22pt } H1.ctl { font-family: "DejaVu Sans"; font-size: 22pt } H2 { margin-top: 0.18in; margin-bottom: 0.18in; line-height: 173%; page-break-inside: avoid } H2.western { font-family: "Cambria", serif; font-size: 16pt } H2.cjk { font-family: "宋体", "SimSun"; font-size: 16pt } H2.ctl { font-family: "Times New Roman", serif; font-size: 16pt } H3 { margin-top: 0.18in; margin-bottom: 0.18in; line-height: 173%; page-break-inside: avoid } H3.western { font-family: "Liberation Serif", serif; font-size: 16pt } H3.cjk { font-family: "DejaVu Sans"; font-size: 16pt } H3.ctl { font-family: "DejaVu Sans"; font-size: 16pt } P { margin-bottom: 0.08in } --> </style>

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)//插入1000int变量

{

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区分,然后桶中的第五个元素指向该链表。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics