发布时间 : 星期二 文章STL应用篇更新完毕开始阅读3a18734ee518964bcf847cf8
1． 概述
泛型编程思想最早缘于A.Stepanov提出的部分算法可独立于数据结构的论断。20世纪90年代初A.Stepanov和Meng Lee根据泛型编程的理论用C++共同编写了STL。但直至1998年，STL才成为C++的正式标准。在后来的几年中，各大主流编译器也都相继加入了对STL的支持，至此STL才开始得到广泛的应用。
STL体现的是泛型编程的核心思想：独立数据结构和算法(这是一种独立于OO的编程哲学)。STL主要由几个核心部件组成，即迭代器、容器、算法、函数对象、适配器。容器即物之所属；算法是解决问题的方式；迭代器是对容器的访问逻辑的抽象，是连接算法和容器的纽带；迭代器通过添加了一种间接层的方式实现了容器和算法之间的独立；函数对象，就是重载了operator()操作符的对象；适配器是通过组合特定的容器实现的一种新的数据结构。在后续的内容中，我们将对几个核心部件的基础应用进行详细的描述。
2． 基础
C++产生的历史背景赋予了C++太多的职责，比如兼容C、综合的编程语言等，这些虽然赋予了C++强大的功能，但同时也扔给了极大的复杂度。在这篇文章中，我们并不打算将你带入C++的复杂地带，但是需要你有一定的C++基础，比如类、结构等。
STL深深地植根于C++的基础设施，这其中包括了内联、函数对象、函数模板、类模板等。
2.1. 内联
内联是C++中一种特殊的语言机制，使用inline来标识。C++在编译inline标识的函数时，将根据特定的规则将inline函数的代码直接插入到inline函数的调用位置，以此来提高程序的运行效率，但同时也在一定程度上导致了代码的膨胀。请看下面的例子：
inline全局函数
inline void max{?};
inline成员函数 class A{
public:
inline void max{?}; }
2.2. 函数对象
函数对象，就是重载了operator()操作符的对象。相对函数指针，函数对象可以具有状态，更安全，更灵活，基本没有额外的开销。在STL中，函数对象经常被用作算法的输入参数或容器的实例化的参数。请看下面的例子：
定义函数对象类 classs LessThan{
public:
LessThan(int val): m_val(val){}
bool operator()(int val){return m_val < val;} private: int m_val; };
定义函数对象
LessThan less(5);
调用定义函数对象
less(10);//返回为true 2.3. 函数模板
C++中的模板是STL实现的技术基础。C++中的模板可分为函数模板和类模板。函数模板抽象了针对不同类型的同一性质的操作。如针对int/long/string的max操作。请看下面的例子：
定义求取两个类型的值或对象的最大值的操作
template
T max(T a,T b){return a>b ? a : b;} 求取两个int值的最大值 max(0,10);//返回10
求取两个string对象的最大值
max(string(“Hello”),string(“world”));//返回string(“world”) 2.4. 类模板
C++中的模板是STL实现的技术基础。C++中的模板可分为函数模板和类模板。类模板抽象了针对不同类型的同一类事务。如针对int/long/string的Stack。请看下面的例子：
定义一个通用堆栈Stack template
public:
inline void push(const T& value){?} T pop(){?}
void clear(){?}
bool empty() const {?} };
声明一个int类型的Stack typdef Stack
3． 迭代器
STL中的迭代器是C++指针的泛化，它在算法和容器之间充当一个中间层，为处理不同的数据结构提供了一致的方式。迭代器也可以看作是对容器数据结构访问的一种约束。STL中的迭代器可分为类：随机存取迭代器（random-access-iterator），双向存取迭代器(bidirectional-access-iterator)，前向迭代器(forward iterator)，输入迭代器(input-iterator)，输出迭代器(output-iterator)。它们之间的继承关系如下图：
input-iterator
output-iteartor
forward-iterator:output-iteartor , input-iterator bidirectional-access-iterator : forward-iterator
random-access-iterator:bidirectional-access-iterator
图一 迭代器关系图
3.1. 输入迭代器
输入迭代器也可以称之为前向的只读访问器，首先它提供了对容器的只读访问，其次它只能在容器中进行前向迭代（即只提供++操作）。所有的容器的迭代器都具有输入迭代器的特征。通过输入迭代器你可以进行下面三种操作：
1.V = *X++ 2.V = *X,X++
3.V = *X,++X
注：V为值，X为迭代器
3.2. 输出迭代器
输出迭代器也可以称之为前向的只写访问器，首先它提供了对容器的只写访问，其次它只能在容器中进行前向迭代（即只提供++操作）。通过输出迭代器你可以进行下面三种操作：
1.*X++ = V 2.*X = V, X++
3.*X = V, ++X
注：V为值，X为迭代器
3.3. 前向迭代器
前向迭代器继承自输入和输出迭代器，因此具有输入和输出迭代器的所有特征，也即提供对容器数据结构的读写访问但也只具有前向迭代的能力（即只提供++操作）。因此，你可以对前向迭代器进行操作：R == S /++R == ++S。 请看下面的例子：
定义一个利用前向迭代器进行线性查找的算法
template
{
for (; first != last; ++first){
if (*first == value) return first; }
return last; }
测试
int ia[] = {35,3,23};
vector
vector
std::cout << \else
std::cout << \测试结果为：Not Found
3.4. 双向存取迭代器
双向存取迭代器从前向迭代器继承过来，因而具有前向迭代器的所有特征，双向存取迭代器还具有后向访问能力（即只提供--操作）。请看下面的例子： 定义一个利用双向迭代器排序算法
template
first,ForwardIterator
void sort_me(BidirectionalIterator first,BidirectionalIterator last,Compare comp)
{
for(BidirectionalIterator i = first; i != last; ++i) {
BidirectionalIterator _last = last; while(i != _last--) {
if (comp(*i,*_last)) iter_swap(i,_last); } } } 测试
int ia[] = {123,343,12,100,343,5,5}; vector
sort_me(vec.begin(),vec.end(),less
copy(vec.begin(),vec.end(),ostream_iterator
测试结果为：5 5 12 100 123 343 343 3.5. 随机存取迭代器
随机存取迭代器从双向存取迭代器继承过来，因而具有双向存取迭代器的所有特征。所不同的是，利用随机存取迭代器你可以对容器数据结构进行随机访问，因而随机存取迭代器还可以定义下面的操作：
1.operator+(int)
2.operator+=(int) 3.operator-(int)
4.operator-=(int) 5.operator[](int)
6.operator-(random-access-iterator) 7.operator>(random-access-iterator) 8.operator<(random-access-iterator) 9.operator>=(random-access-iterator) 10.operator<=(random-access-iterator)
在STL中，随机存取双向迭代器只能作用于顺序容器。请看下面的例子： 测试输出vector里面的数据
int ia[] = {123,343,12,100,343,5,5}; vector
for(int i = 0; i < vec.size(); ++i) std::cout << vec[i] << \测试结果为：123 343 12 100 343 5 5
4． 容器
容器即物之所在。容器是STL的核心部件之一，是迭代器的依附，是算法作用的目标。