目录

一：泛型编程          

二：什么是STL

三：STL发展

四：STL组件

五：容器

六：类型成员

七：适配器

八：迭代器

九：算法

十：顺序容器

十一：向量 vector

十二：双端队列 queue

十三：列表 list

十四：关联容器

十五：map

十六：multimap

十七：set

十八：multiset

十九：迭代器

二十：函数对象

二十一：已经集成的函数对象

二十二：自定义函数对象

二十三：标准C++库中的算法

二十四：STL算法的头文件

二十五：标准函数

二十六：泛型算法例子

二十七：自定义函数作为算法参数                

---

一：泛型编程          

1. 将程序写得尽可能通用  

2. 将算法从特定的数据结构中抽象出来，成为通用的

3. C++的模板为泛型程序设计奠定了关键的基础

二：什么是STL

STL（Standard Template Library），即标准模板库，是一个高效的C++程序库

    被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分

    包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性

从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming）

     在这种思想里，大部分基本算法被抽象，被泛化，独立于与之对应的数据结构，用于以相同或相近的方式处理各种不同情形

从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的

    基于模板(template)

三：STL发展

1971 : David R. Musser 开始倡导Generic Programming 概念

1979 : Alexander Stepanov 创造STL

1987 : Alex 和Musser 开发出一套Ada library

???? : Alex 先后在AT&T 及HP实验室以C 及C++实验大量的体系结构和算法形式。

1992 : Meng Lee 加入称为另一位主要贡献者

1993/11 : Alex 于ANSI/ISO C++ 会议展示

1994 夏: STL 被纳入C++标准

四：STL组件

Container(容器) 各种基本数据结构

Adapter(适配器) 可改变containers或function object接口的一种组件

Algorithm(算法) 各种基本算法如sort、search…等

Iterator(迭代器)* 连接containers和algorithms

Function object(函数对象) *

Allocator(分配器)*

五：容器

容器类是容纳、包含一组元素或元素集合的对象

异类容器类与同类容器类

顺序容器与关联容器

七种基本容器：向量（vector）、双端队列（deque）、链表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）

标准容器的成员绝大部分都具有共同的名称

六：类型成员

七：适配器

适配器是一种接口类

    为已有的类提供新的接口

    目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合

三种类型的适配器：

    容器适配器：用来扩展7种基本容器，它们和顺序容器相结合构成栈、队列和优先队列容器

    迭代器适配器

    函数对象适配器 

八：迭代器

迭代器是面向对象版本的指针，它们提供了访问容器、序列中每个元素的方法

九：算法

C++标准模板库中包括70多个算法

    其中包括查找算法，排序算法，消除算法，记数算法，比较算法，变换算法，置换算法和容器管理等等

这些算法的一个最重要的特性就是它们的统一性，并且可以广泛用于不同的对象和内置的数据类型

十：顺序容器

顺序容器的接口

插入方法

push_front()，push_back()，insert()，运算符“=”

删除方法

pop() ，erase()，clear()

迭代访问方法

使用迭代器

其他顺序容器访问方法（不修改访问方法）

front()，back()，下标[]运算符

十一：向量 vector

1. 向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）

2. 数据结构很像一个数组，所以与其他容器相比，vector 能非常方便和高效访问单个元素，支持随机访问迭代子

3. 向量是动态结构，它的大小不固定，可以在程序运行时增加或减少

    与数组不同，向量的内存用尽时，向量自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区；这是向量类的优点

头文件：#include <vector>

vector 基本操作

(1)头文件

#include<vector>

(2)创建vector对象

vector<int> vec;

(3)尾部插入数字

vec.push_back(a);

(4)使用下标访问元素

cout<<vec[0]<<endl;记住下标是从0开始的

(5)使用迭代器访问元素

vector<int>::iterator it;

for(it=vec.begin();it!=vec.end();it++)

cout<<*it<<endl;

(6)插入元素

vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a;

(7)删除元素   

vec.erase(vec.begin()+2);删除第3个元素

vec.erase(vec.begin()+i,vec.end()+j);删除区间[i,j-1];区间从0开始

(8)向量大小

vec.size();

vec.resize;改变大小

