C++ 用の STL

今日、コードを見ていたら、次のような 1 文でソートされていることがわかりました。

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

Iショックを受けて、sort を調べてみました

sort 関数の使い方

バブルなどの独自の O(n^2) ソートを記述します プログラムはタイムアウトしやすいだけでなく、間違って記述される可能性も非常に高いです。

STL には、n*log2(n) の複雑さで配列を直接ソートできるソート関数があります。この機能を使用するには、ヘッダー ファイルをインクルードする必要があります。
この関数は 2 つのパラメーターまたは 3 つのパラメーターを渡すことができます。最初のパラメータはソートされる間隔の最初のアドレスで、2 番目のパラメータは間隔の終了アドレスの次のアドレスです。

つまり、ソート間隔は[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());//これは、前に見た使い方とまったく同じです
ソートされたデータ型は、算術以下の型を定義している限り、整数に限定されません。文字列クラス文字列など。
小なり演算にデータ型が定義されていない場合、または並べ替え順序を変更したい場合は、3 番目のパラメータである比較関数を使用する必要があります。比較関数は自己定義関数であり、戻り値はbool型でどのような関係にあるのかを指定します。先ほどの整数配列を降順に並べ替えたい場合は、まず比較関数 cmp
bool cmp(int a,int b)
{
return a>b;
}
並べ替えるときは、sort( a,a+100 ,cmp);

構造体 node
struct node{
int a;
int b;
double c;
}
を定義したとします。ノード タイプの配列ノード arr[100] があります。それを並べ替えたいとします。 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[0 ]),cmp);
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}

1. int 型配列のソート

int num[100];

サンプル:

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

{

}

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

{

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

struct In

int; other;

と記述します。
int cmp( const void * a ,const void *b)
{
return ((In *)a)->data - ((In *)b)->data
}

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

構造体をペアにする
{
int y;

{

struct In *d; = (*)b;
if(c->x != d->x) return c->x - d->x
else return d->y - c->y; (s,100,sizeof(s[0]) ,cmp);

struct で

}s[100];構造体の文字列 str の辞書によると 順次ソート

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

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

7. 計算幾何学で凸包を見つけるための Cmp

int cmp(const void *a,const void *b) //重要な cmp 関数は、1 点を除くすべての点を回転角度によってソートすることです
{
struct point * c =(ポイント *)a;
構造体ポイント *d=(ポイント *)b;
if( calc(*c,*d,p[1]) < 0) < 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]. ,p[1].y)) // 直線上にある場合は、遠い方を前に置きます
return 1;
else return -1; さて、sort の使い方をたくさん話しましたが、 STL とは何かについてまだ混乱している人はいますか?

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): コンテナーに特定の値が含まれているかどうかを判断します
隣接検索: 識別された要素の反復子のペアの範囲内で、隣接して繰り返されるペアのペアを検索します要素 (見つかった場合) ペアの最初の要素を指す ForwardIterator を返します。それ以外の場合は最後に戻ります。オーバーロードされたバージョンでは、等価性をチェックする代わりに入力二項演算子を使用します。
Binary_search: 順序付けされたシーケンス内の値を検索し、見つかった場合は true を返します。オーバーロードされたバージョンは、指定された比較関数オブジェクトまたは関数ポインターを使用して等しいかどうかを判断します。
カウント: 等号演算子を使用して、フラグ範囲内の要素を入力値と比較し、等しい要素の数を返します。
Count_if: 入力演算子を使用してフラグ範囲内の要素を操作し、真の結果の数を返します。
等しい範囲: 関数は等しいと似ており、反復子のペアを返します。最初のものは lower_bound を表し、2 つ目は upper_bound を表します。
検索: 基になる要素の等号演算子を使用して、指定された範囲内の要素を入力値と比較します。一致が発生すると、検索が終了し、要素の InputIterator が返されます。
find_end: 指定された範囲内で「入力反復子の別のペアによってマークされた 2 番目のシーケンス」の最後の出現を検索します。見つかった場合は、最後のペアの最初の ForwardIterator が返され、そうでない場合は、入力「他のペア」の最初の ForwardIterator が返されます。オーバーロードされたバージョンでは、equals 演算の代わりにユーザーが入力した演算子が使用されます。
Find_first_of: 指定された範囲内の「入力反復子の別のペアによってマークされた 2 番目のシーケンス」内の任意の要素の最初の出現を検索します。オーバーロードされたバージョンでは、ユーザー定義の演算子が使用されます。
find_if: find を実行するには、等号演算子の代わりに input 関数を使用します。
lower_bound: コンテナーの順序を破壊せずに指定された値を挿入できる、順序付けられたシーケンス範囲内の最初の位置を指す ForwardIterator を返します。オーバーロードされた関数はカスタム比較演算を使用します。
upper_bound: コンテナーの順序を破壊せずに、順序付けされたシーケンス範囲に値を挿入できる最後の位置を指す ForwardIterator を返します。この位置は、値より大きい値をマークします。オーバーロードされた関数はカスタム比較演算を使用します。
検索: 2 つの範囲を指定すると、ForwardIterator が返されます。検索が成功した場合は、最初の範囲内でサブシーケンス (2 番目の範囲) が初めて出現する位置を指します。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。
Search_n: 指定された範囲内で val が n 回出現する部分列を検索します。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。

