Posted on

《STL源码剖析》学习笔记(4)

20,STL仿函数需要定义相应的型别,以便让配接器取出,以此而拥有配接能力,相应型别只是一些typedef,所有操作在编译期全部完成,对程序的执行效率没有影响。仿函数的相应型别主要用来表现函数参数型别和传回值,为了方便,STL已经定义了两个class,代码如下:

template <class Arg, class Result>
struct unary_function {
    typedef Arg argument_type;
    typedef Result result_type;
};
 
template </class><class Arg1, class Arg2, class Result>
struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};      
</class>

Continue reading 《STL源码剖析》学习笔记(4)

Posted on

《STL源码剖析》学习笔记(3)

18,copy算法利用函数重载,对char* 和wchar_t* 的操作直接memmove,利用模版特化对于有trivial operator=的操作memmove,对于RandomAccessIterator通过头尾间隔来确定循环次数,对于InputIterator通过不断累加是否到达last来确定循环次数。

template <class InputIterator, class OutputIterator>
inline OutputIterator __copy(InputIterator first, InputIterator last,
	OutputIterator result, input_iterator_tag)
{
	for ( ; first != last; ++result, ++first)
		*result = *first;
	return result;
}
</class>

Continue reading 《STL源码剖析》学习笔记(3)

Posted on

《STL源码剖析》学习笔记(2)

12,set、map、multiset、multimap底层均以红黑树实现。红黑树是一种平衡二叉搜索树,平衡二叉搜索树比失去平衡的二叉搜索树来说插入和删除的时间长,但是查找速度快,红黑树相对普通平衡二叉搜索树来说据说统计性能比较好。红色树的迭代器内含一个节点的指针,按照一定的规则来移动,是双向迭代器。跟list一样,每个都是个节点,所以插入不会导致其他迭代器失效,内存也是随用随申请和释放。

13,二叉搜索树具有对数平均时间的表现,但是这样的表现构造在输入数据具有足够随机性的假设上。hashtable的数据结构在插入、删除、搜索等操作上也具有常数平均时间的表现,而且这种表现是以统计为基础,不需要依赖输入数据的随机性。
Continue reading 《STL源码剖析》学习笔记(2)

Posted on

《STL源码剖析》学习笔记(1)

1,STL的价值:①,一套可复用的封装了常用算法与数据结构的代码,②,高层次的,以泛型思维为基础的、系统化的、条理分明的“软件组件分类学”。

2,STL的六大组件:容器、算法、迭代器、仿函数、适配器和空间配置器

3,STL allocator将内存申请/释放与对象的构造和析构这两个阶段操作区分开来,内存配置操作由alloc::allocate()负责,内存释放由alloc::deallocate()负责;对象构造由::construct()负责,对象析构由::destory()负责。

4,SGI STL有两级的配置器。第一级直接调用malloc(),free(),realloc()来进行内存配置。第二级配置器在大于128字节的操作时直接调用第一级配置器,小于128字节的为了减少内存碎片和额外负担直接的则从内存池中分配。(需要注意的是内存池中的内存不足时会从系统申请,但是STL返回给内存池的内存并不会从内存池返还给系统,没有看到明确的函数来显式调用使内存池返还内存。VC的STL没有使用内存池。)

5,Traits编程技法 Continue reading 《STL源码剖析》学习笔记(1)