STL简单了解

STL（Standard Template Library，标准模板库）：

•是一种类型参数（type parameterized）的程序设计方法，基于模板的标准类库。其实质是一个高效的，可重用的C++常用的基本数据结构和基本算法的集合。

STL不是面向对象的技术，不强调类的层次结构，而是以效率和实用为目标，STL中的所有容器都是类模板

•组成

–（1）容器（container）：是能够保存其它对象的对象，是按某种特定的逻辑关系把元素组装起来的数据集。常用容器有vector，list，set，map。

–（2）迭代器（iterator）：被认为是一种广义的指针，用于访问容器中某个位置的数据元素，迭代器是连接容器和算法的纽带。

–（3）适配器（adaptor）：适配器对容器进行包装，使其表现出另外一种行为，STL提供了三种容器适配器：stack，queue，priority_queue。

–（4）算法（algorithm)：就是以函数模板实现的一些常用的数据处理方法，STL中包含大约70种标准算法，这些算法是对容器的数据施加特定操作的函数模板；

–（5）函数对象（function object）：在类中重载了函数调用运算符()的类对象。

•常见容器

容器类名	头文件	数据结构	特性	使用
vector	<vector>	T的一维数组	顺序存储，可看作动态数组，提供赿界检查	快速查找，不在意插入和删除速度
list	<list>	T的双向链表	每个结点包含一个元素，每个元素均有指向前一个元素和下一个元素的指针	适用于执行元素的插入和删除
deque	<deque>	T的双端队列	优化的序列，在两端的操作类似于list	两端都快速的操作
map和multimap	<map>	T的关联数组	是键值对组成的集合，集合元素按序排列。不允许有重复的键值对;mutimap允许有	希望将键与值相关联
set和multiset	<set>	T的集合	元素集合，集合中的元素按序存储。无重复元素；multiset允许有	需要使用元素集合，要求较为频繁的查找、插入、删除时

•容器的常用方法

方法	功能
begin()	返回指向首元素的迭代器
end()	返回指向尾元素的迭代器
swap(c)	交换同类型容器中的数据
size()	返回容器的元素个数
empty()	判断容器是否为空
max_size()	返回容器中可容纳的最大数量
rbegin()	返回指向逆向首元素的迭代器
rend()	返回指向逆向尾元素的迭代器
insert(pos,elem)	在迭代器pos所指位置前插入元素elem
erase(pos)	删除迭代器pos所指元素
erase(beg,end)	删除以地址beg开始，到地地址end结束的数据元素
clear()	删除容器中所有元素

1.vector容器

该容器对象以数组的形式存储，将元素存储于连续的内存空间。实际上是动态数组、支持索引形式的访问、随机存取任何元素都能在常数时间内完成、在尾端增删元素具有较佳的性能。

构造函数：

• vector():创建一个空vector
• vector(int nSize):创建一个vector,元素个数为nSize
• vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t
• vector(const vector&):复制构造函数
• vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中

三种访问向量元素的方法：

–（1）下标法，使用重载的下标运算符，以元素的位置索引为参数访问元素，但不执行下标赿界的检查；

   for (i = 0; i<n; i++)     cin>>v1[i];

–（2）at方法，vector提供的at方法，以元素的位置索引为参数，返回值即为要访问的元素，执行下标赿界的检查。

   for (i = 0; i<n; i++)    cout << v1.at(i) << "  ";

–（3）迭代器访问，使用用于向量的迭代器，可以快速遍历向量中的元素

     vector<T>::iterator iter;//定义迭代器

     for (iter = v.begin(); iter != v.end(); iter++)

         cout << *iter << "  ";

参考链接：vector容器学习

2.list容器

双向线性链表，提供了随机的插入和删除元素的高效实现，不支持随机存取，只能顺序访问。

3.set容器

set 即元素的集合，顺序存储。底层使用平衡的搜索树——红黑树实现，插入、删除操作时不涉及到内存移动和拷贝，所以效率比较高。set中不允许存在相同元素，multiset中允许存在相同的元素。

4.map容器

该容器就是映射，通常被称为关联数组，map中存放的是（key，value）偶对序列，其内部自建一棵红黑树(一种非严格意义上的平衡二叉树)。内部所有的数据都是有序的。由于根据key对元素进行排序，所以基于键可以快速插入、删除、修改、检索元素。

•容器适配器

