STL整体结构

STL主要由六部分组成，分别为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)。

它们之间的关系如下：

容器通过内存分配器分配空间

容器和算法分离

算法通过迭代器访问容器

仿函数协助算法完成不同的策略变化

适配器套接仿函数

仿函数，仿函数适配器

仿函数又称为函数对象（Function Object），其作用相当于一个函数指针。 在STL中，将std::remove_if(v.begin().v.end(),ContainsString(L"C++"));中类似于ConstainString这种形为函数指针的对象定义为仿函数，其实它是一个重载了括号运算符的Class。因此，自定义的仿函数必须重载operator():

struct ContainString:

public std::unary_function

{

ConstainString(const std::wstring& wszMatch):

m_wszMatch(wszMatch){}

bool operator()(const std::wstring& wszStringToMatch) const

{

return (wszStringToMatch.find(m_wszMatch)!=-1);

}

std::wstring m_wszMatch;

}

仿函数存在的意义：

1. 普通函数指针不能满足STL的抽象要求（参数和返回型别的定义问题）

2. 函数指针无法和STL其他组件交互

3. 仿函数可以作为模板实参来定义对象的某种默认行为：

//定义set的默认排序行为

template,...>

class set{

...

}

仿函数适配器。STL提供三种适配器：改变容器接口的容器适配器、改变迭代器接口的迭代器适配器以及改变仿函数接口的仿函数适配器。前两者都较为简单，而最后一种则是灵活性最大的，有了它我们可以构造非常复杂的表达式策略。

在一些情况下仿函数可能无法匹配成合适的型别，这个时候我们就需要使用仿函数适配器：binder1st/binder2nd, mem_fun/men_fun_ref。例如，在一个给定的vector中寻找不为零的元素。通常我们会想到使用std::not_equal_to这个仿函数，但是该函数接受两个参数。为了能在std::find_if中使用这个函数，我们这时候就需要绑定其中一个变量为0，以实现判断一个元素是否不为零的功能：

std::vector::iterator it = std::find_if(v.begin(),v.end(),

std::bind1st(std::not_equal_to(),0));

//bind1st 封装了binder1st的调用复杂性：

template

inline binder1st<_Fn2> bind1st(const _Fn2& _Func,const _Ty& _Left)

{

typename _Fn2::first_argument_type_Val(_Left);

return (binder1st<_Fn2>(_Func,_Val));

}

对于类的成员函数的适配，我们可以使用mem_fun/mem_fun_ref：

template <_Result, class _Ty> inline

mem_fun_t<_Result,_Ty> mem_fun(_Result (_Ty::*_Pm)() )

{

return (mem_fun_t<_Result, _Ty>(_Pm));

}

template

class mem_fun_t : public unar_function<_Ty *, _Result>

{

public:

explicit mem_fun_t(_Result (_Ty::*_Pm)())

: _Pmemfun(_Pm)  { }

_Result operator()(_Ty *_Pleft) const

{

return ((_Pleft->*_Pmemfun)());

}

private:

_Result (_Ty::*_Pmemfun());

}

其他需要注意的问题

(1) 单线程情况下涉及对字符串的操作，首选std::string/wstring。 多线程情况下要注意string是否带引用计数。在多线程环境下，避免分配和拷贝所节省下的开销转嫁到了并发控制上。一般考虑使用vector/vector，因为vector的实现是不带引用计数的。

(2) 当用new创建的对象直接放入容器时，要在销毁容器前delete那些对象：

v.push_back(new Person("TOM",1));

...

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

{

delete (*it);

}

v.clear();

(3)尽量使用算法调用代替手写循环，如上面的删除，我们可以定义一个仿函数在for_each中实现：

struct DeleteElement{

template

void operator() (const TElement* p) const

{

delete p;

}

}

std::for_each(v.begin(),v.end(),DeleteElement());

(4) 可以通过swap为容器“缩水”：

std::vector(v).swap(v);//使capacity = size

std::vector().swap(v) //清除v并最小化其容量:capacity = size = 0

