今天，看一段代碼的時(shí)候發(fā)現(xiàn)只一句話就做了個(gè)排序，是這樣的：

sort（rotateArray.begin(),rotateArray.end()）;

很震驚，后來(lái)查了一下sort的用法，

sort函數(shù)的用法

自己寫(xiě)個(gè)冒泡之類(lèi)的O(n^2)排序，不但程序容易超時(shí)，還很有可能寫(xiě)錯(cuò)。

STL里面有個(gè)sort函數(shù)，可以直接對(duì)數(shù)組排序，復(fù)雜度為n*log2(n)。使用這個(gè)函數(shù)，需要包含頭文件。
????這個(gè)函數(shù)可以傳兩個(gè)參數(shù)或三個(gè)參數(shù)。第一個(gè)參數(shù)是要排序的區(qū)間首地址，第二個(gè)參數(shù)是區(qū)間尾地址的下一地址。

也就是說(shuō)，排序的區(qū)間是[a,b)。簡(jiǎn)單來(lái)說(shuō)，有一個(gè)數(shù)組int a[100]，要對(duì)從a[0]到a[99]的元素進(jìn)行排序，只要寫(xiě)sort(a,a+100)就行了，默認(rèn)的排序方式是升序。
????拿我出的“AC的策略”這題來(lái)說(shuō)，需要對(duì)數(shù)組t的第0到len-1的元素排序，就寫(xiě)sort(t,t+len);
????對(duì)向量v排序也差不多，sort(v.begin(),v.end());//這正是我之前看到的用法
????排序的數(shù)據(jù)類(lèi)型不局限于整數(shù)，只要是定義了小于運(yùn)算的類(lèi)型都可以，比如字符串類(lèi)string。
????如果是沒(méi)有定義小于運(yùn)算的數(shù)據(jù)類(lèi)型，或者想改變排序的順序，就要用到第三參數(shù)——比較函數(shù)。比較函數(shù)是一個(gè)自己定義的函數(shù)，返回值是bool型，它規(guī)定了什么樣的關(guān)系才是“小于”。想把剛才的整數(shù)數(shù)組按降序排列，可以先定義一個(gè)比較函數(shù)cmp
bool cmp(int a,int b)
{
????return a>b;
}
???排序的時(shí)候就寫(xiě)sort(a,a+100,cmp);

???假設(shè)自己定義了一個(gè)結(jié)構(gòu)體node
struct node{
????int a;
????int b;
????double c;
}
???有一個(gè)node類(lèi)型的數(shù)組node arr[100]，想對(duì)它進(jìn)行排序：先按a值升序排列，如果a值相同，再按b值降序排列，如果b還相同，就按c降序排列。

就可以寫(xiě)這樣一個(gè)比較函數(shù)：

以下是代碼片段：

bool cmp(node x,node y)
{
     if(x.a!=y.a) return x.a
     if(x.b!=y.b) return x.b>y.b;
     return return x.c>y.c;

}

排序時(shí)寫(xiě)sort(arr,a+100,cmp);

qsort(s[0],n,sizeof(s[0]),cmp);
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}

一、對(duì)int類(lèi)型數(shù)組排序

int num[100];

Sample:

int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}

qsort(num,100,sizeof(num[0]),cmp);

二、對(duì)char類(lèi)型數(shù)組排序（同int類(lèi)型）

char word[100];

Sample:

int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}

qsort(word,100,sizeof(word[0]),cmp);

三、對(duì)double類(lèi)型數(shù)組排序（特別要注意）

double in[100];

int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}

qsort(in,100,sizeof(in[0]),cmp)；

四、對(duì)結(jié)構(gòu)體一級(jí)排序

struct In
{
double data;
int other;
}s[100]

//按照data的值從小到大將結(jié)構(gòu)體排序,關(guān)于結(jié)構(gòu)體內(nèi)的排序關(guān)鍵數(shù)據(jù)data的類(lèi)型可以很多種，參考上面的例子寫(xiě)

int cmp( const void *a ,const void *b)
{
return ((In *)a)->data - ((In *)b)->data ;
}

qsort(s,100,sizeof(s[0]),cmp);

