STL學習小結

STL就是Standard Template Library，標準模板庫。這可能是一個歷史上最令人興奮的工具的最無聊的術語。從根本上說，STL是一些“容器”的集合，這些“容器”有list, vector,set,map等，STL也是算法和其它一些組件的集合。這里的“容器”和算法的集合指的是世界上非常多聰明人非常多年的杰作。是C＋＋標準庫的一個重要組成部分，它由Stepanov and Lee等人最先開發，它是與C＋＋差點兒同一時候開始開發的；一開始STL選擇了Ada作為實現語言，但Ada有點不爭氣，最后他們選擇了C＋＋，C＋＋中已經有了模板。STL又被增加進了C＋＋庫。1996年，惠普公司又免費公開了STL，為STL的推廣做了非常大的貢獻。STL提供了類型安全、高效而易用特性的STL無疑是最值得C++程序猿驕傲的部分。每個C＋＋程序猿都應該好好學習STL。大體上包含container（容器）、algorithm（算法）和iterator（迭代器），容器和算法通過迭代器能夠進行無縫連接。

一、基礎知識

1、泛型技術

泛型技術的實現方法有多種，比方模板，多態等。模板是編譯時決定，多態是執行時決定，其它的比方RTTI也是執行時確定。多態是依靠虛表在執行時查表實現的。比方一個類擁有虛方法，那么這個類的實例的內存起始地址就是虛表地址，能夠把內存起始地址強制轉換成int*，取得虛表，然后(int*)*(int*)取得虛表里的第一個函數的內存地址，然后強制轉換成函數類型，就可以調用來驗證虛表機制。

泛型編程（generic programming，以下直接以GP稱呼）是一種全新的程序設計思想，和OO，OB，PO這些為人所熟知的程序設計想法不同的是GP抽象度更高，基于GP設計的組件之間偶合度底，沒有繼承關系，所以其組件間的互交性和擴展性都非常高。我們都知道，不論什么算法都是作用在一種特定的數據結構上的，最簡單的樣例就是高速排序算法最根本的實現條件就是所排序的對象是存貯在數組里面，由于高速排序就是由于要用到數組的隨機存儲特性，即能夠在單位時間內交換遠距離的對象，而不僅僅是相臨的兩個對象，而假設用聯表去存儲對象，由于在聯表中取得對象的時間是線性的即O[n]，這樣將使高速排序失去其高速的特點。也就是說，我們在設計一種算法的時候，我們總是先要考慮其應用的數據結構，比方數組查找，聯表查找，樹查找，圖查找其核心都是查找，但由于作用的數據結構不同將有多種不同的表現形式。數據結構和算法之間這樣密切的關系一直是我們曾經的認識。泛型設計的根本思想就是想把算法和其作用的數據結構分離，也就是說，我們設計算法的時候并不去考慮我們設計的算法將作用于何種數據結構之上。泛型設計的理想狀態是一個查找算法將能夠作用于數組，聯表，樹，圖等各種數據結構之上，變成一個通用的，泛型的算法。

2、四種類型轉換操作符

static_cast???? 將一個值以符合邏輯的方式轉換。應用到類的指針上，意思是說它同意子類類型的指針轉換為父類類型的指針（這是一個有效的隱式轉換），同一時候，也能夠執行相反動作：轉換父類為它的子類。

比如：float x;

????? Count<<static_cast<int>(x);//把x作為整型值輸出

dynamic_cast????????????? 將多態類型向下轉換為事實上際靜態類型。僅僅用于對象的指針和引用。當用于多態類型時，它同意隨意的隱式類型轉換以及相反過程。dynamic_cast會檢查操作是否有效。也就是說，它會檢查轉換是否會返回一個被請求的有效的完整對象。檢測在執行時進行。假設被轉換的指針不是一個被請求的有效完整的對象指針，返回值為NULL.??????

比如：class Car;

?????? ? class Cabriolet:public Car{

?????? ? …

};

?????? ? class Limousline:public Car{

?????? ? …

};

?????? ? void f(Car *cp)

?????? ? {

????????????? Cabriolet *p = dynamic_cast< Cabriolet > cp;

}

reinterpret_cast?? 轉換一個指針為其它類型的指針。它也同意從一個指針轉換為整數類型。反之亦然。這個操作符能夠在非相關的類型之間轉換。操作結果僅僅是簡單的從一個指針到別的指針的值的二進制拷貝。在類型之間指向的內容不做不論什么類型的檢查和轉換。

比如：

class A {};
class B {};
A * a = new A;
B * b = reinterpret_cast<B *>(a);

const_cast一般用于強制消除對象的常量性。

比如：

class C {};
const C *a = new C;
C *b = const_cast<C *>(a);
其它三種操作符是不能改動一個對象的常量性的。

