STL容器的实现原理 

 
STL共有六大组件
 1、容器。2、算法。3、迭代器。4、仿函数。6、适配器。

STL容器的实现原理

STL来管理数据十分方便,省去了我们自己构建数据结构的时间.其实,STL的实现也是基于我们常见的数据结构.

序列式容器：
vector-数组，元素不够时再重新分配内存，拷贝原来数组的元素到新分配的数组中。
list－单链表。
deque-分配中央控制器map(并非map容器)，map记录着一系列的固定长度的数组的地址.记住这个map仅仅保存的是数组的地址,真正的数据在数组中存放着.deque先从map中央的位置(因为双向队列，前后都可以插入元素)找到一个数组地址，向该数组中放入数据，数组不够时继续在map中找空闲的数组来存数据。当map也不够时重新分配内存当作新的map,把原来map中的内容copy的新map中。所以使用deque的复杂度要大于vector，尽量使用vector。

stack-基于deque。

queue-基于deque。
heap-完全二叉树，使用最大堆排序，以数组(vector)的形式存放。
priority_queue-基于heap。
slist-双向链表。

关联式容器：
set,map,multiset,multimap-基于红黑树(RB-tree)，一种加上了额外平衡条件的二叉搜索树。

hash table-散列表。将待存数据的key经过映射函数变成一个数组(一般是vector)的索引，例如：数据的key%数组的大小＝数组的索引(一般文本通过算法也可以转换为数字)，然后将数据当作此索引的数组元素。有些数据的key经过算法的转换可能是同一个数组的索引值(碰撞问题，可以用线性探测，二次探测来解决)，STL是用开链的方法来解决的，每一个数组的元素维护一个list，他把相同索引值的数据存入一个list，这样当list比较短时执行删除，插入，搜索等算法比较快。

hash_map,hash_set,hash_multiset,hash_multimap-基于hash table。

综上所述大家应该知道了什么情况下该使用哪一个STL容器更合适,可以在适当时候避免使用一些影响效率的STL容器.

这里我们不涉及容器的基本操作之类，只是要讨论一下各个容器其各自的特点STL中的常用容器包括：顺序性容器（vector、deque、list）、关联容器（map、set）、容器适配器（queue、stac）

STL是C/C++开发中一个非常重要的模板，而其中定义的各种容器也是非常方便我们大家使用。下面，我们就浅谈某些常用的容器。这里我们不涉及容器的基本操作之类，只是要讨论一下各个容器其各自的特点。STL中的常用容器包括：顺序性容器（vector、deque、list）、关联容器（map、set）、容器适配器（queue、stac）。

1、顺序性容器

（1）vector
vector是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问。由于具有连续的存储空间，所以在插入和删除操作方面，效率比较慢。vector有多个构造函数，默认的构造函数是构造一个初始长度为0的内存空间，且分配的内存空间是以2的倍数动态增长的，即内存空间增长是按照20,21,22,23.....增长的，在push_back的过程中，若发现分配的内存空间不足，则重新分配一段连续的内存空间，其大小是现在连续空间的2倍，再将原先空间中的元素复制到新的空间中，性能消耗比较大，尤其是当元素是非内部数据时(非内部数据往往构造及拷贝构造函数相当复杂)。vector的另一个常见的问题就是clear操作。clear函数只是把vector的size清为零，但vector中的元素在内存中并没有消除，所以在使用vector的过程中会发现内存消耗会越来越多，导致内存泄露，现在经常用的方法是swap函数来进行解决：  

vector<int> V;V.push_back(1); V.push_back(2);V.push_back(1); V.push_back(2);
vector<int>().swap(V); 或者 V.swap(vector<int>());

利用swap函数，和临时对象交换，使V对象的内存为临时对象的内存，而临时对象的内存为V对象的内存。交换以后，临时对象消失，释放内存。

-------------------

STL: 知道vector吗，一个自然数数组，要删除其中的奇数，写出代码。这个需要注意的是erase删除结点，则该结点的iterator会失效，同时erase会返回下一个有效迭代器，所以iter++只有在偶数的时候才运行。 继续问到iter++和++iter的区别，回答前者会产生一个临时变量，后者的效率更高，如果前面有=的话，得到的值不一样。 vector是怎么存储的，如果让你实现vector，你怎么做，首先说了下STL里面的vector，内存如何分配的，构造函数等等。开始用数组实现vector，然后问一定要写成类似MS提供的STL里面的vector，提示说不用，写个基本框架就可以了，就直接写vector代码，然后写vector的插入操作，注意vector满时

