《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实现，均没有迭代器。

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

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

发表回复取消回复

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

发表回复 取消回复

发表回复取消回复