3、explicit修飾的構造函數不能擔任轉換函數。在非常多情況下，隱式轉換是有意的，而且是正當的。但有時我們不希望進行這種自己主動的轉換。

比如：為了避免這種隱式轉換，應該象以下這樣顯式聲明該帶單一參數的構造函數：

class String {
int size;
char *p;
//..
public:
?????? // 不要隱式轉換
?????? explicit String (int sz);
?????? String (const char *s, int size n = 0); // 隱式轉換
};
void f ()
{
????String s(10);
????s = 100; // 如今編譯時出錯；須要顯式轉換：
????s = String(100); // 好；顯式轉換
????s = "st";????????// 好；此時同意隱式轉換
}

4、命名空間namespace

?? 解決在使用不同模塊和程序庫時，出現名稱沖突問題。

5、C++標準程序庫中的通用工具。由類和函數構成。這些工具包含：

?? 數種通用類型

?? 一些重要的C函數

?? 數值極值

二、STL六大組件

容器（Container）

算法（Algorithm）

迭代器（Iterator）

仿函數（Function object）

適配器（Adaptor）

空間配置器（allocator）

1、容器

作為STL的最主要組成部分－－容器，分為向量（vector），雙端隊列(deque)，表(list)，隊列（queue），堆棧(stack)，集合(set)，多重集合(multiset)，映射(map)，多重映射(multimap)。

容器	特性	所在頭文件
向量vector	能夠用常數時間訪問和改動隨意元素，在序列尾部進行插入和刪除時，具有常數時間復雜度，對隨意項的插入和刪除就有的時間復雜度與到末尾的距離成正比，尤其對向量頭的增加和刪除的代價是驚人的高的	<vector>
雙端隊列deque	基本上與向量同樣，唯一的不同是，其在序列頭部插入和刪除操作也具有常量時間復雜度	<deque>
表list	對隨意元素的訪問與對兩端的距離成正比，但對某個位置上插入和刪除一個項的花費為常數時間。	<list>
隊列queue	插入僅僅能夠在尾部進行，刪除、檢索和改動僅僅同意從頭部進行。依照先進先出的原則。	<queue>
堆棧stack	堆棧是項的有限序列，并滿足序列中被刪除、檢索和改動的項僅僅能是近期插入序列的項。即依照后進先出的原則	<stack>
集合set	由節點組成的紅黑樹，每個節點都包含著一個元素，節點之間以某種作用于元素對的謂詞排列，沒有兩個不同的元素能夠擁有同樣的次序，具有高速查找的功能。可是它是以犧牲插入刪除操作的效率為代價的	<set>
多重集合multiset	和集合基本同樣，但能夠支持反復元素具有高速查找能力	<set>
映射map	由{鍵，值}對組成的集合，以某種作用于鍵對上的謂詞排列。具有高速查找能力	<map>
多重集合multimap	比起映射，一個鍵能夠相應多了值。具有高速查找能力	<map>

STL容器能力表：

2、算法

算法部分主要由頭文件<algorithm>，<numeric>和<functional>組成。< algorithm>是全部STL頭文件里最大的一個，它是由一大堆模版函數組成的，能夠覺得每個函數在非常大程度上都是獨立的，當中經常使用到的功能范圍涉及到比較、交換、查找、遍歷操作、復制、改動、移除、反轉、排序、合并等等。<numeric>體積非常小，僅僅包含幾個在序列上面進行簡單數學運算的模板函數，包含加法和乘法在序列上的一些操作。<functional>中則定義了一些模板類，用以聲明函數對象。

STL的算法也是非常優秀的，它們大部分都是類屬的，基本上都用到了C＋＋的模板來實現，這樣，非常多相似的函數就不用自己寫了，僅僅要用函數模板就能夠了。

我們使用算法的時候，要針對不同的容器，比方：對集合的查找，最好不要用通用函數find（），它對集合使用的時候，性能非常的差，最好用集合自帶的find（）函數，它針對了集合進行了優化，性能非常的高。

3、迭代器

它的具體實如今<itertator>中，我們全然能夠不管迭代器類是怎么實現的，大多數的時候，把它理解為指針是沒有問題的（指針是迭代器的一個特例，它也屬于迭代器），可是，決不能全然這么做。

迭代器功能

輸入迭代器

Input iterator

向前讀

Reads forward

istream

輸出迭代器

Output iterator

向前寫

Writes forward

ostream,inserter

前向迭代器

Forward iterator

向前讀寫

Read and Writes forward

雙向迭代器

Bidirectional iterator

向前向后讀寫

Read and Writes forward and

backward

list,set,multiset,map,mul

timap

隨機迭代器

Random access iterator

隨機讀寫

Read and Write with random

access

vector,deque,array,string