-------------------


（2）deque
deque和vector类似，支持快速随机访问。二者最大的区别在于，vector只能在末端插入数据，而deque支持双端插入数据。deque的内存空间分布是小片的连续，小片间用链表相连，实际上内部有一个map的指针。deque空间的重新分配要比vector快，重新分配空间后，原有的元素是不需要拷贝的。

（3）list
list是一个双向链表，因此它的内存空间是可以不连续的，通过指针来进行数据的访问，这使list的随机存储变得非常低效，因此list没有提供[]操作符的重载。但list可以很好地支持任意地方的插入和删除，只需移动相应的指针即可。

（4）在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
  　　1) 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
  　　2) 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
  　　3) 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque

2、关联容器

（1）map
map是一种关联容器，该容器用唯一的关键字来映射相应的值，即具有key-value功能。map内部自建一棵红黑树（一种自平衡二叉树），这棵树具有数据自动排序的功能，所以在map内部所有的数据都是有序的，以二叉树的形式进行组织。这是map的模板：

template < class Key, class T, class Compare= less<Key>, class Allocator=allocator< pair<const Key,T> > > class map;

从模板中我们可以看出，再构造map时，是按照一定的顺序进行的。map的插入和删除效率比其他序列的容器高，因为对关联容器来说，不需要做内存的拷贝和移动，只是指针的移动。由于map的每个数据对应红黑树上的一个节点，这个节点在不保存你的数据时，是占用16个字节的，一个父节点指针，左右孩子指针，还有一个枚举值（标示红黑色），所以map的其中的一个缺点就是比较占用内存空间。

map简介

　map是STL的一个关联容器（associative container）之一，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。　

map中key值是唯一 

    例子：如果已存在一个键值对(编号,用户名):(1001,"jack")，而我们还想插入一个键值对(1001,"mike") 运行时会报错（不是报错，准确的说是，返回插入不成功！）。而我们又的确想这样做，即一个键对应多个值，幸运的是multimap可是实现这个功能。

map中的类型定义

        关联数组（associative array）是最有用的用户定义类型之一，经常内置在语言中用于文本处理等。一个关联数组通常也称为map，有时也称字典（dictionary），保存一对值。第一个值称为key、第二个称为映射值mapped-value。

// map::begin/end
#include <iostream>
#include <map>

int main ()
{
  std::map<char,int> mymap;
  std::map<char,int>::iterator it;

  mymap['z'] = 100;
  mymap['a'] = 200;
  mymap['z'] = 300;

  // show content:
  for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

  return 0;
}

a => 200
z => 300

（2）set
set也是一种关联性容器，它同map一样，底层使用红黑树实现，插入删除操作时仅仅移动指针即可，不涉及内存的移动和拷贝，所以效率比较高。set中的元素都是唯一的，而且默认情况下会对元素进行升序排列。所以在set中，不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，再插入新元素。不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取。set模板原型：

template <class Key, class Compare=class<Key>, class Alloc=STL_DEFAULT_ALLOCATOR(Key) > class set;
set支持集合的交(set_intersection)、差(set_difference)、并(set_union)及对称差(set_symmetric_difference) 等一些集合上的操作。

3、容器适配器

（1）queue
queue是一个队列，实现先进先出功能，queue不是标准的STL容器，却以标准的STL容器为基础。queue是在deque的基础上封装的。之所以选择deque而不选择vector是因为deque在删除元素的时候释放空间，同时在重新申请空间的时候无需拷贝所有元素。其模板为：
template < TYPENAME _Sequence="deque<_TP" typeneam _Tp,> > class queue;

（2）stack
stack是实现先进后出的功能，和queue一样，也是内部封装了deque，这也是为啥称为容器适配器的原因吧（纯属猜测）。自己不直接维护被控序列的模板类，而是它存储的容器对象来为它实现所有的功能。stack的源代码原理和实现方式均跟queue相同。

下面是他们的区别：

我们常用到的STL容器有vector、list、deque、map、multimap、set和multiset，它们究竟有何区别，各自的优缺点是什么，为了更好的扬长避短，提高程序性能，在使用之前需要我们了解清楚。

verctor

