STL及使用示例

一、STL概述

STL是Standard Template Library的简称，中文名标准模板库，惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL现在是C++的一部分，因此不用安装额外的库文件。

在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。

经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模板类，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。

在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<array>、<vector>、<list>、<forward_list>、<map>、<unordered_map>、<memory>、<numeric>、<queue>、<set>、<unordered_set>、<stack>和<utility>。

STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。

1.容器

容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表总结一下它们和相应头文件的对应关系。

l 序列式容器

向量(vector) 连续存储的元素<vector>

列表(list) 由节点组成的双向链表，每个结点包含着一个元素<list>

双端队列(deque) 连续存储的指向不同元素的指针所组成的数组<deque>

l 适配器容器

栈(stack) 后进先出的值的排列 <stack>

队列(queue) 先进先出的值的排列 <queue>

优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列 <queue>

l 关联式容器

集合(set) 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序 <set>

多重集合(multiset) 允许存在两个次序相等的元素的集合 <set>

映射(map) 由{键，值}对组成的集合，以某种作用于键对上的谓词排列 <map>

多重映射(multimap) 允许键对有相等的次序的映射 <map>

2.迭代器

软件设计有一个基本原则，所有的问题都可以通过引进一个间接层来简化，这种简化在STL中就是用迭代器来完成的。概括来说，迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。

迭代器部分主要由头文件<utility>,<iterator>和<memory>组成。<utility>是一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明，<iterator>中提供了迭代器使用的许多方法，而对于<memory>的描述则十分的困难，它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制,<memory>中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。

3. 算法

大家都能取得的一个共识是函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类型要高。而C++通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的——你可以将所有的类型划分为少数的几类，然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。

STL提供了大约100个实现算法的模版函数，比如算法for_each将为指定序列中的每一个元素调用指定的函数，stable_sort以你所指定的规则对序列进行稳定性排序等等。这样一来，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率。

算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。<algorithm>是所有STL头文件中最大的一个（然而它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。<functional>中则定义了一些模板类，用以声明函数对象。 

二、string容器

C++STL提供了string基本字符系列容器来处理字符串，可以把string理解为字符串类，它提供了添加、删除、替换、查找和比较等丰富的方法。

使用string容器，需要包含头文件，即“#include <string>”。

1.string对象的创建和赋值

创建string对象实际上就是定义string类型的变量，如：

string s;

给string对象赋值与给一般变量赋值的方法相同，可以用另一个string变量给string变量赋值，也可以将一个字符串直接赋给string变量，如：

s = "Microsoft Visual C++";

2.尾部添加字符或字符串

尾部添加字符或字符串可以使用+操作符、也可以使用append()函数。

l +操作符

string s = ""; // 创建了string对象s并将其初始化为空字符串

s = s + 'a'; // s中保存的字符串为“a”

s = s + "abc"; // s中保存的字符串为“aabc”

l append()方法

string s = ""; // 创建了string对象s并将其初始化为空字符串

s.append("abc"); // s中保存的字符串为“abc”

s.append("123"); // s中保存的字符串为“abc123”

3.插入字符或字符串

使用insert()方法可以向一个string对象中插入字符或字符串，如：

string s = "123456"; // 创建了string对象s并将其初始化为“123456”

string s1 = "de"; // 创建了string对象s1并将其初始化为“de”

s.insert(s.begin()+1, 'p'); // 插入字符p后，s中保存的字符串为“1p23456”

s.insert(1, "abc"); // 插入字符串abc后，s中保存的字符串为“1abcp23456”

s.insert(1, s1); // 插入string对象s1中的字符串后，s中保存的字符串为“1deabcp23456”

4.元素的访问和删除

l 元素访问_

可直接采用下标（从0开始）访问，如：

string s = "123456"; // 创建了string对象s并将其初始化为“123456”

cout<<s[1]; // 输出2

l 元素删除

string s = "123456"; // 创建了string对象s并将其初始化为“123456”

s.erase(s.begin()+3); // 删除下标为3的元素，删除后s中保存的字符串“12356”

s.erase(s.begin(), s.begin()+2); // 删除下标从0到2（不包含2）的元素，删除后s中保存的字符串为“356”

s = ""; // 清空字符串

5.其他常用操作

l 采用length()方法可返回字符串的长度；

l 采用empty()方法，可返回字符串是否为空，如果字符串为空，则返回逻辑真，否则，返回逻辑假。

l 使用replace()方法可以很方便地替换string对象中的字符。

