サンプル

[イテレータの挙動を調べるためのデバッグ用関数 iter_print]

  /*
   * iter_print.h
   */

  #ifndef __ITER_PRINT_H__
  #define __ITER_PRINT_H__

  #include <iostream> // cout
  #include <utility>  // pair

  template<class Iterator>
  void _iter_print(Iterator first, Iterator last) {
    while ( first != last ) {
      std::cout << *first++;
      if ( first != last ) std::cout << ' ';
    }
  }

  template<class Iterator>
  void iter_print(Iterator first, Iterator last) {
    std::cout << '[';
    _iter_print(first,last);
    std::cout << ']' << std::endl;
  }

  template<class Iterator>
  void iter_print(Iterator first, Iterator middle, Iterator last) {
    std::cout << '[';
    _iter_print(first,middle);
    std::cout << '|';
    _iter_print(middle,last);
    std::cout << ']' << std::endl;
  }

  template<class Iterator>
  void iter_print(Iterator first, Iterator lower,
                  Iterator upper, Iterator last) {
    std::cout << '[';
    _iter_print(first,lower);
    std::cout << '(';
    _iter_print(lower,upper);
    std::cout << ')';
    _iter_print(upper,last);
    std::cout << ']' << std::endl;
  }

  template<class Iterator>
  void iter_print(Iterator first, std::pair<Iterator,Iterator> middle,
                  Iterator last) {
    iter_print(first,middle.first,middle.second,last);
  }

  #endif

  /*
   * お試し
   */
  #include <iostream>
  #include <algorithm>
  #include <set>
  #include "print.h"

  using namespace std;

  int main() {
    const int N = 10;
    cout << "\narray find" << endl;
    int a[N] = { 1, 2, 2, 4, 5, 6, 7, 8, 8, 8 };
    cout << "  "; iter_print(a, a+N);
    cout << "0:"; iter_print(a, find(a,a+N,0), a+N);
    cout << "3:"; iter_print(a, find(a,a+N,3), a+N);
    cout << "8:"; iter_print(a, find(a,a+N,8), a+N);

    cout << "\nset find" << endl;
    set<int> s(a,a+N);
    cout << "  "; iter_print(s.begin(), s.end());
    cout << "0:"; iter_print(s.begin(), s.find(0), s.end());
    cout << "2:"; iter_print(s.begin(), s.find(2), s.end());
    cout << "6:"; iter_print(s.begin(), s.find(6), s.end());

    cout << "\nmultiset find" << endl;
    multiset<int> ms(a,a+N);
    cout << "  "; iter_print(ms.begin(), ms.end());
    cout << "0:"; iter_print(ms.begin(), ms.find(0), ms.end());
    cout << "2:"; iter_print(ms.begin(), ms.find(2), ms.end());
    cout << "3:"; iter_print(ms.begin(), ms.find(3), ms.end());
    cout << "6:"; iter_print(ms.begin(), ms.find(6), ms.end());

    cout << "\nmultiset equal_range" << endl;
    cout << "  "; iter_print(ms.begin(), ms.end());
    cout << "0:"; iter_print(ms.begin(), ms.equal_range(0), ms.end());
    cout << "2:"; iter_print(ms.begin(), ms.equal_range(2), ms.end());
    cout << "3:"; iter_print(ms.begin(), ms.equal_range(3), ms.end());
    cout << "6:"; iter_print(ms.begin(), ms.equal_range(6), ms.end());

    return 0;
  }

  実行結果:

  array find
    [1 2 2 4 5 6 7 8 8 8]
  0:[1 2 2 4 5 6 7 8 8 8|]
  3:[1 2 2 4 5 6 7 8 8 8|]
  8:[1 2 2 4 5 6 7|8 8 8]

  set find
    [1 2 4 5 6 7 8]
  0:[1 2 4 5 6 7 8|]
  2:[1|2 4 5 6 7 8]
  6:[1 2 4 5|6 7 8]

  multiset find
    [1 2 2 4 5 6 7 8 8 8]
  0:[1 2 2 4 5 6 7 8 8 8|]
  2:[1|2 2 4 5 6 7 8 8 8]
  3:[1 2 2 4 5 6 7 8 8 8|]
  6:[1 2 2 4 5|6 7 8 8 8]

  multiset equal_range
    [1 2 2 4 5 6 7 8 8 8]
  0:[()1 2 2 4 5 6 7 8 8 8]
  2:[1(2 2)4 5 6 7 8 8 8]
  3:[1 2 2()4 5 6 7 8 8 8]
  6:[1 2 2 4 5(6)7 8 8 8]