vector类似于C语言中的数组，它维护一段连续的内存空间，具有固定的起始地址，因而能非常方便地进行随机存取，即 [] 操作符，但因为它的内存区域是连续的，所以在它中间插入或删除某个元素，需要复制并移动现有的元素。此外，当被插入的内存空间不够时，需要重新申请一块足够大的内存并进行内存拷贝。值得注意的是，vector每次扩容为原来的两倍，对小对象来说执行效率高，但如果遇到大对象，执行效率就低了。

list

list类似于C语言中的双向链表，它通过指针来进行数据的访问，因此维护的内存空间可以不连续，这也非常有利于数据的随机存取，因而它没有提供 [] 操作符重载。

deque

deque类似于C语言中的双向队列，即两端都可以插入或者删除的队列。queue支持 [] 操作符，也就是支持随机存取，而且跟vector的效率相差无几。它支持两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率
也差不多。或者我们可以这么认为，deque是vector跟list的折中。

map

map类似于数据库中的１:１关系，它是一种关联容器，提供一对一(C++ primer中文版中将第一个译为键，每个键只能在map中出现一次，第二个被译为该键对应的值)的数据处理能力，这种特性了使得map类似于数据结构里的红黑二叉树。

multimap

multimap类似于数据库中的１:Ｎ关系，它是一种关联容器,提供一对多的数据处理能力。

set

set类似于数学里面的集合，不过set的集合中不包含重复的元素，这是和vector的第一个区别，第二个区别是set内部用平衡二叉树实现，便于元素查找，而vector是使用连续内存存储，便于随机存取。

multiset

multiset类似于数学里面的集合，集合中可以包含重复的元素。

小结

在实际使用过程中，到底选择这几种容器中的哪一个，应该根据遵循以下原则：

１、如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；

2、如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；

3、如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；

4、如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；

5、如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset。

常用ＳＴＬ容器举例

一 常用容器举例 

1 vector：

       vector类似于动态数组，直接访问元素，从后面快速插入或者删除，示例代码如下：

[cpp]  view plain copy

1. #include <iostream>  
2. #include <vector>//包含vector  
3. using namespace std;//指定命名空间  
4.   
5. int main()  
6. {  
7.     cout<<"----------vector test-----------"<<endl;  
8.       
9.     //定义一个vector  
10.     vector <int> vect;  
11.     vector <int> vect1(12);//12个int类型元素，每个元素的初始值均为0  
12.     vector <int> vect2(12,9);//12个int，初试值均为9  
13.       
14.   
15.     //使用数组初始化vector  
16.     int a[]={0,1,2,3,4,5,6,7,8,9,0};  
17.     //vector <数据类型> <容器名> (<开始地址>,<结束地址的下一个地址> )。执行过vt中元素为1,2,3  
18.     vector <int> vt(a+1,a+4);  
19.     //在尾部压入3个值  
20.     vt.push_back(1);  
21.     vt.push_back(2);  
22.     vt.push_back(3);  
23.   
24.     //定义迭代器iterator  
25.     vector <int>::iterator iter=vt.begin();//起始地址  
26.     vector <int>::iterator iter_end=vt.end();//结束地址,两个地址都是指针类型  
27.     //遍历vt  
28.     for(;iter!=iter_end;iter++)  
29.     {  
30.         cout<<*iter<<endl;  
31.     }  
32.       
33.     //弹出一个元素  
34.     vt.pop_back();  
35.       
36.     //以下两行重新获得起始和结尾地址  
37.     iter=vt.begin();  
38.     iter_end=vt.end();  
39.     cout<<"----------executed pop_back------"<<endl;  
40.     for(;iter!=iter_end;iter++)  
41.     {  
42.         cout<<*iter<<endl;  
43.     }  
44.   
45.     //插入元素  
46.     cout<<"----------insert into------------"<<endl;  
47.     //插入格式：vector.insert(<起始地址>,<插入的数量>,<元素值>);如果插入的数量为1，则第二个参数可以被省略  
48.     vt.insert(vt.begin()+1,3,9);  
49.     iter=vt.begin();  
50.     iter_end=vt.end();  
51.     for(;iter!=iter_end;iter++)  
52.     {  
53.         cout<<*iter<<endl;  
54.     }  
55.       
56.     //删除元素  
57.     cout<<"----------erase-------------------"<<endl;  
58.     //删除格式1为：vector.erase(<删除元素的地址>);  
59.     //删除格式2为：vector.erase(<删除元素的起始地址>，<终止地址>);  
60.     iter=vt.begin();  
61.     iter_end=vt.end();  
62.     vt.erase(iter+1,iter_end);//删除第二个到最后一个的元素  
63.     iter_end=vt.end();  
64.     for(;iter!=iter_end;iter++)  
65.     {  
66.         cout<<*iter<<endl;  
67.     }  
68.     return 1;  
69. }  

   2  list

  list 为双向链表，可以从任何地方插入或者删除的，其示例代码如下：

