ホーム | ブログ | C++辞典 | サイトマップ | FAQ | 掲示板 | リンク集
メイン・メニュー
インデックス
プログラミング
その他
Top / <algorithm>ヘッダ / 25.2更新を伴う列演算


更新を伴う列演算 (mutating sequence operations)

copy

列のコピー

形式
namespace std {
  template<class InputIterator, class OutputIterator>
    OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
}

引数
  first:  コピー元である列の先頭要素を指す InputIterator
  last:  コピー元である列の終端要素の次を指す InputIterator
  result:  コピー先である列の先頭要素を指す OutputIterator

返却値
 コピー先である列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) から区間 [result, result + (last - first)) へ、first から順に各要素をコピーする。result は区間 [first, last) にあってはならない。

計算量
 ちょうど last - first 回の代入を行う。

参照
copy_backward

copy_backward

列の逆方向コピー

形式
namespace std {
  template<class BidirectionalIterator1, class BidirectionalIterator2>
    BidirectionalIterator2 copy_backward
                                           (BidirectionalIterator first, BidirectionalIterator last,
                                            BidirectionalIterator result);
}

引数
  first:  コピー元である列の先頭要素を指す BidirectionalIterator
  last:  コピー元である列の終端要素の次を指す BidirectionalIterator
  result:  コピー先である列の終端要素の次を指す BidirectionalIterator

返却値
 コピー先である列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) から区間 [result - (last - first), result) へ、last - 1 から順に first まで各要素をコピーする。result は区間 [first, last) にあってはならない。

参考
last が区間 [result - (last - first), result) にある場合には、copy 関数より copy_backward 関数を使う方がよい。

計算量
 ちょうど last - first 回の代入を行う。

参照
copy_backward

swap

値の交換

形式
namespace std {
  template<class T> void swap(T& a, T& b);
}

引数
  a:  交換対象のオブジェクトへの参照
  b:  交換対象のオブジェクトへの参照

返却値
 なし

解説
 2 つの実引数 a および b に格納されている値を交換する。

参照
swap_ranges, iter_swap

swap_ranges

列の各要素の値交換

形式
namespace std {
  template<class ForwardIterator1, class ForwardIterator2>
    ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                                                        ForwardIterator2 first2);
}

引数
  first1:  対象となる一方の列の先頭要素を指す ForwardIterator
  last1:  対象となる一方の列の終端要素の次を指す ForwardIterator
  first2:  対象となる他方の列の先頭要素を指す ForwardIterator

返却値
 (first2 + (last1 - first1)) を返す。

解説
 区間 [first1, last1) で定義される列および区間 [first2, first2 + (last1 - first1)) で定義される列のそれぞれの要素の値を交換する。具体的には、n < (last1 - first) である負でない整数値 n に対して、swap(*(first1 + n), *(first2 + n)) を実行する。交換対象となる 2 つのの区間は重なっていてはならない。

計算量
 ちょうど last1 - first1 回の交換が行われる。

参照
swap, iter_swap

iter_swap

反復子が指す値の交換

形式
namespace std {
  template<class ForwardIterator1, class ForwardIterator2>
    void iter_swap(ForwardIterator1 a, ForwardIterator1 b);
}

引数
  a:  交換対象の反復子   b:  交換対象の反復子

返却値
 なし

解説
 2 つの反復子 a および b が指す値を交換する。

参照
swap

transform

各要素の変換

形式
namespace std {
  template<class InputIterator, class OutputIterator, class UnaryOperator?>
    OutputIterator transform(InputIterator first, InputIterator last,
                                                OutputIterator result, UnaryOperator? op);

  template<class InputIterator1, class InputIterator2,
                  class OutputIterator, class BinaryOperator?>
    OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
                                                InputIterator2 first2, OutputIterator result,
                                                BinaryOperator? binary_op);
}

引数
  first:  対象列の先頭要素を指す InputIterator
  last:  対象列の終端要素の次を指す InputIterator
  first1:  二項変換で用いる第 1 項用の列の先頭要素を指す InputIterator
  last1:  二項変換で用いる第 1 項用の列の終端要素の次を指す InputIterator
  first2:  二項変換で用いる第 2 項用の列の先頭要素を指す InputIterator
  result:  出力先の列の先頭要素を指す OutputIterator
  op:  単項変換用の述語?
  binary_op:  二項変換用の述語?

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

解説
 最初の形式では、区間 [first, last) にある反復子 iter に対して、op(*iter) を適用した結果を、result から始まる列に出力する。resultfirst と同じであっても構わない。
 2 番目の形式では、区間 [first1, last1) にある反復子 iter1 および区間 [first2, first2 + (last1 - first1)) にある反復子 iter2 に対して、binary_op(*iter1, *iter2) を適用した結果を、result から始まる列に出力する。resultfirst1 または first2 と同じであっても構わない。