<二> 並べ替えおよび一般的なアルゴリズム (14): 要素の並べ替え戦略を提供します。
inplace_merge: 2 つの順序付けられたシーケンスをマージし、結果のシーケンスは範囲の両端をカバーします。オーバーロードされたバージョンは、入力操作を使用してソートされます。
マージ: 2 つの順序付けされたシーケンスをマージし、別のシーケンスに保存します。オーバーロードされたバージョンではカスタム比較が使用されます。
nth_element: n 番目の要素より小さいすべての要素がその前に表示され、それより大きいすべての要素が後ろに表示されるように、範囲内のシーケンスを並べ替えます。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。
partial_sort: ソートされた要素の数が範囲内に収まるようにシーケンスを部分的にソートします。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。
Partial_sort_copy:partial_sort と似ていますが、ソートされたシーケンスを別のコンテナーにコピーします。
パーティション: 指定された範囲内の要素を並べ替え、入力関数を使用し、結果が true の要素を結果が false の要素の前に配置します。
Random_shuffle: 指定された範囲内の要素の順序をランダムに調整します。オーバーロードされたバージョンでは、乱数生成操作が入力されます。
reverse: 指定された範囲内の要素を逆順に並べ替えます。
reverse_copy: reverse と似ていますが、結果を別のコンテナに書き込みます。
回転: 指定された範囲内の要素をコンテナーの最後に移動します。中央が指す要素がコンテナーの最初の要素になります。
rotate_copy: 回転と似ていますが、結果を別のコンテナに書き込みます。
sort: 指定された範囲内の要素を昇順に並べ替えます。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。
steady_sort:sort に似ていますが、等しい要素間の順序関係が保持されます。
steady_partition: パーティションに似ていますが、コンテナー内の相対的な順序が保持されることは保証されません。

<三>削除と置換アルゴリズム (15)
copy: シーケンスのコピー
copy_backward: copy と同じですが、要素は逆の順序でコピーされます。
iter_swap: 2 つの ForwardIterator の値を交換します。
削除: 指定された要素と等しい、指定された範囲内のすべての要素を削除します。この関数は実際の削除関数ではないことに注意してください。組み込み関数は、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: 2 つのオブジェクトに格納されている値を交換します。
swap_range: 指定された範囲内の要素を別のシーケンス要素値と交換します。
unique: シーケンスから重複した要素を削除します。削除と同様に、実際に要素を削除することはできません。オーバーロードされたバージョンではカスタム比較操作が使用されます。
unique_copy: unique と似ていますが、結果を別のコンテナに出力します。

<四>順列と組み合わせのアルゴリズム (2): 特定の順序で指定されたセットのすべての可能な順列と組み合わせを計算します
next_permutation: 現在の範囲内の順列を取り出し、次の順列に並べ替えます。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。
prev_permutation: 指定された範囲のシーケンスを取り出し、前のシーケンスに並べ替えます。前のシーケンスがない場合は false を返します。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。

<五>算術アルゴリズム (4)
Accumulated: イテレータで特定されるシーケンスセグメントの要素の合計を、val で指定される初期値に加算します。オーバーロードされたバージョンでは加算は実行されませんが、渡された二項演算子が要素に適用されます。
partial_sum: 各要素の値が、指定された範囲内のその位置より前にあるすべての要素の合計を表す新しいシーケンスを作成します。オーバーロードされたバージョンでは、加算の代わりにカスタム操作が使用されます。
inner_product: 2 つのシーケンスの内積 (対応する要素を乗算してから合計) を実行し、その内積を入力初期値に加算します。オーバーロードされたバージョンでは、ユーザー定義のアクションが使用されます。
隣接差: 新しいシーケンスを作成します。新しいシーケンス内の各新しい値は、現在の要素と前の要素の差を表します。オーバーロードされたバージョンは、指定された二項演算を使用して隣接する要素間の差分を計算します。