五、對(duì)結(jié)構(gòu)體

struct In
{
int x;
int y;
}s[100];

//按照x從小到大排序，當(dāng)x相等時(shí)按照y從大到小排序

int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}

qsort(s,100,sizeof(s[0]),cmp);

六、對(duì)字符串進(jìn)行排序

struct In
{
int data;
char str[100];
}s[100];

//按照結(jié)構(gòu)體中字符串str的字典順序排序

int cmp ( const void *a , const void *b )
{
return strcmp( ((In *)a)->str , ((In *)b)->str );
}

qsort(s,100,sizeof(s[0]),cmp);

七、計(jì)算幾何中求凸包的cmp

int cmp(const void *a,const void *b) //重點(diǎn)cmp函數(shù)，把除了1點(diǎn)外的所有點(diǎn)，旋轉(zhuǎn)角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一條直線上，則把遠(yuǎn)的放在前面
return 1;
else return -1;
}

好了，說(shuō)了這么多sort的用法，有沒(méi)有人對(duì)什么是STL還迷茫的呢？

下面說(shuō)說(shuō)什么是STL（內(nèi)容來(lái)源網(wǎng)絡(luò)）

一、一般介紹

STL（Standard Template Library），即標(biāo)準(zhǔn)模板庫(kù)，是一個(gè)具有工業(yè)強(qiáng)度的，高效的C++程序庫(kù)。它被容納于C++標(biāo)準(zhǔn)程序庫(kù)（C++ Standard Library）中，是ANSI/ISO C++標(biāo)準(zhǔn)中最新的也是極具革命性的一部分。該庫(kù)包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C++程序員們提供了一個(gè)可擴(kuò)展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。

從邏輯層次來(lái)看，在STL中體現(xiàn)了泛型化程序設(shè)計(jì)的思想（generic programming），引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣，泛型也是一種軟件的復(fù)用技術(shù)；

從實(shí)現(xiàn)層次看，整個(gè)STL是以一種類(lèi)型參數(shù)化（type parameterized）的方式實(shí)現(xiàn)的，這種方式基于一個(gè)在早先C++標(biāo)準(zhǔn)中沒(méi)有出現(xiàn)的語(yǔ)言特性--模板（template）。如果查閱任何一個(gè)版本的STL源代碼，你就會(huì)發(fā)現(xiàn)，模板作為構(gòu)成整個(gè)STL的基石是一件千真萬(wàn)確的事情。除此之外，還有許多C++的新特性為STL的實(shí)現(xiàn)提供了方便；

二、STL的六大組件

容器（Container），是一種數(shù)據(jù)結(jié)構(gòu)，如list，vector，和deques ，以模板類(lèi)的方法提供。為了訪問(wèn)容器中的數(shù)據(jù)，可以使用由容器類(lèi)輸出的迭代器；

迭代器（Iterator），提供了訪問(wèn)容器中對(duì)象的方法。例如，可以使用一對(duì)迭代器指定list或vector中的一定范圍的對(duì)象。迭代器就如同一個(gè)指針。事實(shí)上，C++的指針也是一種迭代器。但是，迭代器也可以是那些定義了operator*()以及其他類(lèi)似于指針的操作符地方法的類(lèi)對(duì)象；

算法（Algorithm），是用來(lái)操作容器中的數(shù)據(jù)的模板函數(shù)。例如，STL用sort()來(lái)對(duì)一個(gè)vector中的數(shù)據(jù)進(jìn)行排序，用find()來(lái)搜索一個(gè)list中的對(duì)象，函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類(lèi)型無(wú)關(guān)，因此他們可以在從簡(jiǎn)單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用；

仿函數(shù)（Function object，仿函數(shù)(functor)又稱之為函數(shù)對(duì)象（function object），其實(shí)就是重載了()操作符的struct，沒(méi)有什么特別的地方

迭代適配器（Adaptor）

空間配制器（allocator）其中主要工作包括兩部分1.對(duì)象的創(chuàng)建與銷(xiāo)毀 2.內(nèi)存的獲取與釋放

以下主要討論：容器，迭代器，算法，適配器。如欲詳加了解 參見(jiàn)C++ Primer

1.STL容器