l 采用find()方法可查找字符串中的第一个字符元素（char，用单引号界定）或者子串（用双引号界定），如果查到，则返回下标值（从0开始计数），如果查不到，则返回-1。

l 使用compare()方法与其他字符串相比较。如果它比对方大，则返回1；如果它比对方小，则返回-1；如果它与对方相同（相等），则返回0。

l 采用reverse()方法可将string对象迭代器所指向的一段区间中的元素（字符）反向排序。reverse()方法需要包含头文件algorithm。

下面通过例子说明string常用操作的使用方法。

【例1】string容器使用示例。

#include <string>

#include <algorithm>

#include <iostream>

using namespace std;

int main()

{

string s = "";

string s1 = "de";

s = s + '1'; // 1

s = s + "23"; // 123

cout<<s.compare("123")<<endl // 0

<<s.compare("a0")<<endl // -1

<<s.compare("0a")<<endl; // 1

s.append("456"); // 123456

s.insert(s.begin()+1, 'p'); // 1p23456

s.insert(1, "abc"); // 1abcp23456

s.insert(1, s1); // 1deabcp23456

cout<<s<<endl;

int nI = s.find("ab");

cout<<nI<<endl; // 3

s.replace(s.find("234"), 3, "fg"); // 1deabcpfg56

cout<<s<<endl;

s.erase(s.begin()+3); // 1debcpfg56

s.erase(s.begin(), s.begin()+2); // ebcpfg56

cout<<s<<endl;

reverse(s.begin(), s.end()); // 65gfpcbe

cout<<s<<endl;

cout<<s.length()<<endl; // 8

if (s.empty() == false)

cout<<"s不为空"<<endl;

s = ""; // 空

if (s.empty() == true)

cout<<"s为空"<<endl;

return 0;

}

输出结果如图1所示。

图1 【例1】的输出结果

二、vector容器简介

vector向量容器不但能像数组一样对元素进行随机访问，还能在尾部插入元素，是一种简单、高效的容器，完全可以代替数组。vector具有内存自动管理的功能，对于元素的插入和删除，可动态调整所占的内存空间。

使用vector向量容器，需要头文件包含声明“#include<vector>”。

vector容器的下标是从0开始计数的，也就是说，如果vector容器的大小是n，那么，元素的下标是0~n-1。对于vector容器的容量定义，可以事先定义一个固定大小，事后，可以随时调整其大小；也可以事先不定义，随时使用push_back()方法从尾部扩张元素，也可以使用insert()在某个元素位置前插入新元素。

vector容器有两个重要的方法，begin()和end()。begin()返回的是首元素位置的迭代器；end()返回的是最后一个元素的下一个元素位置的迭代器。

1.vector容器常用操作

l 创建vector对象

创建vector对象常用的有三种形式：

Ø 不指定容器的元素个数，如定义一个用来存储整型的容器：vector<int> v;

Ø 创建时，指定容器的大小，如定义一个用来存储10个double类型元素的向量容器：vector<double> v(10);

Ø 创建一个具有n个元素的向量容器对象，每个元素具有指定的初始值：

     vector<double> v(10,8.6);

上述语句定义了v向量容器，共有10个元素，每个元素的值是8.6。

l 尾部元素扩张

使用push_back()函数可以在vector容器在尾部追加新元素。vector容器会自动为新元素分配内存空间。

例如：

    vector<int> v; // 创建一个不包含任何元素的向量容器对象v

    v.push_back(2); // 向v的尾部添加元素2

    v.push_back(7); // 向v的尾部添加元素7

    v.push_back(9); // 向v的尾部添加元素9

上述语句执行后，v中包含3个元素，依次是2、7、9。

l 访问元素

Ø 下标方式

如：cout<<v[0]<<" " <<v[1]<<" "<<v[2]<<endl;

Ø 迭代器方式

如：

vector<int>::iterator it; // 定义用于访问vector<int>对象中元素的迭代器

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

{

      //输出迭代器的元素值

      cout<<*it<<" ";

}

l 元素的插入

使用insert()函数可以在vector对象的任意位置前插入一个新的元素，同时，vector自动扩张一个元素空间，插入位置后的所有元素一次向后挪动一个位置。

例如：

//在最前面插入新元素，元素值为8

v.insert(v.begin(),8);

//在第2个元素前面插入新元素1

v.insert(v.begin()+2,1);

//在向量末尾追加新元素3

v.insert(v.end(),3);