<六>生成と突然変異のアルゴリズム (6)
fill: フラグ範囲内のすべての要素に入力値を代入します。
fill_n: first から first+n までの範囲内のすべての要素に入力値を代入します。
for_each: 指定された関数を使用して、指定された範囲内のすべての要素に順番に反復的にアクセスし、指定された関数タイプを返します。この関数はシーケンス内の要素を変更してはなりません。
生成: 入力関数を継続的に呼び出して、指定された範囲を埋めます。
Generate_n: 生成関数と同様に、指定されたイテレータから始まる n 個の要素を埋めます。
変換: 指定された範囲内の各要素に入力操作を適用し、新しいシーケンスを生成します。オーバーロードされたバージョンは、要素のペアを操作し、もう一方の要素は別の入力シーケンスから取得されます。結果は指定したコンテナに出力されます。

等しい: 2 つのシーケンスがロゴ範囲内の要素と等しい場合、TRUE に戻ります。オーバーロードされたバージョンでは、デフォルトの等号演算子の代わりに入力演算子が使用されます。 <七> include: 最初に指定された範囲内のすべての要素が 2 番目の範囲に含まれるかどうかを決定し、基礎となる要素の < 演算子を使用して true を正常に返します。オーバーロードされたバージョンはユーザー入力関数を使用します。
lexicographical_compare: 2 つのシーケンスを比較します。オーバーロードされたバージョンでは、ユーザー定義の比較演算が使用されます。
max: 2 つの要素のうち大きい方を返します。オーバーロードされたバージョンではカスタム比較操作が使用されます。 <操作符，成功返回true。重载版本使用用户输入的函数。
max_element: シーケンス内の最大の要素を指す ForwardIterator を返します。オーバーロードされたバージョンではカスタム比較操作が使用されます。
min: 2 つの要素のうち小さい方を返します。オーバーロードされたバージョンではカスタム比較操作が使用されます。
min_element: シーケンス内の最小の要素を指す ForwardIterator を返します。オーバーロードされたバージョンではカスタム比較操作が使用されます。
不一致: 2 つのシーケンスを並行して比較し、最初の不一致位置を指摘し、最初の不一致要素の位置をマークする反復子のペアを返します。それらがすべて一致する場合は、各コンテナーの最後を返します。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。

set_union: 2 つのシーケンス内のすべての非反復要素を含む順序付けされたシーケンスを構築します。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。 <八> set_intersection: 要素が両方のシーケンスに存在する順序付けされたシーケンスを構築します。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。
Set_difference: 最初のシーケンスには存在するが 2 番目のシーケンスには存在しない要素のみを保持する順序付けされたシーケンスを構築します。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。
Set_metric_difference: 2 つのシーケンスの対​​称差分 (和集合) を取る順序付けされたシーケンスを構築します。

make_heap: 指定された範囲の要素からヒープを生成します。オーバーロードされたバージョンではカスタム比較操作が使用されます。 <九> Pop_heap: 実際にはヒープから最大の要素をポップしませんが、ヒープの順序を変更します。 first と last-1 を交換し、ヒープを再生成します。コンテナの back を使用して「ポップされた」要素にアクセスすることも、pop_back を使用して実際に要素を削除することもできます。オーバーロードされたバージョンでは、カスタム比較操作が使用されます。
Push_heap: first to last-1 が有効なヒープであり、ヒープに追加される要素が last-1 の位置に格納され、ヒープが再生成されると仮定します。この関数を指定する前に、要素をコンテナーに挿入する必要があります。オーバーロードされたバージョンでは、指定された比較演算が使用されます。
sort_heap: シーケンスが順序付けされたヒープであると仮定して、指定された範囲内のシーケンスを並べ替えます。オーバーロードされたバージョンではカスタム比較操作が使用されます。

4. アダプター

STL は、queue、priority_queue、stack の 3 つのコンテナー アダプターを提供します。これらのアダプターは、特定のシーケンス コンテナーをベクター、リスト、および両端キューでラップするラッパーです。注: アダプターはイテレーターを提供しないため、複数の要素を同時に挿入または削除することはできません。以下に各アダプターの概要を示します。

#include

template class stack;
< typename T, typename Container=deque >
スタックの基礎となるモデルとして、3 つの標準的な順次コンテナー vecotr、deque (デフォルト)、および list のいずれかを使用できます。

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< int, vector, greater >
priority_queue< int, list, greater >

标准库默认使用元素类型的<操作符来确定它们之间的优先级关系，用法有三：（下文转自http://www.cnblogs.com/vvilp/articles/1504436.html）

优先队列第一种用法，通过默认使用的<操作符可知在整数中元素大的优先级高。

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编译不通过。