計算量
 ちょうど last - first または last1 - first1 回述語が適用される。

replace

要素の置換

形式 namespace std {
  template<class ForwardIterator, class T>
    void replace(ForwardIterator first, ForwardIterator last,
                         const T& old_value, const T& new_value);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  old_value:  置換対象の値。型 T は Assignable かつ EqualityComparable?
  new_value:  置換後の値。型 T は Assignable かつ EqualityComparable?

返却値]
 なし

解説
 区間 [first, last) にある反復子 iter に対して、*iter == old_value が成立する各要素に対して、new_value を代入する。

計算量
 ちょうど last - first 回比較が行われる。

参照
replace_if, replace_copy, replace_copy_if

replace_if

条件が成立する要素の置換

形式
namespace std {
  template<class ForwardIterator, class Predicate, class T>
    void replace_if(ForwardIterator first, ForwardIterator last,
                             Predicate pred, const T& new_value);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  pred:  述語?
  new_value:  置換後の値。型 T は Assignable

返却値]
 なし

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, old_value) != false が成立する各要素に対して、new_value を代入する。

計算量
 ちょうど last - first 回述語が適用される。

replace_copy

要素の置換コピー

形式
namespace std {
  template<class InputIterator, class OutputIterator, class T>
    OutputIterator replace_copy(InputIterator first, InputIterator last,
                                                    OutputIterator result,
                                                    const T& old_value, const T& new_value);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  result:  出力先となる列の先頭要素を指す OutputIterator
  old_value:  置換対象の値。型 T は Assignable かつ EqualityComparable?
  new_value:  置換後の値。型 T は Assignable かつ EqualityComparable?

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

解説
 区間 [first, last) にある反復子 iter に対して、*iter == old_value が成立する場合は new_value を、それ以外は *iterresult から始まる列にコピーする。元の列と出力先の列は重なっていてはならない。

計算量
 ちょうど last - first 回比較が行われる。

replace_copy_if

条件が成立する要素の置換コピー

形式
namespace std {
  template<class InputIterator, class OutputIterator, class Predicate, class T>
    OutputIterator replace_copy_if(InputIterator first, InputIterator last,
                                                         OutputIterator result,
                                                         Predicate pred, const T& new_value);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  result:  出力先となる列の先頭要素を指す OutputIterator
  pred:  述語?
  new_value:  置換後の値。型 T は Assignable

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

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, old_value) != false が成立する場合は new_value を、それ以外は *iterresult から始まる列にコピーする。元の列と出力先の列は重なっていてはならない。

計算量
 ちょうど last - first 回述語が適用される。

fill

列を指定値で埋める

形式
namespace std {
  template<class ForwardIterator, class T>
    void fill(ForwardIterator first, ForwardIterator last, const T& value);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  value:  列を埋める値

返却値
 なし

解説
 区間 [first, last) にあるすべての反復子を通して、各要素に value代入?する。

計算量
 ちょうど last - first 回代入が行われる。

fill_n

n 要素の列を指定値で埋める

形式
namespace std {
  template<class ForwardIterator, class Size, class T>
    void fill_n(ForwardIterator first, Size n, const T& value);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  n:  対象となる列の要素数
  value:  列を埋める値

返却値
 なし

解説
 区間 [first, first + n) にあるすべての反復子を通して、各要素に value代入?する。

計算量
 ちょうど n 回代入が行われる。

generate

列の生成

形式
namespace std {
  template<class ForwardIterator, class Generator>
    void generate(ForwardIterator first, ForwardIterator last, Generator gen);
}

引数
  first:  生成対象となる列の先頭要素を指す ForwardIterator
  last:  生成対象となる列の終端要素の次を指す ForwardIterator
  gen:  生成関数

返却値
 なし

解説
 区間 [first, last) にあるすべての反復子を通して、gen返却値代入?する。gen実引数を取らない。

計算量
 ちょうど last - firstgen が呼び出される。

参照
generate_n

generate_n

n 要素の列を生成

形式
namespace std {
  template<class ForwardIterator, class Size, class Generator>
    void generate_n(ForwardIterator first, Size n, Generator gen);
}

引数
  first:  生成対象となる列の先頭要素を指す ForwardIterator
  n:  生成対象となる列の要素数
  gen:  生成関数

返却値
 なし

解説
 区間 [first, first + n) にあるすべての反復子を通して、gen返却値代入?する。gen実引数を取らない。また、型 Size は汎整数型に変換できなければならない。

計算量
 ちょうど ngen が呼び出される。

参照
generate

remove

要素の削除

形式
namespace std {
  template<class ForwardIterator, class T>
    ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  value:  削除対象。型 T は EualityComparable?

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

解説
 区間 [first, last) にある反復子 iter に対して、*iter == value が成立する要素を削除する。削除されない要素の相対順序は、元の相対順序が保存される。

計算量
 ちょうど last - first 回比較が行われる。

参照
remove_if, remove_copy, remove_copy_if

remove_if

条件が成立する要素の削除

形式
namespace std {
  template<class ForwardIterator, class Predicate>
    ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  pred:  述語?

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

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, value) != false が成立する要素を削除する。削除されない要素の相対順序は、元の相対順序が保存される。

計算量
 ちょうど last - first 回述語が適用される。

参照
remove, remove_copy, remove_copy_if

remove_copy

指定要素を除くコピー

形式
namespace std {
  template<class InputIterator, class OutputIterator, class T>
    OutputIterator remove_copy(InputIterator first, InputIterator last,
                                                      OutputIterator result, const T& value);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  result:  出力先の先頭要素を指す OutputIterator
  value:  削除対象。型 T は EualityComparable?

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

解説
 区間 [first, last) にある反復子 iter に対して、*iter == value が成立する要素を除き、result から始まる列にコピーする。削除されない要素の相対順序は、元の相対順序が保存される。元の列と出力先の列は重複していてはならない。

計算量
 ちょうど last - first 回比較が行われる。

remove_copy_if

条件が成立する要素を除くコピー

形式
namespace std {
  template<class InputIterator, class OutputIterator, class Predicate>
    OutputIterator remove_copy_if(InputIterator first, InputIterator last,
                                                         OutputIterator result, Predicate pred);
}

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  result:  出力先の先頭要素を指す OutputIterator
  pred:  述語?

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

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, value) != false が成立する要素を除き、result から始まる列にコピーする。削除されない要素の相対順序は、元の相対順序が保存される。元の列と出力先の列は重複していてはならない。

計算量
 ちょうど last - first 回述語が適用される。

unique

連続した重複要素の除去

形式
namespace std {
  template<class ForwardIterator>
    ForwardIterator unique(ForwardIterator first, ForwardIterator last);