4、仿函數

仿函數，又或叫做函數對象，是STL六大組件之中的一個；仿函數盡管小，但卻極大的拓展了算法的功能，差點兒全部的算法都有仿函數版本號。比如，查找算法find_if就是對find算法的擴展，標準的查找是兩個元素相等就找到了，可是什么是相等在不同情況下卻須要不同的定義，如地址相等，地址和郵編都相等，盡管這些相等的定義在變，但算法本身卻不須要改變，這都多虧了仿函數。仿函數(functor)又稱之為函數對象（function object），事實上就是重載了()操作符的struct，沒有什么特別的地方。

如以下代碼定義了一個二元推斷式functor：

struct IntLess
{
bool operator()(int left, int right) const
{
?? return (left < right);
};
};

為什么要使用仿函數呢？

1).仿函數比一般的函數靈活。

2).仿函數有類型識別，能夠作為模板參數。

3).執行速度上仿函數比函數和指針要更快的。

怎么使用仿函數？

除了在STL里，別的地方你非常少會看到仿函數的身影。而在STL里仿函數最經常使用的就是作為函數的參數，或者模板的參數。

在STL里有自己提前定義的仿函數，比方全部的運算符，=，-，*，、比方'<'號的仿函數是less

template<class _Ty>
struct less?? : public binary_function<_Ty, _Ty, bool>
{ // functor for operator<
??????? bool operator()(const _Ty& _Left, const _Ty& _Right) const
?????????????????? { // apply operator< to operands
????????????????????????????? return (_Left < _Right);
?????????????????? }
};

從上面的定義能夠看出，less從binary_function<...>繼承來的，那么binary_function又是什么的？

template<class _Arg1, class _Arg2, class _Result>
struct binary_function
{ // base class for binary functions
??????? typedef _Arg1 first_argument_type;
???? ?? typedef _Arg2 second_argument_type;
????? typedef _Result result_type;
};

事實上binary_function僅僅是做一些類型聲明而已，別的什么也沒做，可是在STL里為什么要做這些呢？假設你要閱讀過STL的源代碼，你就會發現，這種使用方法非常多，事實上沒有別的目的，就是為了方便，安全，可復用性等。可是既然STL里面內定如此了，所以作為程序猿你必須要遵循這個規則,否則就別想安全的使用STL。

比方我們自己定一個仿函數。能夠這樣：

template <typename type1,typename type2>
class func_equal :public binary_function<type1,type2,bool>
{
??????? inline bool operator()(type1 t1,type2 t2) const//這里的const不能少
??????????? {
???????????????? return t1 == t2;//當然這里要overload==

????????? ?? }
}

我們看這一行： inline bool operator()(type1 t1,type2 t2) const//這里的const不能少
inline是聲明為內聯函數，我想這里應該不用多說什么什么了，關鍵是為什么要聲明為const的？要想找到原因還是看源代碼，增加假設我們這里寫一行代碼，find_if(s.begin(),s.end(),bind2nd(func_equal(),temp)),在bind2nd函數里面的參數是const類型的，const類型的對象，僅僅能訪問cosnt修飾的函數！

與binary_function(二元函數)相對的是unary_function(一元函數),其使用方法同binary_function

struct unary_function {
typedef _A argument_type;
typedef _R result_type;
};

注：仿函數就是重載()的class，而且重載函數要為const的，假設要自己定義仿函數，而且用于STL接配器，那么一定要從binary_function或者，unary_function繼承。

5、適配器

適配器是用來改動其它組件接口的STL組件，是帶有一個參數的類模板（這個參數是操作的值的數據類型）。STL定義了3種形式的適配器：容器適配器，迭代器適配器，函數適配器。

容器適配器：包含棧（stack）、隊列(queue)、優先(priority_queue)。使用容器適配器，stack就能夠被實現為基本容器類型（vector,dequeue,list）的適配。能夠把stack看作是某種特殊的vctor,deque或者list容器，僅僅是其操作仍然受到stack本身屬性的限制。queue和priority_queue與之相似。容器適配器的接口更為簡單，僅僅是受限比一般容器要多。

迭代器適配器：改動為某些基本容器定義的迭代器的接口的一種STL組件。反向迭代器和插入迭代器都屬于迭代器適配器，迭代器適配器擴展了迭代器的功能。

函數適配器：通過轉換或者改動其它函數對象使其功能得到擴展。這一類適配器有否定器（相當于"非"操作）、綁定器、函數指針適配器。函數對象適配器的作用就是使函數轉化為函數對象，或是將多參數的函數對象轉化為少參數的函數對象。

比如：