(9)清空

vec.clear();

vector，使用示例如下

#include <iostream>#include <iomanip>#include <vector>//包含向量容器头文件using namespace std ;void main(){    vector<int>  A(10);  //创建vector对象int n;int primecount = 0, i, j;cout<<"Enter a value>=2 as upper limit: ";cin >> n;A[primecount++] = 2;//下标法访问元素for(i = 3; i < n; i++){ if (primecount == A.size())A.resize(primecount + 10); //改变容器大小        if (i % 2 == 0)continue;j = 3; while (j <= i/2 && i % j != 0)j += 2;        if (j > i/2) A[primecount++] = i;}for (i = 0; i<primecount; i++){//输出质数cout<<setw(5)<<A[i]; if ((i+1) % 10 == 0) //每输出10个数换行一次cout << endl;} cout<<endl;}

十二：双端队列 queue

双端队列是一种放松了访问权限的队列

元素可以从队列的两端入队和出队，也支持通过下标操作符“[]”进行直接访问

与向量的对比：

    功能上：和向量没有多少区别，

    性能上：在双端队列起点上的插入和删除操作快

头文件：#include <deque>

十三：列表 list

链表主要用于存放双向链表，可以从任意一端开始遍历。链表还提供了拼接（splice）操作，将一个序列中的元素从插入到另一个序列中

对比：

元素的插入和删除操作对 list 而言尤为高效

与 vector 和 deque 相比，对元素的下标访问操作的低效是不能容忍的，因此 list 不提供这类操作

头文件：#include <list>

列表，使用示例如下

#include <iostream>#include <list>using namespace std ;int main(){list<int> Link;//构造一个列表用于存放整数链表int i, key, item;    for(i=0;i < 10;i++)// 输入10个整数依次向表头插入{cin>>item;Link.push_front(item);}cout<<“List: ”; // 输出链表list<int>::iterator p=Link.begin();    while(p!=Link.end()){ //输出各节点数据，直到链表尾cout <<*p << "  ";p++;  //使P指向下一个节点}cout << endl;cout << "请输入一个需要删除的整数: ";cin >> key;Link.remove(key);   cout << "List: "; // 输出链表p=Link.begin();// 使P重新指向表头while(p!=Link.end()){ cout <<*p << "  ";p++; // 使P指向下一个节点}cout << endl;}

十四：关联容器

通过保存在数据项中的索引项，尽可能快速检索数据项

STL标准库中只包含有序关联容器set、multiset、map、multimap

      set, multiset：数据项就是索引项； multiset允许出现重复的索引项

      map, multimap：数据项是由索引项和其他某种类型的数据组成的一对数据； multimap允许出现重复的索引项

十五：map

1. 增加和删除节点对迭代器的影响很小。对于迭代器来说，可以修改实值，而不能修改key

2. 自动建立Key － value的对应。key 和 value可以是任意你需要的类型

3. 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次

map的构造函数

1. 使用map得包含map类所在的头文件
     #include <map>

2. map对象是模板类，需要关键字和存储对象两个模板参数：
      map<int, string> personnel;//用int作为索引,存储string对象

map的成员函数

1. map类已经对[]操作符进行了重载

2. 插入2时,先在enumMap中查找主键为2的项，没发现，然后将一个新的对象插入enumMap，键是2，值是一个空字符串，插入完成后，将字符串赋为“Two”;

3. 但是该方法会将每个值都赋为缺省值，然后再赋为显示的值，如果元素是类对象，则开销比较大。可以用以下insert()来避免开销

4. 下标操作符给出了获得一个值的最简单方法：

     CString tmp = enumMap[2];

     但是,只有当map中有这个键的实例时才对，否则会自动插入一个实例，值为初始化值

5. 我们可以使用Find()和Count()方法来发现一个键是否存在

6. 查找map中是否包含某个关键字条目用find()方法，传入的参数是要查找的key

7. 通过map对象的方法获取的iterator数据类型是一个std::pair对象，包括两个数据 iterator->first 和 iterator->second 分别代表关键字和存储的数据

从map中删除元素

1. 移除某个map中某个条目用erase()

