C++的STL

今天，看一段程式碼的時候發現只一句話就做了個排序，是這樣的：

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

很震驚，後來查了一下sort的用法，

sort函數的用法

自己寫個冒泡之類的O(n^2)排序，不但程式容易超時，還很有可能寫錯。

STL裡面有個sort函數，可以直接對陣列排序，複雜度為n*log2(n)。使用這個函數，需要包含頭檔。
    這個函數可以傳遞兩個參數或三個參數。第一個參數是要排序的區間首位址，第二個參數是區間尾位址的下一位址。

也就是說，排序的區間是[a,b)。簡單來說，有一個陣列int a[100]，要對從a[0]到a[99]的元素進行排序，只要寫sort(a,a+100)就行了，預設的排序方式是升序。
    拿我出的「AC的策略」這題來說，需要對數組t的第0到len-1的元素排序，就寫sort(t,t+len);
    對向量v排序也差不多，sort (v.begin(),v.end());//這正是我之前看到的用法
    排序的資料類型不限於整數，只要是定義了小於運算的類型都可以，例如字串類string。
    如果是沒有定義小於運算的資料型別，或是想改變排序的順序，就要用到第三參數－比較函數。比較函數是一個自己定義的函數，傳回值是bool型，它規定了什麼樣的關係才是「小於」。想把剛才的整數陣列依降序排列，可以先定義一個比較函數cmp
bool cmp(int a,int b)
{
    return a>b;
}
   排序的時候就寫上sort(a,a+100 ,cmp);

   假設自己定義了一個結構體node
struct node{
    int a;
    int b;
   de ：先依a值升序排列，若a值相同，再依b值降序排列，若b還相同，就依c降序排列。

就可以寫出這樣一個比較函數：

以下是程式碼片段：

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;

}

   排序時寫sort(arr,a+100,cmp);

qsort(s[0],n,sizeof(s[00] ]),cmp);

int cmp(const void *a,const void *b)

{
    return *(int *)a-*(int *)b;
}

 排序  

int num[100];  

Sample:  

int cmp ( const void *a , const void *b )  

{ 

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

二、對char型別陣列排序（同int型別）  

char word[100];  
:cSamplepleple> *a , const void *b )  

{  

return *(char *)a - *(int *)b;  

}  

qsort(word,100,sizeof(word[0]),cmp); 、對double型別陣列排序（特別要注意）  

double in[100];  

int cmp( const void *a , const void *b )  

{ b ? 1 : -1;  
}  

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

四、結構體一級排序other;  

}s[100]  

//依照data的值從小到大將結構體排序,關於結構體內的排序關鍵資料data的型別可以很多種，參考上面的例子寫  

int cmp( constoid void a ,const void *b)  

{  
return ((In *)a)->data - ((In *)b)->data ;  
}  

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

五、對結構體 

struct In  

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

}s[100];  

int y嗚.大到小排序  

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

else return d->y - c->y;  

}  

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

六、對字串進行排序  

