STL指的是C++标准模板库（Standard Template Library），本文介绍常用算法及容器（上篇）。
目录
一、排序与检索
sort 函数
lower_bound 函数
典型样例
二、不定长数组 vector
三、集合 set
四、映射 map
一、排序与检索
常用排序可以使用 algorithm 头文件中的 sort 和 lower_bound 函数。
sort 函数
使用数组元素默认的大小比较运算符进行排序，将原数组从小到大重新排列。无返回值。
基本使用方法如下：
sort ( a , a+n )
数组操作，其中a为数组名，n为数组元素个数
sort ( v.begin(),v.end() )
不定长数组vector操作
lower_bound 函数
查找“大于或等于x的第一个位置”。返回元素位置。基本使用方法如下：
lower_bound ( a , a+n , x )
数组操作，其中a为数组名，n为数组元素个数，x为待查找元素
vector操作同理
注意 lower_bound 不是精确查找，而是寻找大于等于的第一个。返回为 int* 型的元素位置，如果要定位到精确的元素，需要减去首元素位置：
int t = lower_bound ( a , a+n , x ) - a ;
当使用 lower_bound 进行查找时，使用变量 t 储存返回值减去首元素位置（数组名）的结果，再将 a[t] 与 x 进行比较，如果两者相同，说明找到且下标为 t（即原排列的第t+1个）；如果不相等，说明原数组中不存在x。
典型样例
输入5个数字作为卡片数值，从小到大排列并找出输入的具体数在哪一张卡片上。
#include#include //sort和lower_bound头文件 using namespace std; const int ArrayNumber = 5; int main() { int a[ArrayNumber], x; for (int i = 0; i < ArrayNumber; i++) { cin >> a[i]; } cin >> x; //到此数据全部输入完毕，首先使用sort进行排序 sort(a, a + ArrayNumber); //接着使用lower_bound进行查找 int t = lower_bound(a, a + ArrayNumber, x)-a; //判断是否存在 if (a[t] == x) cout << x << " found at " << t + 1 << endl; else cout << "not foundn"; }
测试结果如下，可以完美运行：
二、不定长数组 vector
vector本质上是一个模板类，不但可以储存不定长的数据（数据成员），还封装了一些常用操作函数（成员函数）。常用操作如下：
| a.size() | 读取大小 |
| a.resize(n) | 改变大小为n（下标≥n的都清除） |
| a.push_back(x) | 将x添加在a尾部（size会+1） |
| a.pop_back() | 删除最后一个元素（size会-1） |
| a.empty() | 测试是否为空 |
由于vector是模板类，所以需要带上数据类型一起声明：
vector <数据类型> 数组名
如：vector
a; vector b;
vector的典型使用是移木块问题（The Blocks Problem，UVa 101），题目的大概意思是从左到右有n的木块（n个堆），有以下四种操作：
- 把a和b上方的木块全部归位，把a摞在b上面。
- a上方木块全部归位，把a放在b所在木块堆顶部。
- b上方木块全部归位，把a及以上木块全部放在b上面。
- 把a及以上放在b木块堆上面。
由于在操作过程中每一堆木块的高度是不确定的，而且需要频繁变化移动，可以让每一堆设置为一个vector：
const int maxn=30; //堆数的最大长度 vectorpile[maxn]; //定义了一个vector数组，外围数组的每一个元素都是一个vector
接着介绍几个本程序中重要的操作函数。第一个函数是找出指定木块a所在的堆数和高度层数：
void find_block(int a,int& p,int& h) //以引用的方式传参
{
for(p=0;p
第二个函数执行的是把第p堆高度为h的木块上方的所有木块移回原位：
void clear_above(int p,int h)
{
for(int i=h+1;i
第三个函数是把第p堆高度为h及其以上的木块整体移动到p2堆的顶部：
void pile_onto(int p,int h,int p2)
{
for(int i=h;i
接着可以自行实现主函数、操作的判断和输出等。
三、集合 set
除数组和不定长数组vector，集合set也是常见容器。区别于数组，set中每个元素只可以出现一次，且元素会自动排序（如果储存数据则按照大小排序，储存字符串则按照字典排序）。利用自动排序功能可以实现字典统计等功能。
如经典例题 安迪的第一个字典（Andy's First Dictionary，UVa 10815）中，需要对一段具体的英文文本统计字典。首先可以定义一个 string 类型的集合 dict：
set dict; //string集合
接着可以将整个文本读取到一个字符串中，遍历字符串并使用 isalpha() 函数判断是否为英文字符（因为标点符号不能读入作为字典），如果是则使用 tolower() 函数全部转成小写，如果不是则变成空格。这部分核心代码如下：
//设存放文本的字符串为s
for(int i=0;i>s.length();i++){
if(isalpha(s[i]))
s[i]=tolower(s[i]);
else
s[i]=' ';
}
然后使用字符串流 stringstream 模拟读入，并将读入的单词word（字符串） dict.insert(word) 插入集合 dict 中。最后遍历输出，需要使用 iterator迭代器：
for(set::iterator it=dict.begin();it!=dict.end();++it)
cout<<*it<<'n';
由于 set.begin() 和 set.end() 返回值都是迭代器（都是仿照迭代器命名的），所以这里set类型的迭代器。迭代器使用类似于指针。
四、映射 map
映射就是一个“高阶版”的数组——数组通过 int 型的下标定位元素，而map可以使用各种数据类型定位元素：
map cnt
表示的是该映射是从字符串string映射到int型，相当于一个int型的数组使用string进行元素定位。
map和set都需要自己名称的头文件，且两者都支持 insert / find / count / remove 操作。其中 count函数表示对元素进行计数，如果在容器中存在则返回1，如果不存在则返回0。
如一个 map cnt，需要添加一个string为s的元素为a
可以直接写：cnt [s]=a;
今日完，明学习STL初步（下）及大整数类、竞赛题目举例
