體系結(jié)構(gòu)與內(nèi)核分析
本機(jī)使用了兩個(gè)編譯器
Visual C++ 6.0標(biāo)準(zhǔn)庫(kù)位于：...\Program Files (x86)\Microsoft Visual Studio 14.0\VC\include
devcpp標(biāo)準(zhǔn)庫(kù)位于：...\4.8.1\inlcude
面向?qū)ο缶幊蹋∣OP)VS泛型編程(GP)
OOP:Object-Oriented programmingGP:Generic programming
OOP企圖將datas和methods關(guān)聯(lián)在一起
list不能使用全局的sort()排序陨献，因?yàn)槿謘ort()需要的是隨機(jī)訪問(wèn)迭代器，而list因?yàn)閮?nèi)存模型的原因，不是連續(xù)空間，在內(nèi)存中它是由指針一個(gè)一個(gè)串起來(lái),不能有iterator+5這種操作，所以它不能提供這種迭代器名党。
GP卻是將datas和methods分開(kāi)來(lái),兩者之間通過(guò)迭代器聯(lián)系在一起嘹朗。
分開(kāi)的優(yōu)點(diǎn)：
（1）Containers和Algorithms團(tuán)隊(duì)可各自獨(dú)立開(kāi)發(fā)，其間以Iterator溝通即可餐禁；做好接口就行
（2）Algorithms通過(guò)Iterators確定操作范圍，并通過(guò)Iterators取用Container元素突照。
vector帮非、deque等容器都提供RandomAccessIterator
template
class list{
...
void sort();
}
所有的algorithms，最終設(shè)計(jì)元素本身的操作讹蘑，無(wú)非就是比大小末盔。比如說(shuō)重新定義max函數(shù)，根據(jù)字符長(zhǎng)度來(lái)比大小座慰，我們就必須重寫(xiě)一個(gè)比較函數(shù)陨舱。
所有algorithms，其內(nèi)最終涉及元素本身的操作版仔，無(wú)非就是比大小
bool strLonger(const string& s1,const string& s2) {return s1.size() < s2.size();}
cout<<"max of zoo and hello:"<
cout<<"longest of zoo and hello:"<
template
inline const T& max(const T& a,const T& b){
return a
}template
inline const T& max(const T& a,const T& b,Compare comp){
return comp(a,b)?b:a;
}
操作符重載 Operator Overloading
operator是C++的關(guān)鍵字游盲，它和運(yùn)算符一起使用，表示一個(gè)運(yùn)算符函數(shù)蛮粮，理解時(shí)應(yīng)將operator=整體上視為一個(gè)函數(shù)名益缎。
操作符重載實(shí)現(xiàn)為類成員函數(shù)
重載的操作符在類體中被聲明，聲明方式如同普通成員函數(shù)一樣然想，只不過(guò)他的名字包含關(guān)鍵字operator莺奔，以及緊跟其后的一個(gè)c++預(yù)定義的操作符。
函數(shù)模板
（節(jié)選于前面課程筆記）
template
inline
constT&min(constT&a, constT&b)
{? return b
函數(shù)模板是一種不說(shuō)明某些參數(shù)的數(shù)據(jù)類型的函數(shù)变泄。函數(shù)模板被調(diào)用時(shí)令哟，編譯器根據(jù)實(shí)際參數(shù)的類型確定模板參數(shù)T的類型，并自動(dòng)生成一個(gè)對(duì)應(yīng)的函數(shù)妨蛹。定義函數(shù)模板時(shí)也可以使用多個(gè)類型參數(shù)屏富，這時(shí)，每個(gè)類型參數(shù)前面都要加上關(guān)鍵字class 或typename滑燃，其間用逗號(hào)分隔役听。
成員模板（member template）
任意類（模板或非模板）可以擁有本身為類模板或函數(shù)模板的成員，這種成員稱為成員函數(shù)模板。
template
struct pair{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair()：first(T1()),second(T2()) {}
pair(const T1 &a,const T2 &b):first(a),second(b) {}
template ? ? //成員模板
pair(const pait &p)//T1和T2類型確定了以后典予，U1和U2也能進(jìn)行確定
:first(p.first),second(p.second) {}
}
這里一共有三個(gè)模板：類模板甜滨，函數(shù)模板，成員模板瘤袖。關(guān)于區(qū)別
參考：http://blog.csdn.net/zhangyulin54321/article/details/7897246
模板特化 （specialization）
泛化[全泛化]（模板等）與特化是對(duì)立的，特化艾扮，就是將泛型的東東搞得具體化一些泡嘴，從字面上來(lái)解釋酌予，就是為已有的模板參數(shù)進(jìn)行一些使其特殊化的指定抛虫，使得以前不受任何約束的模板參數(shù)或受到特定的修飾或完全被指定了下來(lái)简僧。
template
struct hash{ };? ? // 泛化
template<>
struct hash{
size_t operator() (char x) const {return x;}//? 重載()
};? ? ? ? ? ? ? ? ? ? ? ? //特化
特化與偏特化資料：http://www.jb51.net/article/56004.htm
模板偏特化（partial specialization）
偏特化就是模板中的模板參數(shù)沒(méi)有被全部確定棉姐，需要編譯器在編譯時(shí)進(jìn)行確定谅海。
個(gè)數(shù)上的偏特化蹦浦，范圍上的偏特化
個(gè)數(shù)上的偏特化
template
class vector
{...};
template ? ? ? ? //Alloc為分配器
class vector
{...};
范圍上的偏特化
template ? //泛化 任何類型均可
class C{...};
template ? //特化 指定指針
class C
{...};
C obj1;
C obj2;
模板模板參數(shù)（template template parameter）
將一個(gè)模板作為另一個(gè)模板的參數(shù)盲镶。
templateclass container>
class XCls
{
private:
containerc;
public:
......
};
template
using Lst=list>;
XCls mylst2;
分配器
分配器（Allocator）是容器管理內(nèi)存的工具，在容器申請(qǐng)內(nèi)存空間上起作用枫吧。
分配器在底層實(shí)現(xiàn)上通過(guò)operator new()和operator delete()來(lái)完成內(nèi)存分配和釋放九杂，而operator new()和operator delete()實(shí)際上是通過(guò)調(diào)用malloc()和free()函數(shù)來(lái)實(shí)現(xiàn)操作。
源代碼可以看出甥捺，無(wú)論是VC镰禾、BC還是GNU的版本中分配器實(shí)際上是通過(guò)operator new和operator delete來(lái)調(diào)用malloc和free來(lái)管理內(nèi)存（allocate()和deallocate(),沒(méi)有什么特殊設(shè)計(jì)）吴侦。
但是在GNU2.9中备韧，容器實(shí)際使用的并非是allocator绸贡，而是alloc。
//VC6使用allocator虑绵，分配512ints
int* p=allocator().allocate(512,(int*)0);
allocator().deallocate(p,512);
//BC5使用allocator声搁，分配512ints
int* p=allocator().allocate(512);
allocator().deallocate(p,512);
//GNU2.9使用allocator捕发，分配512bytes
void* p=alloc::allocate(512);? //也可以alloc().allocate(512);
alloc::deallocate(p,512);
alooc的最終實(shí)現(xiàn)內(nèi)存管理也是通過(guò)malloc和free扎酷，但是可以避免其他額外開(kāi)銷法挨，比如cookie（記錄整塊的大蟹材伞）
配器查看鏈條有沒(méi)有掛內(nèi)存塊荐糜，如果沒(méi)有葛超，向操作系統(tǒng)要內(nèi)存绣张，得到的內(nèi)存塊除了頭尾有cookie胖替，中間的每一小塊內(nèi)存都不帶cookie独令；
實(shí)現(xiàn)過(guò)程示意圖如下圖所示：
容器的結(jié)構(gòu)與分類
（部分節(jié)選自前面課程筆記）
序列式容器（排列有一定秩序）燃箭，關(guān)聯(lián)式容器（key適合做快速查找）招狸、UNordered containers（不定序容器，前身是關(guān)聯(lián)式容器 ）
序列式容器：數(shù)組array（連續(xù)空間厕诡，固定內(nèi)存灵嫌，不能再擴(kuò)充）猖凛、Vector（向量绪穆，前面固定霞幅，后面還可以擴(kuò)充）途乃、Deque（雙向隊(duì)列扔傅，兩端都可擴(kuò)充）、鏈表List（不連續(xù)杠纵，用指針相連比藻，雙向環(huán)狀鏈表）Forward-List（單向鏈表）
關(guān)聯(lián)式容器：set/multiset（set中key不可重復(fù)银亲，multiset可以|后面map相同） （key就是vault）二分樹(shù)（高度平衡）map/multimap（有key和vault）在STL中關(guān)聯(lián)容器使用紅黑樹(shù)來(lái)實(shí)現(xiàn)，因?yàn)椴皇琼樞蚪Y(jié)構(gòu)纽匙，因而不能使用上面提到的push和pop函數(shù)务蝠，使用insert和erase函數(shù)來(lái)實(shí)現(xiàn)元素的插入刪除操作。關(guān)聯(lián)容器支持通過(guò)鍵來(lái)高效地查找和讀取元素烛缔，兩個(gè)基本的關(guān)聯(lián)容器類型是map和set馏段。map的元素以鍵-值（key-value）對(duì)的形式組織：鍵用于元素在map中的索引，而值則表示所存儲(chǔ)和讀取的數(shù)據(jù)践瓷。set僅包含一個(gè)鍵院喜，并有效地支持關(guān)于某個(gè)鍵是否存在的查詢。map可理解為字典晕翠，set可理解為一類元素的集合够坐。關(guān)聯(lián)容器和順序容器的本質(zhì)差別在于：關(guān)聯(lián)容器通過(guò)鍵（key）存儲(chǔ)和讀取元素，而順序容器則通過(guò)元素在容器中的位置順序存儲(chǔ)和訪問(wèn)元素崖面。set 和 map 類型的對(duì)象所包含的元素都具有不同的鍵巫员，不允許為同一個(gè)鍵添加第二個(gè)元素感猛。如果一個(gè)鍵必須對(duì)應(yīng)多個(gè)實(shí)例，則需使用 multimap 或 multi set，這兩種類型允許多個(gè)元素?fù)碛邢嗤逆I。
不定序容器：? hashtable、separate chaining、UNordered set/multiset、UNordered map/multimap
每個(gè)單元獨(dú)立（每段測(cè)試獨(dú)立放一個(gè)namespace）
測(cè)試程序變量聲明不放在最前面，用之前聲明
設(shè)S表示一種容器類型（如：vector）弄抬，s1懊亡、s2都是S類型的實(shí)例鸯两，容器都具有如下基本功能：
S s1? 容器的默認(rèn)構(gòu)造函數(shù)，用于構(gòu)造一個(gè)沒(méi)有任何元素的空容器宅此。
s1 op s2? 對(duì)兩容器之間的元素按字典序進(jìn)行比較青瀑，op表示==、!=、<、<=幕垦、>盏道、>=任何一個(gè)弦撩。
s1.begin()? 返回指向s1第一個(gè)元素的迭代器。
s1.end()? 返回指向s1最后一個(gè)元素的下一個(gè)位置的迭代器禽翼。
s1.empty()? 表示s1容器是否為空屠橄，返回一個(gè)布爾值。
s1.size()? 返回s1容器中元素的個(gè)數(shù)闰挡。
s1.swap(s2)? 將s1容器和s2容器的內(nèi)容交換长酗。
下圖以縮排形式表達(dá)“基層與衍生層”的關(guān)系。這里所謂衍生生均，并非繼承而是復(fù)合出牧。
在C++11中侍匙，slist名為forward_list,hash_set,hash_map名為unordered_set，unordered_map,hash_multiset,hash_multimap名為unordered_multiset,unordered_multimap;且新添array组底。
容器LIST
list 和vector是兩個(gè)最常用的容器（序列式容器）丈积。二者最顯著的區(qū)別自然就是vector是連續(xù)線性空間，list則是不連續(xù)線性空間债鸡，相比于vector（動(dòng)態(tài)數(shù)組）江滨，它的好處是每次插入和刪除一個(gè)元素，只需配置或釋放一個(gè)元素空間厌均，對(duì)于任何位置的元素插入或元素移除唬滑，list永遠(yuǎn)是常數(shù)時(shí)間。
GNU2.9和4.9刻意在環(huán)狀list尾端加一空白節(jié)點(diǎn)node棺弊，用以符合ST“前閉后開(kāi)”區(qū)間晶密。
GNU4.9相較于GNU2.9：
模板參數(shù)只有一個(gè)；
node結(jié)構(gòu)有其parent模她；
node的成員的type較精確稻艰；
list 的迭代器
因?yàn)殒湵砉?jié)點(diǎn)在儲(chǔ)存空間中不一定是連續(xù)存在的，自然也就不能像vector一樣用普通指針作為迭代器侈净。list迭代器必須有能力指向list的節(jié)點(diǎn)尊勿，并有能力正確的遞增。遞減畜侦。取值元扔、成員存取等操作。這是作為任何一個(gè)容器的迭代器必須具備的旋膳。對(duì)于非連續(xù)空間的遞增澎语，遞減等操作自然是針對(duì)該容器的屬性來(lái)的，就list而言验懊，則是指向上一個(gè)節(jié)點(diǎn)擅羞，下一個(gè)節(jié)點(diǎn)，以及獲取指定節(jié)點(diǎn)义图。
STL list是一個(gè)雙向鏈表祟滴，迭代器必須具備前移，后移的能力歌溉，所以list提供的是bidirectional iterator （雙向一個(gè)個(gè)移動(dòng)）。
self operator++(int){self tem=*this ;++*this; return tmp;}(i++)
//1.記錄原值2.進(jìn)行操作調(diào)用了前++3.返回原值
self& operator++(){node =(link_type)((*node).next);return *this;} (++i)
Iterators的設(shè)計(jì)原則
Iterators必須有能力回答算法的五個(gè)問(wèn)題，也就是說(shuō)Iterators必須提供五種associated types痛垛。(category,value,pointer,reference,difference;reference和pointer用得很少)
為了分離class Iterators和non-class Iterators草慧，就產(chǎn)生了Iterator traits，并且可以通過(guò)偏特化實(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>
容器vector深度探索
參考資料：http://blog.csdn.net/wenqian1991/article/details/19486317
vector是C++STL中一種線性容器漫谷，其分配元素在內(nèi)存中是連續(xù)存儲(chǔ)的，本質(zhì)是一個(gè)可變數(shù)組蹂析，當(dāng)申請(qǐng)的空間在需要的時(shí)候默認(rèn)以倍增的形式擴(kuò)充舔示。
vector將其元素置于一個(gè)動(dòng)態(tài)數(shù)組中加以管理，與 array 非常類似电抚，兩者的唯一差別在于空間運(yùn)用的靈活性惕稻，array 是靜態(tài)空間，一旦配置了就不能更改蝙叛，當(dāng)需要容納更多的元素時(shí)(此時(shí)已越界)俺祠，需要重新手動(dòng)配置更大的 array 空間，然后重新置入數(shù)據(jù)借帘。而 vector 是動(dòng)態(tài)空間蜘渣，在同樣的情況下，隨著元素的加入肺然，它的內(nèi)部機(jī)制會(huì)自行擴(kuò)充空間以容納新元素蔫缸。
vector同 array 一樣可以很方便的通過(guò)索引值直接存取任何一個(gè)元素，在數(shù)組的尾端追加或移除元素均非臣势穑快速(當(dāng)追加元素超出原有分配空間時(shí)拾碌，vector需要重新分配空間)，但在其中間或頭部插入移除元素就比較費(fèi)時(shí)加叁，需要移動(dòng)安插點(diǎn)之后的所有元素以保持原來(lái)的相對(duì)位置倦沧。
深度探索array
array是一個(gè)固定大小的順序容器，不能動(dòng)態(tài)改變大小它匕，array內(nèi)的元素在內(nèi)存中以嚴(yán)格的線性順序存儲(chǔ)展融，與普通數(shù)組聲明存儲(chǔ)空間大小[]的方式是一樣有效的，只是加入了一些成員函數(shù)和全局函數(shù)[get (array)豫柬、operators (array)]告希，以便當(dāng)作標(biāo)準(zhǔn)容器使用。與list和vector的iterator類似烧给，有一種iterator traits用以分類class Iterators和non-class Iterators燕偶。
