STL与泛型编程
主要内容：
简单介绍了 OOP 和 GP 编程。详细剖析了 STL 中的分配器、list、Iterator、vector、array、forward_list
OOP（Object-Oriented Programming 面向对象编程） vs. GP（Generic Programming 泛型编程）
OOP
- OOP主要的思想是将datas和methods关联在一起的思想。
- 也就是数据放在类中，操作数据的方法也是放在类中。（class 猫身上有毛，那么他必须有一个方法来管理他的毛，也就是舔毛()这个函数。只需要猫咪.舔毛();来调用这个函数，就可以管理和操作对应的数据）
GP
- GP的主要思想是将datas和methods分开。在STL中大量使用到了GP的思想，来实现了数据和算法的分离，那么，算法如何才能操作数据呢，这中间的桥梁就是Iterators（迭代器）了，通过Iterator，算法可以从容器中获取到需要的数据，同样也就可以起到操作数据的目的。
- 为何STL会采用GP的思想呢？其实使用了GP思想，类和类之间的关系不会那么紧密，也就不会产生很强的耦合性，便于不同的成员，协同开发不同的模块，有助于加快项目开发得效率，大家只需要依据“中间商”Iterator来编写各自代码就行了。
- 对于OOP来说最好的一点就是，方法和数据在同一个类中，那么方法是专门为类所设计的。比较方便能够管理其中的数据。GP由于数据和方法分离，操作的时候，难免有些数据，不能被这个方法所操作。比如，list 不能使用::sort() 进行排序，那到底是为什么呢？
- ::sort() 的源码，发现问题所在：
template <class RandomAccessIterator> inline void sort(RandomAccessIterator first, RandomAccessIterator last) { if(first != last) { _introsort_loop(first, last, value_type(first), __lg(last-first)*2); __final_insertion_sort(first, last); } } ..... template <class RandomAccessIterator, class T, class Size> void __introsort_loop(RandomAccessterator first, RandomAccessIterator last, T*, Size depth_limit) { ...... RandomAccessIterator cut = __unguarded_partition(first, last, T(__median(*first, *(first + (last - first)/2), *(last - 1)))); //由于此处牵扯到了Iterator的下标运算 //list不是一个连续空间，前后节点之间靠指针相连，所以list 的Iterator不具备下表直接运算的能力，所以，list不能直接使用::sort()来进行排序 //也正是由于这个原因::sort() 只能为RandomAccessIterator来进行排序 ...... }
分配器
分配器是容器管理内存的工具，对于容器的效率起着比较重要的作用
- 在正式开始说allocator之前，先说几句operator new()和 malloc()以及operator delete() 和free()
- 在创建对象时，会调用operator new()，而operator new()中分配内存实际也还是调用有C语言的Runtime Library所提供的malloc()，再由系统来分配所需要的内存；销毁对象时，则会使用operator delete()，而他实际会调用free()。
- vc中的operator new()
void *operator new (size_t size, const std::nothrow_t&) { void *p; while((p = malloc(size)) == 0) { _TRY_BEGIN if(_callnewh(size) == 0) break; _CATCH(std::bad_alloc) return(0); _CATCH_END } return (p); }
容器结构分类
序列式容器（Sequence Container）的衍生关系
- array （C++2.0）连续空间
- vector 连续空间
- heap 以算法形式呈现（xxx_heap()）
- priority_queue
- list 双向链表
- slist C++2.0中为forward_list,单向链表
- deque 分段连续空间
- stack Container Adapter
- queue Container Adapter
关联式容器（Associative Containers）的衍生关系(复合)
- rb_tree 红黑树，非公开
- set
- map
- multiset
- multimap
- hashtable非公开
- hash_set非标准，C++2.0为unordered_set
- hash_map非标准，C++2.0为unordered_map
- hash_multiset非标准，C++2.0为unordered_multiset
- hash_mulitmap非标准，C++2.0为unordered_multimap
容器 list
template <class T>
struct __list_node{
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
};
template<class T, class Alloc = alloc>
class list{
protected:
typedef __list_node<T> list_node;
public:
typedef list_node* link_type;
typedef __list_iterator<T, T&, T*> iterator;
protected:
link_type node;
};
template<class T, class Ref, class Ptr>
struct __list_iterator{
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
}
- 内存关系示意图
- list为一个循环链表（如图），但是对于迭代器来说，end()获取到的并非容器中的最后一个元素，而应该是，最后一个元素之后的空元素，所以在list实现的时，可以看到，end()指向了一个灰色的区域，这个区域实际就是end()指向的非容器内元素的区域
- 由于list非连续空间，所以Iterator在++时，如果不作调整，不会默认的移动到下一个不连续空间，所以，为了让Iterator能够和指针的用法相似，Iterator一定是一个class
template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator(T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type; typedef ptrdiff_t difference_type; link_type nod; reference operator*() const{ return (*node).data; } pointer operator->() const { return &(operator*()); } self& operator++(){//前++ node = (link_type)((*node).next); return *this; } self operator++(int){//后++，参数实际无意义 self temp = *this; ++*this; return tmp; } };
Iterator 的设计原则
算法要求这几项的类型必须指定出来
- 算法（algorithms）在操作容器（Container）中的数据需要通过Iterator知道的信息如下：
- iterator_category：Iterator的性质，例如是否可以双向查询
- ifference_type：两个Iterator之间的距离的type（int、unsigned int），决定了容器可以容纳多少元素
- value_type：元素本身的type
- reference：引用
- pointer：指针
- 在Iterator的设计时，必须有这五种associated types
- traits的引入
- 如果Iterator不是一个class的情况，如果这样的情况，无法从一个指针中获取以上的几种类型，那么这时候，需要一个“中介”来去协调这件事，这时候就出现了一个traits的机制
- 这个traits可以区分到底是class设计的Iterator，也能够区分是指针传入的Iterator
// traits的设计 template<class I> struct iterator_traits{ typedef typename I::value_type value_type; typedef typename I::iterator_category typedef typename I::difference_type typedef typename I::pointer typedef typename I::reference }; //针对指针的两种偏特化 template<class T> struct iterator_traits<T*>{ typedef T value_type; typedef random_access_iterator_tag iterator_category; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; }; template <class T> struct iterator_traits<const T*>{ typedef T value_type; typedef random_access_iterator_tag iterator_category; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; } // traits的使用 template<typename I, ....> void algorithm(......){ typename iterator_traits<I>::value_type v1; } - 根据偏特化，如果传入的为指针就会自动进入偏特化的部分，那么就根据偏特化来获取响应信息
- 各式各样的traits以及对应的头文件
- type traits : .../c++/type_traits
- iterator traits: .../c++/bits/stl_iterator.h
- char traits: .../c++/bits/char_traits.h
- allocator traits:.../c++/bits/alloc_traits.h
- pointer traits: .../c++/bits/ptr_traits.h
- array traits:.../c++/bits/array.h
容器Vector
- vector根据三个指针就可以控制全部内容 iterator start;、 iterator finish;、iterator end_of_storage;
其中finish指向最后一个元素之后的位置。template <class T, class Alloc = alloc> class vector { public: typedef T value_type; typedef value_type* iterator; typedef value_tyle& reference; typedef size_t size_type; protected: iterator start; iterator finish; iterator end_of_storage; public: iterator begin(){return start;} iterator end() {return finish;} size_type size() const{ return size_type(end() - begin()); } size_type capacity() const { return size_type(end_of_storage - begin()); } bool empty() const { return begin() == end(); } reference operator[](size_type n){return *(begin() + n); } reference front() {return *begin();} reference back(){ return *(end() - 1); } } - 二倍成长
- 对于内存来说没办法实现原地扩充，因为前后都可能存在着其他程序的数据，如果扩充，意味着会要影响到其他程序，并且操作系统也不允许这样干。那么对于vector来说，hi如何来实现扩充的呢？那么再扩充的时候，需要在内存的其他区域找到空间，在新找到的空间进行扩充完成后，再将数据复制到新开辟的空间中。而且每次增长的空间都是以两倍作为基准。
- 存入元素和两杯增长的代码
void push_back()(const T& x)
{
if(finish != end_of_storage){//尚有备用空间
construct(finish, x);
++finish;
}
else{
insert_aux(end(), x);
}
}
template<class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x){
if(finish != end_of_storage){//空间够用
//在备用空间起始处建一个元素，并以vector最后一个元素为其初值
construct(finish, *(finish - 1);
++finish;
T x_copy = x;
copy_backward(postion, finish - 2, finish - 1);
*postion = x_copy;
}
else{ //空间不够用
const size_type old_size = size();
const size_type len = old_size != 0? 2*old_size: 1;
iterator new_start = data_allocator::allocate(len);
//以上分配原则：剐原大小为0，分配1；不为0，分配原大小的两倍；前半段用来放置原数据，后半段用来放置新数据
iterator new_finish = new start;
try{
//将原vector的内容拷贝到新的vector
new_finish = uninitialized_copy(start, position, new_start);
construnct(new_finish, x);//为新元素设置初值x
++new_finish;
//拷贝安插点后的原内容
new_finish = uninitialized_copy(postion, finish, new_finish);
}
catch(...){
destory(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throwl
}
//析构并释放元vector
destory(begin(), end());
//调整迭代器，指向新的vector
deallocate();
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
容器array
template<typename _Tp, std::size_t _Nm>
struct array{
typedef _Tp;
typedef _Tp*;
typedef value_type*;
value_type _M_instance[_Nm? _Nm: 1];
iterator begin(){
return iterator(&_M_instance[0]);
}
iterator end(){
return iterator(&_M_instance[_Nm]);
}
}
forward_list
- 单向链表，具体可以参考list（双向链表）