在STL程序里，有的算法須要一個一元函數作參數，就能夠用一個適配器把一個二元函數和一個數值，綁在一起作為一個一元函數傳給算法。
比如：
find_if(coll.begin(), coll.end(), bind2nd(greater <int>(), 42));
這句話就是找coll中第一個大于42的元素。
greater <int>()，事實上就是">"號，是一個2元函數
bind2nd的兩個參數，要求一個是2元函數，一個是數值，結果是一個1元函數。
bind2nd就是個函數適配器。

6、空間配置器

STL的內存配置器在我們的實際應用中差點兒不用涉及，但它卻在STL的各種容器背后默默做了大量的工作，STL內存配置器為容器分配并管理內存。統一的內存管理使得STL庫的可用性、可移植行、以及效率都有了非常大的提升。

SGI-STL的空間配置器有2種，一種僅僅對c語言的malloc和free進行了簡單的封裝，而還有一個設計到小塊內存的管理等，運用了內存池技術等。在SGI-STL中默認的空間配置器是第二級的配置器。

SGI使用時std::alloc作為默認的配置器。

A）．alloc把內存配置和對象構造的操作分開，分別由alloc::allocate()和::construct()負責，同樣內存釋放和對象析夠操作也被分開分別由alloc::deallocate()和::destroy()負責。這樣能夠保證高效，由于對于內存分配釋放和構造析夠能夠依據具體類型(type traits)進行優化。比方一些類型能夠直接使用高效的memset來初始化或者忽略一些析構函數。對于內存分配alloc也提供了2級分配器來應對不同情況的內存分配。

B）．第一級配置器直接使用malloc()和free()來分配和釋放內存。第二級視情況採用不同的策略：當需求內存超過128bytes的時候，視為足夠大，便調用第一級配置器；當需求內存小于等于128bytes的時候便採用比較復雜的memeory pool的方式管理內存。

C）．不管allocal被定義為第一級配置器還是第二級，SGI還為它包裝一個接口，使得配置的接口能夠符合標準即把配置單位從bytes轉到了元素的大小：

???????? ???????? template<class T, class Alloc>

class simple_alloc

{

public:

???? static T* allocate(size_t n)

???? {

???????? return 0 == n ? 0 : (T*)Alloc::allocate(n * sizeof(T));

???? }

???? static T* allocate(void)

???? {

???????? return (T*) Alloc::allocate(sizeof(T));

???? }

???? static void deallocate(T* p, size_t n)

???? {

???????? if (0 != n) Alloc::deallocate(p, n * sizeof(T));

???? }

???? static void deallocate(T* p)

???? {

???????? Alloc::deallocate(p, sizeof(T));

???? }

}???

d）．內存的基本處理工具，它們均具有commt or rollback能力。

template<class InputIterator, class ForwardIterator>

ForwardIterator

uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);

template<class ForwardIterator, class T>

void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

template<class ForwardIterator, class Size, class T>

ForwardIterator

uninitialized_fill_n(ForwardIterator first, ForwardIterator last, const T& x)

三、具體容器、算法

1、全部容器都提供了一個默認的構造函數，一個拷貝構造函數。

比如：

list<int> l;

....

vector<int> ivector(l.begin(),l.end());

int array[]={1,2,3,4};

....

set<int> iset(array,array+sizeof(array)/sizeof(array[0]));

2、與大小相關的函數

size(),empty(),max_size()

3、返回迭代器的函數

begin(),end(),rbegin(),rend()

4、比較操作

==,!=,<,>,>=....

Vector具體解釋：

capacity(),返回vector能夠容納的元素個數。

size(),返回vector內現有元素的個數。

賦值操作：

c1=c2; 把c2的全部元素指派給c1

c.assign(n,elem);復制n個elem，指派給c

c.assign(beg,end);將區間beg，end內的元素指派給c

c1.swap(c2);將c1,c2元素互換

swap(c1,c2);同上

元素存取

c.at(index);

c[index];

c.front();返回第一個元素

c.back();

插入和刪除：

c.insert(pos.elem);

c.insert(pos,n.elem); 插入n個elem

c.insert(pos,beg,end); 在pos出插入beg，end區間內的全部元素。

c.push_back(elem);

c.pop_back();

c.erase(pos); 刪除pos上的元素，返回下一個元素

c.erase(beg,end);

c.resize(num);將元素數量改為num，假設size變大了，多出來的新元素都要一default方式構建。

c.resize(num,elem);將元素數量改為num，假設size變大了，多出來的新元素是elem的副本。

c.clear();刪除全部。

vector的reserve和resize

reserve僅僅分配空間，而不創建對象，size()不變。而resize分配空間而且用空對象填充.

reserve是容器預留空間，但并不真正創建元素對象，在創建對象之前，不能引用容器內的元素，因此當增加新的元素時，須要用push_back()/insert()函數。