1）序列式容器（Sequence containers），每個(gè)元素都有固定位置－－取決于插入時(shí)機(jī)和地點(diǎn)，和元素值無(wú)關(guān)，vector、deque、list；

Vectors：將元素置于一個(gè)動(dòng)態(tài)數(shù)組中加以管理，可以隨機(jī)存取元素（用索引直接存?。?，數(shù)組尾部添加或移除元素非?？焖?。但是在中部或頭部安插元素比較費(fèi)時(shí)；

Deques：是“double-ended queue”的縮寫(xiě)，可以隨機(jī)存取元素（用索引直接存?。?，數(shù)組頭部和尾部添加或移除元素都非常快速。但是在中部或頭部安插元素比較費(fèi)時(shí)；

Lists：雙向鏈表，不提供隨機(jī)存?。ò错樞蜃叩叫璐嫒〉脑?，O(n)），在任何位置上執(zhí)行插入或刪除動(dòng)作都非常迅速，內(nèi)部只需調(diào)整一下指針；

2）關(guān)聯(lián)式容器（Associated containers），元素位置取決于特定的排序準(zhǔn)則，和插入順序無(wú)關(guān)，set、multiset、map、multimap；

Sets/Multisets：內(nèi)部的元素依據(jù)其值自動(dòng)排序，Set內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multisets內(nèi)可包含多個(gè)數(shù)值相同的元素，內(nèi)部由二叉樹(shù)實(shí)現(xiàn)（實(shí)際上基于紅黑樹(shù)(RB-tree）實(shí)現(xiàn)），便于查找；

Maps/Multimaps：Map的元素是成對(duì)的鍵值/實(shí)值，內(nèi)部的元素依據(jù)其值自動(dòng)排序，Map內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multimaps內(nèi)可包含多個(gè)數(shù)值相同的元素，內(nèi)部由二叉樹(shù)實(shí)現(xiàn)（實(shí)際上基于紅黑樹(shù)(RB-tree）實(shí)現(xiàn)），便于查找；

另外有其他容器hash_map,hash_set,hash_multiset,hash_multimap。

容器的比較：

2.STL迭代器

Iterator（迭代器）模式又稱Cursor（游標(biāo)）模式，用于提供一種方法順序訪問(wèn)一個(gè)聚合對(duì)象中各個(gè)元素,
而又不需暴露該對(duì)象的內(nèi)部表示?；蛘哌@樣說(shuō)可能更容易理解：Iterator模式是運(yùn)用于聚合對(duì)象的一種模式，通過(guò)運(yùn)用該模式，使得我們可以在不知道對(duì)象內(nèi)部表示的情況下，按照一定順序（由iterator提供的方法）訪問(wèn)聚合對(duì)象中的各個(gè)元素。

迭代器的作用：能夠讓迭代器與算法不干擾的相互發(fā)展，最后又能無(wú)間隙的粘合起來(lái)，重載了*，＋＋，＝＝，?。?，＝運(yùn)算符。用以操作復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，容器提供迭代器，算法使用迭代器；

常見(jiàn)的一些迭代器類(lèi)型：iterator、const_iterator、reverse_iterator和const_reverse_iterator

迭代器一般聲明使用示例

vector<T>::iterator it;
list<T>::iterator it;
deque<T>::iterator it；

input output

\ /

forward

|

bidirectional

|

random access

要注意，上面這圖表并不是表明它們之間的繼承關(guān)系：而只是描述了迭代器的種類(lèi)和接口。處于圖表下層的迭代器都是相對(duì)于處于圖表上層迭代器的擴(kuò)張集。例如：forward迭代器不但擁有input和output迭代器的所有功能，還擁有更多的功能。

各個(gè)迭代器的功能如下：

迭代器的操作：

每種迭代器均可進(jìn)行包括表中前一種迭代器可進(jìn)行的操作。

只有順序容器和關(guān)聯(lián)容器支持迭代器遍歷，各容器支持的迭代器的類(lèi)別如下：

3.STL算法

STL算法部分主要由頭文件,,組成。要使用 STL中的算法函數(shù)必須包含頭文件，對(duì)于數(shù)值算法須包含，中則定義了一些模板類(lèi)，用來(lái)聲明函數(shù)對(duì)象。
STL中算法大致分為四類(lèi)：
1）、非可變序列算法：指不直接修改其所操作的容器內(nèi)容的算法。
2）、可變序列算法：指可以修改它們所操作的容器內(nèi)容的算法。
3）、排序算法：包括對(duì)序列進(jìn)行排序和合并的算法、搜索算法以及有序序列上的集合操作。
4）、數(shù)值算法：對(duì)容器內(nèi)容進(jìn)行數(shù)值計(jì)算。

以下對(duì)所有算法進(jìn)行細(xì)致分類(lèi)并標(biāo)明功能：
<一>查找算法(13個(gè))：判斷容器中是否包含某個(gè)值
adjacent_find: 在iterator對(duì)標(biāo)識(shí)元素范圍內(nèi)，查找一對(duì)相鄰重復(fù)元素，找到則返回指向這對(duì)元素的第一個(gè)元素的ForwardIterator。否則返回last。重載版本使用輸入的二元操作符代替相等的判斷。
binary_search: 在有序序列中查找value，找到返回true。重載的版本實(shí)用指定的比較函數(shù)對(duì)象或函數(shù)指針來(lái)判斷相等。
count: 利用等于操作符，把標(biāo)志范圍內(nèi)的元素與輸入值比較，返回相等元素個(gè)數(shù)。
count_if: 利用輸入的操作符，對(duì)標(biāo)志范圍內(nèi)的元素進(jìn)行操作，返回結(jié)果為true的個(gè)數(shù)。
equal_range: 功能類(lèi)似equal，返回一對(duì)iterator，第一個(gè)表示lower_bound，第二個(gè)表示upper_bound。
find: 利用底層元素的等于操作符，對(duì)指定范圍內(nèi)的元素與輸入值進(jìn)行比較。當(dāng)匹配時(shí)，結(jié)束搜索，返回該元素的一個(gè)InputIterator。
find_end: 在指定范圍內(nèi)查找"由輸入的另外一對(duì)iterator標(biāo)志的第二個(gè)序列"的最后一次出現(xiàn)。找到則返回最后一對(duì)的第一個(gè)ForwardIterator，否則返回輸入的"另外一對(duì)"的第一個(gè)ForwardIterator。重載版本使用用戶輸入的操作符代替等于操作。
find_first_of: 在指定范圍內(nèi)查找"由輸入的另外一對(duì)iterator標(biāo)志的第二個(gè)序列"中任意一個(gè)元素的第一次出現(xiàn)。重載版本中使用了用戶自定義操作符。
find_if: 使用輸入的函數(shù)代替等于操作符執(zhí)行find。
lower_bound: 返回一個(gè)ForwardIterator，指向在有序序列范圍內(nèi)的可以插入指定值而不破壞容器順序的第一個(gè)位置。重載函數(shù)使用自定義比較操作。
upper_bound: 返回一個(gè)ForwardIterator，指向在有序序列范圍內(nèi)插入value而不破壞容器順序的最后一個(gè)位置，該位置標(biāo)志一個(gè)大于value的值。重載函數(shù)使用自定義比較操作。
search: 給出兩個(gè)范圍，返回一個(gè)ForwardIterator，查找成功指向第一個(gè)范圍內(nèi)第一次出現(xiàn)子序列(第二個(gè)范圍)的位置，查找失敗指向last1。重載版本使用自定義的比較操作。
search_n: 在指定范圍內(nèi)查找val出現(xiàn)n次的子序列。重載版本使用自定義的比較操作。

<二>排序和通用算法(14個(gè))：提供元素排序策略
inplace_merge: 合并兩個(gè)有序序列，結(jié)果序列覆蓋兩端范圍。重載版本使用輸入的操作進(jìn)行排序。
merge: 合并兩個(gè)有序序列，存放到另一個(gè)序列。重載版本使用自定義的比較。
nth_element: 將范圍內(nèi)的序列重新排序，使所有小于第n個(gè)元素的元素都出現(xiàn)在它前面，而大于它的都出現(xiàn)在后面。重載版本使用自定義的比較操作。
partial_sort: 對(duì)序列做部分排序，被排序元素個(gè)數(shù)正好可以被放到范圍內(nèi)。重載版本使用自定義的比較操作。
partial_sort_copy: 與partial_sort類(lèi)似，不過(guò)將經(jīng)過(guò)排序的序列復(fù)制到另一個(gè)容器。
partition: 對(duì)指定范圍內(nèi)元素重新排序，使用輸入的函數(shù)，把結(jié)果為true的元素放在結(jié)果為false的元素之前。
random_shuffle: 對(duì)指定范圍內(nèi)的元素隨機(jī)調(diào)整次序。重載版本輸入一個(gè)隨機(jī)數(shù)產(chǎn)生操作。
reverse: 將指定范圍內(nèi)元素重新反序排序。
reverse_copy: 與reverse類(lèi)似，不過(guò)將結(jié)果寫(xiě)入另一個(gè)容器。
rotate: 將指定范圍內(nèi)元素移到容器末尾，由middle指向的元素成為容器第一個(gè)元素。
rotate_copy: 與rotate類(lèi)似，不過(guò)將結(jié)果寫(xiě)入另一個(gè)容器。
sort: 以升序重新排列指定范圍內(nèi)的元素。重載版本使用自定義的比較操作。
stable_sort: 與sort類(lèi)似，不過(guò)保留相等元素之間的順序關(guān)系。
stable_partition: 與partition類(lèi)似，不過(guò)不保證保留容器中的相對(duì)順序。

<三>刪除和替換算法(15個(gè))
copy: 復(fù)制序列
copy_backward: 與copy相同，不過(guò)元素是以相反順序被拷貝。
iter_swap: 交換兩個(gè)ForwardIterator的值。
remove: 刪除指定范圍內(nèi)所有等于指定元素的元素。注意，該函數(shù)不是真正刪除函數(shù)。內(nèi)置函數(shù)不適合使用remove和remove_if函數(shù)。
remove_copy: 將所有不匹配元素復(fù)制到一個(gè)制定容器，返回OutputIterator指向被拷貝的末元素的下一個(gè)位置。
remove_if: 刪除指定范圍內(nèi)輸入操作結(jié)果為true的所有元素。
remove_copy_if: 將所有不匹配元素拷貝到一個(gè)指定容器。
replace: 將指定范圍內(nèi)所有等于vold的元素都用vnew代替。
replace_copy: 與replace類(lèi)似，不過(guò)將結(jié)果寫(xiě)入另一個(gè)容器。
replace_if: 將指定范圍內(nèi)所有操作結(jié)果為true的元素用新值代替。
replace_copy_if: 與replace_if，不過(guò)將結(jié)果寫(xiě)入另一個(gè)容器。
swap: 交換存儲(chǔ)在兩個(gè)對(duì)象中的值。
swap_range: 將指定范圍內(nèi)的元素與另一個(gè)序列元素值進(jìn)行交換。
unique: 清除序列中重復(fù)元素，和remove類(lèi)似，它也不能真正刪除元素。重載版本使用自定義比較操作。
unique_copy: 與unique類(lèi)似，不過(guò)把結(jié)果輸出到另一個(gè)容器。

<四>排列組合算法(2個(gè))：提供計(jì)算給定集合按一定順序的所有可能排列組合
next_permutation: 取出當(dāng)前范圍內(nèi)的排列，并重新排序?yàn)橄乱粋€(gè)排列。重載版本使用自定義的比較操作。
prev_permutation: 取出指定范圍內(nèi)的序列并將它重新排序?yàn)樯弦粋€(gè)序列。如果不存在上一個(gè)序列則返回false。重載版本使用自定義的比較操作。

