STL全名标准模版库(Standard Template Library)，是一群以template为根基的C++程序 库 目的在提供一些基本的容器类别(container class) 与高效的算法(algorithm) 一般来说程序是由算法加上数据结构，互相配合、 一起工作，完成程序的功能。但如此一来便将数 据结构与算法紧密绑定，不能分离，缺乏弹性
STL 有五个组成部分：容器、迭代 器、算法、适配器、函数对象。
容器 (container)－用来储存其他物件 迭代器(iterator)－好比传统 C 语言的指针，可藉之来处理容器对象 算法(algorithm)－算法通过迭代器来操作容器对象 适配器(adaptor)－利用基础容器对象，加以包装，改变其接口，以适应另一种需求 函数对象(function object)－为 STL 中较低阶的对象，用来代替传统的函数指针 (function pointer)
容器分为三大类：
- 顺序容器
vector：后部插入/删除，直接访问
deque：前/后部插入/删除，直接访问
list：双向链表，任意位置插入/删除
2)关联容器
set：集合、可以快速查找，无重复元素
multiset：快速查找，可有重复元素
map：一对一映射，无重复元素，基于关键字查找
multimap：一对一映射，可有重复元素，基于关键字查找
（set/multiset map/multilmap以平衡二叉树来实现、插入、删除、检索、时间复杂度为O（long n））
前2者合称为第一类容器
3)容器适配器
stack LIFO
queue：FIFO
priority_queue：优先级高的元素先出
容器的共有成员函数
所有标准库容器共有的成员函数：
相当于按词典顺序比较两个容器大小的运算符：=, < , <= , > , >=, == , !=
empty : 判断容器中是否有元素
max_size: 容器中多能装多少元素
size: 容器中元素个数
swap: 交换两个容器的内容
begin、end、insert、erase等
vectorjie成员函数介绍
vector示例
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> Array1D; //构建一维数组
typedef vector<vector<int> > Array2D; //构建二维数组
int main(int argc, char *argv[])
{
int i,j;
Array1D sz;
for(i=0;i<10;i++) //输入10个数
sz.push_back(i);
for(i=0;i<10;i++)
cout<<sz[i]<<" "; //vector继承了数组的[]获取元素的方法输出10个数
cout<<"\n"<<sz.front()<<" "<<sz.back()<<endl;
sz.erase(sz.begin()+3); //删除第四个数
for(i=0;i<sz.size();i++)
cout<<sz[i]<<" "; //打印删除后剩余的数
cout<<endl;
sz.erase(sz.begin()+2,sz.begin()+5); //删除第三个数到第六个数 erase两个单数代表删除的区间
for(i=0;i<sz.size();i++)
cout<<sz[i]<<" ";
cout<<endl;
sz.erase(sz.begin(),sz.end());//sz.clear();
Array2D tw;
tw.resize(5); //定义一个5x5的动态二维数组
for(i=0;i<5;i++)
tw[i].resize(5);
for(i=0;i<5;i++)
for(j=0;j<5;j++)
tw[i][j]=i*5+j;
for(i=0;i<tw.size();i++)
{
for(j=0;j<tw[i].size();j++)
cout<<tw[i][j]<<" ";
cout<<endl;
}
system("PAUSE"); //press any key to continue......
return 0;
}
运行结果
0 1 2 3 4 5 6 7 8 9
0 9
0 1 2 4 5 6 7 8 9
0 1 6 7 8 9
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
请按任意键继续. . .
map示例
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef map<string, int> Phone_Book;
void call(Phone_Book pb, string name)
{
cout << "calling ... " << pb[name] << endl;
}
int main(int argc, char *argv[])
{
map<string, int> phone_book;
phone_book["zhangsan"] = 2901101;
phone_book["LiSi"] = 2903105;
call(phone_book, "LiSi");
system("PAUSE");
return EXIT_SUCCESS;
}
运行结果
calling ... 2903105
请按任意键继续. . .
迭代器iterator
它的很多性质是和C++/C中的指针是相似，甚至 可以说指针就是一种C++编译器里内置的迭代器。 可以说就是指针的类实现； 软件设计有一个基本原则，所有的问题都可以 通过引进一个间接层来简化，这种简化在STL中 就是用迭代器来完成的； 迭代器在STL中用来将算法和容器联系起来，起 着一种黏和剂的作用； 几乎STL提供的所有算法都是通过迭代器存取元 素序列进行工作的，每一个容器都定义了其本 身所专有的迭代器，用以存取容器中的元素
有const和非const两种。
通过迭代器可以读取它指向的元素，通过非const 迭代器还能修改其指向的元素。迭代器用法和指针 类似。
定义一个容器类的迭代器的方法可以是：
容器类名::iterator变量名;
或：
容器类名::const_iterator变量名;
访问一个迭代器指向的元素： * 迭代器变量
迭代器上可以执行++操作, 以指向容器中的下一 个元素。如果迭代器到达了容器中的后一个 元素的后面，则迭代器变成past-the-end值。 使用一个past-the-end值的迭代器来访问对象 是非法的，就好像使用NULL或未初始化的指针 一样
STL 中的迭代器按功能由弱到强分为5种
1.输入：Input iterators提供对数据的只读访问。
2.输出：Output iterators提供对数据的只写访问。
3.正向：Forward iterators提供读写操作，并能 一次一个地向前推进迭代器。
4.双向：Bidirectional iterators提供读写操作， 并能一次一个地向前和向后移 动。
5.随机访问：Random access iterators提供读写 操作，并能在数据中随机移动。 编号大的迭代器拥有编号小的迭代器的所有功 能，能当作编号小的迭代器使用
所有迭代器：++p, p ++
输入迭代器：* p, p = p1, p == p1 , p!= p1
输出迭代器：* p, p = p1
正向迭代器：上面全部
双向迭代器：上面全部，–p, p --,
随机访问迭代器：上面全部，以及： p+= i, p -= i,
p+i：返回指向p后面的第i个元素的迭代器
p-i：返回指向p前面的第i个元素的迭代器
p[i]:p后面的第i个元素的引用 p < p1, p <= p1, p > p1, p>= p1
容器 | 迭代器类别 |
vector | 随机 |
deque | 随机 |
list | 双向 |
lsetmultiset | 双向 |
map/multimap | 双向 |
stack | 不支持迭代器 |
queue | 不支持迭代器 |
priority_queue |
迭代器例子
#include <iostream>
#include <vector>
using namespace std;
vector<int> myV;
int main(int argc, char *argv[])
{
for (int i=0;i<10;i++)
myV.push_back(i);
vector<int>::iterator it;
for (it=myV.begin();it!=myV.end();it++)
cout<<(*it)<<' ';
system("PAUSE"); //press any key to continue......
return 0;
}
运行结果
0 1 2 3 4 5 6 7 8 9 请按任意键继续. . .
算法简介
STL中提供能在各种容器中通用的算法，比如插 入，删除，查找，排序等。大约有70种标准算法。
算法就是一个个函数模板； 算法通过迭代器来操纵容器中的元素。许多算法需要两个 参数，一个是起始元素的迭代器，一个是终止元素的后面 一个元素的迭代器。比如，排序和查找； 有的算法返回一个迭代器。比如find() 算法，在容器中查 找一个元素，并返回一个指向该元素的迭代器； 算法可以处理容器，也可以处理C语言的数组
算法分类
变化序列算法 copy ,remove,fill,replace,random_shuffle,swap, …… 会改变容器
非变化序列算法 adjacent-find, equal, mismatch,find ,count, search, count_if, for_each, search_n 以上函数模板都在 中定义
此外还有其他算法，比如中的算法
排序和查找算法
Sort（template void sort(RanItfirst, RanItlast);
例子
#include <algorithm>
#include <iostream>
using namespace std;
int tt[20];
int main(int argc, char *argv[])
{
int i;
for(i=0;i<20;i++)
tt[i]=20-i;
sort(tt,tt+10);
for(i=0;i<10;i++)
cout<<tt[i]<<" ";
system("PAUSE"); //press any key to continue......
return 0;
}
运行结果
11 12 13 14 15 16 17 18 19 20 请按任意键继续. . .
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> gg;
bool sortspecial(int v1,int v2)
{
return v1>v2;
}
int main(int argc, char *argv[])
{
int i;
for(i=0;i<20;i++)
gg.push_back(i);
sort(gg.begin(),gg.end(),sortspecial);
for(i=0;i<20;i++)
cout<<gg[i]<<" ";
system("PAUSE"); //press any key to continue......
return 0;
}
运行结果
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 请按任意键继续. . .
find
template<class InIt, class T>
InItfind(InItfirst, InItlast, const T& val);
#include <algorithm>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
const int ARRAY_SIZE = 8 ;
int IntArray[ARRAY_SIZE] = { 1, 2, 3, 4, 4, 5, 6, 7 } ;
int *location ; // stores the position of the first
// matching element.
int i ;
int value = 4 ;
// print content of IntArray
cout << "IntArray { " ;
for(i = 0; i < ARRAY_SIZE; i++)
cout << IntArray[i] << ", " ;
cout << " }" << endl ;
// Find the first element in the range [first, last + 1)
// that matches value.
location = find(IntArray, IntArray + ARRAY_SIZE, value) ;
//print the matching element if any was found
if (location != IntArray + ARRAY_SIZE) // matching element found
cout << "First element that matches " << value
<< " is at location " << location - IntArray << endl;
else // no matching element was
// found
cout << "The sequence does not contain any elements"
<< " with value " << value << endl ;
system("PAUSE");
return 0;
}
binary_search折半查找，要求容器已经有序
template<class FwdIt, class T>
boolbinary_search(FwdItfirst, FwdItlast, const T& val)