本质上，适配器是使一事物的行为类似于另一类事物的行为的一种机制，容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的方式工作。适配器没有提供与元素的保存形式有关的真正数据结构实现，并且适配器不支持迭代器。使用适配器的优点是能够使程序员选择一种合适的底层数据结构。一般有三种容器适配器：容器适配器、迭代器适配器、函数适配器

标准库提供了三种顺序容器适配器：queue、priority_queue、stack

容器类名	头文件	数据结构	特性	使用
queue	<queue>	T的队列	在一端插入元素，在另一端取出元素，先进先出（FIFO），插入和删除都较快	需要一个FIOFO结构时
stack	<stack>	T的堆栈	在同一端插入和删除元素，具有先进后出（FILO）特性	需要一个FILO结构时
priority_queue	<queue>	T的优先级队列	也是一种队列，每个元素被给定了一个优先级，以此来控制元素可被访问的顺序	需要一个优先级队列时

1.stack容器适配器

stack类即堆栈类：允许在底层数据结构的一端执行插入和删除操作（先入后出），能够用任何序列容器实现：vector、list、deque。

stack的操作包括：

–（1）push函数:将一个元素插入到堆栈顶部（通过调用底层容器的push_back函数实现）

–（2）pop函数:从堆栈的顶部删除一个元素（通过调用底层元素的pop_back函数实现）

–（3）top函数:获取堆栈顶部元素引用（通过调用底层容器的back函数实现）

–（4）empty函数:判断堆栈是否为空（通过调用底层容器的empty函数实现）

–（5）size函数:获取堆栈元素数量（通过调用底层容器的size函数实现）。

为了获得最佳性能，最好使用vector类作为stack的底层容器

2.queue容器适配器

queue类即队列类：允许在底层数据结构的末尾插入元素，也允许从前面插入元素（先入先出），能够用STL数据结构的list和deque实现，默认情况下是用deque实现的。

常见的queue操作

–（1）push函数：在尾插入元素（通过调用底层容器的push_back函数实现）

–（2）pop函数：在队前删除元素（通过调用底层容器的pop_back函数实现）

–（3）front函数：获取队列中第一个元素的引用（通过调用底层容器的front函数实现）

–（4）back函数：获取队列最后一个元素的引用（通过调用底层容器的back函数实现）

–（5）empty函数：判断队列是否为空（通过调用底层容器的empty函数实现）

–（6）size函数：获取队列元素数量（通过调用底层容器的size函数实现）。

3.priority_queue容器适配器

•priority_queue（优先队列）是一个拥有权值观念的queue，允许加入新元素，删除旧元素，审视元素值等功能。且只允许在底端加入元素，并从顶端取出元素。缺省情况下priority_queue队列利用一个max_heap（最大堆）完成，后者是一个以vector表现的完全二叉树，max_heap可以满足priority_queue所需要的“依权值高低自动递减排序”的特性

•STL迭代器

迭代器是指针(pointer)的泛化，它允许程序员以相同的方式处理不同的数据结构(容器)中的元素，是连接容器和算法的纽带。实际上，迭代器是通过重载一元的“*”和“->”从容器中间接地返回一个值。

迭代器用法和指针类似

1.定义一个容器类的迭代器的一般形式是：

容器类名::iterator   变量名;

容器类名::const_iterator 变量名;

2.访问一个迭代器指向的元素的一般形式是：

* 迭代器变量名;

•STL 中的迭代器按功能由弱到强分为5种

–（1）输入迭代器（Input iterator）：只能够从一个序列中读取数据，这种指示器可以被增值，引用，以及进行比较。

–（2）输出迭代器（Output iterator）：只能够向一个序列中一个个写入数据，这种指示器可以增值以及引用

–（3）前向迭代器（Forward iterator）：可读可写，是Input迭代器与Output迭代器的结合，具有Input迭代器的全部功能和Output迭代器的大部分功能，并且能够保存它的值，以便从其原先位置开始重新遍历

–（4）双向迭代器（Bidirectional iterator）：在Forward迭代器的基础上增加了回头遍历的能力

–（5）随机迭代器（Random access iterator）：功能最强大的迭代器，在Bidirectional迭代器的基础上增加随机存取能力

另外

除了标准迭代器外，STL还有3种迭代器

–（1）reverse_iterator：逆向迭代器，重新定义递增运算和递减运算，使其行为正好倒置，从后向前移动来遍历除vector之外的容器中的元素，可以使用reverse_itertor反转遍历的方向，也可用rbegin()代替begin()，rend代替end()，用reverse_iterator时，“++”操作符会从后向前移动。