<五>算術(shù)算法(4個(gè))
accumulate: iterator對(duì)標(biāo)識(shí)的序列段元素之和，加到一個(gè)由val指定的初始值上。重載版本不再做加法，而是傳進(jìn)來(lái)的二元操作符被應(yīng)用到元素上。
partial_sum: 創(chuàng)建一個(gè)新序列，其中每個(gè)元素值代表指定范圍內(nèi)該位置前所有元素之和。重載版本使用自定義操作代替加法。
inner_product: 對(duì)兩個(gè)序列做內(nèi)積(對(duì)應(yīng)元素相乘，再求和)并將內(nèi)積加到一個(gè)輸入的初始值上。重載版本使用用戶定義的操作。
adjacent_difference: 創(chuàng)建一個(gè)新序列，新序列中每個(gè)新值代表當(dāng)前元素與上一個(gè)元素的差。重載版本用指定二元操作計(jì)算相鄰元素的差。

<六>生成和異變算法(6個(gè))
fill: 將輸入值賦給標(biāo)志范圍內(nèi)的所有元素。
fill_n: 將輸入值賦給first到first+n范圍內(nèi)的所有元素。
for_each: 用指定函數(shù)依次對(duì)指定范圍內(nèi)所有元素進(jìn)行迭代訪問(wèn)，返回所指定的函數(shù)類(lèi)型。該函數(shù)不得修改序列中的元素。
generate: 連續(xù)調(diào)用輸入的函數(shù)來(lái)填充指定的范圍。
generate_n: 與generate函數(shù)類(lèi)似，填充從指定iterator開(kāi)始的n個(gè)元素。
transform: 將輸入的操作作用與指定范圍內(nèi)的每個(gè)元素，并產(chǎn)生一個(gè)新的序列。重載版本將操作作用在一對(duì)元素上，另外一個(gè)元素來(lái)自輸入的另外一個(gè)序列。結(jié)果輸出到指定容器。