[関数オブジェクトの数学への応用:N次多項式とニュートン法]

  // N次多項式 f(x)
  template<class T,size_t N>
  class polynomial : public unary_function<T,T> {
    T factor_[N+1]; // 係数
  public:
    polynomial() {}
    explicit polynomial(const T* factor)
      { copy(factor,factor+N+1,factor_); }
    polynomial(const polynomial& p)
      { copy(p.factor_,p.factor_+N+1,factor_); }
    polynomial& operator=(const polynomial& p)
      { copy(p.factor_,p.factor_+N+1,factor_); return *this; }

    // f(x)を求める
    T operator()(const T& x) const {
      T xx = T(1);
      T sum = T(0);
      for ( int i = 0; i <= N; ++i ) {
        sum += factor_[i] * xx;
        xx *= x;
      }
      return sum;
    }

    // f(x)の微分f'(x) : N-1次多項式を返す。
    typedef polynomial<T,N-1> difference_type;
    difference_type difference() const {
      T tmp[N];
      for ( int i = 1; i <= N; ++i )
        tmp[i-1] = i * factor_[i];
      return difference_type(tmp);
    }

    friend ostream& operator<<(ostream& strm, const polynomial& p) {
      strm << "[ ";
      copy(p.factor_,p.factor_+Degree+1,ostream_iterator<T>(strm," "));
      return strm << ']';
    }

  };

  // ニュートン法による解の近似
  template<class Polynomial>
  class newton
    : public unary_function<Polynomial::argument_type,
                            Polynomial::result_type> {
    Polynomial p_;
    Polynomial::difference_type d_;
  public:
    newton(const Polynomial& p) : p_(p), d_(p.difference()) {}

    // x - f(x)/f'(x) は f(x) = 0 のよりよい近似解である...
    Polynomial::result_type
      operator()(const Polynomial::argument_type& x) const {
      return x - p_(x)/d_(x);
    }
  };

  /*
   * お試し
   */
  int main() {
    cout << "Enter a number: " << flush;
    double n;
    cin >> n;
    double tbl[3] = { 0, 0, 1 };
    tbl[0] = -n;
    polynomial<double,2> f(tbl); // f(x) = x*x - n
    // ニュートン法で f(x) = 0 の近似解を求める
    newton< polynomial<double,2> > solve(f);
    double x = n; // 初期値を n とする
    // 5回ほど繰り返してみよう...
    for ( int i = 0; i < 5; ++i ) {
      x = solve(x);
      cout << x << endl;
    }
    return 0;
  }

  実行結果:
    Enter a number: 5
    3
    2.33333
    2.2381
    2.23607
    2.23607

[ユーザ定義コンテナの例 : 固定長配列]

  template<class T>
  class array {
  public:

    // StdLib コンテナとコンパチなtypedef群
    typedef T         value_type;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*        iterator;
    typedef const T*  const_iterator;
    typedef std::reverse_iterator<iterator,value_type,reference,
                            iterator,difference_type> reverse_iterator;
    typedef std::reverse_iterator<const_iterator,value_type,
                  const_reference,const_iterator,difference_type>
                                                const_reverse_iterator;

    // コンストラクタ/デストラクタ
    explicit array(size_type size=0): size_(size)
      { data_ = size ? new T[size] : 0; }
    array(const array& x) {
        data_ = size() ? new T[size()] : 0;
        std::copy(x.begin(),x.end(),begin());
      }
    array(const_iterator first, const_iterator last) {
        size_ = std::distance(first,last);
        data_ = size() ? new T[size()] : 0;
        std::copy(first,last,begin());
      }
    ~array()
      { delete[] data_; }

    // コピー
    array& operator=(const array& x) {
        if ( this == &x ) return *this;
        if ( size() != x.size() ) {
          size_ = x.size();
          delete [] data_;
          data_ = size() ? new T[size()] : 0;
        }
        std::copy(x.begin(),x.end(),begin());
        return *this;
      }

    // 要素数 ( size() == max_size() とする)
    size_type size() const      { return size_; }
    size_type max_size() const  { return size_; }

    // 交換
    void      swap(array& x)
      { std::swap(data_,ar.data_); std::swap(size_,ar.size_); }

    // イテレータ群
    iterator               begin()        { return data_; }
    const_iterator         begin() const  { return data_; }
    iterator               end()          { return data_ + size(); }
    const_iterator         end() const    { return data_ + size(); }
    reverse_iterator       rbegin()
      { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const
      { return const_reverse_iterator(end()); }
    reverse_iterator       rend()
      { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const
      { return const_reverse_iterator(begin()); }

    // n番目の要素にアクセス
    reference       operator[](int n)       { return data_[n]; }
    const_reference operator[](int n) const { return data_[n]; }

    // 比較演算子群
    friend bool operator==(const array& x, const array& y);
      { return compare(x,y) == 0; }
    friend bool operator!=(const array& x, const array& y);
      { return compare(x,y) != 0; }
    friend bool operator< (const array& x, const array& y);
      { return compare(x,y) < 0; }
    friend bool operator<=(const array& x, const array& y);
      { return compare(x,y) <= 0; }
    friend bool operator> (const array& x, const array& y);
      { return compare(x,y) > 0; }
    friend bool operator>=(const array& x, const array& y);
      { return compare(x,y) >= 0; }

  private:
    T*         data_;
    int        size_;
    static int compare(const array<T>& x, const array<T>& y) {
      const_iterator ix = x.begin();
      const_iterator iy = y.begin();
      for ( ; ix != x.end() && iy != y.end(); ++ix, ++iy )
        if ( *ix < *iy ) return -1;
        else if ( *iy < *ix ) return 1;
      if ( x.size() == y.size() ) return 0;
      else return ( x.size() < y.size() ) ? -1 : 1;
    }

  };