–（2）const_iterator：向前方向遍历的迭代器，它返回一个常数值，可以使用这种类型的游标指向一个只读的值。

–（3）const_reverse_iterator：朝反方向遍历的迭代器，它返回一个常数值。

•函数对象

定义了()运算符重载的类，其对象称之为函数对象（function object），简单地说，函数对象其实就是一些使用起来像调用函数一样的对象。在功能上类似于函数指针，它执行的是函数的功能，看起来像一个函数调用，本质上却是一个类对象的成员函数的调用

  特点：

（1）该类只有一个成员函数，即重载了的()运算符函数

（2）没有任何数据

（3）完成特定的简单功能的小的类对象

（4）该类可被模板化，从而可以应对多种数据类型

例：使用函数对象实现sort算法中比较操作的参数化策略

//定义函数对象模板类的模板基类
template<typename T>
class Compare
{ public:
       virtual bool operator()(T a, T b) = 0;
};

//定义函数对象模板类的模板子类
template<typename T>
class Greater :public Compare<T>
{  public:
        bool operator()(T x, T y)
	{return x>y;}
};

//定义函数对象模板类的模板子类
template<typename T>
class Smaller :public Compare<T>
{ public:
       bool operator()(T x, T y)
       {   return x<y;	}
};

函数对象大致分为3类

（1）算术操作：plus、minus、multiplies、divides、modulus和negate

（2）比较操作：equal_to、not_equal_to、greater、less、greater_equal和less_equal；

（3）逻辑操作：logical_and，logical_or和logical_not。

注：

•使用STL中的函数对象时必须传入数据类型

•把函数对象作为参数传递给其他函数

•包含头文件<functional>

函数对象	类型	描述	函数对象	类型	描述
divides<T>	算术	x/y	logical_or<T>	逻辑	x||y
equal_to<T>	关系	x==y	minus<T>	逻辑	x-y
greater<T>	关系	x>y	modulus<T>	算术	x%y
greater_equal<T>	关系	x>=y	negate<T>	算术	-x
less<T>	关系	x<y	not_equal_to<T>	关系	x!=y
less_equal<T>	关系	x<=y	plus<T>	算术	x+y
logical_and<T>	逻辑	x&&y	multiplies<T>	算术	x*y
logical_not<T>	逻辑	!x

#include<vector>
#include<functional>
#include<algorithm>
using namespace std;
void print(double i){    cout << i << "\t";}
int main()
{  
 double test_score[] = { 76, 92, 84, 65, 96 };
 double exp_score[] = { 88, 96, 90, 72, 98 };
 int nTest = sizeof(test_score) / sizeof(test_score[0]);
 int nExp = sizeof(exp_score) / sizeof(exp_score[0]);
//用已有的数组初始化向量
vector<double> vec_test(test_score,test_score + nTest);
//用已有的数组初始化向量
vector<double> vec_exp(exp_score,exp_score + nTest);
vector<double> vec_total(nTest);	
cout << "考试成绩：\n";
for_each(vec_test.begin(), vec_test.end(), print);
cout << endl;cout << "平时成绩：\n";
for_each(vec_exp.begin(), vec_exp.end(), print);
cout << endl;
if (nTest != nExp)   return -1;
for (int i = 0; i < nTest; i++)
 {    vec_test[i] = vec_test[i] * 0.8;
     vec_exp[i]=vec_exp[i] * 0.2;
 }	
cout << "Total score:\n";
/*把前两个序列的值转化（+）后放到第三个序列中，plus<double>为函数对象*/
transform(vec_test.begin(), vec_test.end(), vec_exp.begin(), vec_total.begin(), plus<double>());
//函数名作函数的参数
for_each(vec_total.begin(), vec_total.end(), print);
cout << endl;
cout << "排序后：\n";
//greater<double>为函数对象
sort(vec_total.begin(), vec_total.end(), greater<double>());
for_each(vec_total.begin(), vec_total.end(), print);
cout << endl;
system("pause");	return 0;
}

•STL算法

算法是一些通用函数，作用于各种容器，用于向容器中插入，删除元素，查找容器中的元素，对容器中的元素排序、复制等操作。算法独立于底层元素的类型，独立于所操作的容器。是用函数模板实现的，且都是独立的函数模板。

STL算法可分为如下几类

（１）数据检索或非变动性算法

