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


更新を伴わない列演算 (non-modifying sequence operations)

for_each

各要素に対する処理

形式
namespace std {
  template<class InputIterator, class Funtion>
    Function for_each(InputIterator first, InputIterator last, Function f);
}

引数
  first:  先頭要素を指す InputIterator
  last:  終端要素の次を指す InputIterator
  f:  各要素に適用する処理

返却値
 f を返す。

解説
 区間 [first, last-1) の各反復子 iter に対して、f(*iter) を実行する。f が何らかの返却値を返す場合には、その値は単に無視される。

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

find

の探索

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

引数
  first:  先頭要素を指す InputIterator
  last:  終端要素の次を指す InputIterator
  value:  探索対象の。型 T は EqualityComparable?

返却値
 探査に成功すれば検出位置を指す反復子を、失敗した場合は last を返す。

解説
 区間 [first, last) の反復子 iter であり、かつ *iter == value となる最初の要素を探索する。

計算量
 *iter == value の評価を、多くとも last - first 回実行する。

参照
find_if

find_if

条件に一致する要素の探索

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

引数
  first:  先頭要素を指す InputIterator
  last:  終端要素の次を指す InputIterator
  pred:  探索条件となる述語?

返却値
 探査に成功すれば検出位置を指す反復子を、失敗した場合は last を返す。

解説
 区間 [first, last) の反復子 iter であり、かつ pred(iter) != false となる最初の要素を探索する。

計算量
 述語?の適応を、多くとも last - first 回実行する。

参照
find

find_end

最後の部分列の探索

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

  template<class ForwardIterator1, class ForwardIterator2, ckass BinaryPredicate?>
    ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                                                ForwardIterator2 first2, ForwardIterator2 last2,
                                                BinaryPredicate? pred);
}

引数
  first1:  探索対象となる列の先頭要素を指す ForwardIterator
  last1:  探索対象となる列の終端要素の次を指す ForwardIterator
  first2:  探索する部分列の先頭要素を指す ForwardIterator
  last2:  探索する部分列の終端要素の次を指す ForwardIterator
  pred:  述語?

返却値
 探索に成功した場合、見つけた部分列の先頭要素を指す反復子を返す。失敗した場合には last1 を返す。

解説
 区間 [first1, last1 - (last2 - first2)) で定義される列から区間 [first2, last2) で定義される最後の部分列を探索する。具体的には、区間 [first1, last1 - (last2 - first2)) にある反復子 iter および n < last2 - first2 である負でない n に対して、最初の形式では *(iter + n) == *(first2 + n) が、2 番目の形式では pred(*(iter + n), *(first2 + n)) != false が成立する最後の iter を見つけ出す。

計算量
 多くとも (last2 - first2)×(last1 - first1 - (last2 - first2) + 1) 回比較または述語が適用が行われる。

参照
serach

find_first_of

値集合のひとつに一致する要素の探索

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

  template<class ForwardIterator1, class ForwardIterator2, BinaryPredicate? pred>
    ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
                                                      ForwardIterator2 first2, ForwardIterator2 last2,
                                                      BinaryPredicate? pred);
}

引数
  first1:  探索対象となる列の先頭要素を指す ForwardIterator
  last1:  探索対象となる列の終端要素の次を指す ForwardIterator
  first2:  値集合の先頭要素を指す ForwardIterator
  last2:  値集合の終端要素の次を指す ForwardIterator
  pred:  述語?

返却値
 値集合のひとつに一致する要素が見つかった場合には、その要素を指す反復子を返す。それ以外の場合には last1 を返す。

解説
 区間 [first1, last1) で定義される列から、区間 [first2, last2) で定義される値集合のひとつに一致する要素を探索する。具体的には、区間 [first1, last1) にある反復子 iter1 および区間 [first2, last2) にある反復子 iter2 に対して、最初の形式では *iter1 == *iter2 が、2 番目の形式では pred(*iter1, *iter2) != false が成立する最初の iter1 を見つける。

計算量
 多くとも (last1 - first1)×(last2 - first2) 回比較または述語の適用が行われる。

adjacent_find

隣接する同値要素の探索

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

  template<class ForwardIterator, class Predicate>
    ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,~                                                         Predicate pred);
}

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

返却値
 隣接する同値の要素が見つかった場合、その要素を指す反復子を、見つからなかった場合は last を返す。

解説
 区間 [first, last) にある反復子 iter および iter + 1 に対して、最初の形式では *iter == *(iter + 1) が、2 番目の形式では pred(*iter, *(iter + 1)) が成立する最初の iter を見つける。

計算量
 ちょうど find(find, last, value) - first 回比較または述語の適用が行われる。

count

要素の個数

形式
namespace std {
  template<class InputIterator, class T>
    typename iterator_traits<InputIterator>::difference_type
        count(InputIterator first, InputIterator last, const T& value);
}

引数
  first:  計数対象となる列の先頭要素を指す InputIterator
  last:  計数対象となる列の終端要素の次を指す InputIterator
  value:  計数の対象となる値。型 T は EqualityComparable?