(5) 在有对象继承的情况下，建立指针的容器，而不是对象的容器。因为：a）容器装入的对象是原始对象的拷贝，如果对象很大，则有较大性能开销；b）由于继承的存在，拷贝会发生slicing，导致丢失数据。

泛型算法

简单列出STL为我们提供的算法：

非变易性算法

for_each 提供对于容器内每个元素进行循环操作

find 线性查找

find_fist_of 对于给定值的集合,在容器内线性查找

adjacent_find 线性查找邻近且相等的元素对

count 计算给定值的出现次数

mismatch 比较两个序列,找出第一个不相同元素的位置

equal 两个序列的判等操作,逐一比较元素是否相等

search 在一个序列中查找与另一个序列匹配的子序列

search_n 在序列中查找一系列符合给定值的元素

find_end 在一个序列中查找最后一个与另一个序列匹配的子序列

变易性算法

copy 复制元素到另外一个序列

swap 两个容器元素交换

transform 序列中的元素都用这个元素变换后的值代替

replace 替换给定值的元素

fill 填充给定值的元素

generate 用某函数的返回值来代替序列中的所有元素

remove 删除序列中等于某一给定之的所有元素

unique 删除所有连续相等的元素

reverse 将元素之间的位置关系取逆

rotate 循环移动序列中的元素

random_shuffle 随机排列元素

partition 按某一顺序重新排列元素

有序队列算法

sort,stable_sort,partial_sort 对元素排序

nth_element 查找第n个大的元素

binary_search lower_bound upper_bound equal_range 用二分查找搜索有序队列

merge 归并两个有序队列

includes set_union set_intersection set_difference set_sysmetric_difference 集合运算

push_heap pop_heap make_heap sort_heap 堆操作

min max min_element max_element 求最大,最小元素

lexicographical_compare 字典序比较

next_permutation prev_permutation 依据字典序生成排列

通用数字算法

accumulate 累加

inner_product 内积

partial_sum 累加部分元素

adjacent_difference 计算相邻元素的差,保存在另一个序列中

泛型算法的结构

就像所有的容器都建立在一致的设计模式上一样，算法也具有共同的设计基础。

算法最基本的性质是需要使用的迭代器种类。 另一种算法分类方法是前面介绍的按实现的功能分类：只读算法，不改变元素的值和顺序；给指定元素赋新值的算法；将一个元素的值移给另一个元素的算法。 另外，算法还有两种结构上的算法模式：一种模式是由算法所带的形参定义；另一种模式则通过两种函数命名和重载的规范定义。

算法的形参模式

大多数算法采用下面四种形式之一：

alg (beg, end, other parms);

alg (beg, end, dest, other parms);

alg (beg, end, beg2, other parms);

alg (beg, end, beg2, end2, other parms);

其中，alg是算法名，[beg, end)是输入范围，beg, end, dest, beg2, end2都是迭代器。

对于带有单个目标迭代器的算法：dest形参是一个迭代器，用于指定存储输出数据的目标对象。算法假定无论需要写入多少个元素都是安全的。注意：调用这类算法时，算法是将输出内容写到容器中已存在的元素上，所以必须确保输出容器中有足够大的容量存储输出数据，这也正是通过使用插入迭代器或者ostream_iterator来调用这些算法的原因。

对于带第二个输入序列的算法：beg2和end2标记了完整的输出范围。而只有beg2的算法将beg2视为第二个输入范围的首元素，算法假定以beg2开始的范围至少与beg和end指定的范围一样大。

算法的命名规范

包括两种重要模式：第一种模式包括测试输入范围内元素的算法，第二种模式则应用于输入范围内元素的重新排序的算法。

1）区别带有一个值或一个谓词函数参数的算法版本

很多算法通过检查其输入范围内的元素实现其功能。这些算法通常要用到标准关系操作符：==或<。其中的大部分算法都提供了第二个版本的算法，允许程序员提供比较或测试函数取代默认的操作符的使用。

例如， 排序算法默认使用 < 操作符，其重载版本带有一个额外的形参，表示取代默认的 < 操作符。