<七>關(guān)系算法(8個(gè))
equal: 如果兩個(gè)序列在標(biāo)志范圍內(nèi)元素都相等，返回true。重載版本使用輸入的操作符代替默認(rèn)的等于操作符。
includes: 判斷第一個(gè)指定范圍內(nèi)的所有元素是否都被第二個(gè)范圍包含，使用底層元素的<操作符，成功返回true。重載版本使用用戶輸入的函數(shù)。
lexicographical_compare: 比較兩個(gè)序列。重載版本使用用戶自定義比較操作。
max: 返回兩個(gè)元素中較大一個(gè)。重載版本使用自定義比較操作。
max_element: 返回一個(gè)ForwardIterator，指出序列中最大的元素。重載版本使用自定義比較操作。
min: 返回兩個(gè)元素中較小一個(gè)。重載版本使用自定義比較操作。
min_element: 返回一個(gè)ForwardIterator，指出序列中最小的元素。重載版本使用自定義比較操作。
mismatch: 并行比較兩個(gè)序列，指出第一個(gè)不匹配的位置，返回一對(duì)iterator，標(biāo)志第一個(gè)不匹配元素位置。如果都匹配，返回每個(gè)容器的last。重載版本使用自定義的比較操作。

<八>集合算法(4個(gè))
set_union: 構(gòu)造一個(gè)有序序列，包含兩個(gè)序列中所有的不重復(fù)元素。重載版本使用自定義的比較操作。
set_intersection: 構(gòu)造一個(gè)有序序列，其中元素在兩個(gè)序列中都存在。重載版本使用自定義的比較操作。
set_difference: 構(gòu)造一個(gè)有序序列，該序列僅保留第一個(gè)序列中存在的而第二個(gè)中不存在的元素。重載版本使用自定義的比較操作。
set_symmetric_difference: 構(gòu)造一個(gè)有序序列，該序列取兩個(gè)序列的對(duì)稱差集(并集-交集)。