[cpp]  view plain copy

1. #include <iostream>  
2. #include <list>  
3. using namespace std;  
4.   
5. void main()  
6. {  
7.     list<int> c1;  
8.     c1.push_back(1);//从尾部push数据（结点）到list中   
9.     c1.push_back(2);   
10.     c1.push_back(3);  
11.     c1.push_back(4);  
12.       
13.     c1.push_front(0);//从头部push数据（结点）到list中   
14.       
15.     c1.pop_back();//从尾部pop数据（结点）出去   
16.     int& i = c1.back();//获取list中尾部数据（结点）   
17.     const int& ii = c1.front();//获取list中头部 数据（结点）  
18.       
19.       
20.     cout << "The last integer of c1 is " << i << endl;  
21.     cout << "The front interger of c1 is " << ii << endl;  
22.       
23.     cout << "for循环读出数据举例：" << endl;  
24.     //循环遍历数据举例  
25.     list<int>::iterator it; //定义遍历指示器(类似于int i=0)   
26.     for(it = c1.begin() ; it != c1.end() ;it++)  
27.     {  
28.         cout << *it << endl;  
29.     }  
30.     system("pause");  
31. }  

3 deque：

 deque: 是一个double-ended queue,
 1)支持随即存取，也就是[]操作符，
 2)支持两端操作，push(pop)-back(front)，在两端操作上与list效率差不多

 因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则： 
 1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector 
2、如果你需要大量的插入和删除，而不关心随即存取，则应使用list 
3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。

示例代码如下：

[cpp]  view plain copy

1. /*deque: 是一个double-ended queue, 
2.     1)支持随即存取，也就是[]操作符， 
3.     2)支持两端操作，push(pop)-back(front)，在两端操作上与list效率差不多 
4.  
5.     因此在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：  
6.     1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector  
7.     2、如果你需要大量的插入和删除，而不关心随即存取，则应使用list  
8.     3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。 
9. */  
10.   
11. #include <iostream>  
12. #include <deque>  
13. using namespace std;  
14.   
15. void printDeque(const deque<int>& d)  
16. {  
17.     cout<<"\n使用下标:\n";  
18.     for (unsigned int i = 0; i < d.size(); i++)  
19.     {  
20.     cout<<"d["<<i<<"] = "<<d[i]<<", ";  
21.     }  
22.   
23.   
24.     cout<<"\n使用迭代器\n";  
25.     deque<int>::const_iterator iter = d.begin();  
26.     for (;iter != d.end(); iter ++)  
27.     {  
28.     cout<<"d["<<iter-d.begin()<<"] = "<<(*iter)<<", ";  
29.     }  
30.     cout<<endl;  
31. }  
32.   
33. void main()  
34. {  
35. //创建deque  
36. deque<int> d1;                          //创建一个没有任何元素的deque对象  
37. deque<int> d2(10);                      //创建一个具有10个元素的deque对象，每个元素值为默认  
38. deque<double> d3(10, 5.5);              //创建一个具有10个元素的deque对象,每个元素的初始值为5.5  
39. deque<double> d4(d3);                   //通过拷贝一个deque对象的元素值, 创建一个新的deque对象  
40.   
41. //初始化赋值：同vector一样,使用尾部插入函数push_back()  
42. for (int i = 1; i < 6 ; i++)  
43.    d1.push_back(i*10);  
44.   
45.   
46. //遍历元素: 1-下标方式 2-迭代器方式 反向遍历（略）  
47. cout<<"printDeque(d1) : "<<endl;  
48. printDeque(d1);  
49.   
50. //元素插入：尾部插入用push_back()，头部插入用push_front()，其它位置插入用insert(&pos, elem)  
51. cout<<"d1.push_front(100): "<<endl;  
52. d1.push_front(100);  
53. printDeque(d1);  
54. cout<<"d1.insert(d1.begin()+3, 200): "<<endl; //支持随机存取(即[]操作符)，所以begin()可以+3  
55. d1.insert(d1.begin()+2,200);  
56. printDeque(d1);  
57.   
58. //元素删除 尾部删除用pop_back();头部删除用pop_front();   
59. //任意迭代位置或迭代区间上的元素删除用erase(&pos)/erase(&first, &last)；删除所有元素用clear();  
60. cout<<"d1.pop_front(): "<<endl;  
61. d1.pop_front();  
62. printDeque(d1);  
63.   
64. cout<<"d1.erase(d1.begin()+1): "<<endl;  
65. d1.erase(d1.begin()+1); //删除第2个元素d1[1]  
66. printDeque(d1);  
67.   
68. cout<<"d1.erase(d1.begin(), d1.begin() + 2) = "<<endl;  
69. d1.erase(d1.begin(), d1.begin() + 2);  
70. printDeque(d1);  
71.   
72. cout<<"d1.clear() :"<<endl;  
73. d1.clear();  
74. printDeque(d1);  
75.   
76.   
77.   
78. }  