sort (beg, end);        // use < operator to sort the elements

sort (beg, end, comp);  // use function named comp to sort the elements

又如，查找算法默认使用 == 操作符。标准库为这类算法提供另外命名的（而非重载的）版本，带有谓词函数形参。对于带有谓词函数形参的算法，其名字带有后缀 _if：

find (beg, end, val);      // find first instance of val in the input range

find_if (beg, end, pred);  // find first instance for which pred is true

标准库为这类算法提供另外命名的版本，而非重载版本，原因在于这两种版本的算法带有相同的参数个数，容易导致二义性。

2）区别是否实现复制的算法版本

默认情况下，算法将重新排列的写回其范围。标准库也为这类算法提供了另外命名的版本，将元素写到指定的输出目标。此版本的算法在名字中添加 _copy后缀，例如：

reverse (beg, end);

reverse_copy (beg, end, dest);

第一个版本将输入序列中的元素反向重新排列；而第二个版本将复制输入序列中的元素，并将它们以逆序存储到dest开始的序列中。

容器特有的算法

list容器上的迭代器是双向的，而不是随机访问类型。由于list容器不支持随机访问，因此，在此容器上不能使用需要随机访问迭代器的算法。如sort类算法。其它有些算法，如merge, remove, reverse, unique等，虽然可以用在list上，但性能太差。list容器结合自己的结构专门实现了更为高效的算法。因此，对于list对象，应该优先使用list容器特有的成员版本，而不是泛型算法。

list容器特有的算法与其泛型算法版本之间有两个重要的差别：1）remove和unique的list版本修改了其关联的基础容器：真正删除了指定的元素；2）list容器提供的merge和splice操作会破坏它们的实参。使用泛型算法的merge版本，合并的序列将写入目标迭代器指向的对象，而它的两个输入序列保持不变。

STL的内存分配器

隐藏在STL的容器后的内存管理工作是通过STL提供的一个默认的allocator实现的。当然，用户也可以定制自己的allocator，只要实现allocator模板所定义的接口方法即可，然后通过将自定义的allocator作为模板参数传递给STL容器，创建一个使用自定义allocator的STL容器对象，如：

stl::vector array;

大多数情况下，STL默认的allocator就已经足够了。这个allocator是一个由两级分配器构成的内存管理器，当申请的内存大小大于128byte时，就启动第一级分配器通过malloc直接向系统的堆空间分配，如果申请的内存大小小于128byte时，就启动第二级分配器，从一个预先分配好的内存池中取一块内存交付给用户，这个内存池由16个不同大小（8的倍数，8~128byte）的空闲列表组成，allocator会根据申请内存的大小（将这个大小round up成8的倍数）从对应的空闲块列表取表头块给用户。

这种做法有两个优点：

1）小对象的快速分配。小对象是从内存池分配的，这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用，当内存池耗尽时再向系统申请一块新的区域，整个过程类似于批发和零售，起先是由allocator向总经商批发一定量的货物，然后零售给用户，与每次都总经商要一个货物再零售给用户的过程相比，显然是快捷了。当然，这里的一个问题时，内存池会带来一些内存的浪费，比如当只需分配一个小对象时，为了这个小对象可能要申请一大块的内存池，但这个浪费还是值得的，况且这种情况在实际应用中也并不多见。

2）避免了内存碎片的生成。程序中的小对象的分配极易造成内存碎片，给操作系统的内存管理带来了很大压力，系统中碎片的增多不但会影响内存分配的速度，而且会极大地降低内存的利用率。以内存池组织小对象的内存，从系统的角度看，只是一大块内存池，看不到小对象内存的分配和释放。

实现时，allocator需要维护一个存储16个空闲块列表表头的数组freelist，数组元素i是一个指向块大小为8*(i+1)字节的空闲块列表的表头，一个指向内存池起始地址的指针startfree和一个指向结束地址的指针end_free。空闲块列表节点的结构如下：

union obj {

union obj *free_list_link;

char client_data[1];

};

