Prefer C++ （二） (转)[@more@]

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

 

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

Stl中有几个基本的概念：

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

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

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

举个容易理解的例子：

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

 

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

 

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

4．1 stl中的容器

 

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

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

 

vector

 

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

 

Deque

 

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

 

 

List 

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

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

 

 

 

Set/Multiset:

 

 

 

 

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

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

 

Map/Multimap:

 

 

 

 

 

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

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

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

 

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

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

用Map来举个例子：

typedef map 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<<“姓名：”<first<<” ”

  <<”余额：”<second<

}

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

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

其中：

 

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

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

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

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

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

 

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

 

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

 

构造与析构

vector c  产生一个空vector

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

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

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

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

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

 

非变动性操作

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

c.empty()  大小是否为0

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

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

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

c1==c2

c1!=c2

c1

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 stringarray;

 

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

template

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<

  }

  }

int main()

  {

  stringarray filename;//empty vector

 

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

  filename.reserve(10);

 

  filename.push_back("c: est1.emf");

  filename.push_back("c: est2.emf");

  filename.push_back("c: est3.emf");

  filename.push_back("c: est4.emf");

  filename.push_back("c: est5.emf");

  filename.push_back("c: est6.emf");

 

  PRINT_ELEMENTS(filename,"After push_back:");

 

  cout<< "max_size():" <

  cout<< "size():" <

  cout<< "capacity():" <

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

  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 v;

  v.resize(41);

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

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

  return 0;

  }

输出结果为：

After push_back:

c: est1.emf

c: est2.emf

c: est3.emf

c: est4.emf

c: est5.emf

c: est6.emf

max_size():357913941

size():6

capacity():10

After insert:

d:ie.emf

c: est1.emf

c: est2.emf

c: est3.emf

c: est4.emf

c: est5.emf

c: est6.emf

Now the first element is: d:ie.emf

Now the last element is: c: est6.emf

Before erase:

d:ie.emf

c: est1.emf

c: est2.emf

c: est3.emf

c: est4.emf

c: est5.emf

c: est6.emf

after erase:

c: est3.emf

c: est4.emf

c: est5.emf

c: est6.emf

after pop_back():

c: est3.emf

c: est4.emf

c: est5.emf

this is a test