目录

一：泛型编程          

二：什么是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);
	//累加,52
	cout<<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*2
	cout << 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;
}