《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编程技法

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
 
 
template <class Iterator>
struct iterator_traits {
	typedef typename Iterator::iterator_category iterator_category;
	typedef typename Iterator::value_type        value_type;
	typedef typename Iterator::difference_type   difference_type;
	typedef typename Iterator::pointer           pointer;
	typedef typename Iterator::reference         reference;
};
 
template <class T>
struct iterator_traits<T*> {
	typedef random_access_iterator_tag iterator_category;
	typedef T                          value_type;
	typedef ptrdiff_t                  difference_type;
	typedef T*                         pointer;
	typedef T&                         reference;
};
 
template <class T>
struct iterator_traits<const T*> {
	typedef random_access_iterator_tag iterator_category;
	typedef T                          value_type;
	typedef ptrdiff_t                  difference_type;
	typedef const T*                   pointer;
	typedef const T&                   reference;
};

一些算法会根据迭代器的类型进行优化,比如

template <class InputIterator, class Distance>
inline void __distance(InputIterator first, InputIterator last, Distance& n, 
	input_iterator_tag) {
		while (first != last) { ++first; ++n; }
}
 
template <class RandomAccessIterator, class Distance>
inline void __distance(RandomAccessIterator first, RandomAccessIterator last, 
	Distance& n, random_access_iterator_tag) {
		n += last - first;
}
 
template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n) {
	__distance(first, last, n, iterator_category(first));
}

6,SGI中还有__type_traits负责萃取型别的特性

template <class type>
struct __type_traits { 
   typedef __true_type     this_dummy_member_must_be_first;
   typedef __false_type    has_trivial_default_constructor;
   typedef __false_type    has_trivial_copy_constructor;
   typedef __false_type    has_trivial_assignment_operator;
   typedef __false_type    has_trivial_destructor;
   typedef __false_type    is_POD_type;
};
 
__STL_TEMPLATE_NULL struct __type_traits<char> {
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
 
/////////////////////////////////////
 
template <class ForwardIterator, class T>
inline void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, 
                         const T& x, __true_type)
{
  fill(first, last, x);
}
 
template <class ForwardIterator, class T>
void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, 
                         const T& x, __false_type)
{
  ForwardIterator cur = first;
  __STL_TRY {
    for ( ; cur != last; ++cur)
      construct(&*cur, x);
  }
  __STL_UNWIND(destroy(first, cur));
}
 
template <class ForwardIterator, class T, class T1>
inline void __uninitialized_fill(ForwardIterator first, ForwardIterator last, 
                                 const T& x, T1*) {
  typedef typename __type_traits<T1>::is_POD_type is_POD;
  __uninitialized_fill_aux(first, last, x, is_POD());
 
}

如果使用SGI STL的话,可以在程序中使用__type_traits,自行设计一个__type_traits的特化版本,以便于编译器优化

__STL_TEMPLATE_NULL struct __type_traits<Shape> {
   typedef __true_type    has_trivial_default_constructor;
   typedef __false_type    has_trivial_copy_constructor;
   typedef __false_type    has_trivial_assignment_operator;
   typedef __false_type    has_trivial_destructor;
   typedef __false_type    is_POD_type;
};

7,vector就是一个数组,迭代器就是一个指针,插入一个元素可能会导致所有迭代器失效(如果重新申请了内存的话)。vector在需要扩充内存时会申请两倍大的内存,但是删除元素时并不释放内存,可以利用swap的技巧来释放内存。

8,list是一个双向环状列表,迭代器是一个类的实例,插入并不会导致其他的迭代器失效。list每个节点的内存随着插入而申请,删除而释放。

9,deque采用所谓的map作为主控,这里的map是一小块连续控件,其中每个元素都指向另一块较大的连续线性空间,称之为缓冲区,这个缓冲区才是deque的储存控件主体。STL STL允许指定缓冲区的大小。 deque的插入元素可能导致前面的迭代器失效,也可能导致后面的迭代器失效,总之认为全部失效就不会出错了。deque在需要新缓冲区的时候申请内存,在一个缓冲区的内容都被删光光时释放内存。

10,遍历删除时要考虑,序列容器删除时总是返回下一个元素,关联容器删除时下一个元素的迭代器不会失效,所以应在删除前进行后自增。

11,stack和queue均为容器适配器,默认底层以deque实现,也可使用list实现,均没有迭代器。

2 Replies to “《STL源码剖析》学习笔记(1)”

  1. 破麦是一头扎进 STL 了哇~ 期待更多文章,弄个全集,以后我需要重学 STL 的时候当教材 :)

    • 国庆期间读完了,现在做这个笔记,呵呵。别全信啊,里面参杂不少自己的理解,误导了我可不负责。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

*