resize是改變容器的大小，而且創建對象，因此，調用這個函數之后，就能夠引用容器內的對象了，因此當增加新的元素時，用operator[]操作符，或者用迭代器來引用元素對象。

再者，兩個函數的形式是有差別的，reserve函數之后一個參數，即須要預留的容器的空間；resize函數能夠有兩個參數，第一個參數是容器新的大小，第二個參數是要增加容器中的新元素，假設這個參數被省略，那么就調用元素對象的默認構造函數。

vector有而deque無的：capacity(), reserve();

deque有而vector無的：push_front(elem), pop_front(); push_back(elem), pop_back();

STL提供的另兩種容器queue、stack，事實上都僅僅只是是一種adaptor，它們簡單地修飾deque的界面而成為另外的容器類型

List具體解釋：

for_each? (.begin(), .end(), “函數”);

count (.begin(), .end(), 100, jishuqi);

返回對象等于100的個數jishuqi值。

count_if() 帶一個函數對象的參數(上面“100”的這個參數)。函數對象是一個至少帶有一個operator()方法的類。這個類能夠更復雜。

find(*.begin().*end(),“要找的東西”)；

假設沒有找到指出的對象，就會返回*.end()的值，要是找到了就返回一個指著找到的對象的iterator

fine_if()；與count_if()相似，是find的更強大版本號。

STL通用算法search()用來搜索一個容器，可是是搜索一個元素串，不象find()和find_if() 僅僅搜索單個的元素。

search算法在一個序列中找還有一個序列的第一次出現的位置。

search(A.begin(), A.end(), B.begin(), B.end());

在A中找B這個序列的第一次出現。

要排序一個list，我們要用list的成員函數sort()，而不是通用算法sort()。

list容器有它自己的sort算法，這是由于通用算法僅能為那些提供隨機存取里面元素的容器排序。

list的成員函數push_front()和push_back()分別把元素增加到list的前面和后面。你能夠使用insert() 把對象插入到list中的不論什么地方。

insert()能夠增加一個對象，一個對象的若干份拷貝，或者一個范圍以內的對象。

list成員函數pop_front()刪掉list中的第一個元素，pop_back()刪掉最后一個元素。函數erase()刪掉由一個iterator指出的元素。還有還有一個erase()函數能夠刪掉一個范圍的元素。

list的成員函數remove()用來從list中刪除元素。

*.remove("要刪除的對象");

通用算法remove()使用和list的成員函數不同的方式工作。普通情況下不改變容器的大小。

remove(*.begin(),*.end(),"要刪除的對象");

使用STL通用算法stable_partition()和list成員函數splice()來劃分一個list。

stable_partition()是一個有趣的函數。它又一次排列元素，使得滿足指定條件的元素排在不滿足條件的元素前面。它維持著兩組元素的順序關系。

splice 把還有一個list中的元素結合到一個list中。它從源list中刪除元素。

Set Map具體解釋：

STL map和set的使用雖不復雜，但也有一些不易理解的地方，如：

為何map和set的插入刪除效率比用其它序列容器高？

為何每次insert之后，曾經保存的iterator不會失效？

為何map和set不能像vector一樣有個reserve函數來預分配數據？

當數據元素增多時（10000到20000個比較），map和set的插入和搜索速度變化怎樣？

C++ STL中標準關聯容器set, multiset, map, multimap內部採用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也成為RB樹(Red-Black Tree)。RB樹的統計性能要好于一般的平衡二叉樹(AVL-樹).

為何map和set的插入刪除效率比用其它序列容器高？

大部分人說，非常easy，由于對于關聯容器來說，不須要做內存拷貝和內存移動。說對了，確實如此。map和set容器內全部元素都是以節點的方式來存儲，其節點結構和鏈表差點兒相同，指向父節點和子節點。這里的一切操作就是指針換來換去，和內存移動沒有關系。

為何每次insert之后，曾經保存的iterator不會失效？(同解)

為何map和set不能像vector一樣有個reserve函數來預分配數據？

究其原理來說時，引起它的原因在于在map和set內部存儲的已經不是元素本身了，而是包含元素的節點。

事實上你就記住一點，在map和set內面的分配器已經發生了變化，reserve方法你就不要奢望了。

當數據元素增多時（10000和20000個比較），map和set的插入和搜索速度變化怎樣？

假設你知道log2的關系你應該就徹底了解這個答案。在map和set中查找是使用二分查找，也就是說，假設有16個元素，最多須要比較4次就能找到結果，有32個元素，最多比較5次。那么有10000個呢？最多比較的次數為log10000，最多為14次，假設是20000個元素呢？最多只是15次。

泛型算法：

全部算法的前兩個參數都是一對iterators：[first，last)，用來指出容器內一個范圍內的元素。