<九>堆算法(4個(gè))
make_heap: 把指定范圍內(nèi)的元素生成一個(gè)堆。重載版本使用自定義比較操作。
pop_heap: 并不真正把最大元素從堆中彈出，而是重新排序堆。它把first和last-1交換，然后重新生成一個(gè)堆?？墒褂萌萜鞯腷ack來(lái)訪問(wèn)被"彈出"的元素或者使用pop_back進(jìn)行真正的刪除。重載版本使用自定義的比較操作。
push_heap: 假設(shè)first到last-1是一個(gè)有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向該函數(shù)前，必須先把元素插入容器后。重載版本使用指定的比較操作。
sort_heap: 對(duì)指定范圍內(nèi)的序列重新排序，它假設(shè)該序列是個(gè)有序堆。重載版本使用自定義比較操作。

4.適配器

STL提供了三個(gè)容器適配器：queue、priority_queue、stack。這些適配器都是包裝了vector、list、deque中某個(gè)順序容器的包裝器。注意：適配器沒(méi)有提供迭代器，也不能同時(shí)插入或刪除多個(gè)元素。下面對(duì)各個(gè)適配器進(jìn)行概括總結(jié)。

（1）stack用法

#include
template < typename T, typename Container=deque > class stack;

可以使用三個(gè)標(biāo)準(zhǔn)順序容器vecotr、deque(默認(rèn))、list中的任何一個(gè)作為stack的底層模型。