返却値
 計数した個数を返す。

解説
 区間 [first, last) にある反復子 iter に対して、*iter == value が成立する反復子の個数を数える。

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

参照
count_if

count_if

条件が成立する要素の個数

形式
namespace std {
  template<class InputIterator, class Predicate>
    typename iterator_traits<InputIterator>::difference_type
        count_if(InputIterator first, InputIterator last, Predicate pred);
}

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

返却値
 計数した個数を返す。

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, value) != false が成立する反復子の個数を数える。

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

参照
count

mismatch

不一致要素の探索

形式
namespace std {
  template<class InputIterator1, class InputIterator2>
    pair<InputIterator1, InputIterator2>
        mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

  template<class InputIterator1, class InputIterator2, class Predicate>
    pair<InputIterator1, InputIterator2>
        mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
                        Predicate pred);
}

引数
  first1:  比較対象となる一方の列の先頭要素を指す InputIterator
  last1:  比較対象となる一方の列の終端要素の次を指す InputIterator
  first2:  比較対象となる他方の列の先頭要素を指す InputIterator
  pred:  述語?

返却値
 不一致要素が見つかった場合、不一致要素を指す反復子の対を返す。不一致要素が見つからなければ それぞれの列の終端要素の次を指す反復子が格納される。

解説
 区間 [first1, last1) で定義される列と区間 [first2, first2 + (last1 - first1)) の各要素を比較し、不一致要素を見つける。不一致要素が見つかった場合の返却値の .first は区間 [first1, last1) 側の、.second は区間 [first2, first2 + (last1 - first1)) 側の反復子が格納される。

計算量
 多くとも last1 - first1 回比較または述語の適用が行われる。

equal

列の等価判定

形式
namespace std {
  template<class InputIterator1, class InputIterator2>
    bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

  template<class InputIterator1, class InputIterator2, Predicate pred>
    bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
                      Predicate pred);
}

引数
  first1:  比較対象となる一方の列の先頭要素を指す InputIterator
  last1:  比較対象となる一方の列の終端要素の次を指す InputIterator
  first2:  比較対象となる他方の列の先頭要素を指す InputIterator
  pred:  述語?

返却値
 比較対象の 2 つの列が等価の場合は true を、そうでなければ false を返す。

解説
 区間 [first1, last1) で定義される列と区間 [first2, first2 + (last1 - first1)) で定義される列の各要素を比較する。具体的には、区間 [first1, last1) にある反復子 iter に対して、最初の形式の場合は *iter == *(first2 + (iter - first1)) が、2 番目の形式の場合は pred(*iter, *(first2 + (iter - first1))) が成立する場合に 2 つの列が等価であると判定される。

計算量
 多くとも last1 - first1 回比較または述語の適用が行われる。

search

部分列の探索

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

  template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate?>
    ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
                                            ForwardIterator2 first2, ForwardIterator2 last2,
                                            BinaryPredicate pred);
}

引数
  first1:  探索対象となる列の先頭要素を指す ForwardIterator
  last1:  探索対象となる列の終端要素の次を指す ForwardIterator
  first2:  探索する部分列の先頭要素を指す ForwardIterator
  last2:  探索する部分列の終端要素の次を指す ForwardIterator
  pred:  述語?

返却値
 探索に成功した場合、見つけた部分列の先頭要素を指す反復子を返す。失敗した場合には last1 を返す。

解説
 区間 [first1, last1 - (last2 - first2)) で定義される列から区間 [first2, last2) で定義される部分列を探索する。具体的には、区間 [first1, last1 - (last2 - first2)) にある反復子 iter および n < last2 - first2 である負でない n に対して、最初の形式では *(iter + n) == *(first2 + n) が、2 番目の形式では pred(*(iter + n), *(first2 + n)) != false が成立する最初の iter を見つけ出す。

計算量
 多くとも (last1 - first1)×(last2 - first2) 回比較または述語が適用が行われる。

参照
serach_n, find_end

search_n

n 個の連続値からなる部分列の探索

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

  template<class ForwardIterator, class Size, class T, BinaryPredicate? pred>
    ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
                                                Size count, const T& value, BinaryPredicate pred);
}

引数
  first:  探索対象となる列の先頭要素を指す ForwardIterator
  last:  探索対象となる列の終端要素の次を指す ForwardIterator
  count:  探索する部分列の要素数
  value:  探索する部分列の要素の値
  pred:  述語?

返却値
 探索に成功した場合、見つけた部分列の先頭要素を指す反復子を返す。失敗した場合には last1 を返す。

解説
 区間 [first, last - count) で定義される列から count 個の value からなる部分列を探索する。具体的には、区間 [first, last - count) にある反復子 iter および n < count である負でない n に対して、最初の形式では *(iter + n) == valueが、2 番目の形式では pred(*(iter + n), value) が成立する最初の iter を見つけ出す。

計算量
 多くとも (last - firstcount 回比較または述語が適用が行われる。

参照
serach


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