4 容器适配器：stack

（1）可用 vector, list, deque来实现

（2）缺省情况下，用deque实现      

template<classT, class Cont = deque<T> > 

               class stack {    …..    }；

（3）用 vector和deque实现，比用list实现性能好

（4）stack是后进先出的数据结构，

（5）只能插入、删除、访问栈顶的元素的操作:  push:     插入元素pop:       弹出元素      top: 返回栈顶元素的引用

测试代码如下：

[cpp]  view plain copy

1. <span style="font-size:16px;">#include <iostream>  
2. #include <Stack>  
3. using namespace std;  
4.   
5. void main()  
6. {  
7.     stack<double> s;//可以是各种数据类型；  
8.     for( int i=0; i < 10; i++ )  
9.         s.push(i);  
10.     while(!s.empty())  
11.     {  
12.         printf("%lf\n",s.top());  
13.         s.pop();  
14.     }  
15.     cout << "the size of  s: " << s.size() << endl;  
16. }  
17. </span>  

5 deque

可以用 list和deque实现，缺省情况下用deque实现

          template<class T, class Cont = deque<T>>

           class queue {  …  };

 FIFO先进先出的数据结构，也有push,pop,top函数，但是push发生在队尾，pop,top发生在队头，

示例代码如下：

[cpp]  view plain copy

1. /************************************************************************/  
2. /*  
3.  
4. 详细用法: 
5. 定义一个queue的变量     queue<Type> M 
6. 查看是否为空范例        M.empty()    是的话返回1，不是返回0; 
7. 从已有元素后面增加元素   M.push() 
8. 输出现有元素的个数      M.size() 
9. 显示第一个元素          M.front() 
10. 显示最后一个元素        M.back() 
11. 清除第一个元素          M.pop() 
12.                                                                      */  
13. /************************************************************************/  
14.   
15. #include <iostream>  
16. #include <queue>  
17. #include <assert.h>  
18.   
19. using namespace std;  
20.   
21. int main()  
22. {  
23.     queue <int> myQ;  
24.     int i;  
25.     cout<< "现在 queue 是否 empty? "<< myQ.empty() << endl;   
26.       
27.     for( i =0; i<10 ; i++)  
28.     {  
29.         myQ.push(i);  
30.     }  
31.     for( i=0; i<myQ.size(); i++)  
32.     {  
33.         printf("myQ.size():%d\n",myQ.size());  
34.         cout << myQ.front()<<endl;  
35.         myQ.pop();  
36.     }  
37.       
38.     system("PAUSE");   
39.       
40.     return 0;  
41. }  

二 常用算法

1  count（）and  count_if()

 count()在序列中统计某个值出现的次数

 count_if()在序列中统计与某谓词匹配的次数

示例代码如下：

[cpp]  view plain copy