（２）变动性算法

（３）排序算法

（４）集合算法

（５）关系算法

sort()：是对序列进行排序的，需要随机访问迭代器，它们最好是用于vector或类似容器。

find()：从头至尾查看一个序列或者一个值，函数返回值是一个迭代器。如果找到，则该迭代器指向被找到的元素，如果找不到，则该迭代器指向查找区间的终点。

binary_search()：折半查找，要求容器已经有序

for_each()：对每个元素执行同一操作，使用它可以去掉显式循环

copy()：是由一个序列产生另一个序列的最简单方式。复制算法的目标不必是容器，可以是任何可以用输出迭代器描述的对象

merge()：将两个有序序列归并成一个新的有序序列

STL算法主要由头文件 <algorithm>、<numeric>和<functional>组成：
“<algorithm>”是所有STL头文件中最大的一个，它是由很多函数模板组成的。可以认为每个函数模板在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历、赋值、修改、移动、移除、反转、排序、合并等。如果使用这些函数模板，要在头文件中包含<algorithm>。

“<numeric>”体积很小，只包括几个在序列上面进行简单数学运算的函数模板，包括加法和乘法在序列上的一些操作。
“<functional>”中则定义了一些类模板，用以声明函数对象

STL中算法的应用：

#include <vector>
#include <functional>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;

void print(double i)
{cout<<i<<"\t";}
int main()
{
	double test_score[]={76,92,84,65,96};
	double exp_score[]={88,96,90,72,98};
	int nTest=sizeof(test_score)/sizeof(test_score[0]);
        int nExp=sizeof(exp_score)/sizeof(exp_score[0]);
	//用已有数组初始化向量
	vector<double>vec_test(test_score,test_score+nTest);
	//用已有数组初始化向量
	vector<double>vec_exp(exp_score,exp_score+nExp);
	vector<double>vec_total(nTest);
	cout<<"for_each输出考试成绩：\n";
	//调用for_each输出每个元素
	for_each(vec_test.begin(),vec_test.end(),print);
	cout<<endl;
	cout<<"for_each输出平时成绩：\n";
	for_each(vec_exp.begin(),vec_exp.end(),print);
	cout<<endl;
	//求容器中小于等于10的元素个数
	double x=80;
	int count1;
	count1=count_if(vec_test.begin(),vec_test.end(),bind2nd(less_equal<int>(),x));
	cout<<"count_if执行结果，考试成绩小于"<<x<<"的学生人数：";
	cout<<count1<<endl;
	x=84;
	vector<double>::iterator iter;
	iter=find(vec_test.begin(),vec_test.end(),x);
	cout<<endl<<"find找到的元素为："<<*iter<<endl;
	if(nTest!=nExp) return -1;
	for(int i=0;i<nTest;i++)
	{
		vec_test[i]=vec_test[i]*0.8;
		vec_exp[i]=vec_exp[i]*0.2;
	}
	cout<<"Total score:\n";
	//把前两个序列的值转化（+）后放到第三个序列中，plus<double>为函数对象
    transform(vec_test.begin(),vec_test.end(),vec_exp.begin(),vec_total.begin(),plus<double>());
	//函数名作函数的参数
	for_each(vec_total.begin(),vec_total.end(),print);
	cout<<endl;
	cout<<"sort排序后：\n";
	//greater<double>为函数对象
	sort(vec_total.begin(),vec_total.end(),greater<double>());
	for_each(vec_total.begin(),vec_total.end(),print);
	cout<<endl;
	cout<<"使用binary_search查找的结果："<<endl;
	if(binary_search(vec_test.begin(),vec_test.end(),x)) 
		cout<<x<<"在向量vec_test里"<<endl;
	else
		cout<<x<<"不在向量vec_test里"<<endl;
	cout<<"合并vec_test,vec_exp:\n";
	vector<double> vec_merge(nTest+nExp);
	sort(vec_test.begin(),vec_test.end());
	sort(vec_exp.begin(),vec_exp.end());
	merge(vec_test.begin(),vec_test.end(),vec_exp.begin(),vec_exp.end(),vec_merge.begin());
	cout<<"\n使用输出copy模板函数将vec_merge数据输出到输出流cout上\n"<<endl;
	//定义输出流迭代器
	ostream_iterator<double>output(cout,"\t");
	copy(vec_merge.begin(),vec_merge.end(),output);
	cout<<endl;
	return 0;
}

参考资料：STL学习教材