Prefer C++ （二）

webcenterol

浏览: 923433 次

最近访客更多访客>>

athena507

wyx065747

一往无前bhz

u012363178

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1745)

社区版块

存档分类

2012-02 ( 2)
2011-11 ( 10)
2011-10 ( 112)
更多存档...

4、超强的标准库<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

标准库里有什么呢，同C标准库最大的不同应该是STL。有了STL，不必再写大多的标准数据结构和算法，并且可获得非常高的性能。

Stl中有几个基本的概念：

容器：可容纳各种数据类型的数据结构。

迭代器：可依次存取容器中数据的结构

算法：通过迭代器对容器进行某种操作的函数

举个容易理解的例子：

数组就是个容器，而指针就是迭代器。

接下来将用几小节专门描述stl的概貌。

下面所提到的内容多取自《C++ 标准程序库》一书，以下将不另行说明。

4．1 stl中的容器

标准容器有7种，不同实现有相应的扩充。

7种容器对应的模型如下：

<?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" /><group id="_x0000_s1026" style="MARGIN-TOP: 0px; Z-INDEX: 1; LEFT: 0px; MARGIN-LEFT: 1in; WIDTH: 153pt; POSITION: absolute; HEIGHT: 23.4pt; TEXT-ALIGN: left" coordorigin="3237,12048" coordsize="3060,468"><group id="_x0000_s1027" style="LEFT: 3237px; WIDTH: 3060px; POSITION: absolute; TOP: 12048px; HEIGHT: 468px" coordorigin="3237,12048" coordsize="3060,468"><rect id="_x0000_s1028" style="LEFT: 3237px; WIDTH: 2160px; POSITION: absolute; TOP: 12048px; HEIGHT: 468px"></rect><line id="_x0000_s1029" style="POSITION: absolute" from="3777,12048" to="3777,12516"></line><line id="_x0000_s1030" style="POSITION: absolute" from="4317,12048" to="4317,12516"></line><line id="_x0000_s1031" style="POSITION: absolute" from="4857,12048" to="4857,12516"></line><line id="_x0000_s1032" style="POSITION: absolute" from="5397,12360" to="6297,12360"><stroke endarrow="block"></stroke></line></group><line id="_x0000_s1033" style="POSITION: absolute" from="5397,12048" to="5757,12048"></line><line id="_x0000_s1034" style="POSITION: absolute" from="5397,12516" to="5757,12516"></line></group>vector

其中箭头表示数据增长方向。实际上就是个动态数组。在尾端增删元素具有较佳的性能。

<shapetype id="_x0000_t66" coordsize="21600,21600" o:spt="66" adj="5400,5400" path="m@0,0l@0@1,21600@1,21600@2@0@2@0,21600,,10800xe"><stroke joinstyle="miter"></stroke><formulas><f eqn="val #0"></f><f eqn="val #1"></f><f eqn="sum 21600 0 #1"></f><f eqn="prod #0 #1 10800"></f><f eqn="sum #0 0 @3"></f></formulas><path o:connecttype="custom" o:connectlocs="@0,0;0,10800;@0,21600;21600,10800" o:connectangles="270,180,90,0" textboxrect="@4,@1,21600,@2"></path><handles><h position="#0,#1" xrange="0,21600" yrange="0,10800"></h></handles></shapetype><shape id="_x0000_s1047" style="MARGIN-TOP: 7.8pt; Z-INDEX: 3; LEFT: 0px; MARGIN-LEFT: 54pt; WIDTH: 45pt; POSITION: absolute; HEIGHT: 7.8pt; TEXT-ALIGN: left" type="#_x0000_t66"></shape><group id="_x0000_s1035" style="MARGIN-TOP: 0px; Z-INDEX: 2; LEFT: 0px; MARGIN-LEFT: 1in; WIDTH: 180pt; POSITION: absolute; HEIGHT: 23.4pt; TEXT-ALIGN: left" coordorigin="3237,13296" coordsize="3600,468"><group id="_x0000_s1036" style="LEFT: 3777px; WIDTH: 3060px; POSITION: absolute; TOP: 13296px; HEIGHT: 468px" coordorigin="3237,12048" coordsize="3060,468"><group id="_x0000_s1037" style="LEFT: 3237px; WIDTH: 3060px; POSITION: absolute; TOP: 12048px; HEIGHT: 468px" coordorigin="3237,12048" coordsize="3060,468"><rect id="_x0000_s1038" style="LEFT: 3237px; WIDTH: 2160px; POSITION: absolute; TOP: 12048px; HEIGHT: 468px"></rect><line id="_x0000_s1039" style="POSITION: absolute" from="3777,12048" to="3777,12516"></line><line id="_x0000_s1040" style="POSITION: absolute" from="4317,12048" to="4317,12516"></line><line id="_x0000_s1041" style="POSITION: absolute" from="4857,12048" to="4857,12516"></line><line id="_x0000_s1042" style="POSITION: absolute" from="5397,12360" to="6297,12360"><stroke endarrow="block"></stroke></line></group><line id="_x0000_s1043" style="POSITION: absolute" from="5397,12048" to="5757,12048"></line><line id="_x0000_s1044" style="POSITION: absolute" from="5397,12516" to="5757,12516"></line></group><line id="_x0000_s1045" style="POSITION: absolute" from="3237,13296" to="3777,13296"></line><line id="_x0000_s1046" style="POSITION: absolute" from="3237,13764" to="3777,13764"></line></group>Deque