每個算法的聲明中，都表現出它所須要的最低層次的iterator類型。

經常使用算法：

accumulate() 元素累加

adjacent_difference() 相鄰元素的差額

adjacent_find() 搜尋相鄰的反復元素

binary_search() 二元搜尋

copy() 復制

copy_backward() 逆向復制

count() 計數

count_if() 在特定條件下計數

equal() 推斷相等與否

equal_range() 推斷相等與否（傳回一個上下限區間范圍）

fill() 改填元素值

fill_n() 改填元素值，n 次

find() 搜尋

find_if() 在特定條件下搜尋

find_end() 搜尋某個子序列的最后一次出現地點

find_first_of() 搜尋某些元素的首次出現地點

for_each() 對范圍內的每個元素施行某動作

generate() 以指定動作的運算結果充填特定范圍內的元素

generate_n() 以指定動作的運算結果充填 n 個元素內容

includes() 涵蓋於

inner_product() 內積

inplace_merge() 合并并取代（覆寫）

iter_swap() 元素互換

lexicographical_compare() 以字典排列方式做比較

lower_bound() 下限

max() 最大值

max_element() 最大值所在位置

min() 最小值

min_element() 最小值所在位置

merge() 合并兩個序列

mismatch() 找出不吻合點

next_permutation() 獲得下一個排列組合

泛型演算法（Generic Algorithms）與 Function Obje4 cts

nth_element() 又一次安排序列中第n個元素的左右兩端

partial_sort() 局部排序

partial_sort_copy() 局部排序并拷貝到它處

partial_sum() 局部總和

partition() 分割

prev_permutation() 獲得前一個排列組合

random_shuffle() 隨機重排

remove() 移除某種元素（但不刪除）

remove_copy() 移除某種元素并將結果拷貝到還有一個 container

remove_if() 有條件地移除某種元素

remove_copy_if() 有條件地移除某種元素并將結果拷貝到還有一個 container

replace() 取代某種元素

replace_copy() 取代某種元素，并將結果拷貝到還有一個 container

replace_if() 有條件地取代

replace_copy_if() 有條件地取代，并將結果拷貝到還有一個 container

reverse() 顛倒元素次序

reverse_copy() 顛倒元素次序并將結果拷貝到還有一個 container

rotate() 旋轉

rotate_copy() 旋轉，并將結果拷貝到還有一個 container

search() 搜尋某個子序列

search_n() 搜尋「連續發生 n 次」的子序列

set_difference() 差集

set_intersection() 交集

set_symmetric_difference() 對稱差集

set_union() 聯集

sort() 排序

stable_partition() 分割并保持元素相對次序

stable_sort() 排序并保持等值元素的相對次序

swap() 置換（對調）

swap_range() 置換（指定范圍）

transform() 以兩個序列為基礎，交互作用產生第三個序列

unique() 將反復的元素摺疊縮編，使成唯一

unique_copy() 將反復的元素摺疊縮編，使成唯一，并拷貝到他處

upper_bound() 上限

四、注意細節：

1、auto_ptr 不能用new[]所生成的array作為初值，由于釋放內存時用的是delete，而不是delete[]

2、就搜尋速度而言，hash table通常比二叉樹還要快5~10倍。hash table不是C++標準程序庫的一員。

3、迭代器使用過程中優先選用前置式遞增操作符（++iter）而不是選擇后置式遞增操作符（iter++）。

3、迭代器三個輔助函數：advance(),distance(),iter_swap()。

?????? advance()可令迭代器前進

?????? distance()可處理迭代器之間的距離。

?????? iter_swap()可交換兩個迭代器所指內容。

4、hasp函數 makeheap()、push_heap()、pop_heap()、sort_heap()

5、’/0’在string之中并不具有特殊意義，可是在一般C形式的string中卻用來標記字符串結束。在string中，字符 ‘/0’和其它字符的地位全然同樣。string中有三個函數能夠將字符串內容轉換成字符數組或C形式的string。

data()???? 以字符數組的形式返回字符串內容。但末未追加’/0’字符，返回類型并非有效的C形式string。

c_str()??? 以C形式返回字符串內容（在末尾端增加’/0’字符）。

copy()??? 將字符串內容拷貝到“調用者提供的字符數組”中，不增加’/0’字符。

6、容器中用empty來取代檢查size是否為0；當使用new得到指針的容器時，切記在容器銷毀前delete那些指針；千萬不要把auto_ptr放入容器中。

7、盡量使用vector和string來取代動態申請的數組；避免使用vector<bool>，vector<bool>有兩個問題．第一，它不是一個真正STL容器，第二，它并不保存bool類型。

8、迭代器使用過程中，盡量使用iterator取代const_iterator，reverse_iterator和const_reverse_iterator；使用distance和advance把const_iterators轉化成iterators。