struct In  
{  
int data;  

char str[100]; 

int data;  

char str[100]; 

順序排序  

int cmp ( const void *a , const void *b )  
{  
return strcmp( ((In *)a)->str , ((In*)b)->str ); qsort(s,100,sizeof(s[0]),cmp);  

七、計算幾何中求凸包的cmp  

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

好了，說了這麼多sort的用法，有沒有人對什麼是STL還迷惘的呢？

下面說說什麼是STL（內容來源網路）

一、一般介紹

      STL（Standard Template Library），即標準模板庫，是一個具有工業強度的，高效的C++程式庫。它被容納在C++標準程式庫（C++ Standard Library）中，是ANSI/ISO C++標準中最新的也是極具革命性的一部分。該函式庫包含了許多在電腦科學領域中所常用的基本資料結構和基本演算法。為廣大C++程式設計師提供了一個可擴展的應用框架，高度體現了軟體的可重複使用性。

      從邏輯層次來看，在STL中體現了泛型化程序設計的思想（generic programming），引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），演算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態（polymorphism）一樣，泛型也是一種軟體的複用技術；

       從實現層次來看，整個STL是以一種類型參數化（type parameterized）的方式實現的，這種方式是基於一個在早先C++標準中沒有出現的語言特性--模板（template）。如果你查閱任何一個版本的STL原始碼，你會發現，模板作為構成整個STL的基石是一件千真萬確的事情。除此之外，還有許多C++的新特性為STL的實作提供了方便；

 

二、STL的六大組件

容器（Container），是一種資料結構，如list，vector，和deques ，以模板類別的方法提供。為了存取容器中的數據，可以使用由容器類別輸出的迭代器；

迭代器（Iterator），提供了存取容器中物件的方法。例如，可以使用一對迭代器指定list或vector中的一定範圍的物件。迭代器就如同一個指標。事實上，C++的指標也是一種迭代器。但是，迭代器也可以是那些定義了operator*()以及其他類似指標的操作符地方法的類別物件；

演算法（Algorithm），是用來操作容器中的資料的模板函數。例如，STL用sort()來對一個vector中的資料進行排序，用find()來搜尋一個list中的對象，函數本身與他們操作的資料的結構和類型無關，因此他們可以在從簡單數組到在高度複雜容器的任何資料結構上使用；

仿函數（Function object，仿函數(functor)又稱之為函數物件（function object），其實就是重載了()操作符的struct，沒有什麼特別的地方

迭代適配器（Adaptor）

空間配製器（allocator）其中主要工作包括兩部分1.對象的創建與銷毀    2.內存的獲取與釋放

以下主要討論：容器，迭代器，算法，適配器。 vector、deque、list；

   Vectors：將元素置於一個動態數組中加以管理，可以隨機存取元素（用索引直接存取），數組尾部添加或移除元素非常快速。但在中部或頭部安插元素比較費時；

   Deques：是「double-ended queue」的縮寫，可以隨機存取元素（用索引直接存取），數組頭部和尾部添加或移除元素都非常快速。但在中部或頭部安插元素比較費時；

   Lists：雙向鍊錶，不提供隨機存取（依序走到需存取的元素，O(n)），在任何位置執行插入或刪除動作都非常迅速，內部只需調整指針；

2）關聯式容器（Associated containers），元素位置取決於特定的排序準則，和插入順序無關，set、multiset、map、multimap；

   Sets/Multisets：內部的元素依據其值自動排序，Set內的相同數值的元素只能出現一次，Multisets內可包含多個數值相同的元素，內部由二元樹實現（實際上基於紅黑樹(RB-tree）實現） ，方便查找；

   Maps/Multimaps：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现（实际上基于红黑树(RB-tree）实现），便于查找；

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

  容器的比较：

2.STL迭代器 

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 
而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；

常见的一些迭代器类型：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                            

要注意，上面这图表并不是表明它们之间的继承关系：而只是描述了迭代器的种类和接口。处于图表下层的迭代器都是相对于处于图表上层迭代器的扩张集。例如：forward迭代器不但拥有input和output迭代器的所有功能，还拥有更多的功能。

各个迭代器的功能如下：

迭代器的操作：

每种迭代器均可进行包括表中前一种迭代器可进行的操作。

只有顺序容器和关联容器支持迭代器遍历，各容器支持的迭代器的类别如下：

 3.STL算法

STL算法部分主要由头文件,,组成。要使用 STL中的算法函数必须包含头文件，对于数值算法须包含，中则定义了一些模板类，用来声明函数对象。
STL中算法大致分为四类：
1）、非可变序列算法：指不直接修改其所操作的容器内容的算法。
2）、可变序列算法：指可以修改它们所操作的容器内容的算法。
3）、排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
4）、数值算法：对容器内容进行数值计算。

 

以下對所有演算法進行細緻分類並標明功能：
    查找演算法(13個)：判斷容器中是否包含某個值
    adjacent_find:         adjacent_find:     傳回指向這對元素的第一個元素的ForwardIterator。否則返回last。重載版本使用輸入的二元運算子來取代相等的判斷。
    binary_search:            在有序序列中找出value，並找出回傳true。重載的版本實用指定的比較函數物件或函數指標來判斷相等。
    count:                    使用且等於運算符，且將標誌範圍內的元素與輸入值比較，並回復為等元素個數。
    count_if:                 以輸入的動作符，且針對標誌範圍內的元素操作，且傳回結果為true的數量。
    equal_range:              功能類似equal，並返回一對iterator，而第一個表示lower_bound，第二個表示upper_bound。
    find:                     以底層元素的等於運算符，以指定範圍內的元素與輸入值進行比較。當匹配時，結束搜索，返回該元素的一個InputIterator。
    find_end:                 在另一個針對另一個已輸入」的另一個由輸入的另一對iterator標誌的第二個序列"的最後一次出現。找到則傳回最後一對的第一個ForwardIterator，否則傳回輸入的"另外一對"的第一個ForwardIterator。重載版本使用使用者輸入的操作符代替等於操作。
    find_first_of:            以先於輸入的另外一對iterator標誌為參考的第二個序列"中任一個元素的第一次出現。重載版本中使用了使用者自訂操作符。
    find_if:                  以輸入的函數來取代等於運算子執行find。
    lower_bound:              以中傳回一個ForwardIterator，並指向在有序序列範圍內的可插入指定值而不破壞容器順序的第一個位置。重載函數使用自訂比較操作。
    upper_bound:              以造成ForwardIterator，指向有序序列範圍內插入value而不破壞容器順序的最後一個位置，該位置標誌一個大於value的值。重載函數使用自訂比較操作。
    search:                 ‧重載版本使用自訂的比較操作。
    search_n:                 以指定範圍內找出val出現n次的子序列。重載版本使用自訂的比較操作。
 
    排序與一般演算法(14個)：提供元素排序策略
    inplace_merge:            合併兩個有序序列，且結果序列則涵蓋兩端範圍。重載版本使用輸入的操作進行排序。
    merge:                    且有兩個順序序列，且存放於另一個序列中所包含。重載版本使用自訂的比較。
    nth_element:              將範圍內的序列重新排序，且使所有小於第n個元素的元素都出現在它前面，而大於它的都出現在後面。重載版本使用自訂的比較操作。
    partial_sort:             以序列作部分排序，且以排序元素數量剛好可放至範圍內。重載版本使用自訂的比較操作。
    partial_sort_copy:        與partial_sort類似，但將經過排序的序列複製到另一個容器。
    partition:                對指定範圍內元素重新排序，並使用輸入的函數，以結果為true的元素放在結果為false的元素之前。
    random_shuffle:           以指定範圍內的元素以隨機調整順序。重載版本輸入一個隨機數產生運算。
    reverse:                 則以指定內元素以重新反轉排序。
    reverse_copy:            則與reverse類似，且將結果寫入另一個容器中。
    rotate:                   將指定範圍內元素移至容器末端，且由middle所指向的元素成為容器第一個元素。
    rotate_copy:              類似，且將結果寫入另一個容器中。
    sort:                    以以升序重新排列指定範圍內的元素。重載版本使用自訂的比較操作。
    stable_sort:              類似，且已保留等元素之間的順序關係。
    stable_partition:         與partition類似，但不保證保留容器內的相對順序。
 
    刪除與替換演算法(15個)
    copy:                   與copy相同，不過元素是以相反順序被拷貝。
    iter_swap:                交換兩個以ForwardIterator中的值。
    remove:                  且以所有等於指定元素的元素刪除所指定範圍的元素。注意，該函數不是真正刪除函數。內建函數不適合使用remove和remove_if函數。
    remove_copy:              將所有不符合元素複製到一個制定容器，並返回OutputIterator指向被拷貝的末元素的下一個位置。
    remove_if:               且為所有指定範圍內輸入作業結果為true的元素。
    remove_copy_if:           將所有不符元素拷貝至指定容器中。
    replace:                  且以所有等於vold的元素指定範圍以vnew。
    replace_copy:             與replace類似，且將結果寫入另一個容器。
    replace_if:               所有以所有作業結果為true的元素以新值取代。
    replace_copy_if:          與replace_if，但將結果寫入另一個容器。
    swap:                     以兩個物件儲存儲存的數值。
    swap_range:               將指定範圍內的元素與另一個序列元素值交換。
    unique:                   清除序列中重複元素，且與remove類似，且它無法真正移除元素。重載版本使用自訂比較操作。
    unique_copy:              類似，且已輸出結果於另一個容器中。
 
    排列組合演算法(2個)：提供計算給定集合依一定順序的​​所有可能排列組合
    next_permutation:         取出目前範圍內的排列，並重新排序為下一個排列。重載版本使用自訂的比較操作。
    prev_permutation:         取出指定範圍內的序列並將它重新排序為上一個序列。如果不存在上一個序列則回傳false。重載版本使用自訂的比較操作。
 

    算術演算法(4個)
    accumulate:               iterator對接的序列段元素和識別值重載版本不再做加法，而是傳進來的二元運算子被應用到元素上。
    partial_sum:              建立一個新序列，且每個元素值代表指定範圍內該位置前所有元素總和。重載版本使用自訂操作代替加法。
    inner_product:            以兩個序列中為中積(對應元素相乘，而求和)並將內積加到一個輸入的初始值上。重載版本使用使用者定義的操作。
    adjacent_difference:      建立一個新序列，新序列中每個新值代表目前元素與上一個元素的差。重載版本用指定二元運算計算相鄰元素的差。
 
    產生與異變演算法(6個)
    fill:               
    fill_n:                   以將輸入值指派給first至first+n所處的所有元素。
    for_each:                 以指定函數依序針對指定範圍內所有元素進行迭代訪問，並傳回所指定的函數型別。此函數不得修改序列中的元素。
    generate:                且以持續呼叫輸入的函數填入指定中的範圍內。
    generate_n:               與generate函數類似，而填入由指定iterator開始的n個元素。
    transform:                將輸入的操作作用與每個在指定範圍內的元素，並產生一個新的序列。重載版本將操作作用在一對元素上，另外一個元素來自輸入的另一個序列。結果輸出到指定容器。
 

                                                                                                                                                                                                                                                             Relational algorithm:                                   . The overloaded version uses the input operator instead of the default equals operator. includes: Determines whether all elements in the first specified range are included in the second range. Use the lexicographical_compare: Compare two sequences. The overloaded version uses user-defined comparison operations.
max: Returns the larger of the two elements. Overloaded version uses custom comparison operation. max_element: Returns a ForwardIterator, pointing out the largest element in the sequence. Overloaded version uses custom comparison operation.
min: Returns the smaller of the two elements. Overloaded version uses custom comparison operation.
min_element: Returns a ForwardIterator, pointing out the smallest element in the sequence. Overloaded version uses custom comparison operation.
mismatch: Compares two sequences in parallel, points out the first mismatched position, and returns a pair of iterators, marking the position of the first mismatched element. If they all match, return the last of each container. The overloaded version uses a custom comparison operation.

Set algorithm (4)

set_union: Construct an ordered sequence that contains all non-repeating elements in the two sequences. The overloaded version uses a custom comparison operation. set_intersection: Constructs an ordered sequence in which elements exist in both sequences. The overloaded version uses a custom comparison operation.
set_difference: Constructs an ordered sequence that only retains elements that exist in the first sequence but not in the second. The overloaded version uses a custom comparison operation.
Set_symmetric_difference: Construct an ordered sequence, which takes the symmetric difference (union-intersection) of two sequences.

Heap algorithm (4)

make_heap: Generate a heap from the elements in the specified range. Overloaded version uses custom comparison operation. pop_heap: does not actually pop the largest element from the heap, but reorders the heap. It swaps first and last-1, and then regenerates a heap. You can use the container's back to access the "popped" element or use pop_back to actually delete it. The overloaded version uses a custom comparison operation.
push_heap: Assume that first to last-1 is a valid heap, the elements to be added to the heap are stored in position last-1, and the heap is regenerated. Before pointing to this function, the element must be inserted into the container. The overloaded version uses the specified comparison operation.
sort_heap: Reorders the sequence within the specified range. It assumes that the sequence is an ordered heap. Overloaded version uses custom comparison operation.

4. Adapter

STL provides three container adapters: queue, priority_queue, and stack. These adapters are wrappers that wrap a certain sequence container in vector, list, and deque. Note: The adapter does not provide an iterator and cannot insert or delete multiple elements at the same time. Below is a summary of each adapter.

(1) stack usage

#include

template class stack;

You can use any of the three standard sequential containers vecotr, deque (default), and list as the underlying model of the stack.

bool stack::empty()                               //判断堆栈是否为空
void stack::pop()                                 //弹出栈顶数据
stack::push(T x)                                  //压入一个数据
stack::size_type stack::size()                 //返回堆栈长度
T stack::top()                                    //得到栈顶数据

代码示例：

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

2）queue用法

#include
template > class  queue;

第一个参数指定要在queue中存储的类型，第二个参数规定queue适配的底层容器，可供选择的容器只有dequeue和list。对大多数用途使用默认的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也是一个队列，其元素按有序顺序排列。其不采用严格的FIFO顺序，给定时刻位于队头的元素正是有最高优先级的元素。如果两个元素有相同的优先级，那么它们在队列中的顺序就遵循FIFO语义。默认适配的底层容器是vector，也可以使用deque，list不能用，因为priority_queue要求能对元素随机访问以便进行排序。

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, greater >
priority_queue, greater >

 

标准库默认使用元素类型的

优先队列第一种用法，通过默认使用的

priority_queue qi;

示例中输出结果为：9 6 5 3 2

优先队列第二种用法，建立priority_queue时传入一个比较函数，使用functional.h函数对象作为比较函数。

priority_queue, greater >qi2;

示例2中输出结果为：2 3 5 6 9

优先队列第三种用法，是自定义优先级。

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

在示例3中输出结果为：

优先级  值

9          5

8          2

6          1

2          3

1          4

在该结构中，value为值，priority为优先级。通过自定义operator编译不通过。