標(biāo)準(zhǔn)庫源代碼在計(jì)算機(jī)中的分布
本機(jī)所用開發(fā)環(huán)境為visual studio 2013（包含了VC）亿柑，其中C/C++所用的工具庫包含在VC里面。
OOP（面向?qū)ο缶幊蹋￢S GP（泛型編程）
- OOP企圖將dates和methods關(guān)聯(lián)在一起
- list不能使用全局的sort()排序庇勃，因?yàn)槿謘ort()需要的是隨機(jī)訪問迭代器，例如first+（last-first）/2這樣的只有RandomAccessIterator才能如此操作槽驶，而list因?yàn)閮?nèi)存模型的原因责嚷，不是連續(xù)空間，不能有iterator+5這種操作掂铐，所以它不能提供這種迭代器罕拂。
- vector揍异、deque等容器都提供RandomAccessIterator。
template<class T,class Alloc=alloc>
class list{
...
void sort();
}
- GP卻是將datas和methods分開來爆班，這樣做的好處是：
- Containers和Algorithms團(tuán)隊(duì)可各自閉門造車衷掷，其間以Iterator溝通即可。
- Algorithms通過Iterators確定操作范圍柿菩，并通過Iterators取用Container元素戚嗅。
//Data Structures(Containers)
template<class T,class Alloc=alloc>
class vector{
...
};
//Alorithms
template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator _first,_RandomAccessIterator _last)
{
...
}
- 所有algorithms，其內(nèi)最終涉及元素本身的操作碗旅，無非就是比大小
bool strLonger(const string& s1,const string& s2) {return s1.size() < s2.size();}
cout<<"max of zoo and hello:"<<max(string("zoo"),string("hello"))<<endl; //max調(diào)用函數(shù)1
cout<<"longest of zoo and hello:"<<max(string("zoo"),string("hello"),strLonger)<<endl; //max調(diào)用函數(shù)2
template<class T> //函數(shù)1
inline const T& max(const T& a,const T& b){
return a<b ? b:a;
}
template<class T,class Compare> //函數(shù)2
inline const T& max(const T& a,const T& b,Compare comp){
return comp(a,b)?b:a;
}
分配器
- operator new()追究到底最后調(diào)用的是C函數(shù)庫中malloc()函數(shù)
- VC6+渡处、BC++、GCC2.9的allocator都只是以::operator new和::operator delete完成allocate()和deallocate()祟辟，沒有任何特殊設(shè)計(jì)医瘫。
//VC6使用allocator，分配512ints
int* p=allocator<int>().allocate(512,(int*)0);
allocator<int>().deallocate(p,512);
//BC5使用allocator旧困，分配512ints
int* p=allocator<int>().allocate(512);
allocator<int>().deallocate(p,512);
//G2.9使用allocator醇份，分配512bytes
void* p=alloc::allocate(512); //也可以alloc().allocate(512);
alloc::deallocate(p,512);
-
G2.9所附的標(biāo)準(zhǔn)庫，其allocator實(shí)現(xiàn)如下:
G2.9 allocator實(shí)現(xiàn).png -
其中alloc的實(shí)現(xiàn)如下圖（<stl_alloc.h>）：
alloc實(shí)現(xiàn).png - G4.9STL對allocator的使用:
template<typename _Tp,typename _Alloc = std::allocator< _Tp>>
class vector :protected _Vector_base<_Tp , _Alloc>
{
...
}
-
G4.9所附的標(biāo)準(zhǔn)庫吼具，其allocator實(shí)現(xiàn)如下：
G4.9 allocator實(shí)現(xiàn).png
G4.9 allocator實(shí)現(xiàn).png - 相比G2.9僚纷，G4.9對于allocator的寫法因?yàn)榇罅繎?yīng)用了類的繼承、復(fù)合拗盒，使得觀察者在理解allocator的實(shí)現(xiàn)上增加不少難度怖竭！
容器之間的實(shí)現(xiàn)關(guān)系與分類
- 本圖以縮排形式表達(dá)“基層與衍生層”的關(guān)系。這里所謂衍生陡蝇，并非繼承而是復(fù)合痊臭。
-
在C++中，slist名為forward_list,hash_set,hash_map名為unordered_set登夫，unordered_map,hash_multiset,hash_multimap名為unordered_multiset,unordered_multimap;且新添array广匙。
容器結(jié)構(gòu)再分類.png
迭代器的設(shè)計(jì)原則和Iterator Traits的作用與設(shè)計(jì)
Iterators必須有能力回答algorithms的五個問題，也就是說Iterators必須提供五種associated types恼策。
為了分離class Iterators和non-class Iterators鸦致，就產(chǎn)生了Iterator traits，并且可以通過偏特化實(shí)現(xiàn)涣楷。
- 還有其他各式各樣的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>
深度探索list
參考鏈接【深度探索STL】詳解 list
list 和vector 是兩個最常用的容器（序列式容器）分唾。二者最顯著的區(qū)別自然就是vector是連續(xù)線性空間，list則是不連續(xù)線性空間狮斗，相比于vector（動態(tài)數(shù)組）鳍寂，它的好處是每次插入和刪除一個元素，只需配置或釋放一個元素空間情龄，對于任何位置的元素插入或元素移除迄汛，list永遠(yuǎn)是常數(shù)時間捍壤。尺有所長，寸有所短鞍爱，list 尋址某一元素也沒有vector（常數(shù)時間）方便鹃觉。
- list 的迭代器
- 因?yàn)殒湵砉?jié)點(diǎn)在儲存空間中不一定是連續(xù)存在的，自然也就不能像vector一樣用普通指針作為迭代器睹逃。list迭代器必須有能力指向list的節(jié)點(diǎn)盗扇，并有能力正確的遞增。遞減沉填。取值疗隶、成員存取等操作。這是作為任何一個容器的迭代器必須具備的翼闹。對于非連續(xù)空間的遞增斑鼻，遞減等操作自然是針對該容器的屬性來的，就list而言猎荠，則是指向上一個節(jié)點(diǎn)坚弱，下一個節(jié)點(diǎn)，以及獲取指定節(jié)點(diǎn)关摇。
STL list是一個雙向鏈表荒叶，迭代器必須具備前移，后移的能力输虱，所以list提供的是bidirectional iterator （雙向一個個移動）些楣。關(guān)于迭代器的分類，參見STL迭代器宪睹。vector是隨機(jī)迭代器類型（random access iterator）戈毒，這也是符合vector 可隨機(jī)存取的能力。
- 因?yàn)殒湵砉?jié)點(diǎn)在儲存空間中不一定是連續(xù)存在的，自然也就不能像vector一樣用普通指針作為迭代器睹逃。list迭代器必須有能力指向list的節(jié)點(diǎn)盗扇，并有能力正確的遞增。遞減沉填。取值疗隶、成員存取等操作。這是作為任何一個容器的迭代器必須具備的翼闹。對于非連續(xù)空間的遞增斑鼻，遞減等操作自然是針對該容器的屬性來的，就list而言猎荠，則是指向上一個節(jié)點(diǎn)坚弱，下一個節(jié)點(diǎn)，以及獲取指定節(jié)點(diǎn)关摇。
struct _List_iterator_base {
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef bidirectional_iterator_tag iterator_category;
_List_node_base* _M_node;
//構(gòu)造函數(shù)
_List_iterator_base(_List_node_base* __x) : _M_node(__x) {}
_List_iterator_base() {}
//增加和減少横堡，就是指向上一個節(jié)點(diǎn)和下一個節(jié)點(diǎn)
void _M_incr() { _M_node = _M_node->_M_next; }
void _M_decr() { _M_node = _M_node->_M_prev; }
//運(yùn)算符重載
bool operator==(const _List_iterator_base& __x) const {
return _M_node == __x._M_node;
}
bool operator!=(const _List_iterator_base& __x) const {
return _M_node != __x._M_node;
}
};
template<class _Tp, class _Ref, class _Ptr>
struct _List_iterator : public _List_iterator_base {
typedef _List_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _List_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
typedef _List_iterator<_Tp, _Ref, _Ptr> _Self;
typedef _Tp value_type;
typedef _Ptr pointer;
typedef _Ref reference;
typedef _List_node<_Tp> _Node;
//下面是子類指針賦值給父類指針，is-a原則（反過來不行）
_List_iterator(_Node* __x) : _List_iterator_base(__x) {}
_List_iterator() {}
_List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {}
//對迭代器取值冠桃，獲取節(jié)點(diǎn)的數(shù)據(jù)
reference operator*() const { return ((_Node*)_M_node)->_M_data; }
//對迭代器的成員存取命贴，返回的是地址
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
//前綴和后綴++和--自增自減符重載
_Self& operator++() {
this->_M_incr();
return *this;//返回引用，可鏈?zhǔn)讲僮?
}
_Self operator++(int) {
_Self __tmp = *this;
this->_M_incr();
return __tmp;//返回變量食听，不可鏈?zhǔn)讲僮?
}
_Self& operator--() {
this->_M_decr();
return *this;
}
_Self operator--(int) {
_Self __tmp = *this;
this->_M_decr();
return __tmp;
}
};
深度探索vector
vector 將其元素置于一個動態(tài)數(shù)組中加以管理胸蛛，與 array 非常類似，兩者的唯一差別在于空間運(yùn)用的靈活性樱报，array 是靜態(tài)空間葬项，一旦配置了就不能更改，當(dāng)需要容納更多的元素時(此時已越界)迹蛤，需要重新手動配置更大的 array 空間民珍，然后重新置入數(shù)據(jù)襟士。而 vector 是動態(tài)空間，在同樣的情況下嚷量，隨著元素的加入陋桂，它的內(nèi)部機(jī)制會自行擴(kuò)充空間以容納新元素。vector 同 array 一樣可以很方便的通過索引值直接存取任何一個元素蝶溶，在數(shù)組的尾端追加或移除元素均非呈壤快速(當(dāng)追加元素超出原有分配空間時，vector需要重新分配空間)抖所，但在其中間或頭部插入移除元素就比較費(fèi)時梨州，需要移動安插點(diǎn)之后的所有元素以保持原來的相對位置。
深度探索array&forward_list
與list和vector的iterator類似田轧，有一種iterator traits用以分類class Iterators和non-class Iterators暴匠。