1. #include <iostream>  
2. #include <algorithm>  
3. #include <functional>  
4. #include <string>  
5. #include <vector>  
6.   
7. using namespace std;  
8.   
9.   
10. void CountFuc()  
11. {  
12.     const int VECTOR_SIZE = 8 ;  
13.       
14.     // Define a template class vector of strings  
15.     typedef vector<string > StringVector ;  
16.       
17.     //Define an iterator for template class vector of strings  
18.     typedef StringVector::iterator StringVectorIt ;  
19.       
20.     StringVector NamesVect(VECTOR_SIZE) ;   //vector containing names  
21.       
22.     string value("Sea") ;  // stores the value used  
23.     // to count matching elements  
24.       
25.     StringVectorIt start, end, it ;  
26.       
27.     int result = 0 ;   // stores count of elements  
28.     // that match value.  
29.       
30.     // Initialize vector NamesVect  
31.     NamesVect[0] = "She" ;  
32.     NamesVect[1] = "Sells" ;  
33.     NamesVect[2] = "Sea" ;  
34.     NamesVect[3] = "Shells" ;  
35.     NamesVect[4] = "by" ;  
36.     NamesVect[5] = "the" ;  
37.     NamesVect[6] = "Sea" ;  
38.     NamesVect[7] = "Shore" ;  
39.       
40.     start = NamesVect.begin() ;   // location of first  
41.     // element of NamesVect  
42.       
43.     end = NamesVect.end() ;       // one past the location  
44.     // last element of NamesVect  
45.       
46.     // print content of NamesVect  
47.     cout << "NamesVect { " ;  
48.     for(it = start; it != end; it++)  
49.         cout << *it << " " ;  
50.     cout << " }\n" << endl ;  
51.       
52.     // Count the number of elements in the range [first, last +1)  
53.     // that match value.  
54.     result = count(start, end, value) ;  
55.       
56.     // print the count of elements that match value  
57.     cout << "Number of elements that match \"Sea\" = "  
58.         << result << endl  ;  
59. }  
60.   
61.   
62. int MatchFirstChar( const string& str)  
63. {  
64.     string s("S") ;  
65.     return s == str.substr(0,1) ;  
66. }  
67.   
68.   
69. void CountIfFuc()  
70. {  
71.     const int VECTOR_SIZE = 8 ;  
72.       
73.     // Define a template class vector of strings  
74.     typedef vector<string > StringVector ;  
75.       
76.     //Define an iterator for template class vector of strings  
77.     typedef StringVector::iterator StringVectorIt ;  
78.       
79.     StringVector NamesVect(VECTOR_SIZE) ;   //vector containing names  
80.       
81.     StringVectorIt start, end, it ;  
82.       
83.     int result = 0 ;   // stores count of elements  
84.     // that match value.  
85.       
86.     // Initialize vector NamesVect  
87.     NamesVect[0] = "She" ;  
88.     NamesVect[1] = "Sells" ;  
89.     NamesVect[2] = "Sea" ;  
90.     NamesVect[3] = "Shells" ;  
91.     NamesVect[4] = "by" ;  
92.     NamesVect[5] = "the" ;  
93.     NamesVect[6] = "Sea" ;  
94.     NamesVect[7] = "Shore" ;  
95.       
96.     start = NamesVect.begin() ;   // location of first  
97.     // element of NamesVect  
98.       
99.     end = NamesVect.end() ;       // one past the location  
100.     // last element of NamesVect  
101.       
102.     // print content of NamesVect  
103.     cout << "NamesVect { " ;  
104.     for(it = start; it != end; it++)  
105.         cout << *it << " " ;  
106.     cout << " }\n" << endl ;  
107.       
108.     // Count the number of elements in the range [first, last +1)  
109.     // that start with letter 'S'  
110.     result = count_if(start, end, MatchFirstChar) ;  
111.       
112.     // print the count of elements that start with letter 'S'  
113.     cout << "Number of elements that start with letter \"S\" = "  
114.         << result << endl  ;  
115. }  
116.   
117.   
118. void main()  
119. {  
120.     CountFuc();  
121.     CountIfFuc();  
122. }  

 

2 find and  find_if

  find       在序列中找出某个值的第一次出现的位置
  find_if     在序列中找出符合某谓词的第一个元素

示例代码如下：

[cpp]  view plain copy

