STLソース分析のstl_algo.hにおける基本アルゴリズム

前言

前節ではstl_algo.hのrotate関数の実現を分析し、本節ではこのファイルの他の基本アルゴリズムを分析し続けた.これらのアルゴリズム機能の実現は簡単そうに見えるが、これらのアルゴリズムは派生することができ、ユーザーはカスタマイズすることができ、私たちの一部のプログラミングを簡単化し、直接使用するには再定義する必要はない.

きほんアルゴリズム

for_each

[first,last]の範囲の要素を入力擬似関数(関数)で処理し、最後に擬似関数(関数)を返す.

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f) {
  for ( ; first != last; ++first)
    f(*first);	//       
  return f;
}

例:

void For_each(int i)  { i = 1; }

void For_func(int i) { cout << i << " "; }

int main()
{
	vector<int> a(10);
	for_each(a.begin(), a.end(), For_each);	//       
	for(const auto &i : a)
		cout << i <<  " ";	// 0 0 0 0 0 0 0 0 0 0
	for_each(a.begin(), a.end(), For_func);	// 0 0 0 0 0 0 0 0 0 0

	return 0;
}

初期化値の試行に問題があることは明らかである、for_eachは入力値を修正せず、入力は右値であるため、一般的にfor_eachを用いるのは反復器の出力を実現するので、forサイクルを書くことなく出力することができる.

find

2つのバージョン

//    
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
  while (first != last && *first != value) ++first;
  return first;
}
//    
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
                      Predicate pred) {	
  while (first != last && !pred(*first)) ++first;	//     ,        
  return first;
}

adjacent_find

2つのバージョン
最初のバージョンでは、隣接する要素間で最初に発生した要素が同じ場合を見つけ、最初に発生した反復器を返します.
2番目のバージョンでは、隣接する要素間で最初に擬似関数条件を満たす場合を見つけ、最初に状況を満たす反復器を返します.

//                         ,            
template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last) {
  if (first == last) return last;
  ForwardIterator next = first;
  while(++next != last) {
    if (*first == *next) return first;
    first = next;
  }
  return last;
}
//                          ,              
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
                              BinaryPredicate binary_pred) {
  if (first == last) return last;
  ForwardIterator next = first;
  while(++next != last) {
    if (binary_pred(*first, *next)) return first;
    first = next;
  }
  return last;
}

count

2つのバージョン
バージョン1:統計[first,last)範囲に現れる指定要素の回数
バージョン2:統計[first,last)範囲が条件を満たす要素の回数

//     :   [first, last)            
template <class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last, const T& value, Size& n) {
  for ( ; first != last; ++first)
    if (*first == value)
      ++n;
}
//     :   [first, last)            
template <class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n) {
  for ( ; first != last; ++first)
    if (pred(*first))
      ++n;
}

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
//     :   [first, last)            
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value) {
  typename iterator_traits<InputIterator>::difference_type n = 0;
  for ( ; first != last; ++first)
    if (*first == value)
      ++n;
  return n;
}
//     :   [first, last)            
template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred) {
  typename iterator_traits<InputIterator>::difference_type n = 0;
  for ( ; first != last; ++first)
    if (pred(*first))
      ++n;
  return n;
}

replace

2つのバージョン
バージョン1:すべてold_valueのデータをnew_に変更value
バージョン2:擬似関数(関数)を満たすすべてのデータをnew_に変換value

//     :     old_value     new_value
template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last, const T& old_value,
             const T& new_value) {
  for ( ; first != last; ++first)
    if (*first == old_value) *first = new_value;
}
//     :               new_value
template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred,
                const T& new_value) {
  for ( ; first != last; ++first)
    if (pred(*first)) *first = new_value;
}

replace_copy

2つのバージョン両方のバージョンで元のコンテナのデータは変更されません.
バージョン1:すべての要素を別のコンテナに保存し、すべてをold_valueのデータをnew_に変更value
バージョン2:すべての要素を別のコンテナに保存し、シミュレーション関数を満たすすべてのデータをnew_に変更します.value

//              ,      old_value     new_value
template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
                            OutputIterator result, const T& old_value,
                            const T& new_value) {
  for ( ; first != last; ++first, ++result)
    *result = *first == old_value ? new_value : *first;
  return result;
}
//              ,               new_value
template <class Iterator, class OutputIterator, class Predicate, class T>
OutputIterator replace_copy_if(Iterator first, Iterator last,
                               OutputIterator result, Predicate pred,
                               const T& new_value) {
  for ( ; first != last; ++first, ++result)
    *result = pred(*first) ? new_value : *first;
  return result;
}

まとめ

本節では,stl_algo.hの基本アルゴリズムの実装を解析し,通常のプログラムのコード量を簡略化することができ,その中で通常最も多く用いられるのがfor_である.each関数