《C++ primer》中所提的評價容器性能的主要兩個方面：
- 向容器添加或刪除元素的代價
- 非順序訪問容器中元素的代價
要想理解和熟練運(yùn)用好標(biāo)準(zhǔn)庫的容器，就要明白它們在實現(xiàn)上的不同氧苍，才能分辨出范式算法在不同容器上的不同之處。
array
array是固定大小的容器二打，物理存儲地址是連續(xù)的拒课。
vector
vector的物理存儲地址是連續(xù)的捅僵。vector的內(nèi)存空間是向后擴(kuò)展的钱反，支持push_back(),不支持push_front()掖看，若在尾部之外的地方插入或刪除，后面的數(shù)據(jù)都要重新操作
deque
deque是順序存儲的容器面哥，但是不同于array和vector是整塊地址連續(xù)，deque的實現(xiàn)是分段連續(xù)的毅待，通過指向不同地址的buffer尚卫，形成邏輯上和物理上的連續(xù)，支持push_front()和push_back()尸红。
formward_list和list
作為比較特殊的容器吱涉，與 list(單向鏈表）相比刹泄，forward_list的迭代器只支持 ++遞增運(yùn)算符，不支持--遞減運(yùn)算符怎爵，因為單向鏈表的節(jié)點(diǎn)只存儲一個向后的指針特石，而雙向鏈表則存儲向前和向后的指針。forward_list設(shè)計出來是為了實現(xiàn)相當(dāng)性能的容器鳖链，沒有back()姆蘸，也不計算鏈表的長度size()，只支持push_front()芙委，不支持push_back()逞敷。
原因是
若要在末節(jié)點(diǎn)插入元素，單向鏈表沒有記錄back()和size()灌侣，只能由頭結(jié)點(diǎn)循序找到末節(jié)點(diǎn)推捐，這樣的效率是很低的，而若要在頭結(jié)點(diǎn)插入侧啼，只需要構(gòu)建一個新結(jié)點(diǎn)牛柒，指向原來的頭結(jié)點(diǎn)，成為新的頭結(jié)點(diǎn)痊乾，這樣的時間成本就很低了焰络。
struct ListNode
{
ListNode * pNext;
int value;
}
ListNode * push_front(int value)
{
ListNode * p=new ListNode(_pHead,value);
_pHead=p;
}
但是相對于其他順序的容器，鏈表的物理存儲順序和邏輯順序并不連續(xù)符喝，是用指針的指向?qū)崿F(xiàn)結(jié)點(diǎn)的順序闪彼，在內(nèi)存分配上很靈活，可以隨意進(jìn)行插入和刪除协饲，但是從內(nèi)存消耗來講畏腕，鏈表的內(nèi)存額外消耗大，用于存儲指針了茉稠，若是用forward_list存儲int類型的數(shù)據(jù)描馅，那么就多消耗了一倍的內(nèi)存。
關(guān)聯(lián)容器
map multimap set multimap 是由紅黑樹實現(xiàn)的而线，邏輯上是連續(xù)的铭污。
無序關(guān)聯(lián)容器
unordered_map unordered_set unordered_multimap unordered_multiset 是根據(jù)哈希表實現(xiàn)的，沒有順序膀篮，維護(hù)代價小嘹狞，性能也更加優(yōu)秀。