1. #include <algorithm>  
2. #include <iostream>  
3.   
4. using namespace std;  
5.   
6.   
7. void FindFuc()  
8. {  
9.     const int ARRAY_SIZE = 8 ;  
10.     int IntArray[ARRAY_SIZE] = { 1, 2, 3, 4, 4, 5, 6, 7 } ;  
11.       
12.     int *location ;   // stores the position of the first  
13.     // matching element.  
14.       
15.     int i ;  
16.       
17.     int value = 4 ;  
18.       
19.     // print content of IntArray  
20.     cout << "IntArray { " ;  
21.     for(i = 0; i < ARRAY_SIZE; i++)  
22.         cout << IntArray[i] << ", " ;  
23.     cout << " }" << endl ;  
24.       
25.     // Find the first element in the range [first, last + 1)  
26.     // that matches value.  
27.     location = find(IntArray, IntArray + ARRAY_SIZE, value) ;  
28.       
29.     //print the matching element if any was found  
30.     if (location != IntArray + ARRAY_SIZE)  // matching element found  
31.         cout << "First element that matches " << value  
32.         << " is at location " << location - IntArray << endl;  
33.     else                                    // no matching element was  
34.         // found  
35.         cout << "The sequence does not contain any elements"  
36.         << " with value " << value << endl ;  
37. }  
38.   
39. int IsOdd( int n)  
40. {  
41.     return n % 2 ;  
42. }  
43.   
44.   
45. void FindIfFuc()  
46. {  
47.     const int ARRAY_SIZE = 8 ;  
48.     int IntArray[ARRAY_SIZE] = { 1, 2, 3, 4, 4, 5, 6, 7 } ;  
49.     int *location ;   // stores the position of the first  
50.     // element that is an odd number  
51.     int i ;  
52.       
53.     // print content of IntArray  
54.     cout << "IntArray { " ;  
55.     for(i = 0; i < ARRAY_SIZE; i++)  
56.         cout << IntArray[i] << ", " ;  
57.     cout << " }" << endl ;  
58.       
59.     // Find the first element in the range [first, last -1 ]  
60.     // that is an odd number  
61.     location = find_if(IntArray, IntArray + ARRAY_SIZE, IsOdd) ;  
62.       
63.     //print the location of the first element  
64.     // that is an odd number  
65.     if (location != IntArray + ARRAY_SIZE)  // first odd element found  
66.         cout << "First odd element " << *location  
67.         << " is at location " << location - IntArray << endl;  
68.     else         // no odd numbers in the range  
69.         cout << "The sequence does not contain any odd numbers"  
70.         << endl ;  
71.   
72. }  
73.   
74.   
75. void main()  
76. {  
77.     FindFuc();  
78.     FindIfFuc();  
79. }  

3 for_each()

函数声明如下：

template<class InIt, class Fun>
    Fun for_each(InIt first, InIt last, Fun f);

          在区间【first，last）上的每个元素执行f操作

示例代码如下：

[cpp]  view plain copy

1. #include <iostream>  
2. #include <vector>  
3. #include <algorithm>  
4.   
5. using namespace std;  
6.   
7.   
8. // prints the cube of integer n  
9. void PrintCube(int n)  
10. {  
11.     cout << n * n * n << " " ;  
12. }  
13.   
14. void main()  
15. {  
16.     const int VECTOR_SIZE = 8 ;  
17.       
18.     // Define a template class vector of integers  
19.     typedef vector<int > IntVector ;  
20.       
21.     //Define an iterator for template class vector of integer  
22.     typedef IntVector::iterator IntVectorIt ;  
23.       
24.     IntVector Numbers(VECTOR_SIZE) ;   //vector containing numbers  
25.       
26.     IntVectorIt start, end, it ;  
27.       
28.     int i ;  
29.       
30.     // Initialize vector Numbers  
31.     for (i = 0; i < VECTOR_SIZE; i++)  
32.         Numbers[i] = i + 1 ;  
33.       
34.     start = Numbers.begin() ;   // location of first  
35.     // element of Numbers  
36.       
37.     end = Numbers.end() ;       // one past the location  
38.     // last element of Numbers  
39.       
40.     // print content of Numbers  
41.     cout << "Numbers { " ;  
42.     for(it = start; it != end; it++)  
43.         cout << *it << " " ;  
44.     cout << " }\n" << endl ;  
45.       
46.     // for each element in the range [first, last)  
47.     // print the cube of the element  
48.     for_each(start, end, PrintCube) ;  
49.     cout << "\n\n" ;  
50. }  

 

4 unique

  unique --常用来删除重复的元素，将相邻的重复的元素移到最后，返回一个iterator指向最后的重复元素，所以用它来删除重复元素时必须先排序

示例代码如下：

[cpp]  view plain copy

