#include <iostream>
using namespace std;
//交换俩个整数变量的swap函数
void swap(int &x,int &y){
int temp = x;
x = y;
y = temp;
}
//交换两个double型变量值得swap函数
void Swap( double & x,double & y)
{
double temp = x;
x = y;
y = temp;
}
//用函数模板解决
/*template <calss 类型参数1 ，class 类型参数2，....>
返回值值类型 模板名（形参表）{
函数体；
};
*/
template<class T>
void Swap( T & x,T & Y){
T temp = x;
x = y;
y = temp;
}
//函数中可以有可以不止一个类型参数
template <class T1,class T2>
T2 print( T1 arg1,T2 arg2){
cout << arg1 << "," << arg2 << endl;
return arg2;
}
//求数组最大元素的MaxElement函数模板
template<class T>
T MaxElement(T a[],int size){
T tmpMax = a[0];
for(int i = 1;i < size;++i){
if(tmpMax < a[i])
tmpMax = a[i];
return tmpMax;
}
}
int main()
{
//STL模板类的使用
int a = 5;
int b = 3;
double x = 10.12;
double y = 3.1415;
swap(a,b);
Swap(x,y);
cout << "a=" << a << "," << "b = "<< b << endl;
cout << "x=" << x << "," << "y = "<< y << endl;
return 0;
}
//不能通过参数的实例化函数模板
#include <iostream>
using namespace std;
template <class T>
T Inc(T n){
return 1+n;
}
int main(){
cout << Inc<double>(4)/2;//输出2.5
return 0;
}
//函数模板可以重载，只要他们的形参表或类型参数表不同即可
template<class T1,class T2>
void print(T1 arg1,T2 arg2){
cout << arg1 << " " << arg2 << endl;
}
template<class T>
void print(T arg1,T arg2)
{
cout << arg1 << " " << arg2 << endl;
}
template<class T,class T2>
{
cout << arg1 << " " << arg2 << endl;
}
#include<iostream>
using namespace std;
template <class T>
//运算顺序按照完全匹配的优先
T Max(T a,T b)
{
cout << "TemplateMax" << endl;
return 0;
}
template<class T ,class T2>
T Max(T a,T2 b)
{
cout << "TemplateMax2" << endl;
return 0;
}
double Max(double a,double b)
{
cout << "MyMax" << endl;
return 0;
}
int main(){
int i = 4;
int j = 5;
Max(1.2,3.4);//MyMax
Max(i,j);//TemplateMax
Max(1.2,3);//TemplateMax2
return 0;
}
#include<iostream>
using namespace std;
template<class T,class Pred>
void Map(T s, T e,T x, Pred op)
{
for(;s!=e;++s,++x)
{
*x = op (*s);
}
}
int Cube(int x){ return x * x *x ;}
double Square(double x){ return x*x ;}
int a[5] ={1,2,3,4,5},b[5];
double d[5] = {1.2,2.1,3.1,4.1,5.1},c[5];
int main(){
Map(a,a+5,b,Square);
for(int i = 0;i<5;++i)cout << b[i] << ",";
cout << endl;
Map(a,a+5,b,Cube);
for(int i = 0;i<5;++i)cout << b[i] << ",";
cout << endl;
Map(d,d+5,c,Square);
for(int i = 0;i<5;++i)cout << c[i] << ",";
cout << endl;
Map(d,d+5,c,Cube);
for(int i = 0;i<5;++i)cout << c[i] << ",";
cout << endl;
/*
1,4,9,16,25,
1,8,27,64,125,
1.44,4.41,9.61,16.81,26.01,
1,8,27,64,125,
*/
return 0;
}
#include<iostream>
using namespace std;
//类模板的定义
/*template<class 类型参数1 ，class 类型参数2,......>//类型参数表
class 类模板名
{
成员函数和成员变量；
};
//用类模板定义对象的写法
类模板名<真实类型参数表> 对象名(构造函数参数表)；
*
/
template<class T1,class T2>
class Pair
{
public:
T1 key;
T2 value;
Pair(T1 k,T2 v):key(k),value(v){};
bool operator < ( const Pair<T1,T2> & p)const;
};
template<class T1,class T2>
bool Pair<T1,T2>::operator<(const Pair<T1,T2> & p) const
{
//Pair的成员函数operator <
return key < p.key;
}
int main()
{
Pair<string ,int>student("tom",19);
//实例化一个类Pair<String ,int>
cout << student.key << "," << student.value;//tom 19
return 0;
}
#include<iostream>
using namespace std;
template<class T>
class A
{
public :
template<class T2>
void Func(T2 t){ cout << t;}//成员函数模板
};
int main()
{
A<int >a;
a.Func('K');//成员函数模板Func被实例化
a.Func("hello");//成员函数模板Func再次被实例化
return 0;
}
//输出：Khello
//STL中的基本概念
/*1.容器:可容纳各种数据类型的通用数据结构，是类
模板
2.迭代器:可用于依次存取容器中元素，类似于指针
3.算法：用来操作容器的元素的函数模板
1)sort()来对一个vector数据进行排序
2）find()来搜索一个list的对象
算法本身与他们操作的数据的类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用
/
/
容器可以存放各种类型的数据（基本类型的变量，对象等）的数据结构，基本都是类模板。分为三种：
1）顺序容器
vector,deque,list
2)关联容器
set multiset,map,multimap
3）容器适配器
stack，queue,priority_queue
对象被插入容器中时，被插入的是对象的一个复制品，许多算法，比如排序，查找，要求对容器中的元素进行比较
，有的容器本身就是排序的，所以放入容器的对象所属的类，往往还应该重载 == 和 < 运算符
顺序容器简介：
容器并非排序的，元素的插入位置同元素的值无关
有vector，deque,list三种
1)vector:动态数组，元素在内存连续存放，随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能
#include
2)deque 头文件
双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成（但次于vector）。
在两端增删元素具有较佳的性能。
3)list 头文件
双向链表，元素在内存不连续存放，在任何位置增删元素都能在常数时间完成，不支持随机存取。
关联容器简介：
1.元素是排序的
2.插入任何元素，都按相应的排序规则来确定其位置
3.在查找时具有非常好的性能
4.通常以平衡二叉树的方式实现，插入和检索的时间都是O(log(N)
set/multiset 头文件
set即集合。set中不允许相同元素，multiset中允许相同的元素。
map/mutilmap 头文件
map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first,
另一个名为second,map根据first的值对元素进行从小到大排序，并可快速地根据first来检索元素
map与multimap的不同在于是否允许相同的first值得元素
容器适配器简介
stack： 头文件
栈，是项的优先序列，并满足序列中被删除，检索和修改的项只能是最近插入序列的项(栈顶的项)。后进先出。
queue头文件
队列，插入只可以在尾部进行，删除，检索和修改只允许从头部进行，先进先出。
priority_queue头文件
优先级队列，最高优先级元素总是在第一个出列
顺序容器与关联容器中都有的成员函数
begin 返回指向容器中的第一个元素的迭代器
end 返回指向容器中最后一个元素后面的位置的迭代器
rbegin 返回指向容器的最后一个元素的迭代器
rend 返回指向容器的第一元素前面的位置的迭代器
erase 从容器中删除一个或几个元素
clear 从容器中删除所有元素
顺序容器的常用的成员函数
front:返回容器中第一元素的引用
back：返回容器中最后一个元素的引用
push_back:在容器末尾增加的新元素
pop_back:删除容器末尾的元素
erase:删除迭代器指向的元素，可能会使该迭代器失效，
或删除一个区间，返回被删除元素后面的那个元素的迭代器
迭代器：
1.用于指向顺序容器与关联容器中的元素
2.迭代器用法与指针类似 clear
3.有const和非const两种
4.通过迭代器可以读取指向的元素
5.通过非const迭代器还能修改其指向的元素
定义一个容器类的迭代器的方法可以是：
容器类名：iterator 变量名
或
容器名：const_iterator 变量名
访问一个迭代器指向的元素
*迭代器变量名
迭代器上可以指向++操作，可以使其指向容器的下一个元素。如果迭代器到达了容器中的最后一个元素的后面
此时使用它就会出错，类似于使用null或未初始化的指针一样。
*/
#include<vector>
#include<iostream>
using namespace std;
int main(){
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::const_iterator i;
for(i = v.begin();i!=v.end();++i){
cout << *i << ",";
}
cout << endl;
vector<int>::reverse_iterator r;
for( r = v.rbegin();r!=v.rend();++i){
cout << *r << ",";
}
cout << endl;
vector<int>::iterator j;
for(j = v.begin();j!=v.end();j++)
{
*j = 100;
}
for( i = v.begin();i!=v.end();i++){
cout << *i << ",";
}
cout << endl;
return 0;
}
*/
//双向迭代器
/*
若p和p1都是双向迭代器，则可对p、p1可进行一下操作
++p,p++ 使p指向容器中下一个元素
–p,p-- 使p指向容器中上一个元素
*p 取p指向的元素
p = p1 赋值
p == p1,p!=p1 判断是否相等、不等
随机访问迭代器
若p和p1都是双向访问迭代器，则可对p、p1可进行一下操作
1.双向迭代器的所有操作
p+=i 将p向后移动i个元素
p-=i 将p向向前移动i个元素
p+i 值为：指向p后面的第i个元素的迭代器
p-i 值为：指向p前面的第i个元素的迭代器
p[i] 值为：p后面的第i个元素的引用
p<p1,p<=p1,p>p1,p>=p1
p-p1：p1和p之间的元素个数
容器 容器上的迭代器类别
vector 随机访问
deque 随机访问
list 双向
set/multiset 双向
map/multimap 双向
stack 不支持迭代器
queue 不支持迭代器
priority_queue 不支持迭代器
*/
算法：
1.算法就
是一个函数模板，大多数都是在中定义
2.STL中提供能在各种容器中通用的算法，比如查找你，排序等
3.算法通过迭代器来操纵容器中的元素，许多算法可以对容器中的一个
局部区间的操作，因此需要两个参数，一个起始元素的迭代器，一个是终止
元素的后面一个元素的迭代器，比如查找和排序
4.有的算法返回一个迭代器，比如find()算法，在容器中查找一个元素
并返回一个指向元素的迭代器
5.算法可以处理容器，也可以处理普通数组
/
/
算法是例：find()
template<class Init ,class T>
Init find(Init first,Init last,const T & val);
1.first和last这两个参数都是容器的迭代器，它们给出了容器中的查找
区间起点和终点[first,last)。区间的起点是位于查找范围之中的，二终点不是
find在[first,last)查找等于val的元素
2.用 == 运算符判断相等
3。函数返回值是一个迭代器，如果找到，则该迭代器指向被找到的元素
如果找不到，则该迭代器等于last.
*/
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int array[10] ={10,20,30,40};
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator p;
p = find(v.begin(),v.end(),3);
if( p != v.end())
cout << *p << endl;
p = find(v.begin(),v.end(),9);
if( p == v.end())
cout << "not found" << endl;
p = find(v.begin()+1,v.end()-2,1);
if( p != v.end())
cout << *p << endl;
int *pp = find(array,array+4,20);
cout << *pp << endl;
}
/*
STL中“大” “小”的概念
1.关联容器内部的元
素是从小到大排序的
2.关联容器要求其操作的区间是从小到大排序的，称为“有序区间算法”
3.有些算法会对区间进行从小到大排序，称为排序算法
4.还有一些其他算法会用到大于小的概念
使用STL时，在缺省的情况下，一下三种说法等价
x比y小 表达式x<y为真 y比y大
相等的概念
1.有时x和y相等等价于x==y为真
2.x和y相等等价于x小于y和y小于x同时为假
有序区间算法，如binary_search
关联容器自身的成员函数find
*/
//STL中相等表的概念
#include<iostream>
#include<algorithm>
using namespace std;
class A{
int v;
public:
A(int n):v(n){}
bool operator < (const A & a2) const {
//必须为常量成员函数
count << v << "<" << a2.v << "?" << endl;
return false;
}
bool operator == (const A & a2) const{
cout << v << "==" << a2.v << "?" << endl;
return v == a2.v;
}
};
int main(){
A a[] = {A(1),A(2),A(3),A(4),A(5)};
cout << binary_search(a,a+4,A(9));
//折半查找
return 0;
}
//vector示例程序
#include<iostream>
#include<vector>
using namespace std;
template<class T>
void PrintVector(T s,T e)
{
for( ; s!=e ; ++s)
{
cout << *s << " ";
}
cout << endl;
}
int main(){
int a[5] = {1,2,3,4,5};
vector<int>v(a,a+5);//将数组a的内容放入v
cout << "1)" <<v.end() -v.begin() << endl;
cout << "2)" ;
PrintVector(v.begin(),v.end());
v.insert(v.begin()+2,13);
cout << "3)";
PrintVector(v.begin(),v.end());
v.erase(v.begin()+2);
cout << "4)";PrintVector(v.begin(),v.end());
vector<int>v2(4,100);//v2有四个元素都是100
v2.insert(v2.begin(),v.begin()+1,v.begin()+3);
//将v的一段插入v2开头
cout << "5) v2:" ;
PrintVector(v2.begin(),v2.end());
v.erase(v.begin()+1,v.begin()+3);
cout << "6)";
PrintVector(v.begin(),v.end());
return 0;
}
//vector实现二维数组示例程序
#include<iostream>
#include<vector>
using namespace std;
int main()
{
//v有三个元素，每个元素都是vector<int>容器
vector< vector<int> > v(3);
for( int i = 0;i < v.size();++i){
for(int j = 0;j < 4;++j){
v[i].push_back(j);
}
}
for( int i = 0;i < v.size();++i){
for(int j = 0;j < v[i].size();++j){
cout << v[i][j] << " ";
}
cout << endl;
}
return 0;
}
/*
deque
所有适用于vector的操作都适用于deque
deque还有push_front（将元素插入到前面）和pop_front（删除最前面的元素），
复杂度是o(1)
/
/
双向链表list
list容器
1.在任何位置插入删除都是常数时间，不支持随机存取
2.除了具有所有容器都有的成员函数以外，还支持8个成员函数：
push_front:在前面插入
pop_front:删除前面的元素
sort:排序（list不支持STL的算法sort）
remove:删除和指定值相等的元素
unique:删除所有和前一个元素相同的元素（要做到元素不重复则unique之前还要使用sort）
merge:合并两个链表，并清空被合并的那个
reverse:颠倒链表
splice:在指定位置前面插入另一个链表中的一个或多个元素，并在另一个链表中删除被插入的元素
*/
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
class A{
private:
int n;
public:
A(int n_){ n = n_;}
friend bool operator <( const A & a1,const A &a2);
friend bool operator ==( const A & a1,const A &a2);
friend ostream & operator << ( ostream & o,const A & a);
};
bool operator < (const A & a1,const A & a2)
{
return a1.n < a2.n;
}
bool operator == (const A & a1,const A & a2)
{
return a1.n == a2.n;
}
ostream & operator <<( ostream & o,const A & a)
{
o << a.n;
return o;
}
template<class T>
void PrintList(const list<T> & lst)
{
//不推荐的写法，还是使用两个迭代器作为参数更好
int tmp = lst.size();
if( tmp > 0)
{
//typename用来说明list<T>::const——iterator是个类型在vs中可以不写
typename list<T>::const_iterator i;
i=lst.begin();
for( ; i!=lst.end();i++)
cout << *i << ",";
}
}
int main()
{
list<A> lst1,lst2;
lst1.push_back(1);lst1.push_back(3);
lst1.push_back(2);lst1.push_back(4);lst1.push_back(2);
lst2.push_back(40); lst2.push_back(20);
lst2.push_back(10); lst2.push_back(30);
lst2.push_back(30); lst2.push_back(40);
lst2.push_back(40);
cout << "1)";PrintList(lst1);cout << endl;//1) 1 3 2 4 2
cout << "2)";PrintList(lst2);cout << endl;//2) 40 20 10 30 30 40 40
lst2.sort();
cout << "3)";PrintList(lst2);cout << endl;
lst2.pop_front();
cout << "4)";PrintList(lst2);cout << endl;
lst1.remove(2);//删除所有和A（2）相等的元素
cout << "5)";PrintList(lst1);cout << endl;// 1 3 4
lst2.unique();//删除所有和前一个函数相等的元素
cout << "6)" ;PrintList(lst2);cout << endl;//20 30 40
lst1.merge(lst2);//合并lst2到lst1并清空lst2
cout << "7)";PrintList(lst1);cout << endl;
cout << "8)";PrintList(lst2);cout << endl;//空
lst1.reverse();
cout<<"9)";PrintList(lst1);cout << endl;
lst2.push_back(100);lst2.push_back(200);
lst2.push_back(300);lst2.push_back(400);
list<A>::iterator p1,p2,p3;
p1 = find(lst1.begin(),lst1.end(),3);
p2 = find(lst2.begin(),lst2.end(),200);
p3 = find(lst2.begin(),lst2.end(),400);
//将[p2,p3]插入p1之前，并从lst2中删除[p2,p3]
lst1.splice(p1,lst2,p2,p3);
cout << "10)";PrintList(lst1);cout << endl;
cout << "11)";PrintList(lst2);cout << endl;
return 0;
}
/*
函数对象
是个对象，但用起来看上去像函数，实际上也执行了函数调用
*/
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
class CMyAverage{
public :
double operator ()(int a1,int a2,int a3){
//重载()运算符
return (double)(a1+a2+a3)/3;
}
};
int main()
{
CMyAverage Average;//函数对象
cout << Average(3,2,3)<< endl;
return 0;
}
/*
函数对对象的应用
STL有
以下模板：
template<class InIt,class T,class Pred>
T accumulate(InIt first,InIt last,T val ,Pred pr)
pr就是一个函数对象
对[first,last]中的每个迭代器
执行val=pr(val,*I),返回最终的val.
Pr也可以是个函数
*/
using namespace std;
//Accumulate源代码1
//typename等效于class
template<typename _InputIterator,typename _Tp>
_Tp accumulate(_InputIterator _first,_InputIterator _last,_Tp _init)
{
for( ; _first != _last;++_first)
{
_init += _first;
}
return _init;
}
//Accumulate源代码2
template<typename _InputIterator,typename _Tp,typename _BinaryOperation>
_Tp accumulate(_InputIterator _first,_InputIterator _last,_Tp _init,_BinaryOperation _binary_op)
{
for( ; _first != _last;++_first){
_init = _binary_op(_init,_first);
}
return _init;
}
/*
函数对对象的应用
STL有以下模板：
template<class InIt,class T,class Pred>
T accumulate(InIt first,InIt last,T val ,Pred pr)
pr就是一个函数对象
对[first,last]中的每个迭代器
执行val=pr(val,*I),返回最终的val.
Pr也可以是个函数
*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<functional>
using namespace std;
/*template<typename _InputIterator,typename _Tp,typename _BinaryOperation>
_Tp accumulate(_InputIterator _first,_InputIterator _last,_Tp _init,_BinaryOperation _binary_op)
{
for( ; _first != _last;++_first){
_init = _binary_op(_init,*_first);
}
return _init;
}*/
int sumSquares(int total,int value)
{
return total + value * value;
}
template<class T>
void PrintInterval(T first,T last)
{
//输出在区间[first，last]中的元素
for( ; first != last;++first)
cout<< *first << " ";
cout << endl;
}
template<class T>
class SumPowers{
private:
int power;
public :
SumPowers(int p):power(p){}
const T operator () (const T & total,const T & value)
{
//计算value的power次方，加到total上
T v = value;
for( int i = 0;i < power -1;++i){
v = v * value;
}
return total + v;
}
};
int main()
{
const int SIZE = 10;
int a1[] = {1,2,3,4,5,6,7,8,9,10};
vector<int> v(a1,a1+SIZE);
cout << "1)" ;PrintInterval(v.begin(),v.end());
int result = accumulate(v.begin,v.end(),0,sumSquares);
cout << "2)平方和"<<result << endl;
result = accumulate(v.begin(),v.end(),0,SumPowers<int>(3));
count << "3)立方和:"<<result << endl;
result = accumulate(v.begin(),v.end(),0,SumPowers<int>(4));
cout << "4)4次立方和：" << result;
return 0;
}
/*
STL的里面还有以下函数对象的模板：
equal_to
greater
less
这些函数模
板可以用来生成函数对象
greater函数对象的类模板
template
struct greater :public binary_function<T,T,bool>{
bool operator() (const T & x,const T * y)const{
return x > y;
}
}
binary_function定义
template<class Arg1,class Arg2,class Result>
struct binary_function
{
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
greater的应用
1.list有两个sort函数，它将list中的元素按<规定的比较方法升序排列>
2.list还有另一个sort函数
template
void sort(T2 op)
可以用op来比较大小，即op(x,y)为true则认为x应该排在前面
copy类似于
template<class T1,class T2>
void copy(T1 s,T2 e,T2 x)
{
for( ; s!=e ; ++s,++x)
*x =*s;
}
*/
*/
#include<iostream>
#include<list>
#include<iterator>
#include<functional>
using namespace std;
class MyLess{
public:
bool operator()(const int & c1,const int & c2){
return ( c1 % 10 )<( c2 % 10 );
}
};
int main()
{
const int SIZE = 5;
int a[SIZE] = {5,21,14,2,3};
list<int>lst(a,a+SIZE);
lst.sort(MyLess());
ostream_iterator<int> output(cout,",");
copy(lst.begin(),lst.end(),output);
cout << endl;
lst.sort(greater<int>());
copy(lst.begin(),lst.end(),output);
cout << endl;
return 0;
/*
输出：
21,2,3,14,5,
21,14,5,3,2,
*/
}