这个结构可以看做是从一个内存块中抠出4个字节大小来，当这个内存块空闲时，它存储了下个空闲块，当这个内存块交付给用户时，它存储的时用户的数据。因此，allocator中的空闲块链表可以表示成

obj* free_list[16];

分配算法

allocator分配内存的算法如下：

算法：allocate

输入：申请内存的大小size

输出：若分配成功，则返回一个内存的地址，否则返回NULL

{

if(size大于128）{ 启动第一级分配器直接调用malloc分配所需的内存并返回内存地址；}

else {

将size向上round up成8的倍数并根据大小从free_list中取对应的表头free_list_head;

if(free_list_head不为空）{

从该列表中取下第一个空闲块并调整free_list；

返回free_list_head;

} else {

调用refill算法建立空闲块列表并返回所需的内存地址；

}

}

}

算法： refill

输入：内存块的大小size

输出：建立空闲块链表并返回第一个可用的内存块地址

{

调用chunk_alloc算法分配若干个大小为size的连续内存区域并返回起始地址chunk和成功分配的块数nobj；

if(块数为1)直接返回chunk；

否则

{

开始在chunk地址块中建立free_list;

根据size取free_list中对应的表头元素free_list_head;

将free_list_head指向chunk中偏移起始地址为size的地址处, 即free_list_head=(obj*)(chunk+size);

再将整个chunk中剩下的nobj-1个内存块串联起来构成一个空闲列表；

返回chunk，即chunk中第一块空闲的内存块；

}

}

算法：chunk_alloc

输入：内存块的大小size，预分配的内存块块数nobj(以引用传递)

输出：一块连续的内存区域的地址和该区域内可以容纳的内存块的块数

{

计算总共所需的内存大小total_bytes；

if(内存池中足以分配，即end_free - start_free >= total_bytes) {

则更新start_free;

返回旧的start_free;

} else if(内存池中不够分配nobj个内存块，但至少可以分配一个){

计算可以分配的内存块数并修改nobj；

更新start_free并返回原来的start_free;

} else { //内存池连一块内存块都分配不了

先将内存池的内存块链入到对应的free_list中后；

调用malloc操作重新分配内存池，大小为2倍的total_bytes加附加量，start_free指向返回的内存地址；

if(分配不成功) {

if(16个空闲列表中尚有空闲块）

尝试将16个空闲列表中空闲块回收到内存池中再调用chunk_alloc(size, nobj)；

else {

调用第一级分配器尝试out of memory机制是否还有用；

}

}

更新end_free为start_free+total_bytes，heap_size为2倍的total_bytes;

调用chunk_alloc(size,nobj);

}

}

算法：deallocate

输入：需要释放的内存块地址p和大小size

{

if(size大于128字节）直接调用free(p)释放；

else{

将size向上取8的倍数，并据此获取对应的空闲列表表头指针free_list_head;

调整free_list_head将p链入空闲列表块中；

}

}

内存分配器小结

STL中的内存分配器实际上是基于空闲列表(free list)的分配策略，最主要的特点是通过组织16个空闲列表，对小对象的分配做了优化。

1）小对象的快速分配和释放。当一次性预先分配好一块固定大小的内存池后，对小于128字节的小块内存分配和释放的操作只是一些基本的指针操作，相比于直接调用malloc/free，开销小。

2）避免内存碎片的产生。零乱的内存碎片不仅会浪费内存空间，而且会给OS的内存管理造成压力。

3）尽可能最大化内存的利用率。当内存池尚有的空闲区域不足以分配所需的大小时，分配算法会将其链入到对应的空闲列表中，然后会尝试从空闲列表中寻找是否有合适大小的区域，

但是，这种内存分配器局限于STL容器中使用，并不适合一个通用的内存分配。因为它要求在释放一个内存块时，必须提供这个内存块的大小，以便确定回收到哪个free list中，而STL容器是知道它所需分配的对象大小的，比如上述：

stl::vector array;

array是知道它需要分配的对象大小为sizeof(int)。一个通用的内存分配器是不需要知道待释放内存的大小的，类似于free(p)。