C++泛型编程，标准模板库(STL)

C++的特点就是添加了面向对象和泛型。面向对象是用类实现的，泛型是用模板实现的，C++的标准模板库(STL)是泛型一个实例，已经被集成到C++，STL是一些常用的数据结构(数组、链表、二叉数)和算法(排序、查找)的集合。
C++的标准模板库(STL)主要由三个组件构成：1、容器；2、迭代器；3、泛型算法

一、容器

容器主要有顺序容器、关联容器和容器适配器

顺序容器：元素是按照人为设定顺序的，元素插入容器的时候是什么位置，就会位于什么位置，主要有:可变长度数组vector, 双向链表list, 双向队列deque

关联容器：内部是按照一定规则自动排序的，不能指定插入位置，主要有set, multiset(允许相同元素), map, multimap(允许有相同关键字Key)

容器适配器: stack, queue, priority_queue

1、所有容器都有的两个成员函数
1）int size() :返回元素的个数
2）bool empty() :判断容器是非为空，是否有元素

2、顺序容器和关联容器都有的成员函数
1）iterator begin() : 返回指向第一个元素的迭代器
2）iterator end() :返回指向最后一个元素后面一个位置的迭代其
3）reverse_iterator rbegin() :返回指向最后一个元素的反向迭代器
4）reverse_iterator rend() :返回指向第一个元素前面一个位置的迭代器
5）erase(iterator) :删除一个迭代器指向的元素，或者两个迭代器之间的元素
6）clear() : 删除清空所有元素