l 元素的删除

使用erase()函数可以删除vector中迭代器所指的一个元素或一段区间中的所有元素。使用clear()函数则一次删除vector中的所有元素。

例如：

//删除第2个元素，从0开始计数

v.erase(v.begin()+2);

//删除迭代器第1到第5区间的所有元素

v.erase(v.begin()+1,v.begin()+5);

v.clear(); //清空向量

l 其他常用操作

使用size()方法可以返回向量的大小，即元素的个数。使用empty()方法返回向量是否为空。

【例2】vector容器常用操作使用示例。

#include <vector>

#include <iostream>

using namespace std; 

void OutputByIndex(vector<int> &v)

{

int nI;

cout<<"下标方式输出结果：";

for(nI=0; nI<v.size(); nI++)

{

      cout<<v[nI]<<" ";

}

cout<<endl;

}

void OutputByIterator(vector<int> &v)

{

vector<int>::iterator it;

cout<<"迭代器方式输出结果：";

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

{

      //输出迭代器的元素值

      cout<<*it<<" ";

}

cout<<endl;

}

int main()

{

vector<int> v;

v.push_back(2);

v.push_back(7);

v.push_back(9);

OutputByIndex(v);

OutputByIterator(v); // 输出2 7 9

//在最前面插入新元素，元素值为8

v.insert(v.begin(),8);

//在第2个元素前面插入新元素1

v.insert(v.begin()+2,1);

//在向量末尾追加新元素3

v.insert(v.end(),3);

OutputByIterator(v); // 输出8 2 1 7 9 3

//删除第2个元素，从0开始计数

v.erase(v.begin()+2);

OutputByIterator(v); // 输出8 2 7 9 3

//删除迭代器第1到第5区间的所有元素

v.erase(v.begin()+1,v.begin()+5);

OutputByIterator(v); // 输出8

if (v.empty()==false)

cout<<"向量不为空"<<endl;

v.clear(); //清空向量

OutputByIterator(v); // 无输出

if (v.empty()==true)

cout<<"向量为空"<<endl;

return 0;

}

2. vector容器 – 算法

下面我们学习两种算法，分别是元素反向排列算法和元素排序算法。

l reverse反向排列算法

使用reverse算法需要包含头文件<algorithm>，其作用是将向量中某段迭代器区间元素反向排列。

【例3】reverse使用示例。

#include <vector>

#include <algorithm>

#include <iostream>

#include <time.h>

using namespace std;

void OutputByIterator(vector<int> &v)

{

vector<int>::iterator it;

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

{

      //输出迭代器的元素值

      cout<<*it<<" ";

}

cout<<endl;

}

int main()

{

vector<int> v(10);

vector<int>::iterator it;

srand((unsigned int)time(NULL)); // 准备开始取随机数

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

*it = rand()%100; // 取随机数

cout<<"原始数据：";

OutputByIterator(v);

reverse(v.begin(), v.end()); // 将数据反向排列

cout<<"反向排列后数据：";

OutputByIterator(v);

return 0;

}

l 使用sort算法对向量元素排序

使用sort算法也需要包含头文件<algorithm>。默认情况下，sort算法对向量元素进行升序排列，也可以自己设计排序比较函数来指定排序规则。

【例4】sort使用示例。

#include <vector>

#include <algorithm>

#include <iostream>

#include <time.h>

using namespace std;

void OutputByIterator(vector<int> &v)

{

vector<int>::iterator it;

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

{

      //输出迭代器的元素值

      cout<<*it<<" ";

}

cout<<endl;

}

//自己设计排序比较函数：对于元素的值进行降序排列

bool Comp(const int &a,const int &b)

{

return a>b;

}

int main()

{

vector<int> v(10);

vector<int>::iterator it;

srand((unsigned int)time(NULL)); // 准备开始取随机数

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

*it = rand()%100; // 取随机数

cout<<"原始数据：";

OutputByIterator(v);

sort(v.begin(), v.end()); // 对元素按默认规则进行升序排序

cout<<"升序排序后的数据：";

OutputByIterator(v);

sort(v.begin(), v.end(), Comp); // 对元素按Comp指定比较规则进行降序排序

cout<<"降序排序后的数据：";

OutputByIterator(v);

return 0;

}

提示：

Ø 向量的使用方法还有很多，这里举出的只是常用的方法

Ø 向量的元素类型可以是int,double,char等简单类型，也可以是结构体、类或string基本字符序列容器，使用起来非常灵活。