Accelerated C++ Chapter08

どもです。
調子の波が激しい。。。
それではいってみましょう。

メモ

• Iterator category
  • Input iterator
    • sequential read-only access
    • 要するに覗くだけ。
    • ==, !=, ++, * できる。
  • Ouptput iterator
    • sequential write-only access
    • 要するに書くだけ。ほんとか?
    • *iter = val できる。
    • back_inserter(container) で返ってくるやつも，output iterator。
  • Forward iterator
    • Output iterator の機能
    • 2回連続で，++iter できる。
  • Bidirectional iterator
    • Forward iterator の機能
    • -- できる。pre-decrement, post-decrement ね。
    • 例えば list のイテレータ
  • Random-access iterator
    • Bidirectional iterator の機能
    • 2項演算子の +，- を使用できる。
    • [], <, <=, >, >= 演算子
    • 例えば vector のイテレータ
  • Stream iterators
    • istream_iterator
      • copy(istream_iterator(cin), istream_iterator(), back_inserter(vec)) とか。
      • istream_iterator() は，eof かエラー状態に対して，「==」が true となる。
• あるイテレータがどの型を指しているか?
  • typename iterator_traits::value_type val;
    • iterator_traits はテンプレートクラス。
    • value_type は，typedef されている。

Exercises

なげーどー。
テストコードは全部削った。

Exercise 8-2

#include <algorithm>
#include <iostream>
#include <vector>
#include <stdexcept>
#include <iterator>
#include <cctype>
#include <map>
#include <numeric>

using namespace std;

template<class In>
bool my_equal(In start, In end, In start2)
{
  if (start > end) {
    return false;
  }
  else if (start == end) {
    return *start == *start2;
  }

  while (start < end) {
    if (*start != *start2) {
      return false;
    }
    ++start;
  }

  return true;
}

template<class For>
For my_search(For start, For end, For start2, For end2)
{
  if (start == end) {
    return start;
  }

  if (start2 == end2) {
    return end;
  }

  while (start != end) {
    while (start != end && *start != *start2) {
      ++start;
    }
    if (start == end) { return end; }

    For next_start = start;
    For needle_beg = start2;
    while (start != end && needle_beg != end2 && *start == *needle_beg) {
      ++start;
      ++needle_beg;
    }
    if (needle_beg == end2) {
      return next_start;
    }
    start = next_start + 1;
  }

  return end;
}

template<class In, class X>
In my_find(In start, In end, const X& x)
{
  while (start != end) {
    if (*start == x) {
      return start;
    }
    ++start;
  }
  return end;
}

template<class In, class Pred>
In my_find_if(In start, In end, Pred pred)
{
  while (start != end) {
    if (pred(*start)) {
      return start;
    }
    ++start;
  }
  return end;
}

template<class In, class Out>
Out my_copy(In start, In end, Out dest)
{
  if (start == end) { return dest; }
  while (start != end) {
    *dest++ = *start++;
  }
  return dest;
}

template<class In, class Out, class X>
Out my_remove_copy(In start, In end, Out out, X x)
{
  while (start != end) {
    if (*start != x) {
      *out = *start;
      ++out;
    }
    ++start;
  }

  return out;
}

template<class In, class Out, class Pred>
Out my_remove_copy_if(In start, In end, Out out, Pred pred)
{
  while (start != end) {
    if (!pred(*start)) {
      *out = *start;
      ++out;
    }
    ++start;
  }

  return out;
}

template<class For, class X>
For my_remove(For start, For end, const X& val)
{
  while (*start != val) {
    if (++start == end) {
      return start;
    }
  }

  For next = start;
  while (++next != end) {
    if (*next != val) {
      my_swap(start, next);
      ++start;
    }
  }
  return start;
}

template<class In, class Out, class Pred>
Out my_transform(In start, In end, Out out, Pred p)
{
  while (start != end) {
    *out = p(*start);
    ++start;
    ++out;
  }

  return out;
}

template<class I>
void my_swap(I a, I b)
{
  typename iterator_traits<I>::value_type tmp = *a;
  *a = *b;
  *b = tmp;
}

template<class For, class Pred>
For my_partition(For start, For end, Pred p)
{
  while (p(*start)) {
    if (++start == end) {
      return start;
    }
  }
  For next = start;
  // At this point, p(*start) yields false.
  while (++next != end) {
    if (p(*next)) {
      my_swap(start, next);
      ++start;
    }
  }

  return start;
}

template<class In, class T>
T my_accumulate(In start, In end, T val)
{
  if (start == end) {
    return val;
  }

  while (start != end) {
    val += *start;
    ++start;
  }
  return val;
}

Exercise 8-6

x is of type pair.

Exercise 8-7

イテレータ同士の足し算はサポートされていないから。
サポートされていたとしても，begin + end したら，どっかいってしまう。