2. 该成员方法的定义如下

iterator erase(iterator it);              //通过一个条目对象删除iterator erase(iterator first, iterator last);//删除一个范围size_type erase(const Key& key);   //通过关键字删除

例如：

enumMap.erase(1);//删掉关键字“1”对应的条目enumMap.erase(enumMap.begin());//删掉第一个条目enumMap.erase(enumMap.begin(), enumMap.begin() + 2);//删掉起始的两个条目

3. clear()就相当于

 enumMap.erase(enumMap.begin(), enumMap.end()); 

map，使用示例如下

#include <map>#include <iostream>#include <string>using namespace std;void main(){map< string, string > trans_map;typedef map< string, string >::value_type valType;trans_map.insert( valType( "001", "grateful" ));trans_map.insert( valType( "002", "them" ));trans_map.insert( valType( "003", "because" ));trans_map.insert( valType( "004", "no" ));trans_map.insert( valType( "005", "says" ));trans_map.insert( valType( "006", "thanks" ));trans_map.insert( valType( "007", "was" ));    trans_map.insert( valType( "008", "suppose" ));map< string,string >::iterator it;cout << "Here is our transformation map: \n\n";for(it=trans_map.begin();it!=trans_map.end();++it)cout<<"key: "<<(*it).first<<"\t"<<"value: " <<(*it).second<<"\n";cout<<"Find Key:005"<<endl;it=trans_map.find("105");if (it==trans_map.end()){cout<<"not found"<<endl;}else{cout<<"key: "<<(*it).first <<"\t"<<"value: " <<(*it).second<<"\n";}}

十六：multimap

multimap 除了元素对的关键字不是唯一外，与 map 相似

头文件：#include <map>

十七：set

set 可以被视为只有关键字而没有相关的元素值的 map，因此 set 的用户接口也发生了微小的变化：成员类型中没有：

     typedef Key value_type;

     typedef Cmp value_compare

     操作中没有元素的下标访问操作

头文件：#include <set>

十八：multiset

multiset 除了关键字不是唯一外，与 set 相似

头文件：#include <set>

十九：迭代器

迭代器是面向对象版本的指针

     指针可以指向内存中的一个地址

     迭代器可以指向容器中的一个位置

STL的每一个容器类模版中，都定义了一组对应的迭代器类。使用迭代器，算法函数可以访问容器中指定位置的元素，而无需关心元素的具体类型

迭代器的类型

1. 输入迭代器

可以用来从序列中读取数据

2. 输出迭代器

允许向序列中写入数据

3. 前向迭代器

既是输入迭代器又是输出迭代器，并且可以对序列进行单向的遍历

4. 双向迭代器

与前向迭代器相似，但是在两个方向上都可以对数据遍历

5. 随机访问迭代器

也是双向迭代器，但能够在序列中的任意两个位置之间进行跳转

迭代器的类型表

迭代器，使用示例

#include <list>#include <iostream>using namespace std;int main(){int i,key;list<int> intList;list<int>::iterator it;cout<<"input 5 digit:";for(i=0;i<5;i++){cin>>key;intList.push_front(key);}    cout<<"data list:"<<endl; it=intList.end();while(1){cout.width(6);cout<<*(--it);if(it==intList.begin())break;}return 0;}

二十：函数对象

1. 一个行为类似函数的对象，它可以没有参数，也可以带有若干参数，其功能是获取一个值，或者改变操作的状态

2. 任何普通的函数和任何重载了调用运算符operator()的类的对象都满足函数对象的特征

3. STL中也定义了一些标准的函数对象，如果以功能划分，可以分为算术运算、关系运算、逻辑运算三大类；为了调用这些标准函数对象，需要包含头文件<functional>

二十一：已经集成的函数对象

二十二：自定义函数对象

#include <iostream>using namespace std;class CFunObj{public:void operator()(){cout<<"hello,function object!"<<endl;}int operator()(int i){cout<<"hello, function object other!"<<endl;return i+1;}private:int dat;};void main(){CFunObj fo;fo();cout<<fo(1)<<endl;//CFunObj()();}

二十三：标准C++库中的算法

1. 算法本身是一种函数模板

