アルゴリズム(Algorithm)

STLの中心的存在がアルゴリズムです。コンテナ、イテレータ、関数オブジェクトはどれもアルゴリズムを機能させるために用意されたと言ってもいいでしょう。

STLのほとんどのアルゴリズムには入力となる要素の集合を2つのイテレータで指定します。ひとつは集合の先頭を指すイテレータfirst、もうひとつは集合の末尾の次を指すイテレータlastです。すなわちアルゴリズムはfirstから始まりlastに達しない範囲(first以上last未満)にある要素を入力とします。

末尾位置を指定するのに"末尾の次"を使うのは、

です。
 // 例: array[0]..array[N-1]を出力する
 void print(int n) { cout << n << ' ' << flush; }

 int array[N];
 for_each(array, array+N, print);
アルゴリズムはおおまかに の3つに分類されます。この3つの分類に属する代表的なアルゴリズムについてコーディング例と使い方に関する注意などを示します。なお、コンテナ内の要素のプリントには巻末の'iter_print'を用いました。
表: カテゴリー別アルゴリズム一覧 ここから
 - 要素を書き換えない(read-only)操作

 操作の適用      for_each
 検索            find, find_if, find_end, find_first_of, adjacent_find
 計数            count, count_if
 不一致検索      mismatch
 一致判断        equal
 部分集合の検索  search, search_n

 - 要素の追加/削除/変更を伴う操作

 複製            copy, copy_backward
 交換            swap, swap_ranges, iter_swap
 変換            transform
 置換            replace, replace_if, replace_copy, replace_copy_if
 充填            fill, fill_n
 生成            generate, generate_n
 削除            remove, remove_if, remove_copy, remove_copy_if
 隣接要素の削除  unique, unique_copy
 反転            reverse, reverse_copy
 回転            rotate, rotate_copy
 攪拌            random_shuffle
 分類            partition, stable_partition

 - ソート(並び替え)およびソートに関連した操作

 ソート          sort, stabe_sort,
 部分ソート      partial_sort, partial_sort_copy
 分類            nth_element

 検索            lower_bound, upper_bound, equal_range, binary_search
 併合            merge, inplace_merge
 集合演算        includes, set_union,set_intersection,
                 set_difference, set_symmetric_difference
 ヒープ操作      push_heap, pop_heap, make_heap, sort_heap
 最大値/最小値   min, max, min_element, max_element
 辞書順比較      lexicographical_compare
 順列生成        next_permutation, prev_permutation
表: イテレータによるアルゴリズムの分類

イテレータを必要としないアルゴリズム:
  max                    min                 swap

InputIterator(入力)を引数とするアルゴリズム:
  accumulate             find                mismatch
  count                  find_if
  count_if               includes
  equal                  inner_product
  for_each               lexicographical_compare

OutputIterator(出力)を引数とするアルゴリズム:
  fill_n                 generate_n

InputIterator(入力)とOutputIterator(出力)を引数とするアルゴリズム:
  adjacent_difference    replace_copy        transform
  copy                   replace_copy_if     unique_copy
  merge                  set_difference
  partial_sum            set_intersedtion
  remove_copy            set_symmetric_difference
  remove_copy_if         set_union

ForwardIterator(入出力)を引数とするアルゴリズム
  adjacent_find            iter_swap            replace_if
  binary_search            lower_bound          rotate
  equal_range              max_element          search
  fill                     min_element          search_n
  find_end                 remove               swap_ranges
  find_first_of            remove_if            unique
  generate                 replace              upper_bound

ForwardIterator(入力)とOutputIterator(出力)を引数とするアルゴリズム:
  rotate_copy

BidirectionalIteratorを引数とするアルゴリズム
  copy_backward          partition
  inplace_merge          prev_permutation
  next_permutation       reverse
                         stable_permutation

BidirectionalIterator(入力)とOutputIterator(出力)を引数とするアルゴリズム:
  reverse_copy

RandomAccessIteratorを引数とするアルゴリズム:
  make_heap              pop_heap            sort
  nth_element            push_heap           sort_heap
  partial_sort           random_shuffle      stable_sort

InputIterator(入力)とRandomAccessIterator(出力)を引数とするアルゴリズム:
  partial_sort_copy

[要素を書き換えない(read-only)操作]

[要素の追加/削除/変更を伴う操作]

この分類に属するアルゴリズムは要素の変更や追加/削除を伴います。

[ソート(並び替え)およびソートに関連した操作]

[算術アルゴリズム]

ほとんどのアルゴリズムはヘッダ<algorithm>に定義されていますが、算術演算を行なうアルゴリズムはヘッダ<numeric>にあります。

[アルゴリズムの作り方]

STLが用意してくれているアルゴリズムの組み合わせで大抵の処理を実現できることと思います。が、それではコードが複雑になり、一見してなにを行なっているのかわからなくなることがあります。たとえば集合の中から3と等しい要素を見つけるには
  // a[N]から3を見つける
  int a[N];
  int* i = find(a, a+N, 3);
  if ( i != a+N ) [
    // 見つかった!
  }
