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 ,value)对。它提供基于key的 快速 检索能力,在一个map中key值是唯一的。map提供双向迭代器,即有从前往后的(iterator),也有从后往前的(reverse_iterator)。

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

multimap

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

set

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

multiset

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

小结

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

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

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

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

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

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


常用STL容器举例

一 常用容器举例 

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)用 vectordeque实现,比用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.     forint 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

可以用 listdeque实现,缺省情况下用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上测试通过)




Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