STL六⼤组件
容器（Container）
算法（Algorithm）
迭代器（Iterator）
仿函数（Function object）
适配器（Adaptor）
空间配置器（allocator）
1、容器
作为STL的最主要组成部分－－容器，分为向量（vector），双端队列(deque)，表(list)，队列（queue），堆栈(stack)，集合(set)，多重集合(multiset)，映射(map)，多重映射(multimap)。
容器特性所在头⽂件
<vector>
向量vector可以⽤常数时间访问和修改任意元素，在序列
尾部进⾏插⼊和删除时，具有常数时间复杂
度，对任意项的插⼊和删除就有的时间复杂度
与到末尾的距离成正⽐，尤其对向量头的添加
和删除的代价是惊⼈的⾼的
<deque>
双端队列deque基本上与向量相同，唯⼀的不同是，其在序
列头部插⼊和删除操作也具有常量时间复杂度
<list>
表list对任意元素的访问与对两端的距离成正⽐，但
对某个位置上插⼊和删除⼀个项的花费为常数
时间。
<queue>
队列queue插⼊只可以在尾部进⾏，删除、检索和修改只
允许从头部进⾏。按照先进先出的原则。
<stack>
堆栈stack堆栈是项的有限序列，并满⾜序列中被删除、
检索和修改的项只能是最近插⼊序列的项。即
按照后进先出的原则
<set>
集合set由节点组成的红⿊树，每个节点都包含着⼀个
元素，节点之间以某种作⽤于元素对的谓词排
列，没有两个不同的元素能够拥有相同的次
序，具有快速查的功能。但是它是以牺牲插
⼊删除操作的效率为代价的
<set>
多重集合multiset和集合基本相同，但可以⽀持重复元素具有快
速查能⼒
<map>
映射map由{键，值}对组成的集合，以某种作⽤于键对上
的谓词排列。具有快速查能⼒
<map>
多重集合multimap⽐起映射，⼀个键可以对应多了值。具有快速
查能⼒
STL容器能⼒表：
2、算法
算法部分主要由头⽂件<algorithm>，<numeric>和<functional>组成。< algorithm>是所有STL头⽂件中最⼤的⼀个，它是由⼀⼤堆模版函数组成的，可以认为每个函数在很⼤程度上都是独⽴的，其中常⽤到的功能范围涉及到⽐较、交换、查、遍历操作、复制、修改、移除、反转、排序、合并等等。<numeric>体积很⼩，只包括⼏个在序列上⾯进⾏简单数学运算的模板函数，包括加法和乘法在序列上的⼀些操作。<functional>中则定义了⼀些模板类，⽤以声明函数对象。
STL的算法也是⾮常优秀的，它们⼤部分都是类属的，基本上都⽤到了C＋＋的模板来实现，这样，很多相似的函数就不⽤⾃⼰写了，只要⽤函数模板就可以了。
我们使⽤算法的时候，要针对不同的容器，⽐如：对集合的查，最好不要⽤通⽤函数find（），它对集合使⽤的时候，性能⾮常的差，最好⽤集合⾃带的find（）函数，它针对了集合进⾏了优化，性能⾮常的⾼。
3、迭代器
它的具体实现在<itertator>中，我们完全可以不管迭代器类是怎么实现的，⼤多数的时候，把它理解为指针是没有问题的（指针是迭代器的⼀个特例，它也属于迭代器），但是，决不能完全这么做。
迭代器功能
输⼊迭代器
Input iterator
、Reads forward istream
sizeof是什么
输出迭代器Output iterator 向前写
Writes forward
ostream,inserter
前向迭代器Forward iterator 向前读写
Read and Writes forward
双向迭代器Bidirectional iterator 向前向后读写
Read and Writes forward
and
backward
list,set,multiset,map,mul
timap
随机迭代器Random access iterator 随机读写
Read and Write with
random
access
vector,deque,array,string
4、仿函数
1仿函数(functor)的概念
仿函数(functor)，就是使⼀个类的使⽤看上去象⼀个函数。其实现就是类中实现⼀个operator()，这个类就有了类似函数的⾏为，就是⼀个仿函数类了。
在我们写代码时有时会发现有些功能的实现的代码，会不断的在不同的成员函数中⽤到，但是⼜不好将这些代码独⽴出来成为⼀个类的⼀个成员函数。但是⼜很想复⽤这些代码。写⼀个公共的函数，可以，这是⼀个解决⽅法，不过函数⽤到的⼀些，就可能成为公共的，再说为了复⽤这么⼀⽚代码，就要单⽴出⼀个函数，也不是很好维护。这时就可以⽤仿函数了，写⼀个简单类，除了那些维护⼀个外，就只是实现⼀个operator()，在类实例化时，就将要⽤的，⾮参数的元素传⼊类中。这样就免去了对⼀些公共的全局化的维护了。⼜可以使那些代码独⽴出来，以便下次复⽤。⽽且这些仿函数，还可以⽤关联，聚合，依赖的类之间的关系，与⽤到他们的类组合在⼀起，这样有利于资源的管理（这点可能是它相对于函数最显著的优点了）。如果在配合上模板技术和policy编程思想，那就更是威⼒⽆穷了，⼤家可以慢慢的体会。
仿函数，⼜或叫做函数对象，是STL六⼤组件之⼀；仿函数虽然⼩，但却极⼤的拓展了算法的功能，⼏乎所有的算法都有仿函数版本。例如，查算法find_if就是对find算法的扩展，标准的查是两个元素相等就到了，但是什么是相等在不同情况下却需要不同的定义，如地址相等，地址和邮编都相等，虽然
这些相等的定义在变，但算法本⾝却不需要改变，这都多亏了仿函数。仿函数(functor)⼜称之为函数对象（function object），其实就是重载了()操作符的struct，没有什么特别的地⽅。
仿函数(functor)在各编程语⾔中的应⽤
C
C语⾔使⽤和来实现仿函数，例如⼀个⽤来排序的函数可以这样使⽤仿函数
#include <stdlib.h>
/* Callback function */
int compare_ints_function(void*A,void*B)
{
return*((int*)(A))<*((int*)(B));
}
/* Declaration of C sorting function */
void sort(void*first_item,size_t item_size,void*last_item,int(*cmpfunc)(void*,void*));
int main(void)
{
int items[]={4,3,1,2};
sort((void*)(items),sizeof(int),(void*)(items +3), compare_ints_function);
return 0;
}
C++
在C++⾥，我们通过在⼀个类中括号的⽅法使⽤⼀个⽽不是⼀个普通函数。
class compare_class
{
public:
bool operator()(int A, int B)const{return A < B;}
};
// Declaration of C++ sorting function.
template<class ComparisonFunctor>
void sort_ints(int* begin_items, int num_items, ComparisonFunctor c);
int main()
{
int items[]={4, 3, 1, 2};
compare_class functor;
sort_ints(items, sizeof(items)/sizeof(items[0]), functor);
}
如以下代码定义了⼀个⼆元判断式functor：
struct IntLess
{
bool operator()(int left, int right) const
{
return (left < right);
};
};
最基本的仿函数举例：
/**
Function Object
*/
class PrintInt
{
public:
void operator()(int elem) const
{
std::cout<<elem<<' ';
}
};
void testPrintInt()
{
std::vector<int> intVec;
for(int i=1;i<10;++i)
intVec.push_back(i);
for_each(intVec.begin(),d(),
PrintInt());    ///PrintInt()产⽣此类型的⼀个临时对象，当for_each算法的⼀个参数    std::cout<<std::endl;
}
STL中for_each()算法⼤致实现如下：
template <typename Iterator, typename operation>
operation for_each(Iterator b,Iterator e,operation op)
{
while(b++ != e)
{
op(*b);
}
return op;
}
在本例中，for_each()调⽤PrintInt::operator(*b);
为什么要使⽤仿函数呢？
1).仿函数⽐⼀般的函数灵活。
2).仿函数有类型识别，可以作为模板参数。
3).执⾏速度上仿函数⽐函数和指针要更快的。
怎么使⽤仿函数？
除了在STL⾥，别的地⽅你很少会看到仿函数的⾝影。⽽在STL⾥仿函数最常⽤的就是作为函数的参数，或者模板的参数。
在STL⾥有⾃⼰预定义的仿函数，⽐如所有的运算符，=，-，*，、⽐如'<'号的仿函数是less
template<class _Ty>
struct less  : public binary_function<_Ty, _Ty, bool>
{ // functor for operator<
bool operator()(const _Ty& _Left, const _Ty& _Right) const
{ // apply operator< to operands
return (_Left < _Right);
}
};
从上⾯的定义可以看出，less从binary_function<...>继承来的，那么binary_function⼜是什么的？
template<class _Arg1, class _Arg2, class _Result>
struct binary_function
{ // base class for binary functions
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
其实binary_function只是做⼀些类型声明⽽已，别的什么也没做，但是在STL⾥为什么要做这些呢？如果你要阅读过STL的源码，你就会发现，这样的⽤法很多，其实没有别的⽬的，就是为了⽅便，安全，可复⽤性等。但是既然STL⾥⾯内定如此了，所以作为程序员你必须要遵循这个规则，否则就别想安全的使⽤STL。
⽐如我们⾃⼰定⼀个仿函数。可以这样：
template <typename type1,typename type2>
class func_equal :public binary_function<type1,type2,bool>
{
inline bool operator()(type1 t1,type2 t2) const//这⾥的const不能少
{
return t1 == t2;//当然这⾥要overload==
}
}
我们看这⼀⾏： inline bool operator()(type1 t1,type2 t2) const//这⾥的const不能少
inline是声明为内联函数，我想这⾥应该不⽤多说什么什么了，关键是为什么要声明为const的？要想
到原因还是看源码，加⼊如果我们这⾥写⼀⾏代码，find_if(s.begin(),s.end(),bind2nd(func_equal(),temp))，在bind2nd函数⾥⾯的参数是const类型的，const类型的对象，只能访问cosnt修饰的函数！
与binary_function(⼆元函数)相对的是unary_function(⼀元函数)，其⽤法同binary_function
struct unary_function {
typedef _A argument_type;
typedef _R result_type;
};
注：仿函数就是重载()的class，并且重载函数要为const的，如果要⾃定义仿函数，并且⽤于STL接配器，那么⼀定要从binary_function或者，unary_function继承。
5、适配器
适配器是⽤来修改其他组件接⼝的STL组件，是带有⼀个参数的类模板（这个参数是操作的值的数据类型）。STL定义了3种形式的适配器：容器适配器，迭代器适配器，函数适配器。
容器适配器：包括栈（stack）、队列(queue)、优先(priority_queue)。使⽤容器适配器，stack就可以被实现为基本容器类型
（vector,dequeue,list）的适配。可以把stack看作是某种特殊的vctor,deque或者list容器，只是其操作仍然受到stack本⾝属性的限制。queue 和priority_queue与之类似。容器适配器的接⼝更为简单，只是受限⽐⼀般容器要多。
迭代器适配器：修改为某些基本容器定义的迭代器的接⼝的⼀种STL组件。反向迭代器和插⼊迭代器都属于迭代器适配器，迭代器适配器扩展了迭代器的功能。
函数适配器：通过转换或者修改其他函数对象使其功能得到扩展。这⼀类适配器有否定器（相当于"⾮"操作）、绑定器、函数指针适配器。函数对象适配器的作⽤就是使函数转化为函数对象，或是将多参数的函数对象转化为少参数的函数对象。
例如：
在STL程序⾥，有的算法需要⼀个⼀元函数作参数，就可以⽤⼀个适配器把⼀个⼆元函数和⼀个数值，绑在⼀起作为⼀个⼀元函数传给算法。
bind1st和bind2nd函数⽤于将⼀个⼆元算⼦（binary functor，bf）转换成⼀元算⼦（unary functor，uf）。
我们在做⽐较的时候所写的表达式像 x > k ，x < k，这⾥的k是⼀个参数表⽰你程序⾥⾯的表达式要和k值去⽐较。上⾯这两个表达式对应的应该是bind2nd ，简单的理解就是把k作为⽐较表达式的第⼆个参数。如果使⽤bind1st则对应的表达式是 k > x，k < x，也就是把k作为⽐较表达式的第⼀个参数。
例如：
find_if(coll.begin(), d(), bind2nd(greater <int>(), 42));
这句话就是coll中第⼀个⼤于42的元素。
greater <int>()，其实就是">"号，是⼀个2元函数
bind2nd的两个参数，要求⼀个是2元函数，⼀个是数值，结果是⼀个1元函数。
bind2nd就是个函数适配器。
eg:
1、⾸先看⼀个容器的操作：
void f(std::vector<int> &vect)
{
std::vector<int>::iterator firstOne;
for (firstOne = vect.begin();
firstOne != d();
++firstOne)
{
doSomething(*firstOne, "Some string literal");
}
}
这个f调⽤就是完成对容器vect的迭代，并在迭代过程中，处理iter值和⼀个不变的字符串，⾄于dosomething完成什么功能，根本不必关⼼。这⾥有⼈肯定要说，不是⽤for_each就可完成这种功能吗，可for_each只接受⼀个参数的函数。如下所⽰：
funcation for_each(iterator beg_it, iterator end_it, funcation func);
那么怎样让func能够绑定当前iterator值和⼀个不变的字符串呢？如果成功，问题就OK了。
在解决这个问题必须要⽤到适配器函数，如bind1nd, bind2st之流的捆绑函数。在解析这两个函数之前，先看看Funcation的类声明：
2、Funcation的类声明：
template <class Arg, class Arg2, class Res>
struct binary_function {
typedef Arg first_argument_type;
typedef Arg2 second_argument_type;
typedef Res result_type;
};
ok, 我们⾃⼰的func也可继承这个基类，哈哈，改进后的dosomething声明：
class dosomething:public
std::binary_funcation<int, const char *, void>
{
//其中,int是我们当前iterator值类型，const char *是要传递的固定不变的字符串，void是我们func的返回值。看看下⾯的重载() 声明，就明⽩了：
public:
void  operator()(int ival, const char *s)
{
// 在这⾥添加你想⼲的事情，记住，ival就是当前iterator的值， s是需要绑定的不变字符串
}
};
3、bind1st和bind2nd的选择
从如上的dosomething可以看出，需要绑定的是s这个不变字符串，是第⼆个参数，所以当然选择bind2nd，如果dosomething的声明如下：