STL與泛型編程
主要內(nèi)容：
簡(jiǎn)單介紹了 OOP 和 GP 編程冀自。詳細(xì)剖析了 STL 中的分配器揉稚、list、Iterator熬粗、vector搀玖、array、forward_list
OOP（Object-Oriented Programming 面向?qū)ο缶幊蹋?vs. GP（Generic Programming 泛型編程）
OOP
- OOP主要的思想是將datas和methods關(guān)聯(lián)在一起的思想驻呐。
- 也就是數(shù)據(jù)放在類(lèi)中灌诅，操作數(shù)據(jù)的方法也是放在類(lèi)中芳来。（class 貓身上有毛，那么他必須有一個(gè)方法來(lái)管理他的毛猜拾，也就是舔毛()這個(gè)函數(shù)即舌。只需要貓咪.舔毛();來(lái)調(diào)用這個(gè)函數(shù)，就可以管理和操作對(duì)應(yīng)的數(shù)據(jù)）
GP
- GP的主要思想是將datas和methods分開(kāi)挎袜。在STL中大量使用到了GP的思想顽聂，來(lái)實(shí)現(xiàn)了數(shù)據(jù)和算法的分離，那么盯仪，算法如何才能操作數(shù)據(jù)呢芜飘，這中間的橋梁就是Iterators（迭代器）了，通過(guò)Iterator磨总，算法可以從容器中獲取到需要的數(shù)據(jù)，同樣也就可以起到操作數(shù)據(jù)的目的笼沥。
- 為何STL會(huì)采用GP的思想呢蚪燕？其實(shí)使用了GP思想，類(lèi)和類(lèi)之間的關(guān)系不會(huì)那么緊密奔浅，也就不會(huì)產(chǎn)生很強(qiáng)的耦合性馆纳，便于不同的成員，協(xié)同開(kāi)發(fā)不同的模塊汹桦，有助于加快項(xiàng)目開(kāi)發(fā)得效率鲁驶，大家只需要依據(jù)“中間商”Iterator來(lái)編寫(xiě)各自代碼就行了。
- 對(duì)于OOP來(lái)說(shuō)最好的一點(diǎn)就是舞骆，方法和數(shù)據(jù)在同一個(gè)類(lèi)中钥弯，那么方法是專(zhuān)門(mén)為類(lèi)所設(shè)計(jì)的。比較方便能夠管理其中的數(shù)據(jù)督禽。GP由于數(shù)據(jù)和方法分離脆霎，操作的時(shí)候，難免有些數(shù)據(jù)狈惫，不能被這個(gè)方法所操作睛蛛。比如，list 不能使用::sort() 進(jìn)行排序胧谈，那到底是為什么呢忆肾？
- ::sort() 的源碼，發(fā)現(xiàn)問(wèn)題所在：
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的下標(biāo)運(yùn)算 //list不是一個(gè)連續(xù)空間菱肖，前后節(jié)點(diǎn)之間靠指針相連客冈，所以list 的Iterator不具備下表直接運(yùn)算的能力，所以蔑滓，list不能直接使用::sort()來(lái)進(jìn)行排序 //也正是由于這個(gè)原因::sort() 只能為RandomAccessIterator來(lái)進(jìn)行排序 ...... }
分配器
分配器是容器管理內(nèi)存的工具郊酒，對(duì)于容器的效率起著比較重要的作用
- 在正式開(kāi)始說(shuō)allocator之前遇绞，先說(shuō)幾句operator new()和 malloc()以及operator delete() 和free()
- 在創(chuàng)建對(duì)象時(shí)，會(huì)調(diào)用operator new()燎窘，而operator new()中分配內(nèi)存實(shí)際也還是調(diào)用有C語(yǔ)言的Runtime Library所提供的malloc()摹闽，再由系統(tǒng)來(lái)分配所需要的內(nèi)存；銷(xiāo)毀對(duì)象時(shí)褐健，則會(huì)使用operator delete()付鹿，而他實(shí)際會(huì)調(diào)用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); }
容器結(jié)構(gòu)分類(lèi)
序列式容器（Sequence Container）的衍生關(guān)系
- array （C++2.0）連續(xù)空間
- vector 連續(xù)空間
- heap 以算法形式呈現(xiàn)（xxx_heap()）
- priority_queue
- list 雙向鏈表
- slist C++2.0中為forward_list,單向鏈表
- deque 分段連續(xù)空間
- stack Container Adapter
- queue Container Adapter
關(guān)聯(lián)式容器（Associative Containers）的衍生關(guān)系(復(fù)合)
- rb_tree 紅黑樹(shù)蚜迅，非公開(kāi)
- set
- map
- multiset
- multimap
- hashtable非公開(kāi)
- hash_set非標(biāo)準(zhǔn)舵匾，C++2.0為unordered_set
- hash_map非標(biāo)準(zhǔn)，C++2.0為unordered_map
- hash_multiset非標(biāo)準(zhǔn)谁不，C++2.0為unordered_multiset
- hash_mulitmap非標(biāo)準(zhǔn)坐梯，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;
}
- 內(nèi)存關(guān)系示意圖
- list為一個(gè)循環(huán)鏈表（如圖），但是對(duì)于迭代器來(lái)說(shuō)刹帕，end()獲取到的并非容器中的最后一個(gè)元素吵血，而應(yīng)該是，最后一個(gè)元素之后的空元素偷溺，所以在list實(shí)現(xiàn)的時(shí)蹋辅，可以看到，end()指向了一個(gè)灰色的區(qū)域挫掏，這個(gè)區(qū)域?qū)嶋H就是end()指向的非容器內(nèi)元素的區(qū)域
- 由于list非連續(xù)空間侦另，所以Iterator在++時(shí)，如果不作調(diào)整尉共，不會(huì)默認(rèn)的移動(dòng)到下一個(gè)不連續(xù)空間褒傅，所以，為了讓Iterator能夠和指針的用法相似爸邢，Iterator一定是一個(gè)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){//后++樊卓，參數(shù)實(shí)際無(wú)意義 self temp = *this; ++*this; return tmp; } };
Iterator 的設(shè)計(jì)原則
算法要求這幾項(xiàng)的類(lèi)型必須指定出來(lái)
- 算法（algorithms）在操作容器（Container）中的數(shù)據(jù)需要通過(guò)Iterator知道的信息如下：
- iterator_category：Iterator的性質(zhì)，例如是否可以雙向查詢(xún)
- ifference_type：兩個(gè)Iterator之間的距離的type（int杠河、unsigned int）碌尔，決定了容器可以容納多少元素
- value_type：元素本身的type
- reference：引用
- pointer：指針
- 在Iterator的設(shè)計(jì)時(shí)，必須有這五種associated types
- traits的引入
- 如果Iterator不是一個(gè)class的情況券敌，如果這樣的情況唾戚，無(wú)法從一個(gè)指針中獲取以上的幾種類(lèi)型，那么這時(shí)候待诅，需要一個(gè)“中介”來(lái)去協(xié)調(diào)這件事叹坦，這時(shí)候就出現(xiàn)了一個(gè)traits的機(jī)制
- 這個(gè)traits可以區(qū)分到底是class設(shè)計(jì)的Iterator，也能夠區(qū)分是指針傳入的Iterator
// traits的設(shè)計(jì) 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 }; //針對(duì)指針的兩種偏特化 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; } - 根據(jù)偏特化卑雁，如果傳入的為指針就會(huì)自動(dòng)進(jìn)入偏特化的部分募书，那么就根據(jù)偏特化來(lái)獲取響應(yīng)信息
- 各式各樣的traits以及對(duì)應(yīng)的頭文件
- 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根據(jù)三個(gè)指針就可以控制全部?jī)?nèi)容 iterator start;绪囱、 iterator finish;、iterator end_of_storage;
其中finish指向最后一個(gè)元素之后的位置莹捡。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); } } - 二倍成長(zhǎng)
- 對(duì)于內(nèi)存來(lái)說(shuō)沒(méi)辦法實(shí)現(xiàn)原地?cái)U(kuò)充鬼吵，因?yàn)榍昂蠖伎赡艽嬖谥渌绦虻臄?shù)據(jù)，如果擴(kuò)充篮赢，意味著會(huì)要影響到其他程序齿椅，并且操作系統(tǒng)也不允許這樣干。那么對(duì)于vector來(lái)說(shuō)启泣，hi如何來(lái)實(shí)現(xiàn)擴(kuò)充的呢涣脚？那么再擴(kuò)充的時(shí)候，需要在內(nèi)存的其他區(qū)域找到空間寥茫，在新找到的空間進(jìn)行擴(kuò)充完成后遣蚀，再將數(shù)據(jù)復(fù)制到新開(kāi)辟的空間中。而且每次增長(zhǎng)的空間都是以?xún)杀蹲鳛榛鶞?zhǔn)纱耻。
- 存入元素和兩杯增長(zhǎng)的代碼
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){//空間夠用
//在備用空間起始處建一個(gè)元素妙同，并以vector最后一個(gè)元素為其初值
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，分配原大小的兩倍胰耗；前半段用來(lái)放置原數(shù)據(jù)限次，后半段用來(lái)放置新數(shù)據(jù)
iterator new_finish = new start;
try{
//將原vector的內(nèi)容拷貝到新的vector
new_finish = uninitialized_copy(start, position, new_start);
construnct(new_finish, x);//為新元素設(shè)置初值x
++new_finish;
//拷貝安插點(diǎn)后的原內(nèi)容
new_finish = uninitialized_copy(postion, finish, new_finish);
}
catch(...){
destory(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throwl
}
//析構(gòu)并釋放元vector
destory(begin(), end());
//調(diào)整迭代器，指向新的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（雙向鏈表）