  template<class ForwardIterator, class BinaryPredicate?>
    ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                                            BinaryPredicate? pred); }

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  pred:  述語?

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

解説
 区間 [first, last) にあるすべての重複要素を取り除く。すなわち、区間内の (先頭位置を除く) 反復子 iter に対して、最初の形式では *iter == *(iter - 1) を、2 番目の形式では pred(*iter, *(iter - 1)) == false が成立する最長の部分から、その先頭要素を残して他の要素が除去される。

計算量
 列が空でなければ、ちょうど (last - first) - 1 回比較または述語? が適用される。そうでなければ、比較または述語は 1 回も適用されることはない。

参照
unique_copy

unique_copy

連続した重複要素を除くコピー

形式
namespace std {
  template<class InputIterator, class OutputIterator>
    OutputIterator unique_copy(InputIterator first, InputIterator last,
                                                    OutputIterator result);

  template<class InputIterator, class OutputIterator, class BinaryPredicate?>
    OutputIterator unique_copy(InputIterator first, InputIterator last,
                                                    OutputIterator result, BinaryPredicate? pred); }

引数
  first:  対象となる列の先頭要素を指す ForwardIterator
  last:  対象となる列の終端要素の次を指す ForwardIterator
  result:  出力先の先頭要素を指す OutputIterator
  pred:  述語?

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

解説
 区間 [first, last) にあるすべての重複要素を除いて、result から始まる列にコピーする。すなわち、区間内の (先頭位置を除く) 反復子 iter に対して、最初の形式では *iter == *(iter - 1) を、2 番目の形式では pred(*iter, *(iter - 1)) == false が成立する最長の部分から、その先頭要素のみがコピーされる。

計算量
 ちょうど (last - first) - 1 回比較または述語? が適用される。

参照
unique

reverse

列の逆順再配置

形式
namespace std {
  template<class BidirectionalIterator>
    void reverse(BidirectionalIterator first, BidirectionalIterator last); }

引数
  first:  再配置対象となる列の先頭要素を指す BidirectionalIterator
  last:  再配置対象となる列の終端要素の次を指す BidirectionalIterator

返却値
 なし

解説
 区間 [iter, last) で定義される列を iter_swap により逆順に再配置する。

計算量
 多くとも last - first 回の交換を行う。

参照
reverse_copy

reverse_copy

列の逆順コピー

形式
namespace std {
  template<class BidirectionalIterator, class OutputIterator>
    OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last
                                                      OutputIterator result); }

引数
  first:  対象となる列の先頭要素を指す BidirectionalIterator
  last:  対象となる列の終端要素の次を指す BidirectionalIterator
  result:  出力先となる列の先頭要素を指す OutputIterator

返却値
 なし

解説
 区間 [iter, last) で定義される列を、result から始まる列に、逆順にコピーする。元の列と出力先の列が重なっていてはならない。

計算量
 ちょうど last - first 回の代入が行われる。

参照
reverse

rotate

列の回転

形式
namespace std {
  template<class ForwardIterator>
    void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
}

引数
  first:  回転対象となる列の先頭要素を指す ForwardIterator
  middle:  回転後に先頭に移動する要素を指す ForwardIterator
  last:  回転対象となる列の終端要素の次を指す ForwardIterator

返却値
 なし

解説
 区間 [first, last) を、middle が指す要素が先頭になるように回転しする。区間 [first, middle) および区間 [middle, last) は正しい列でなければならない。

計算量
 多くとも last - first 回の交換が行われる。

参照
rotate_copy

rotate_copy

列の回転とコピー

形式
namespace std {
  template<class ForwardIterator, class OutputIterator>
    OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
                                                    ForwardIterator last, OutputIterator result);
}

引数
  first:  回転対象となる列の先頭要素を指す ForwardIterator
  middle:  回転後に先頭に移動する要素を指す ForwardIterator
  last:  回転対象となる列の終端要素の次を指す ForwardIterator
  result:  出力先となる列の先頭要素を指す OutputIterator

返却値
 結果列の終端位置の次を指す反復子を返す。

解説
 区間 [first, last) を、middle が指す要素が先頭になるように回転し、その結果を result から始まる列に格納する。区間 [first, middle) および区間 [middle, last) は正しい列でなければならない。また、元の列と出力先の列が重なっていてはならない。

計算量
 ちょうど last - first 回の代入が行われる。

参照
rotate

random_shuffle

乱数によるシャッフル

形式
namespace std {
  template<class RandomAccessIterator?>
    void random_shuffle(RandomAccessIterator? first, RandomAccessIterator? last);

