ホーム | ブログ | C++辞典 | サイトマップ | FAQ | 掲示板 | リンク集
メイン・メニュー
インデックス
プログラミング
その他

#navi(<algorithm>ヘッダ)

**整列及びその関連演算 (sorting and related operations) [#d655c20b]

&aname(sort);
***sort [#i2ccb711]
整列

''形式''~
&nbsp; template<class [[RandomAccessIterator>反復子#random-access]]>~
&nbsp; &nbsp; void ''sort''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''');~

&nbsp; template<class [[RandomAccessIterator>反復子#random-access]], class Compare>~
&nbsp; &nbsp; void ''sort''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''', Compare '''comp''');~

''[[引数]]''~
  '''first''':  整列対象となる列の先頭要素を指す [[RandomAccessIterator>反復子#random-access]]~
  '''last''':  整列対象となる列の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 なし

''解説''~
 区間 ['''first''', '''last''') で定義される列を整列する。

''計算量''~
 平均的に '''N''' log '''N''' 回の比較が行われる。ただし、'''N''' は '''last''' - '''first''' である。

''参照''~
→ [[stable_sort>#stable_sort]]

&aname(stable_sort);
***stable_sort [#u610894d]
安定な整列

''形式''~
&nbsp; template<class [[RandomAccessIterator>反復子#random-access]]>~
&nbsp; &nbsp; void ''stable_sort''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''');

&nbsp; template<class [[RandomAccessIterator>反復子#random-access]], class Compare>~
&nbsp; &nbsp; void ''stable_sort''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Compare '''comp''');

''[[引数]]''~
  '''first''':  整列対象となる列の先頭要素を指す [[RandomAccessIterator>反復子#random-access]]~
  '''last''':  整列対象となる列の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 なし

''解説''~
 区間 ['''first''', '''last''') で定義される列を整列する。同値の要素の順序は整列後も保存される。

''計算量''~
 多くとも '''N''' (log '''N''')
&htmlinsert(sup2.html); 
回の比較を行う。メモリが十分にある場合には '''N''' log '''N''' 回の比較が行われる。ただし、'''N''' は '''last''' - '''first''' である。

''参照''~
→ [[sort>#sort]]

&aname(partial_sort);
***partial_sort [#h9b2ba01]
部分整列

''形式''~
&nbsp; template<class [[RandomAccessIterator>反復子#random-access]]>~
&nbsp; &nbsp; void ''partial_sort''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''middle''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[RandomAccessIterator>反復子#random-access]] '''last''');

&nbsp; template<class [[RandomAccessIterator>反復子#random-access]], class Compare>~
&nbsp; &nbsp; void ''partial_sort'']([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''middle''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[RandomAccessIterator>反復子#random-access]] '''last''', Compare '''comp''');

''[[引数]]''~
  '''first''':  整列対象となる列の先頭要素を指す [[RandomAccessIterator>反復子#random-access]]~
  '''middle''':  整列結果となる列の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''last''':  整列対象となる列の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 なし

''解説''~
 区間 ['''first''', '''last''') を整列した場合の最初の '''middle''' - '''first''' 個の要素を、区間 ['''first''', '''middle''') に格納する。実行後の区間 ['''middle''', '''last''') の内容は[[未規定>未規定の動作]]である。

''計算量''~
 ほぼ ('''last''' - '''first''')×log('''middle''' - '''first''') 回の比較を行う。

''参照''~
→ [[partial_sort_copy>#partial_sort_copy]]

&aname(partial_sort_copy);
***partial_sort_copy [#nc0eebc3]
部分整列とコピー

''形式''~
&nbsp; template<class [[InputIterator>反復子#input]], class [[RandomAccessIterator>反復子#random-access]]>~
&nbsp; &nbsp; [[RandomAccessIterator>反復子#random-access]]~
&nbsp; &nbsp; &nbsp; &nbsp; ''partial_sort_copy''([[InputIterator>反復子#input]] '''first''', [[InputIterator>反復子#input]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[RandomAccessIterator>反復子#random-access]] '''result_first''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[RandomAccessIterator>反復子#random-access]] '''result_last''');~

&nbsp; template<class [[InputIterator>反復子#input]], class [[RandomAccessIterator>反復子#random-access]], class Compare>~
&nbsp; &nbsp; [[RandomAccessIterator>反復子#random-access]]~
&nbsp; &nbsp; &nbsp; &nbsp; ''partial_sort_copy''([[InputIterator>反復子#input]] '''first''', [[InputIterator>反復子#input]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[RandomAccessIterator>反復子#random-access]] '''result_first''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[RandomAccessIterator>反復子#random-access]] '''result_last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Compare '''comp''');~

''[[引数]]''~
  '''first''':  元の列の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last''':  元の列の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''result_first''':  出力先となる列の先頭要素を指す [[RandomAccessIterator>反復子#random-access]]~
  '''result_last''':  出力先となる列の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 結果の列の終端要素の次を指す[[反復子]]を返す。

''解説''~
 '''first''' から始まる、区間 ['''first''', '''last''') または区間 ['''result_first''', '''result_last''') のうちの小さい方の要素数を整列して、'''result_first''' から始まる列に出力する。

''計算量''~
 ほぼ ('''last''' - '''first''')×log( min( ('''last''' - '''first'''), ('''result_last''' - '''result_first''') ) ) 回の比較が行われる。

''参照''~
→ [[partial_sort>#partial_sort]]

&aname(nth_element);
***nth_element [#l5e12654]
基準位置による列の分割

''形式''~
&nbsp; template<class [[RandomAccessIterator>反復子#random-access]]>~
&nbsp; &nbsp; void ''nth_element''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''nth''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[RandomAccessIterator>反復子#random-access]] '''last''');

&nbsp; template<class [[RandomAccessIterator>反復子#random-access]], class Compare>~
&nbsp; &nbsp; void ''nth_element''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''nth''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[RandomAccessIterator>反復子#random-access]] '''last''', Compare '''comp''');

''[[引数]]''~
  '''first''':  分割対象となる列の先頭要素を指す [[RandomAccessIterator>反復子#random-access]]~
  '''nth''':  分割の基準位置を指す [[RandomAccessIterator>反復子#random-access]]~
  '''last''':  分割対象となる列の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 なし

''解説''~
 区間 ['''first''', '''nth''') にある任意の[[反復子]] '''iter1''' が、区間 ['''nth''', '''last''') にある任意の反復子 '''iter2''' に対して、最初の形式では !(*'''iter1''' > *'''iter2''') が、2 番目の形式では '''comp'''(*'''iter2''', *'''iter1''') == false が成立するように再配置する。'''nth''' の位置には、列全体を整列したときにその位置に来る要素が格納される。

''計算量''~
 平均で線形である。

&aname(lower_bound);
***lower_bound [#ad89ff0a]
順を乱さずに要素を挿入できる下限

''形式''~
&nbsp; template<class [[ForwardIterator>反復子#forward]], class T>~
&nbsp; &nbsp; [[ForwardIterator>反復子#forward]] ''lower_bound''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;const T& '''value''');~

&nbsp; template<class [[ForwardIterator>反復子#forward]], class T, class Compare>~
&nbsp; &nbsp; [[ForwardIterator>反復子#forward]] ''lower_bound''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;const T& '''value''', Compare '''comp''');~

''[[引数]]''~
  '''first''':  探索対象となる列の先頭要素を指す [[ForwardIterator>反復子#forward]]~
  '''last''':  探索対象となる列の終端要素の次を指す [[ForwardIterator>反復子#forward]]~
  '''value''':  探索する値。型 T は LessThanComparable~
  '''comp''':  比較関数~

''[[返却値]]''~
 順を乱さずに '''value''' を挿入できる最初の位置 (下限) を指す[[反復子]]を返す。

''解説''~
 区間 ['''first''', '''last''') にある任意の[[反復子]] '''iter''' の位置に、順序を乱さずに要素 '''value''' を挿入することができる最初の位置を探索する。順序を乱さずに挿入ができるとは、最初の形式では !(*'''iter''' < '''value''') && !('''value''' < *'''iter''') が、2 番目の形式では !'''comp'''(*'''iter''', '''value''') && !'''comp'''('''value''',  *'''iter''') が成立することを意味する。

''計算量''~
 多くとも log('''last''' - '''first''') + 1 回の比較が行われる。

''参照''~
→ [[upper_bound>#upper_bound]], [[equal_range>#equal_range]]

&aname(upper_bound);
***upper_bound [#cb1508e7]
順を乱さずに要素を挿入できる上限

''形式''~
&nbsp; template<class [[ForwardIterator>反復子#forward]], class T>~
&nbsp; &nbsp; [[ForwardIterator>反復子#forward]] ''upper_bound''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;const T& '''value''');~

&nbsp; template<class [[ForwardIterator>反復子#forward]], class T, class Compare>~
&nbsp; &nbsp; [[ForwardIterator>反復子#forward]] ''upper_bound''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;const T& '''value''', Compare '''comp''');~

''[[引数]]''~
  '''first''':  探索対象となる列の先頭要素を指す [[ForwardIterator>反復子#forward]]~
  '''last''':  探索対象となる列の終端要素の次を指す [[ForwardIterator>反復子#forward]]~
  '''value''':  探索する値。型 T は LessThanComparable~
  '''comp''':  比較関数~

''[[返却値]]''~
 順を乱さずに '''value''' を挿入できる最後の位置 (上限) を指す[[反復子]]を返す。

''解説''~
 区間 ['''first''', '''last''') にある任意の[[反復子]] '''iter''' の位置に、順序を乱さずに要素 '''value''' を挿入することができる最後の位置を探索する。順序を乱さずに挿入ができるとは、最初の形式では !(*'''iter''' < '''value''') && !('''value''' < *'''iter''') が、2 番目の形式では !'''comp'''(*'''iter''', '''value''') && !'''comp'''('''value''',  *'''iter''') が成立することを意味する。

''計算量''~
 多くとも log('''last''' - '''first''') + 1 回の比較が行われる。

''参照''~
→ [[lower_bound>#lower_bound]], [[equal_range>#equal_range]]

&aname(equal_range);
***equal_range [#oc0683c5]
順を乱さずに要素を挿入できる範囲

''形式''~
&nbsp; template<class [[ForwardIterator>反復子#forward]], class T>~
&nbsp; &nbsp; pair<[[ForwardIterator>反復子#forward]], [[ForwardIterator>反復子#forward]]>~
&nbsp; &nbsp; &nbsp; &nbsp; ''equal_range''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''', const T& '''value''');~

&nbsp; template<class [[ForwardIterator>反復子#forward]], class T, class Compare>~
&nbsp; &nbsp; pair<[[ForwardIterator>反復子#forward]], [[ForwardIterator>反復子#forward]]>~
&nbsp; &nbsp; &nbsp; &nbsp; ''equal_range''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''', const T& '''value''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Compare '''comp''');~

''[[引数]]''~
  '''first''':  探索対象となる列の先頭要素を指す [[ForwardIterator>反復子#forward]]~
  '''last''':  探索対象となる列の終端要素の次を指す [[ForwardIterator>反復子#forward]]~
  '''value''':  探索する値。型 T は LessThanComparable~
  '''comp''':  比較関数~

''[[返却値]]''~
 返却値のメンバ .first には '''value''' を順を乱さずに要素を挿入できる最初の位置 (下限) を、.second には最後の位置 (上限) が格納される。対応する範囲が見つからなかった場合は .first および .second には '''last''' が格納される。

''解説''~
 区間 ['''first''', '''last''') にある任意の[[反復子]] '''iter''' の位置に、順序を乱さずに要素 '''value''' を挿入することができる最大の範囲を返す。順序を乱さずに挿入ができるとは、最初の形式では !(*'''iter''' < '''value''') && !('''value''' < *'''iter''') が、2 番目の形式では !'''comp'''(*'''iter''', '''value''') && !'''comp'''('''value''',  *'''iter''') が成立することを意味する。

''計算量''~
 多くとも 2×log('''last''' - '''first''') + 1 回の比較が行われる。

''参照''~
→ [[lower_bound>#lower_bound]], [[upper_bound>#upper_bound]]

&aname(binary_search);
***binary_search [#i3314fda]
二分探索

''形式''~
&nbsp; template<class [[ForwardIterator>反復子#forward]], class T>~
&nbsp; &nbsp; bool ''binary_search''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''', const T& '''value''');~

&nbsp; template<class [[ForwardIterator>反復子#forward]], class T, class Compare>~
&nbsp; &nbsp; bool ''binary_search''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''', const T& '''value''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Compare '''comp''');~

''[[引数]]''~
  '''first''':  探索対象となる列の先頭要素を指す [[ForwardIterator>反復子#forward]]~
  '''last''':  探索対象となる列の終端要素の次を指す [[ForwardIterator>反復子#forward]]~
  '''value''':  探索する値。型 T は LessThanComparable~
  '''comp''':  比較関数~

''[[返却値]]''~
 探索に成功すれば true を、失敗すれば false を返す。

''解説''~
 区間 ['''first''', '''last''') にある[[反復子]] '''iter''' に対して、最初の形式では !(*'''iter''' < '''value''') && !('''value''' < *'''iter''') が、2 番目の形式では '''comp'''(*'''iter''', '''value''') == false && '''comp'''('''value''',  *'''iter''') == false が成立する要素を探索する。

''計算量''~
 多くとも log('''last''' - '''first''') + 2 回の比較が行われる。

''参照''~
→ [[bsearch><cstdlib>ヘッダ#bsearch]]

&aname(merge);
***merge [#p96ceabb]
併合

''形式''~
&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]]>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''merge''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[OutputIterator>反復子#output]] '''result''');~

&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]],~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; class Compare>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''merge''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[OutputIterator>反復子#output]] '''result''', Compare '''comp''');~

''[[引数]]'''~
  '''first1''':  第 1 区間の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last1''':  第 1 区間の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''first2''':  第 2 区間の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last2''':  第 2 区間の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''result''':  結果集合の出力先の先頭要素を指す [[OutputIterator>反復子#output]]~
  '''comp''':  比較関数~

''[[返却値]]'''~
 結果集合の終端要素の次を指す[[反復子]]を返す。

''解説''~
 2 つの整列された区間を併合する。構築された集合は昇順に整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。両方の区間に存在する同じ値の要素は、第 1 区間にあったものが第 2 区間にあったものより前に格納される。

''計算量''~
 多くとも ('''last1''' - '''first1''') + ('''last2''' - '''first2''') - 1 回の比較が行われる。

''参照''~
→ [[inplace_merge>#inplace_merge]]

&aname(inplace_merge);
***inplace_merge [#y2f644d3]
連続区間の併合

''形式''~
&nbsp; template<class [[BidirectionalIterator>反復子#bidirectional]]>~
&nbsp; &nbsp; void ''inplace_merge''([[BidirectionalIterator>反復子#bidirectional]] '''first''', [[BidirectionalIterator>反復子#bidirectional]] '''middle''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[BidirectionalIterator>反復子#bidirectional]] '''last''');~

&nbsp; template<class [[BidirectionalIterator>反復子#bidirectional]], class Compare>~
&nbsp; &nbsp; void ''inplace_merge''([[BidirectionalIterator>反復子#bidirectional]] '''first''', [[BidirectionalIterator>反復子#bidirectional]] '''middle''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[BidirectionalIterator>反復子#bidirectional]] '''last''', Compare '''comp''');~

''[[引数]]''~
  '''first''':  第 1 区間の先頭要素を指す [[BidirectionalIterator>反復子#bidirectional]]~
  '''middle''':  第 1 区間の終端要素の次であり、かつ第 2 区間の先頭要素を指す [[BidirectionalIterator>反復子#bidirectional]]~
  '''last''':  第 2 区間の終端要素の次を指す [[BidirectionalIterator>反復子#bidirectional]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 なし

''解説''~
 2 つの連続している整列された区間 ['''first''', '''middle''') および ['''middle''', '''last''') を併合し、結果を ['''first''', '''last''') に格納する。結果の区間は昇順に整列される。両方の区間に存在する同じ値の要素は、第 1 区間にあったものが第 2 区間にあったものより前に格納される。

''計算量''~
 メモリが十分にある場合には ('''last''' - '''first''') - 1 回の比較が行われる。メモリが十分でない場合には '''N''' log '''N''' 回の比較を行う。ただし、'''N''' は '''last''' - '''first''' である。

''参照''~
→ [[merge>#merge]]

&aname(includes);
***includes [#bfd44fba]
部分集合の判別

''形式''~
&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]]>~
&nbsp; &nbsp; bool ''includes''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2''');~

&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class Compare>~
&nbsp; &nbsp; bool ''includes''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2'''~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Compare '''comp''');~

''[[引数]]'''~
  '''first1''':  比較対象となる第 1 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last1''':  比較対象となる第 1 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''first2''':  比較対象となる第 2 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last2''':  比較対象となる第 2 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''result''':  結果集合の出力先の先頭要素を指す [[OutputIterator>反復子#output]]~
  '''comp''':  比較関数~

''[[返却値]]'''~
 第 2 集合が第 1 集合の部分集合であれば true を、そうでなければ false を返す。

''解説''~
 区間 ['''first2''', '''last2''') で定義される集合のすべての要素が区間 ['''first1''', '''last1''') で定義される集合に含まれるかどうかを判別する。

''計算量''~
 多くとも 2×( ('''last1''' - '''first1''') + ('''last2''' - '''first2''') ) - 1 回の比較が行われる。

&aname(set_union);
***set_union [#jd0f466f]
集合の和

''形式''~
&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]]>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''set_union''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2'''~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[OutputIterator>反復子#output]] '''result''');~

&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]],~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; class Compare>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''set_union''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2'''~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[OutputIterator>反復子#output]] '''result''', Compare '''comp''');~

''[[引数]]'''~
  '''first1''':  比較対象となる第 1 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last1''':  比較対象となる第 1 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''first2''':  比較対象となる第 2 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last2''':  比較対象となる第 2 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''result''':  結果集合の出力先の先頭要素を指す [[OutputIterator>反復子#output]]~
  '''comp''':  比較関数~

''[[返却値]]'''~
 結果集合の終端要素の次を指す[[反復子]]を返す。

''解説''~
 2 つの区間の和集合、すなわち、区間 ['''first1''', '''last1''') で定義される第 1 集合および区間 ['''first2''', '''last2''') で定義される第 2 集合のいずれかに存在する要素の集合を構築する。構築された集合は整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。

''計算量''~
 多くとも 2×( ('''last1''' - '''first1''') + ('''last2''' - '''first2''') ) - 1 回の比較が行われる。

''参照''~
→ [[set_intersection>#set_intersection]]

&aname(set_intersection);
***set_intersection [#j84a4e5b]
集合の積

''形式''~
&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]]>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''set_intersection''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2'''~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[OutputIterator>反復子#output]] '''result''');~

&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]],~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; class Compare>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''set_intersection''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2'''~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[OutputIterator>反復子#output]] '''result''', Compare '''comp''');~

''[[引数]]'''~
  '''first1''':  比較対象となる第 1 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last1''':  比較対象となる第 1 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''first2''':  比較対象となる第 2 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last2''':  比較対象となる第 2 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''result''':  結果集合の出力先の先頭要素を指す [[OutputIterator>反復子#output]]~
  '''comp''':  比較関数~

''[[返却値]]'''~
 結果集合の終端要素の次を指す[[反復子]]を返す。

''解説''~
 2 つの区間の積集合、すなわち、区間 ['''first1''', '''last1''') で定義される第 1 集合および区間 ['''first2''', '''last2''') で定義される第 2 集合の両方に存在する要素の集合を構築する。構築された集合は整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。

''計算量''~
 多くとも 2×( ('''last1''' - '''first1''') + ('''last2''' - '''first2''') ) - 1 回の比較が行われる。

''参照''~
→ [[set_union>#set_union]]

&aname(set_difference);
***set_difference [#i312d9b2]
集合の差

''形式''~
&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]]>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''set_difference''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2'''~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[OutputIterator>反復子#output]] '''result''');~

&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]],~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; class Compare>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''set_difference''([[InputIterator1>反復子#input]] '''first1''', InoputIterator1 '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2'''~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[OutputIterator>反復子#output]] '''result''', Compare '''comp''');~

''[[引数]]'''~
  '''first1''':  比較対象となる第 1 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last1''':  比較対象となる第 1 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''first2''':  比較対象となる第 2 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last2''':  比較対象となる第 2 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''result''':  結果集合の出力先の先頭要素を指す [[OutputIterator>反復子#output]]~
  '''comp''':  比較関数~

''[[返却値]]'''~
 結果集合の終端要素の次を指す[[反復子]]を返す。

''解説''~
 区間 ['''first1''', '''last1''') で定義される第 1 集合に存在し、区間 ['''first2''', '''last2''') で定義される第 2 集合には存在しない要素を、'''result''' から始まる区間にコピーする。構築された集合は整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。

''計算量''~
 多くとも 2×( ('''last1''' - '''first1''') + ('''last2''' - '''first2''') ) - 1 回の比較が行われる。

''参照''~
→ [[set_symmetric_difference>#set_symmetric_difference]]

&aname(set_symmetric_difference);
***set_symmetric_difference [#xdf534dc]
集合の対称差

''形式''~
&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]]>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''set_symmetric_difference''([[InputIterator1>反復子#input]] '''first1''', [[InputIterator1>反復子#input]] '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2'''~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[OutputIterator>反復子#output]] '''result''');~

&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class [[OutputIterator>反復子#output]],~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; class Compare>~
&nbsp; &nbsp; [[OutputIterator>反復子#output]] ''set_symmetric_difference''([[InputIterator1>反復子#input]] '''first1''', [[InputIterator1>反復子#input]] '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2'''~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[OutputIterator>反復子#output]] '''result''', Compare '''comp''');~

''[[引数]]'''~
  '''first1''':  比較対象となる第 1 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last1''':  比較対象となる第 1 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''first2''':  比較対象となる第 2 集合の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last2''':  比較対象となる第 2 集合の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''result''':  結果集合の出力先の先頭要素を指す [[OutputIterator>反復子#output]]~
  '''comp''':  比較関数~

''[[返却値]]'''~
 結果集合の終端要素の次を指す[[反復子]]を返す。

''解説''~
 区間 ['''first1''', '''last1''') で定義される第 1 集合および区間 ['''first2''', '''last2''') で定義される第 2 集合のいずれかにのみ存在しない要素を、'''result''' から始まる区間にコピーする。構築された集合は整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。

''計算量''~
 多くとも 2×( ('''last1''' - '''first1''') + ('''last2''' - '''first2''') ) - 1 回の比較が行われる。

''参照''~
→ [[set_difference>#set_difference]]

&aname(push_heap);
***push_heap [#pf438c6b]
[[ヒープ]]に要素を追加

''形式''~
&nbsp; template<class [[RandomAccessIterator>反復子#random-access]]>~
&nbsp; &nbsp; void ''push_heap''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''');~

&nbsp; template<class [[RandomAccessIterator>反復子#random-access]], class Compare>~
&nbsp; &nbsp; void ''push_heap''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Compare '''comp''');~

''[[引数]]''~
  '''first''':  [[ヒープ]]の先頭要素を指す [[RandomAccessIterator>反復子#random-access]]~
  '''last''':  [[ヒープ]]の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 なし

''解説''~
 '''last''' - 1 の位置にある要素を移動し、区間 ['''first''', '''last''') を[[ヒープ]]にする。元の区間 ['''first''', '''last''') は正しいヒープでなければならない。

''計算量''~
 多くとも log('''last''' - '''first''') 回の比較が行われる。

''参照''~
→ [[pop_heap>#pop_heap]], [[make_heap>#make_heap]], [[sort_heap>#sort_heap]]

&aname(pop_heap);
***pop_heap [#d7f8de06]
[[ヒープ]]から要素を除去

''形式''~
&nbsp; template<class [[RandomAccessIterator>反復子#random-access]]>~
&nbsp; &nbsp; void ''pop_heap''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''');~

&nbsp; template<class [[RandomAccessIterator>反復子#random-access]], class Compare>~
&nbsp; &nbsp; void ''pop_heap''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Compare '''comp''');~

''[[引数]]''~
  '''first''':  [[ヒープ]]の先頭要素を指す [[RandomAccessIterator>反復子#random-access]]~
  '''last''':  [[ヒープ]]の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 なし

''解説''~
 '''first''' の位置にある要素と '''last''' - 1 の位置にある要素を交換し、区間 ['''first''', '''last''' - 1) を[[ヒープ]]にする。元の区間 ['''first''', '''last''') は正しいヒープでなければならない。

''計算量''~
 多くとも 2×log('''last''' - '''first''') 回の比較が行われる。

''参照''~
→ [[push_heap>#push_heap]], [[make_heap>#make_heap]], [[sort_heap>#sort_heap]]

&aname(make_heap);
***make_heap [#u1e529f6]
[[ヒープ]]の構築

''形式''~
&nbsp; template<class [[RandomAccessIterator>反復子#random-access]]>~
&nbsp; &nbsp; void ''make_heap''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''');~

&nbsp; template<class [[RandomAccessIterator>反復子#random-access]], class Compare>~
&nbsp; &nbsp; void ''make_heap''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Compare '''comp''');~

''[[引数]]''~
  '''first''':  [[ヒープ]]の先頭要素を指す [[RandomAccessIterator>反復子#random-access]]~
  '''last''':  [[ヒープ]]の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 なし

''解説''~
 区間 ['''first''', '''last''') から[[ヒープ]]を構築する。

''計算量''~
 多くとも 3×('''last''' - '''first''') 回の比較が行われる。

''参照''~
→ [[push_heap>#push_heap]], [[pop_heap>#pop_heap]], [[sort_heap>#sort_heap]]

&aname(sort_heap);
***sort_heap [#oda7922b]
[[ヒープ]]の整列

''形式''~
&nbsp; template<class [[RandomAccessIterator>反復子#random-access]]>~
&nbsp; &nbsp; void ''sort_heap''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''');~

&nbsp; template<class [[RandomAccessIterator>反復子#random-access]], class Compare>~
&nbsp; &nbsp; void ''sort_heap''([[RandomAccessIterator>反復子#random-access]] '''first''', [[RandomAccessIterator>反復子#random-access]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Compare '''comp''');~

''[[引数]]''~
  '''first''':  [[ヒープ]]の先頭要素を指す [[RandomAccessIterator>反復子#random-access]]~
  '''last''':  [[ヒープ]]の終端要素の次を指す [[RandomAccessIterator>反復子#random-access]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 なし

''解説''~
 区間 ['''first''', '''last''') で定義される[[ヒープ]]を整列する。整列は安定ではない。

''計算量''~
 多くとも '''N''' log '''N''' 回の比較が行われる。ただし、'''N''' は '''last''' - '''first''' である。

''参照''~
→ [[push_heap>#push_heap]], [[pop_heap>#pop_heap]], [[make_heap>#make_heap]]

&aname(min);
***min [#s8ace75b]
最小値

''形式''~
&nbsp; template<class T> const T& min(const T& '''a''', const T& '''b''');~

&nbsp; template<class T, class Compare>~
&nbsp; &nbsp; const T& ''min''(const T& '''a''', const T& '''b''', Compare '''comp''');~

''[[引数]]''~
  '''a''':  ~
  '''b''':  ~
  '''comp''':  比較関数。型 T は LessThanComparable かつ CopyConstructible~

''[[返却値]]''~
 最小値を返す。

''解説''~
 '''a''' と '''b''' を比較し、小さい方を返す。最初の形式では比較に [[< 演算子>関係演算子#less]]を、2 番目の形式では '''comp''' を使用する。'''a''' と '''b''' が等しい場合は '''a''' を返す。

''参照''~
→ [[max>#max]]

&aname(max);
***max [#t9fad70b]
最大値

''形式''~
&nbsp; template<class T> const T& max(const T& '''a''', const T& '''b''');~

&nbsp; template<class T, class Compare>~
&nbsp; &nbsp; const T& ''max''(const T& '''a''', const T& '''b''', Compare '''comp''');~

''[[引数]]''~
  '''a''':  ~
  '''b''':  ~
  '''comp''':  比較関数。型 T は LessThanComparable かつ CopyConstructible~

''[[返却値]]''~
 最大値を返す。

''解説''~
 '''a''' と '''b''' を比較し、大きい方を返す。最初の形式では比較に [[< 演算子>関係演算子#less]]を、2 番目の形式では '''comp''' を使用する。'''a''' と '''b''' が等しい場合は '''a''' を返す。

''参照''~
→ [[min>#min]]

&aname(min_element);
***min_element [#m5ce69f6]
最小要素の探索

''形式''~
&nbsp; template<class [[ForwardIterator>反復子#forward]]>~
&nbsp; &nbsp; [[ForwardIterator>反復子#forward]] ''min_element''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''');~

&nbsp; template<class [[ForwardIterator>反復子#forward]], class Compare>~
&nbsp; &nbsp; [[ForwardIterator>反復子#forward]] ''min_element''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Comapre '''comp''');~

''[[引数]]''~
  '''first''':  探索対象の先頭要素を指す [[ForwardIterator>反復子#forward]]~
  '''last''':  探索対象の終端要素の次を指す [[ForwardIterator>反復子#forward]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 最小要素を指す[[反復子]]を返す。'''first''' == '''last''' の場合は '''last''' を返す。 

''解説''~
 区間 ['''first''', '''last''') 内の[[反復子]] '''iter1''' であり、任意の[[反復子]] '''iter2''' に対して、!(*'''iter2''' < *'''iter1''') または '''comp'''(*'''iter2''', *'''iter1''') == false が成立する最初の '''iter1''' を探索する。

''計算量''~
 ちょうど max( ('''last''' - '''first''') - 1, 0) ) 回比較が行われる。

''参照''~
→ [[max_element>#max_element]]

&aname(max_element);
***max_element [#a94a5c32]
最大要素の探索

''形式''~
&nbsp; template<class [[ForwardIterator>反復子#forward]]>~
&nbsp; &nbsp; [[ForwardIterator>反復子#forward]] ''max_element''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''');~

&nbsp; template<class [[ForwardIterator>反復子#forward]], class Compare>~
&nbsp; &nbsp; [[ForwardIterator>反復子#forward]] ''max_element''([[ForwardIterator>反復子#forward]] '''first''', [[ForwardIterator>反復子#forward]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Comapre '''comp''');~

''[[引数]]''~
  '''first''':  探索対象の先頭要素を指す [[ForwardIterator>反復子#forward]]~
  '''last''':  探索対象の終端要素の次を指す [[ForwardIterator>反復子#forward]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 最大要素を指す[[反復子]]を返す。'''first''' == '''last''' の場合は '''last''' を返す。 

''解説''~
 区間 ['''first''', '''last''') 内の[[反復子]] '''iter1''' であり、任意の[[反復子]] '''iter2''' に対して、!(*'''iter1''' < *'''iter2''') または '''comp'''(*'''iter1''', *'''iter2''') == false が成立する最初の '''iter1''' を探索する。

''計算量''~
 ちょうど max( ('''last''' - '''first''') - 1, 0) ) 回比較が行われる。

''参照''~
→ [[min_element>#min_element]]

&aname(lexicographical_compare);
***lexicographical_compare [#q04f134b]
辞書純比較

''形式''~
&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]]>~
&nbsp; &nbsp; bool ''lexicographical_compare'']([[InputIterator1>反復子#input]] '''first1''', [[InputIterator1>反復子#input]] '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2''');~

&nbsp; template<class [[InputIterator1>反復子#input]], class [[InputIterator2>反復子#input]], class Compare>~
&nbsp; &nbsp; bool ''lexicographical_compare''([[InputIterator1>反復子#input]] '''first1''', [[InputIterator1>反復子#input]] '''last1''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[InputIterator2>反復子#input]] '''first2''', [[InputIterator2>反復子#input]] '''last2''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Compare '''comp''');~

''[[引数]]''~
  '''first1''':  比較対象となる一方の列の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last1''':  比較対象となる一方の列の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''first2''':  比較対象となる他方の列の先頭要素を指す [[InputIterator>反復子#input]]~
  '''last2''':  比較対象となる他方の列の終端要素の次を指す [[InputIterator>反復子#input]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 区間 ['''first1''', '''last1''') の列が区間 ['''first2''', '''last2''') の列より小さい場合は true を、そうでなければ false を返す。 

''解説''~
 区間 ['''first1''', '''last1''') で定義される列と区間 ['''first2''', '''last2''')で定義される列を辞書順で比較する。最初の形式では、比較には [[< 演算子>関係演算子#less]]を使用し、2 番目の形式では '''comp''' を使用する。

''計算量''~
 多くとも 2×min( ('''last1''' - '''first1'''), ('''last2''' - '''first2''') ) 回の比較を行う。

&aname(next_permutation);
***next_permutation [#x68034f8]
次の順列

''形式''~
&nbsp; template<class [[BidirectionalIterator>反復子#bidirectional]]>~
&nbsp; &nbsp; bool ''next_permutation''([[BidirectionalIterator>反復子#bidirectional]] '''first''', [[BidirectionalIterator>反復子#bidirectional]] '''last''');~

&nbsp; template<class [[BidirectionalIterator>反復子#bidirectional]], class Compare>~
&nbsp; &nbsp; bool ''next_permutation''([[BidirectionalIterator>反復子#bidirectional]] '''first''', [[BidirectionalIterator>反復子#bidirectional]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Compare '''comp''');~

''[[引数]]''~
  '''first''':  先頭要素を指す [[BidirectionalIterator>反復子#bidirectional]]~
  '''last''':  終端要素の次を指す [[BidirectionalIterator>反復子#bidirectional]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 次の順列が存在する場合は true を、そうでなければ false を返す。

''解説''~
 区間 ['''first''', '''last''') の列を前の順列に変換する。次の順列とは、[[< 演算子>関係演算子#less]]または[[述語]] '''comp''' によって辞書順に整列した場合に直前の位置に来る列である。次の順列が存在しない場合、昇順に整列した列に変換する。

''計算量''~
 多くとも ('''last''' - '''first''') / 2 の交換が行われる。

''参照''~
→ [[prev_permutation>#prev_permutation]]

&aname(prev_permutation);
***prev_permutation [#i0c378a1]
前の順列

''形式''~
&nbsp; template<class [[BidirectionalIterator>反復子#bidirectional]]>~
&nbsp; &nbsp; bool ''prev_permutation''([[BidirectionalIterator>反復子#bidirectional]] '''first''', [[BidirectionalIterator>反復子#bidirectional]] '''last''');~

&nbsp; template<class [[BidirectionalIterator>反復子#bidirectional]], class Compare>~
&nbsp; &nbsp; bool ''prev_permutation''([[BidirectionalIterator>反復子#bidirectional]] '''first''', [[BidirectionalIterator>反復子#bidirectional]] '''last''',~
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Compare '''comp''');~

''[[引数]]''~
  '''first''':  先頭要素を指す [[BidirectionalIterator>反復子#bidirectional]]~
  '''last''':  終端要素の次を指す [[BidirectionalIterator>反復子#bidirectional]]~
  '''comp''':  比較関数~

''[[返却値]]''~
 前の順列が存在する場合は true を、そうでなければ false を返す。

''解説''~
 区間 ['''first''', '''last''') の列を前の順列に変換する。前の順列とは、[[< 演算子>関係演算子#less]]または[[述語]] '''comp''' によって辞書順に整列した場合に直前の位置に来る列である。前の順列が存在しない場合には、降順に整列した列に変換する。

''計算量''~
 多くとも ('''last''' - '''first''') / 2 の交換が行われる。

''参照''~
→ [[next_permutation>#next_permutation]]


トップ   一覧 単語検索   ヘルプ   最終更新のRSS
 ホーム | プロフィール | メール | ログイン | 管理
Copyright © 2005-2009 by TAKAGI Nobuhisa