在两端增删元素具有较佳的性能。

List

双向链表，在任何位置增删元素都具有相近的性能。

上述三种容器称为序列式容器（sequence container）。元素的插入位置同元素的值无关。

Set/Multiset:

此种容器内的元素是已序的，插入任何元素，都按相应的排序准则来确定其位置。

Set中不允许相同元素，multiset中允许存在相同的元素。

<group id="_x0000_s1068" style="MARGIN-TOP: 0px; Z-INDEX: 6; LEFT: 0px; MARGIN-LEFT: 90pt; WIDTH: 153pt; POSITION: absolute; HEIGHT: 85.8pt; TEXT-ALIGN: left" coordorigin="3597,5184" coordsize="3060,1716"><group id="_x0000_s1069" style="LEFT: 3597px; WIDTH: 3060px; POSITION: absolute; TOP: 5184px; HEIGHT: 1716px" coordorigin="3957,2532" coordsize="3060,1716"><oval id="_x0000_s1070" style="LEFT: 3957px; WIDTH: 3060px; POSITION: absolute; TOP: 2532px; HEIGHT: 1716px"></oval><rect id="_x0000_s1071" style="LEFT: 4677px; WIDTH: 360px; POSITION: absolute; TOP: 3000px; HEIGHT: 312px"></rect><rect id="_x0000_s1072" style="LEFT: 5217px; WIDTH: 360px; POSITION: absolute; TOP: 3000px; HEIGHT: 312px"></rect><rect id="_x0000_s1073" style="LEFT: 4677px; WIDTH: 360px; POSITION: absolute; TOP: 3624px; HEIGHT: 312px"></rect><rect id="_x0000_s1074" style="LEFT: 5217px; WIDTH: 360px; POSITION: absolute; TOP: 3624px; HEIGHT: 312px"></rect><rect id="_x0000_s1075" style="LEFT: 5937px; WIDTH: 360px; POSITION: absolute; TOP: 3000px; HEIGHT: 312px"></rect><rect id="_x0000_s1076" style="LEFT: 5937px; WIDTH: 360px; POSITION: absolute; TOP: 3624px; HEIGHT: 312px"></rect></group><line id="_x0000_s1077" style="POSITION: absolute" from="4497,5652" to="4497,5964"></line><line id="_x0000_s1078" style="POSITION: absolute" from="5037,5652" to="5037,5964"></line><line id="_x0000_s1079" style="POSITION: absolute" from="5757,5652" to="5757,5964"></line><line id="_x0000_s1080" style="POSITION: absolute" from="4497,6276" to="4497,6588"></line><line id="_x0000_s1081" style="POSITION: absolute" from="5037,6276" to="5037,6588"></line><line id="_x0000_s1082" style="POSITION: absolute" from="5757,6276" to="5757,6588"></line></group>Map/Multimap:

Map同Multimap的不同在于是否允许相同的元素。

Map与Set的不同在于Map中存放的是成对的key/value。

并根据key对元素进行排序。

上述四种容器称为关联式容器（Associative Container）。特点是在查找时具有非常好的性能。

以上述7种容器为基础，stl还实现了Stacks,Queues,Priority Queues。

用Map来举个例子：

typedef map<string,float> mapforaccount;

//定义

mapforaccount lunch;

//赋值

lunch[“陈勇”]＝50.00;

lunch[“林立坚”]＝35.00;

lunch[“陈阵”]＝45.00;

lunch[“czzs”]=65.00;

//打印

mapforaccount：：iterator pos;

for(pos=lunch.begin();pos!=lunch.end();++pos)

{

cout<<“姓名：”<<pos->first<<”/t”

<<”余额：”<<pos->second<<endl;

}

上述各种容器都有一些成员函数，支持一些基本的操作和对某些算法进行优化。

不同的容器的成员函数并不完全相同。

其中：

l 所有容器都支持以下操作符：＝＝，！＝，<,>,<=,>=。当且仅当两个容器类型相同，元素数目相同，元素顺序相同，并每个元素都相等时＝＝为true。

小于的情况以字典序进行判定。

l insert(),push_front(),push_back()等添加成员得函数

l remove(),pop_front(),pop_back(),[],at()等删除及读取元素的函数。

总之这些函数使你对容器中元素得读写更为方便。

剩下得成员函数，诸如sort(),merge()等是容器根据本身特性对某些算法得优化，实现与下面所讲得算法相同得功能。

可作为动态数组的vector 非常的常用，以他为例来看一下容器都可以为我们做些什么。

构造与析构

vector<Elem> c 产生一个空vector

vector<Elem> c1(c2) 生成一个c2的副本

vector<Elem> c(n) 产生一大小为n的容器，用缺省构造函数生成其中每个元素的值

