コンテナslistの実装:プログラミング原論(ステパノフ)の補助資料

プログラミング原論(ステパノフ)のサンプルコードはここにあるのですが、1万行を超えていることもあり、少し読むのに時間もかかります。ということで、単方向リンクリスト(slist)に関係するところだけ引っ張り出して、テストを書いてみました。他のコンテナ(list, slist, array..)も同じような関数でできているので、他の部分を読むのにも役立つと思います。

#include<cstddef>// NULL, ptrdiff_t
#include<new>// placement operator new
#include<cassert>// assert
#include<cstdlib>// malloc, free
template<typename T>
bool operator!=(const T& x, const T& y) {
  return !(x == y);
}
#define pointer(T) T*
template<typename T>
T& sink(pointer(T) x) {
  return *x;
}
template<typename T>
T& source(pointer(T) x) {
  return *x;
}
template<typename T>
T& deref(pointer(T) x) {
  return *x;
}
template<typename T>
pointer(T) successor(pointer(T) x) {
  return x + ptrdiff_t(1);
}
template<typename S>
struct iterator_type;
#define IteratorType(S) typename iterator_type<S>::type
template<typename T>
struct value_type;
#define ValueType(T) typename value_type<T>::type
template<typename T>
struct underlying_type {
  typedef T type;
};
#define UnderlyingType(T) typename underlying_type<T>::type
template<typename T>
UnderlyingType(T)& underlying_ref(T& x) {
  return reinterpret_cast<UnderlyingType(T)&>(x);
}
template<typename W>
bool empty(const W& x) {
  return begin(x) == end(x);
}
template<typename T>
struct slist_node {
  T value;
  pointer(slist_node) forward_link;
  slist_node(const T& v, pointer(slist_node) f): value(v), forward_link(f) {} 
};
template<typename T>
struct slist_iterator {
  pointer(slist_node<T>) p;
  slist_iterator(): p(NULL) {}
  slist_iterator(pointer(slist_node<T>) p): p(p) {}
};
template<typename T>
bool operator==(const slist_iterator<T>& x, const slist_iterator<T>& y) {
  return x.p == y.p;
}
template<typename T>
const T& source(slist_iterator<T> x) {
  return source(x.p).value;
}
template<typename T>
T& sink(slist_iterator<T> x) {
  return sink(x.p).value;
}
template<typename T>
void set_link_forward(slist_iterator<T> i, slist_iterator<T> j) {
  sink(i.p).forward_link = j.p;
}
template<typename T>
slist_iterator<T>  successor(const slist_iterator<T>& x) {
  return slist_iterator<T>(sink(x.p).forward_link);
}
template<typename T>
struct slist {
  slist_iterator<T> first;
  slist(): first(NULL) {}
  template<typename W>
  slist(const W& w) {
    dynamic_sequence_construction(sink(this), w);
  }
  ~slist() {
    erase_all(sink(this));
  }
};
template<typename T>
struct underlying_type< slist<T> > {
  typedef slist_iterator<T> type;
};
template<typename T>
struct value_type< slist<T> > {
  typedef T type;
};
template<typename T>
struct iterator_type< slist<T> > {
  typedef slist_iterator<T> type;
};
template<typename T>
IteratorType(slist<T>) begin(const slist<T>& x) {
  return x.first;
}
template<typename T>
IteratorType(slist<T>) end(const slist<T>&) {
  return slist_iterator<T>();
}
template<typename S>
struct after {
  typedef IteratorType(S) I;
  pointer(S) s;
  I i;
  after(S& s, I i): s(&s), i(i) {}
};
template<typename S>
struct value_type< after<S> >{
  typedef ValueType(S) type;
};
template<typename S>
S& base(after<S>& p) {
  return deref(p.s);
}
template<typename S>
IteratorType(S) current(after<S>& x) {
  return x.i;
}
template<typename S>
IteratorType(S) begin(after<S>& x) {
  return begin(base(x));
}
template<typename S>
IteratorType(S) end(after<S>& x) {
  return end(base(x));
}
template<typename T>
void construct(T& p) {
  new (&p) T();
}
template<typename T, typename U>
void construct(T& p, const U& initializer) {
  new (&p) T(initializer);
}
template<typename T>
void destroy(T& p) {
  sink(&p).~T();
}
template<typename T, typename U>
void insert_0(after< slist<T> >& p, const U& u) {
  assert(current(p) == end(p));
  slist_iterator<T> i((slist_node<T>*)malloc(sizeof(slist_node<T>)));
  construct(sink(i), u);
  set_link_forward(i, begin(p));
  base(p).first = i;
}
void test_insert_after_0(void) {
  typedef int Z;
  slist<Z> s;
  after< slist<Z> >  w(s, end(s));
  insert_0(w, Z(2));
  assert(Z(2) == source(s.first));
}
template<typename T, typename U>
after< slist<T> > insert(after< slist<T> >& p, const U& u) {
  slist_iterator<T> i((slist_node<T>*)malloc(sizeof(slist_node<T>)));
  construct(sink(i), u); 
  if(current(p) == end(p)) {
    set_link_forward(i, begin(p));
    base(p).first = i;
  } else {
    set_link_forward(i, successor(current(p)));
    set_link_forward(current(p), i);
  }
  return after< slist<T> >(base(p), i);
}
void test_insert_after(void) {
  typedef int Z;
  slist<Z> s;
  after< slist<Z> >  w(s, end(s));
  int i;
  for(i = 0; i < 6; i++)
    w = insert(w, Z(i));
  slist_iterator<Z> p = s.first;
  for(i = 0; i < 6; i ++) {
    assert(Z(i) == source(p));
    p = successor(p);
  }
}
template<typename T>
struct distance_type;
#define DistanceType(T) typename distance_type<T>::type
template<typename T>
struct distance_type<pointer(T)> {
  typedef T type;
};
template<typename I>
struct counted_range{
  typedef DistanceType(I) N;
  N n;
  I f;
  counted_range(I f, N n): f(f), n(n) {}
};
template<typename I>
struct iterator_type< counted_range<I> > {
  typedef I type;
};
template<typename I>
I begin(const counted_range<I>& x) {
  return x.f;
}
template<typename I>
I end(const counted_range<I>& x) {
  return x.f + x.n;
}
template<typename I, typename O>
void copy_step(I& f_i, O& f_o) {
  sink(f_o) = source(f_i);
  f_i = successor(f_i);
  f_o = successor(f_o);
}
template<typename I, typename O>
void copy(I f_i, I f_l, O f_o) {
  while(f_i != f_l) copy_step(f_i, f_o);
}
void test_copy(void) {
  typedef int Z;
  slist<Z> s;
  after< slist<Z> >  w(s, end(s));
  int i;
  for(i = 0; i < 6; i++)
    w = insert(w, Z(i));
  Z a[6];
  counted_range<Z*> s2(a, sizeof(a)/sizeof(a[0]));  
  copy(begin(s), end(s), begin(s2));
  for(i = 0; i < 6; i++)
    assert(a[i] == i);
}
template<typename P>
struct insert_iterator {
  P p;
  insert_iterator(const P& p): p(p) {}
  void operator=(const ValueType(P)& x) { p = insert(p, x);}
};
template<typename P>
insert_iterator<P> successor(const insert_iterator<P>& x) {
  return x;
}
template<typename P>
insert_iterator<P>& sink(insert_iterator<P>& i) {
  return i;
}
template<typename P, typename W>
void insert_range(P p, const W& w) {
 copy(begin(w), end(w), insert_iterator<P>(p));
}
void test_insert_range(void) {
  typedef int Z;
  Z a[] = {0,1,2,3,4,5};
  slist<Z> s;
  after< slist<Z> > p(s, end(s));
  insert_range(p, counted_range<Z*>(a, sizeof(a)/sizeof(a[0])));
  int i = 0;
  slist_iterator<Z> f = begin(s);
  slist_iterator<Z> l = end(s);
  while(f != l) {
    assert(source(f) == i++);
    f = successor(f);
  }
}
template<typename T>
void swap(T& x, T& y) {
  UnderlyingType(T) tmp = underlying_ref(x);
  underlying_ref(x) = underlying_ref(y);
  underlying_ref(y) = tmp;
}
template<typename S, typename W>
void dynamic_sequence_construction(S& s, const W& w) {
  construct(s);
  S tmp;
  insert_range(after<S>(tmp, end(tmp)), w);
  swap(s, tmp);
}
void test_dynamic_sequence_construction(void) {
  typedef int Z;
  Z a[] = {0,1,2,3,4,5};
  slist<Z> s(counted_range<Z*>(a, sizeof(a)/sizeof(a[0])));
  slist_iterator<Z> f = begin(s);
  slist_iterator<Z> l = end(s);
  int i = 0;
  while(f != l) {
    assert(source(f) == i++);
    f = successor(f);
  }
  assert(6 == i);
}
template<typename T>
slist_iterator<T> erase_first(slist_iterator<T> i) {
  slist_iterator<T> j = successor(i);
  destroy(sink(i));
  free(i.p);
  return j;
}
template<typename T>
void erase_first(slist<T>& x) {
  x.first = erase_first(begin(x));
}
void test_erase_first(void) {
  typedef int Z;
  Z a[] = {0,1,2,3,4,5};
  slist<Z> s(counted_range<Z*>(a, sizeof(a)/sizeof(a[0])));
  erase_first(s);
  slist_iterator<Z> f = begin(s);
  slist_iterator<Z> l = end(s);
  int i = 1;
  while(f != l) {
    assert(source(f) == i++);
    f = successor(f);
  }
  assert(6 == i);
}
template<typename T>
void erase_all(slist<T>& x) {
  while(!empty(x)) erase_first(x);
}
void test_erase_all(void) {
  typedef int Z;
  Z a[] = {0,1,2,3,4,5};
  slist<Z> s(counted_range<Z*>(a, sizeof(a)/sizeof(a[0])));
  erase_all(s);
  assert(empty(s));
}
int main(void) {
  test_insert_after_0();
  test_insert_after();
  test_copy();
  test_insert_range();
  test_dynamic_sequence_construction();
  test_erase_first();
  test_erase_all();
  return 0;
}