  template<class RandomAccessIterator?, class RandomNumberGenerator?>
    void random_shuffle(RandomAccessIterator? first, RandomAccessIterator? last
                                      RandomNumberGenerator?& rand); }

引数
  first:  シャッフル対象となる列の先頭要素を指す RandomAccessIterator?
  last:  シャッフル対象となる列の終端要素の次を指す RandomAccessIterator?
  rand:  乱数生成関数オブジェクト?

返却値
 なし

解説
 区間 [first, last) で定義される列を一様にシャッフルする。乱数生成関数オブジェクト? rand は任意のものを指定してもよいが、[[iterator_traits>#<iterator>ヘッダ#iterator_traits]]<RandomAccessIterator?>:: difference_type 型の正の実引数 n に対して、rand(n) は、iterator_traits<RandomAccessIterator?>:: difference_type 型に変換可能な型を持ち、かつ値域 [0, n) の中からランダムに抽出された値を返さなければならない。

計算量
 ちょうど (last - first) - 1 回の交換が行われる。

参照
rand, srand

partition

列の分割

形式
namespace std {
  template<class BidirectionalIterator, class Predicate>
    BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last,
                                                      Predicate pred);
}

引数
  first:  分割対象となる列の先頭要素を指す BidirectionalIterator
  last:  分割対象となる列の終端要素の次を指す BidirectionalIterator
  pred:  述語?

返却値
 分割位置を指す反復子を返す。

解説
 区間 [first, last) で定義される列を、述語? pred が成立する要素を前に、成立しない要素を後ろに再配置する。

計算量
 多くとも (last - first) / 2 回の交換が行われる。メモリが十分にある場合には線形になる可能性がある。また、last - first 回だけ述語 pred が適用される。

参照
stable_partition

stable_partition

列の安定な分割

形式
namespace std {
  template<class BidirectionalIterator, class Predicate>
    BidirectionalIterator stable_partition(BidirectionalIterator first,
                                                                  BidirectionalIterator last, Predicate pred);
}

引数
  first:  分割対象となる列の先頭要素を指す BidirectionalIterator
  last:  分割対象となる列の終端要素の次を指す BidirectionalIterator
  pred:  述語?

返却値
 分割位置を指す反復子を返す。

解説
 区間 [first, last) で定義される列を、述語? pred が成立する要素を前に、成立しない要素を後ろに再配置する。同値の要素の順序は、再配置後も保存される。

計算量
 多くとも (last - first)×log(last - first) 回の交換が行われる。メモリが十分にある場合には線形になる可能性がある。また、last - first 回だけ述語 pred が適用される。

参照
partition


トップ   編集 差分 バックアップ 添付 複製 名前変更   一覧 単語検索   ヘルプ   最終更新のRSS
Counter: 3761, today: 1, yesterday: 0
Last-modified: Sun, 20 Nov 2005 22:32:06 JST (4407d)
 ホーム | プロフィール | メール | ログイン | 管理
Copyright © 2005-2009 by TAKAGI Nobuhisa