一目瞭然のわかりやすいコードです。一方、3と等しくない要素を見つけるには、STLには"等しくない要素を探し出す"アルゴリズムが用意されていませんから、
  // a[N]から3でない要素を見つける
  int a[N];
  int* i = find_if(a, a+N, bind1st(not_equal_to<int>(),3);
  if ( i != a+N ) {
    // 見つかった!
  ]
となり、単に条件が反転しただけなのにコードの見かけが複雑になっています。"等しくない要素を探し出す"アルゴリズムを実装してみましょう。
  // xと等しくない要素を見つける
  template<class InputIterator, class T>
  InputIterator
  find_not(InputIterator first, InputIterator last, const T& x) {
    while ( first != last && *first == x )
      ++first;
    return first;
  }

  // a[N]から3でない要素を見つける
  int a[N];
  int* i = find_not(a, a+N, 3);
  if ( i != a+N ) {
    // 見つかった!
  }
新たなアルゴリズムfind_notを定義することにより、コードが簡潔でとてもわかりやすくなります。独自のアルゴリズムを定義することでコードの可読性を向上させることができます。

アルゴリズムを作るときに注意することは、

「引数としてコンテナを渡すのは極力避け、代わりにイテレータを渡す」

ことです。コンテナを引数として、

  // xと等しくない要素を見つける
  template<class Container, class T>
  Container::const_iterator
  find_not(const Container& c, const T& x) {
    Container::const_iterator first = c.begin();
    while ( first != c.end() && *first == x )
      ++first;
    return first;
  }
という実装も可能です。しかしこれでは配列の中からの検索ができなくなってしまいます。配列はメンバ関数begin(),end() および typedef const_iteratorを持っていないからです。

コンテナの代わりにイテレータを引数とするのは既存のSTLアルゴリズムとの一貫性を保ち、アルゴリズムを汎用のものにするためです(もちろんそのアルゴリズムが汎用性を考慮しなくていいのなら構いませんが)。

この例"等しくない要素を探し出す"では、新たな関数オブジェクトを定義することでも同様の効果が得られます。

  template<class T>
  struct unary_not_equal_to : unary_function<T,bool> {
    T value_;
    explicit unary_not_equal_to(const T& v) : value_(v) {}
    bool operator()(const T& x) {
      return !(value_ == x);
    }
  };

  template<class T>
  inline unary_not_equal_to<T>
  ne(const T& v) {
    return unary_not_equal_to<T>(v);
  }

  // a[N]から3でない要素を見つける
  int a[N];
  int* i = find_if(a, a+N, ne(3));
  if ( i != a+N ) {
    // 見つかった!
  }
関数オブジェックトを定義するこの方法でもコードは十分簡潔になります。アルゴリズムfind_notを定義する方がより簡潔ではありますが、関数オブジェクトunary_not_equal_toを定義すれば、これを他のアルゴリズムに対して使えるのが大きなメリットとなります。
  // a[N]の中に3でない要素はいくつあるか
  size_t n = count_if(a, a+N, ne(3));
  /*
   * ユーザ定義アルゴリズムの例
   */
  #include <iterator>

  //--- 二項の for_each -----------------------------------
  template<class InputIterator1, class InputIterator2,
           class BinaryFunction>
  inline BinaryFunction
  for_each(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, BinaryFunction f) {
    while ( first1 != last1 )
    f(*first1++,*first2++);
    return f;
  }

  //--- ...でない要素を探す find_not / find_not_if --------
  template<class InputIterator, class T>
  inline InputIterator
  find_not(InputIterator first, InputIterator last, const T& val) {
    while ( first != last && *first == val )
      ++first;
    return first;
  }

  template<class InputIterator, class UnaryPredicate>
  inline InputIterator
  find_not_if(InputIterator first, InputIterator last,
              UnaryPredicate pred) {
    while ( first != last && pred(*first) )
      ++first;
    return first;
  }

  //--- 条件を満たす要素があればtrue : some / some_if ----
  template<class InputIterator, class T>
  inline bool
  some(InputIterator first, InputIterator last, const T& val) {
    while ( first != last && !(*first == val) )
      ++first;
    return first != last;
  }

  template<class InputIterator, class UnaryPredicate>
  inline bool
  some_if(InputIterator first, InputIterator last, UnaryPredicate pred) {
    while ( first != last && !pred(*first) )
      ++first;
    return first != last;
  }

  //--- 全要素が条件を満たせばtrue : every / every_if -----
  template<class InputIterator, class T>
  inline bool
  every(InputIterator first, InputIterator last, const T& val) {
    while ( first != last && *first == val )
      ++first;
    return first == last;
  }

  template<class InputIterator, class UnaryPredicate>
  inline bool
  every_if(InputIterator first, InputIterator last,
           UnaryPredicate pred) {
    while ( first != last && pred(*first) )
      ++first;
    return first == last;
  }

  //--- ...でない要素の数 count_not / count_not_if --------
  template<class InputIterator, class T>
  inline std::iterator_traits<InputIterator>::distance_type
  count_not(InputIterator first, InputIterator last, const T& value) {
    std::iterator_traits<InputIterator>::distance_type n = 0;
    for ( ; first != last; ++first )
      if ( !(*first == value) )
        ++n;
    return n;
  }

  template<class InputIterator, class UnaryPredicate>
  inline std::iterator_traits<InputIterator>::distance_type
  count_not_if(InputIterator first, InputIterator last,
               UnaryPredicate pred) {
    std::iterator_traits<InputIterator>::distance_type n = 0;
    for ( ; first != last; ++first )
      if ( !pred(*first) )
        ++n;
    return n;
  }

  //--- 条件を満たすものだけをコピー copy_if --------------
  template<class InputIterator, class OutputIterator, class Predicate>
  inline OutputIterator
  copy_if(InputIterator first, InputIterator last,
          OutputIterator result, Predicate pred) {
    for ( ; first != last; ++first )
      if ( pred(*first) )
        *result++ = *first;
    return result;
  }

コラム iterator_traits

集合内の全要素の平均値を求めるアルゴリズム mean を実装したとしましょう:
  template<InputIterator>
  要素の型 mean(InputIterator first, InputIterator last) {
    要素の型 sum = 0;
    int count = 0;
    while ( first != last ) {
      sum += *first++;
      ++count;
    }
    return sum / count;
  }
このとき、InputIteratorが指す"要素の型"がわからないとmeanを作ることができません。STLコンテナのメンバbegin()やend()返すイテレータはすべてクラステンプレートiteratorの派生クラスです。
  template<class Category, class T, class Distance = ptrdiff_t,
           class Pointer = T*, class Reference = T&>
  struct iterator {
    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
    typedef Category  iterator_category;
  };
したがって、iteratorに定義された型 value_type を使って:
  template<InputIterator>
  InputIterator::value_type
  mean(InputIterator first, InputIterator last) {
    InputIterator::value_type sum = 0;
    int count = 0;
    while ( first != last ) {
      sum += *first++;
      ++count;
    }
    return sum / count;
  }
アルゴリズム mean は STLコンテナに対しては正しく動作します。
  list<double> l;
  double m = mean(l.begin(), l.end();
ところが、
  double a[10];
  double m = mean(a, a+10);
の場合テンプレート引数としてdouble*が与えられたのですから、
  double*::value_type
  mean(InputIterator first, InputIterator last) {
    double*::value_type sum = 0;
    ...
  }
ということになり、double*::value_type がコンパイルエラーとなります。このままでは mean は配列に対して使えません。

この問題を解決するため、iterator_traits が定義されています。

  template<class Iterator> struct iterator_traits {
    typedef typename Iterator::difference_type   difference_type;
    typedef typename Iterator::value_type        value_type;
    typedef typename Iterator::pointer           pointer;
    typedef typename Iterator::reference         reference;
    typedef typename Iterator::iterator_category iterator_category;
  };

  template<class T> struct iterator_traits<T*> {
    typedef ptrdiff_t                  difference_type;
    typedef T                          value_type;
    typedef T*                         pointer;
    typedef T&                         reference;
    typedef random_access_iterator_tag iterator_category;
  };

  template<class T> struct iterator_traits<const T*> {
    typedef ptrdiff_t                  difference_type;
    typedef T                          value_type;
    typedef const T*                   pointer;
    typedef const T&                   reference;
    typedef random_access_iterator_tag iterator_category;
  };
iterator_traitsを使ってmeanを書き直すと:
  template<InputIterator>
  iterator_traits<InputIterator>::value_type
  mean(InputIterator first, InputIterator last) {
    iterator_traits<InputIterator>::value_type sum = 0;
    int count = 0;
    while ( first != last ) {
      sum += *first++;
      ++count;
    }
    return sum / count;
  }
iterator_traits<double*>::value_typeはdoubleのtypedefと定義されていますから、配列に対してもmeanが使えるようになるわけです。

残念ながら現時点ではiterator_traitsのように

  template<class T> class X<T*> { ... };
という形式("partial specialization:部分的特殊化"という)のtemplateを正しく解釈できるコンパイラは極めて少ないのが現状です。
  #define ITERATOR_TRAITS(T) \
  template<> struct iterator_traits<T*> { \
    typedef ptrdiff_t                  difference_type; \
    typedef T                          value_type; \
    typedef T*                         pointer; \
    typedef T&                         reference; \
    typedef random_access_iterator_tag iterator_category; \
  }; \
  \
  template<> struct iterator_traits<const T*> { \
    typedef ptrdiff_t                  difference_type; \
    typedef T                          value_type; \
    typedef const T*                   pointer; \
    typedef const T&                   reference; \
    typedef random_access_iterator_tag iterator_category; \
  };
のようなマクロを用意して対処しました。