typedef deque<int> IntDeque;? // 和曾經一樣

typedef IntDeque::iterator Iter;

typedef IntDeque::const_iterator ConstIter;

IntDeque? d;

ConstIter ci;

...???? // 讓ci指向d

Iter i(d.begin());??? // 初始化i為d.begin()

advance(i, distance(i, ci));? // 調整i，指向ci位置

9、避免對set和multiset的鍵值進行改動。

10、永遠讓比較函數對同樣元素返回false。

11、排序選擇：

1）假設你須要在vector、string、deque或數組上進行全然排序，你能夠使用sort或stable_sort。

2）假設你有一個vector、string、deque或數組，你僅僅須要排序前n個元素，應該用partial_sort。

3）假設你有一個vector、string、deque或數組，你須要鑒別出第n個元素或你須要鑒別出最前的n個元素，而不用知道它們的順序，nth_element是你應該注意和調用的。

4）假設你須要把標準序列容器的元素或數組分隔為滿足和不滿足某個標準，你大概就要找partition或stable_partition。

5）假設你的數據是在list中，你能夠直接使用partition和stable_partition，你能夠使用list的sort來取代sort和stable_sort。假設你須要partial_sort或nth_element提供的效果，你就必須間接完畢這個任務。
12、假設你真的想刪除東西的話就在相似remove的算法后接上erase。remove從一個容器中remove元素不會改變容器中元素的個數，erase是真正刪除東西。
13、提防在指針的容器上使用相似remove的算法，在調用相似remove的算法前手動刪除和廢棄指針。
14、盡量用成員函數取代同名的算法，有些容器擁有和STL算法同名的成員函數。關聯容器提供了count、find、lower_bound、upper_bound和equal_range，而list提供了remove、remove_if、unique、sort、merge和reverse。大多數情況下，你應該用成員函數取代算法。這樣做有兩個理由。首先，成員函數更快。其次，比起算法來，它們與容器結合得更好（尤其是關聯容器）。那是由于同名的算法和成員函數通常并非是一樣的。
15、容器中使用自己定義的結構體時，假設用到拷貝與賦值，結構體須要重載operator=符號；比較容器分成相等與不等，相等時重載operator==符號，不等時重載operator<符號。比方set、map、multiset、multimap、priority_queue等容器類要求重載operator<符號。
16、Map/Multimap，Sets/Multisets都不能用push_back,push_front,由于它是自己主動排序的。

Set內的同樣數值的元素僅僅能出現一次，Multisets內可包含多個數值同樣的元素。

Map內的同樣數值的元素僅僅能出現一次，Multimap內可包含多個數值同樣的元素。內部由二叉樹實現，便于查找。

17、string 與數字之間的轉換，轉換的方法有非常多種，一般使用stringstream來實現轉換。比方：

#include? <iostream>

#include? <sstream>??

#include? <string>??

using?? namespace?? std;??

int?? main()??

{??

? int?? i=0;??

? string?? temp;????

? stringstream?? s;??

? //string轉換為數字

? temp = “1234”;?

? s<<temp;??

? s>>i;??

? cout<<i<<endl;??

?//數字轉換為string

?i=256;

?s<<i;

?temp = s.str();

?cout<<temp<<end;

?system("pause");??

?return?? 0;

}

18、對于自己定義的結構體，放入容器中，最好不要對容器進行內存初始化（不要調用memset,zeromemory函數），否則假設結構體中有指針類型的變量時，就會出現故障。

19、Vector的函數泄漏問題

定義了一個

struct temp

{

???? char name[256];

???? int i;

}

Vector<temp> vect;

當對這個vect執行pushback一些temp的結構體后，執行clear這樣是否會內存泄露？能夠釋放掉temp結構體中的name內存嗎？

解決方法：

不行，clear僅僅是把那些元素全部刪除掉，并非釋放內存。再者，你這種定義容器是不須要釋放內存的，假設你這樣定義，std::vector <temp> *pVec。就須要了。先pVec->clear()再 pVec->swap( (std::vector <temp>)(*pVec) )。就能實現內存的釋放。??

20、stl之map erase方法的正確使用
STL的map表里有一個erase方法用來從一個map中刪除掉指令的一個節點，不存在不論什么問題。
假設刪除多一個節點時，須要使用正確的調用方法。比方以下的方法是有問題：
for(ITER iter=mapTest.begin();iter!=mapTest.end();++iter)
{
cout<<iter->first<<":"<<iter->second<<endl;
mapTest.erase(iter);
}
這是一種錯誤的寫法,會導致程序行為不可知.究其原因是map 是關聯容器,對于關聯容器來說，假設某一個元素已經被刪除，那么其相應的迭代器就失效了，不應該再被使用；否則會導致程序無定義的行為。