3、顺序容器还有以下的成员函数
1）T& front() :返回地一个元素的引用
2）T& back() :返回最后一个元素的引用
3）push_back(T&) :在末尾添加一个元素
4）pop_back(T&) :在末尾删除一个元素
5）insert(iterator, T&) :在一个位置插入一个元素（元素），或者插入一段多个元素(两个迭代器）

对容器的通用型操作：
"==", "!=" 判断两个容器是否相等
"=" 将一个容器复制给另一个容器

1、顺序容器

1. array
   数组array，最一般的数组，和C的数组一样，长度固定，声明如下：

   #include<array>
   
   //格式array<typename,length> Varname;
   array<int, 10> arr;
   

2. vector
   头文件#include<vector>，可变长度数组，最常用，物理内存是连续的，可以随机访问，所以可以用下标访问元素[i]，很快，但是如果频繁向中间插入元素，速度比较慢

   成员函数	作用
   vector()	无参构造函数，容器初始化为空 ， .empty() = true
   vector(int n)	构造函数，容器的size为n
   vector(int n, const T& val)	构造函数，初始化为n个val
   vector(iter firat, iter last)	构造函数，初始化为其他容器first和last之间的元素
   bool empty()	判断容器是否为空
   int size()	返回元素个数
   void clear()	删除所有元素
   T& front()	返回第一个元素的引用
   T& back()	返回最后一个元素的引用
   void push_back(T& val)	末尾添加元素val
   void pop_back()	删除末尾元素
   iter insert(iter i, const T& val)	在i处插入元素val,返回i
   iter insert(iter i, iter first, iter last)	在i处插入[first, last)之间的内容
   iter erase(iter i)	删除i处的元素，返回删除元素后面的元素的迭代器
   iter erase(iter first, iter last)	删除[first,last)之间的元素
   swap(vector<T>& v)	自身和另一个容器的元素互换

   #include<vector>
   //格式vector<typename> Varname;
   vector<double> Vet;
   vector<int> Vet1(10);
   Vet1.push_back(5);//后端插入
   Vet1.pop_back();//后端删除
   

3. deque
   头文件#include<deque>也是个可变长度数组，物理内存连续，不过是双向的，可以在前端插入和删除，所有vector的操作(成员函数)deque也有，可以随机访问，相比vector的优点就是在头部插入元素也快一些，所以多了两个成员函数

   成员函数	作用
   void pop_front()	删除头部一个元素
   void push_front(const T& val)	向容器头部插入元素

   #include<deque>
   deque<double> Var1;
   Var1.push_front(6);//前端插入
   Var1.pop_front();//前端删除
   

4. list
   双向链表，不是线性表，物理内存不是连续的，每个节点都有一个data和两个指针back, front分别指向前面和后面的节点；
   链表只有头head信息和元素个数信息，所以无法随机访问元素，不能用下标的方式访问，只能用迭代器按顺序向下找元素，所以访问元素速度慢，但是插入删除元素非常快
   除了顺序容器都有的成员函数以外，list还有以下成员函数：

   成员函数	作用
   void push_front(T& val)	在前面插入元素
   void pop_front()	删除最前面的一个元素，速度很快
   void sort()	将链表从下到大排序 （vector没有，但是因为vector和deque可以随机访问，所以可以用泛型非成员函数sort()）
   void remove(T& val)	删除和val相等的元素, （删除元素， vector没有，只能用迭代器）
   remove_if	删除符合条件的元素
   void unique()	删除所有和前一个元素相等的元素
   void merge(list<T>& x)	将链表x合并进来并清空x,要求自身和x都是有序的
   void splice(iter i, list<T>& x, iter first, iter last)	在i处插入x的[first,last)的内容，并删除x的该内容，x可以是自身，只要i不再区间内

5. pair<class1, class2>
   pair模板，相当与一个结构，两个成员变量first, second；可以存放两个两种不同类型的数据

   pair<int,double> p1;
   pair<string, int> p1("lihua", 20);
   

2、关联容器

6. set排好序的集合，不允许有相同的元素，只有key
   头文件#include<set>

   成员函数	作用
   find	查找某个值
   lower_bound	下界
   upper_bound	上界
   equal_range	同上查找上界和下界
   count()	计算元素个数
   insert	插入

   #include<set>
   #include<string>
   set<string> word_set;
   word_set.count(key);//返回个数，要么0，要么1
   

7. map 键值对key/value，不允许相同的Key
   key通常是字符串，相当于索引；
   有.find(key)成员函数，返回查找的key的iterator,否则返回map.end()

   #include<iostream>
   #include<map>
   #include<string>
   using namespace std;
   int main()
   {
   	map<string,int> words;
   	string word;
   	//统计输入每种字符的个数，map中没有的会自动创建
   	while(cin>>word)
   		words[word]++;
   	map<string,int>::iterator it=words.begin()
   	//依次打印map中的内容，first成员对应key，second成员对应value
   	for(;it!=words.end();it++)
   		cout<<"key: "it->first<<" value: "<<it->second<<endl;
   	return 0;
   }
   

二、迭代器iterator（泛型指针）

类似于指针，作用于容器类上, 有以下四种
1、正向迭代器，如:vector<double>::iterator it

2、反向迭代器, 如:vector<double>::reverse_iterator rit

3、常量正向迭代器，如:vecror<double>::const_iterator cit

4、常量反向迭代器, 如:vector<double>::const_reverse_iterator it

1. .begin()
   相当与头指针，指向第一个元素的指针

2. .end()
   指向最后一个元素的后面的指针

   vector<int> Var{4,5,7,8};
   vector<int>::iterator head=Var.begin();
   vector<int>::iterator tail=Var.end();
   //或者
   auto it = Var.begin();
   for(;head!=tail;head++)  //遍历容器类
   {
   	cout<<*head<<endl;
   }
   

3. .rbegin()

4. .rend()

三、算法Generic Programming

算法是通用函数，不是成员函数，头文件#include <algorithem>

1. insert()插入

   //插入到position之前一个元素,返回被插入的元素的iterator
   iterator insert(itrator position, elemType value);
   
   //插入count个值
   void insert(iterator position, int count, elemType value);
   
   //插入[first,last)之间的元素
   void insert(iterator position, iterator first, iterator last);
   

2. erase()删除

   //删除一个元素，返回被删除后，接下来后一个元素的iterator
   iterator erase(iterator position);
   
   //删除范围内元素[first,last)
   iterator erase(iterator first, iterator last);
   

3. find()用于无序搜索，搜素范围[first, last), 返回iterator, 找不到则返回last

   iterator find(iterator first, iterator last, elemType findvalue);
   

4. copy() 复制

   //参数 要复制的  开始  结束，   复制目的地的 开始
   copy(iterator first, iterator last, iterator To_first);
   vector<int> ivet;
   vector<int> temp{1,2,3,4,5};
   copy(temp.begin(), temp.end(), ivec.begin());
   

#include<vector>
#include<deque>
#include<list>
#include<string>
using namespace std;
int main()
{
	//产生空的容器
	list<string> slist;
	vector<int> ivec;

	//产生特定大小的容器
	list<int> ilist(100);
	vector<string> svec(32);

	//产生特定大小的容器，并赋值全相同的初值
	vector<int> ivec(10,1);  //10个1
	list<string> slist(16,"WoW");

	//通过两个迭代器iterator赋值
	int arr[8]={1,1,2,2,3,5,6,4};
	vector<int> ivec1(ia,ia+8); //赋值[ia,ia+8)之间的内容
	int a=ivec1.front();//读取第一个元素
	a=ivec1.back(); //读取最后一个元素
	ivec1.push_back(10); //在最后插入元素
	ivec1.pop_back(); //删除最后一个元素

	//复制容器赋值
	list<string> slist1(5,"wfq");
	list<string> slist2(slist1);  //复制赋值


	return 0;
}

学习链接1