bool stack::empty() //判斷堆棧是否為空
void stack::pop() //彈出棧頂數(shù)據(jù)
stack::push(T x) //壓入一個(gè)數(shù)據(jù)
stack::size_type stack::size() //返回堆棧長(zhǎng)度
T stack::top() //得到棧頂數(shù)據(jù)

代碼示例：

stack<int> intDequeStack;  
stack<int,vector<int>> intVectorStack;  
stack<int,list<int>> intListStack;

2）queue用法

#include
template > class queue;

第一個(gè)參數(shù)指定要在queue中存儲(chǔ)的類(lèi)型，第二個(gè)參數(shù)規(guī)定queue適配的底層容器，可供選擇的容器只有dequeue和list。對(duì)大多數(shù)用途使用默認(rèn)的dequeue。

queue<T>::push(T x)
void queue<T>::pop()
T queue<T>::back()
T queue<T>::front()
queue<T>::size_type 
queue<T>::size()
bool queue<T>::empty()

代碼示例：

queue intDequeQueue;
queue> intListQueue;

（3）priority_queue用法

#include
template , typename Compare = less > class priority_queue;

priority_queue也是一個(gè)隊(duì)列，其元素按有序順序排列。其不采用嚴(yán)格的FIFO順序，給定時(shí)刻位于隊(duì)頭的元素正是有最高優(yōu)先級(jí)的元素。如果兩個(gè)元素有相同的優(yōu)先級(jí)，那么它們?cè)陉?duì)列中的順序就遵循FIFO語(yǔ)義。默認(rèn)適配的底層容器是vector，也可以使用deque，list不能用，因?yàn)閜riority_queue要求能對(duì)元素隨機(jī)訪問(wèn)以便進(jìn)行排序。

priority_queue<T>::push(T x)
void priority_queue<T>::pop()
T priority_queue<T>::top()
priority_queue<T>::size_type 
priority_queue<T>::size()
bool priority_queue<T>::empty()

代碼示例：

priority_queue< int, vector, greater >
priority_queue< int, list, greater >

標(biāo)準(zhǔn)庫(kù)默認(rèn)使用元素類(lèi)型的<操作符來(lái)確定它們之間的優(yōu)先級(jí)關(guān)系，用法有三：（下文轉(zhuǎn)自http://www.cnblogs.com/vvilp/articles/1504436.html）

優(yōu)先隊(duì)列第一種用法，通過(guò)默認(rèn)使用的<操作符可知在整數(shù)中元素大的優(yōu)先級(jí)高。

priority_queue qi;

示例中輸出結(jié)果為：9 6 5 3 2

優(yōu)先隊(duì)列第二種用法，建立priority_queue時(shí)傳入一個(gè)比較函數(shù)，使用functional.h函數(shù)對(duì)象作為比較函數(shù)。

priority_queue, greater >qi2;

示例2中輸出結(jié)果為：2 3 5 6 9

優(yōu)先隊(duì)列第三種用法，是自定義優(yōu)先級(jí)。

struct node 
{
     friend bool operator< (node n1, node n2)
     {
         return n1.priority < n2.priority;
     } 
     int priority;
     int value; 
}; 
priority_queue<node> qn;

在示例3中輸出結(jié)果為：

優(yōu)先級(jí)? 值

9????????? 5

8????????? 2

6????????? 1

2????????? 3

1????????? 4

在該結(jié)構(gòu)中，value為值，priority為優(yōu)先級(jí)。通過(guò)自定義operator編譯不通過(guò)。