正確的使用方法：
1).使用刪除之前的迭代器定位下一個元素。STL建議的使用方式
for(ITER iter=mapTest.begin();iter!=mapTest.end();)
{
cout<<iter->first<<":"<<iter->second<<endl;
mapTest.erase(iter++);
}

或者
for(ITER iter=mapTest.begin();iter!=mapTest.end();)
{
ITER iterTmp = iter;
iter++;
cout<<iterTmp->first<<":"<<iterTmp->second<<endl;
mapTest.erase(iterTmp);
}

2). erase() 成員函數返回下一個元素的迭代器
for(ITER iter=mapTest.begin();iter!=mapTest.end();)
{
cout<<iter->first<<":"<<iter->second<<endl;
iter=mapTest.erase(iter);
}

?21、boost::bind總結
bind 是一組重載的函數模板.用來向一個函數(或函數對象)綁定某些參數. bind的返回值是一個函數對象.
性質：
不是函數，是一個class，是一個多元仿函數

模板參數：
帶模板參數，但不須要，會自己主動推導！

構造函數參數：
格式：_須要綁定類型，_參數1，_參數2，_參數3，_參數4…

_須要綁定類型：能夠是普通函數，類成員函數，成員變量

_參數N：能夠是一個占位符，或者實際參數。

假設綁定的類型是一個類成員函數或變量，那么第一個參數必須是對象或者對象指針。
仿函數參數：
隨意

仿函數返回值
?????? 假設綁定的是函數，返回綁定函數的返回值。

?????? 假設綁定是成員變量，返回成員變量值

占位符：
_1,_2,_3,_4….._9

占位符的數字表示仿函數時相應參數的位置。

一個bind里能夠嵌入多個bind,但占位符是相對于這一塊的bind是共享。

注意事項
a)假設綁定的是類函數，傳入對象時，最好使用對象指針，假設使用對象實例會產生多次對象復制。假設非要傳對象而不想多次被復制傳在在使用ref或cref(ref的const版)

b)?跟lambda混用時一定要特別小心

第一、?? 會與lambda的占位符有沖突

第二、?? lambda庫里有跟同樣名字的bind,功能相似，但沒有此功能強大

總結
無模板參數，構函數對綁定函數負責，仿函數是隨意的。

舉例說明
例一：

void nine_arguments(

?????????????????????? int i1,int i2,int i3,int i4,

?????????????????????? int i5,int i6,int i7,int i8, int i9) {

??????????????????????????? std::cout << i1 << i2 << i3 << i4 << i5

???????????????????????????????? << i6 << i7 << i8 << i9 << '/n';

}

int main() {

???? int i1=1,i2=2,i3=3,i4=4,i5=5,i6=6,i7=7,i8=8,i9=9;

???? (boost::bind(&nine_arguments,_9,_2,_1,_6,_3,_8,_4,_5,_7))

???????? (i1,i2,i3,i4,i5,i6,i7,i8,i9);

}
輸出結果921638457

推薦書籍：

《C++標準程序庫》本書將焦點放在標準模板庫（Standard Template Library）身上，檢驗當中的容器（containers）、迭代器（iterators）、仿函數（functors）和算法（algorithms）。你還能夠找到特殊容器、字符串（strings）、數值類別、國際化議題、IOStream。每個組件都有深刻的呈現，包含其介紹、設計、運用實例、細部講解、陷阱、意想不到的危急，以及相關類別和函數的確切標記（signature）和定義。一份見解深刻的基礎概念介紹和一個程序庫綜合俯視，會對新手帶來高速的提升。

《泛型編程與STL》闡述了泛型程序設計的中心觀念:concepts,modeling, refinement,并為你展示這些觀念怎樣導出 STL 的基礎概念:iterators, containers, function objects.循此路線,你能夠把 STL 想象為一個由 concepts(而非明白之 functions 或 classes)組成的 library.你將學習其正式結構并因此獲得其潛在威力之完整優勢.

《Effective STL》闡述了怎樣有效地使用STL（Standard Template Library, 標準模板庫）進行編程。書中講述了怎樣將STL組件組合在一起，從而利用庫的設計。這些內容會幫助你針對簡單的問題開發出簡單、直接的解決方式，而且針對復雜的問題開發出精致的解決方式。書中還描寫敘述了常見的STL使用錯誤，并告訴你怎樣避免這些錯誤。

《STL源代碼剖析》了解源代碼，看到vector的實現、list的實現、heap的實現、deque的實現、RB-tree的實現、hash-table的實現、set/map 的實現；你將看到各種算法（排序、搜尋、排列組合、數據移動與復制…）的實現；你甚至將看究竟層的memory pool 和高階抽象的traits 機制的實現。