vector<Elem> c(n,elem) 产生一大小为n的容器，其中每个元素的值都是elem

vector<Elem> c(beg,end) 产生一个以[beg,end]区间为初值的vector

c.~vector<Elem>() 销毁所有元素，并释放内存

非变动性操作

c.size() 返回容器中元素的数量

c.empty() 大小是否为0

c.max_size() 可容纳元素的最大数量

capacity() 重新分配空间前所能容纳的元素的最大数量

reserve() 保留一定大小的空间

c1==c2

c1!=c2

c1<c2

c1>c2

c1<=c2

c1>=c2

赋值操作

c1=c2 将c2的元素全部复制给c1

c.assign(n,elem) 用n个元素填充c

c.assign(beg,end) 用指定区间的内容填充c

c1.swap(c2) c1，c2的内容互换

swap(c1,c2) 同上为全局函数

元素的存取

c.at[idx] 返回索引idx所表示的元素，检查边界

c[idx] 同上但不检查边界

c.front() 返回第一个元素，不检查其是否存在

c.back() 返回最后一个元素，不检查其是否存在

迭代器相关函数

c.begin() 返回指向第一个元素的随机存取迭代器

c.end() 返回指向最后一个元素的随机存取迭代器

c.rbegin() 返回指向第一个元素的逆向迭代器

c.rend() 返回指向最后一个元素的逆向迭代器

安插及移除操作

c.insert(pos,elem) 在pos位置插入一个新元素副本，并返回新元素位置

c.insert(pos,n,elem) 在pos位置插入n个新元素副本

c.insert(pos,beg,end) 在pos位置插入[beg,end）区间内所有元素的副本

c.push_back(elem) 在尾部添加一个elem

c.pop_back() 移除最后一个元素，不回传

c.erase(pos) 移除pos位置的元素，返回下一元素的位置

c.erase(beg,end) 移除[beg,end）区间内所有元素，并传回新位置

c.resize(num) 将元素数量改为num

c.clear() 移除所有元素

看如下的程序段：

这是为说明vector各个成员函数的使用而做的。

typedef vector<string> stringarray;

// PRINT_ELEMENTS负责输出容器中的所有元素

template <class T>

inline void PRINT_ELEMENTS(const T& coll, const char* cptcstr=" ")

{

typename T::const_iterator pos;

cout<< cptcstr<< endl;

for(pos=coll.begin();pos!=coll.end();++pos)

{

cout<< *pos <<' ';

cout<<endl;

}

int main()

{

stringarray filename;//empty vector

//在容器中的元素数量达到10之前不用重新分配内存

filename.reserve(10);

filename.push_back("c://test1.emf");

filename.push_back("c://test2.emf");

filename.push_back("c://test3.emf");

filename.push_back("c://test4.emf");

filename.push_back("c://test5.emf");

filename.push_back("c://test6.emf");

PRINT_ELEMENTS(filename,"After push_back:");

cout<< "max_size():" <<filename.max_size() <<endl;

cout<< "size():" <<filename.size() <<endl;

cout<< "capacity():" <<filename.capacity()<<endl;

//在第一个元素的位置插入

filename.insert(filename.begin(),"d://ie.emf");

PRINT_ELEMENTS(filename,"After insert:");

cout<< "Now the first element is: "<< filename[0] << endl;

// back()返回最后一个元素

cout<< "Now the last element is: "<< filename.back() << endl;

//为tempfilename赋初值

stringarray tempfilename=filename;

PRINT_ELEMENTS(tempfilename,"Before erase:");

//删除前三个元素

tempfilename.erase(tempfilename.begin(),tempfilename.begin()+3);

PRINT_ELEMENTS(tempfilename,"after erase:");

//删除最后一个元素

tempfilename.pop_back();

PRINT_ELEMENTS(tempfilename,"after pop_back():");

//来个恐怖的,这个说明vector在内存中是连续存放的

vector<char> v;

v.resize(41);

strcpy(&v[0],"this is a test");

printf("%s/n",&v[0]);

return 0;

}

输出结果为：

After push_back:

c:/test1.emf

c:/test2.emf

c:/test3.emf

c:/test4.emf

c:/test5.emf

c:/test6.emf

max_size():357913941

size():6

capacity():10

After insert:

d:/ie.emf

c:/test1.emf

c:/test2.emf

c:/test3.emf

c:/test4.emf

c:/test5.emf

c:/test6.emf

Now the first element is: d:/ie.emf

Now the last element is: c:/test6.emf

Before erase:

d:/ie.emf

c:/test1.emf

c:/test2.emf

c:/test3.emf

c:/test4.emf

c:/test5.emf

c:/test6.emf

after erase:

c:/test3.emf

c:/test4.emf

c:/test5.emf

c:/test6.emf

after pop_back():

c:/test3.emf

c:/test4.emf

c:/test5.emf

this is a test

分享到：

闲话高手 | 编程本质论

2003-12-07 22:29
浏览 571
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

Prefer C++ （二）

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

Prefer C++ （二）

评论

发表评论

相关推荐

最近访客更多访客>>