2. 不可变序列算法（non-mutating algorithms）

       不直接修改所操作的容器内容的算法

3. 可变序列算法（mutating algorithms）

       可以修改它们所操作的容器的元素

4. 算法部分主要由头文件<algorithm>，<numeric>和<functional>组成

二十四：STL算法的头文件

<algorithm>是所有STL头文件中最大的一个，它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等

<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作

<functional>中则定义了一些模板类，用以声明函数对象

二十五：标准函数

二十六：泛型算法例子

#include <iostream>#include <vector>#include <algorithm>#include <iterator>#include <numeric>#include <functional>using namespace std;int main(){int ia[] = { 1, 2, 3, 4, 5, 7, 9, 11 };vector<int> iv(ia, ia+8);//累加,52cout<<accumulate(iv.begin(),iv.end(),10)<<endl; //相邻差值adjacent_difference(iv.begin(),iv.end(),iv.begin());//复制到ostream_iterator 去, 每列印一个元素, 即加上一个空格    copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, “ ”));// 1 1 1 1 1 2 2 2 //计算元素值为2 的个数cout << count(iv.begin(), iv.end(), 2) << endl; // 3//计算奇数元素的个数cout << count_if(iv.begin(), iv.end(),bind2nd(modulus<int>(),2)) << endl; // 5//从头开始填入新值7, 填3 次fill_n(iv.begin(), 3, 7);copy(iv.begin(), iv.end(), ostream_iterator<int>(cout,“ ”));// 7 7 7 1 1 2 2 2//内积, 7*7 + 7*7 + 7*7 + 1*1 + 1*1 + 2*2 + 2*2 + 2*2cout << inner_product(iv.begin(), iv.end(), iv.begin(),0) << endl; //161    //排序sort(iv.begin(), iv.end());copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, “ ”));// 1 1 2 2 2 7 7 7//顛倒元素次序reverse(iv.begin(), iv.end());copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, “ ”));// 7 7 7 2 2 2 1 1//旋转, 交换[first, middle)和[middle, last)rotate(iv.begin(), iv.begin()+3, iv.begin()+6);copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, “ ”));// 2 2 2 7 7 7 1 1}

二十七：自定义函数作为算法参数                

#ifndef CMYCLASS_H#define CMYCLASS_H#include <string.h>class CMyClass{public:CMyClass();CMyClass(string name,int age);friend bool Less(const CMyClass &num,const CMyClass &myclass);bool operator==(const CMyClass &myclass);string &GetName();int GetAge();private:string m_name;int m_age;};#endif

CMyClass::CMyClass(){m_name="";m_age=12;}CMyClass::CMyClass(string name,int age){m_name=name;m_age=age;}bool CMyClass::operator==(const CMyClass &myclass){return m_name==myclass.m_name;}string & CMyClass::GetName(){return m_name;}int CMyClass::GetAge(){return m_age;}

#include "MyClass.h"#include <iostream>#include <algorithm>#include <vector>#include <functional>#include <numeric>using namespace std;bool Less(const CMyClass &num,const CMyClass &myclass){return num.m_name<myclass.m_name;}void PrintMyClass(CMyClass &myclass){cout<<"name:"<<myclass.GetName()<<"\t age:"<<myclass.GetAge()<<endl;}bool SearchByName(CMyClass &myclass){return myclass.GetName()=="AAAAZ";}

void  main(){CMyClass myclass;vector<CMyClass> vec;vec.push_back(CMyClass("AAAA",12));vec.push_back(CMyClass("DFKASDF",12));vec.push_back(CMyClass("ASDFSAFA",12));vec.push_back(CMyClass("Z",12));vec.push_back(CMyClass("AAAAZ",12));vec.push_back(CMyClass("DFKSADFZ",12));sort(vec.begin(),vec.end(),Less);//for (vector<CMyClass>::iterator it=vec.begin();it!=vec.end();it++){//cout<<it->GetName()<<endl;}for_each(vec.begin(),vec.end(),PrintMyClass);vector<CMyClass>::iterator r=find_if(vec.begin(),vec.end(),SearchByName);cout<<(*r).GetName()<<endl;}