1. #include <iostream>  
2. #include <algorithm>  
3. #include <vector>  
4. #include <string>  
5. using namespace std;  
6.   
7.   
8. void main()  
9. {  
10.     string str;  
11.     vector<string> words;  
12.     while(cin>>str&&str!="#")  
13.     {  
14.         words.push_back(str);  
15.     }  
16.       
17.     sort(words.begin(),words.end());  
18.     vector<string>::iterator end_unique =  
19.         unique(words.begin(),words.end());  
20.     words.erase(end_unique,words.end());  
21.       
22.       
23.     vector<string> ::iterator ite=words.begin();  
24.     for(;ite!=words.end();ite++)  
25.     {  
26.         cout<<*ite<<"   ";  
27.     }  
28.       
29.     cout<<endl;  
30. }  

 

5 常用排序算法

常用排列算法如下：
1 sort    对给定区间所有元素进行排序  
2 stable_sort  对给定区间所有元素进行稳定排序  
3 partial_sort  对给定区间所有元素部分排序  
4 partial_sort_copy 对给定区间复制并排序

示例代码如下：

[cpp]  view plain copy

1. #include <iostream>  
2. #include <algorithm>  
3. #include <stdlib.h>  
4. #include <time.h>  
5. #include <VECTOR>  
6. using namespace std;  
7.   
8.   
9. const int N=10;  
10.   
11. void print(const vector<int>& v)  
12. {  
13.     vector<int>::const_iterator ite=v.begin();  
14.     for(;ite!=v.end();ite++)  
15.     {  
16.         cout<<*ite<<"  ";  
17.     }  
18.   
19.     cout<<endl;  
20. }  
21.   
22. void Create(vector<int>& v)  
23. {  
24.     srand((unsigned int)time(NULL));  
25.     v.resize(N);  
26.     for(int i=0;i<N;i++)  
27.         v[i]=rand()%100;  
28. }  
29.   
30.   
31. // bool cmp(int arg1,int arg2)  
32. // {  
33. //  return arg1<arg2;  
34. // }  
35.   
36.   
37. void sort1(vector<int> v)  
38. {  
39.     sort(v.begin(),v.end());  
40.     cout<<"after sort funtion:\n";  
41.     print(v);  
42. }  
43.   
44. void sort2(vector<int> v)  
45. {  
46.     stable_sort(v.begin(),v.end());  
47.     cout<<"after stable_sort funtion:\n";  
48.     print(v);  
49. }  
50.   
51. void sort3(vector<int> v)  
52. {  
53.     partial_sort(v.begin(),v.begin()+v.size()/2,v.end()); //对前半部分排序  
54.     cout<<"after partial_sort funtion:\n";  
55.     print(v);  
56. }  
57.   
58. void sort4(vector<int> v)  
59. {  
60.     vector<int> temp;  
61.     temp.resize(v.size());  
62.     partial_sort_copy(v.begin(),v.end(),temp.begin(),temp.end()); //复制并排序  
63.     cout<<"after partial_sort_copy funtion:\n";  
64.     print(temp);  
65. }  
66.   
67.   
68. void main()  
69. {  
70.     vector<int> v;  
71.   
72.     Create(v);  
73.     cout<<"before sort:\n";  
74.     print(v);  
75.   
76.     sort1(v);  
77.     sort2(v);  
78.     sort3(v);  
79.     sort4(v);  
80. }  

6 生成全排列

next_permutation（）的原型如下：

template<class BidirectionalIterator>
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
BidirectionalIterator _First,
BidirectionalIterator _Last,
BinaryPredicate _Comp
);
两个重载函数,第二个带谓词参数_Comp,其中只带两个参数的版本,默认谓词函数为"小于".，返回值为bool类型

示例代码如下：

[cpp]  view plain copy

1. #include <iostream>  
2. #include <algorithm>  
3. using namespace std;  
4.   
5. void permutation(char* str,int length)  
6. {  
7.     sort(str,str+length);  
8.     do  
9.     {  
10.         for(int i=0;i<length;i++)  
11.             cout<<str[i];  
12.         cout<<endl;  
13.     }while(next_permutation(str,str+length));  
14.       
15. }  
16. int main(void)  
17. {  
18.     char str[] = "acb";  
19.     cout<<str<<"所有全排列的结果为："<<endl;  
20.     permutation(str,3);  
21.     system("pause");  
22.     return 0;  
23. }  

（注 ：以上所有代码在vc6.0上测试通过）