STL tree structure and benchmark.

tree-bench.cc

#include <set>

#include <stdio.h>
#include <sys/time.h>

double now()
{
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec + tv.tv_usec / 1000000.0;
}

class Usage // noncopyable
{
 public:
  Usage(int divide)
    : start_(now()),
      divide_(divide)
  { }

  ~Usage()
  {
    printf("%3d: %.4fs\n", divide_, (now() - start_)/divide_);
  }
 private:
  double start_;
  int divide_;
};

template<typename C>
class end_inserter_iterator
  : public std::iterator<std::output_iterator_tag, void, void, void, void>
{
 public:
  end_inserter_iterator(C& c)
    : container_(&c)
  {
  }

  // non-standard return type
  void operator=(typename C::const_reference value)
  {
    container_->insert(container_->end(), value);
  }

  end_inserter_iterator& operator*() { return *this; }
  // operator++ are omitted

 private:
  C* container_;
};

template<typename C>
end_inserter_iterator<C> end_inserter(C& c)
{
  return end_inserter_iterator<C>(c);
}

template<typename C>
class at_inserter_iterator
  : public std::iterator<std::output_iterator_tag, void, void, void, void>
{
 public:
  at_inserter_iterator(C& c, typename C::iterator it)
    : container_(&c),
      iter_(it)
  {
  }

  // non-standard return type
  void operator=(typename C::const_reference value)
  {
    iter_ = container_->insert(iter_, value);
  }

  at_inserter_iterator& operator*() { return *this; }
  // operator++ are omitted

 private:
  C* container_;
  typename C::iterator iter_;
};

template<typename C>
at_inserter_iterator<C> at_inserter(C& c, typename C::iterator it)
{
  return at_inserter_iterator<C>(c, it);
}

int main()
{
  std::set<int> s;

  printf("warm\n");
  {
    Usage u(10);
    for (int i = 0; i < 10 * 1000 * 1000; ++i)
      s.insert(i);
    s.clear();
  }

  const int N = 10;
  printf("end\n");
  for (int load = 1; load <= N; ++load)
  {
    s.clear();
    Usage u(load);
    for (int i = 0; i < load * 1000 * 1000; ++i)
      s.insert(s.end(), i);
  }

  printf("begin\n");
  for (int load = 1; load <= N; ++load)
  {
    s.clear();
    Usage u(load);
    for (int i = load * 1000 * 1000; i > 0; --i)
      s.insert(s.begin(), i);
  }

  printf("root\n");
  for (int load = 1; load <= N; ++load)
  {
    s.clear();
    Usage u(load);
    for (int i = 0; i < load * 1000 * 1000; ++i)
      s.insert(i);
  }

  printf("inserter end()\n");
  for (int load = 1; load <= N; ++load)
  {
    s.clear();
    Usage u(load);
    auto ins = inserter(s, s.end());
    for (int i = 0; i < load * 1000 * 1000; ++i)
      *ins = i;
  }

  printf("inserter begin()\n");
  for (int load = 1; load <= N; ++load)
  {
    s.clear();
    Usage u(load);
    auto ins = inserter(s, s.begin());
    for (int i = 0; i < load * 1000 * 1000; ++i)
      *ins = i;
  }

  printf("end_inserter\n");
  for (int load = 1; load <= N; ++load)
  {
    s.clear();
    Usage u(load);
    auto ins = end_inserter(s);
    for (int i = 0; i < load * 1000 * 1000; ++i)
      *ins = i;
  }

  printf("at_inserter end\n");
  for (int load = 1; load <= N; ++load)
  {
    s.clear();
    Usage u(load);
    auto ins = at_inserter(s, s.end());
    for (int i = 0; i < load * 1000 * 1000; ++i)
      *ins = i;
  }

  printf("at_inserter begin\n");
  for (int load = 1; load <= N; ++load)
  {
    s.clear();
    Usage u(load);
    auto ins = at_inserter(s, s.begin());
    for (int i = 0; i < load * 1000 * 1000; ++i)
      *ins = -i;
  }
}

tree-structure.cc

#include <functional> // std::less
#include <utility> // std::pair

#include <stdio.h>

/**
 * Non-template code
 **/

enum rb_tree_color { kRed, kBlack };

struct rb_tree_node_base
{
  rb_tree_color       color_;
  rb_tree_node_base*  parent_;
  rb_tree_node_base*  left_;
  rb_tree_node_base*  right_;
};

// defined in library, not in header
rb_tree_node_base* rb_tree_increment(rb_tree_node_base* node);
// others: decrement, reblance, etc.

/**
 * template code
 **/

template<typename Value>
struct rb_tree_node : public rb_tree_node_base
{
  Value value_field_;
};

template<typename Value>
struct rb_tree_iterator
{
  Value& operator*() const
  {
    return static_cast<rb_tree_node<Value>*>(node_)->value_field_;
  }

  rb_tree_iterator& operator++()
  {
    node_ = rb_tree_increment(node_);
    return *this;
  }

  rb_tree_node_base* node_;
};

template<typename Key, typename Value> // key_compare and allocator
class rb_tree
{
 public:
  typedef std::less<Key> key_compare;
  typedef rb_tree_iterator<Value> iterator;
 protected:

  struct rb_tree_impl // : public node_allocator
  {
    key_compare       key_compare_;
    rb_tree_node_base header_;
    size_t            node_count_;
  };
  rb_tree_impl impl_;
};

template<typename Key, typename T> // key_compare and allocator
class map
{
 public:
  typedef std::pair<const Key, T> value_type;
 private:
  typedef rb_tree<Key, value_type> rep_type;
  rep_type tree_;
};

int main()
{
  map<int, int> m;
  printf("%zd\n", sizeof(m));
}

tree-traversal.py

#!/usr/bin/python

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

class Tree:
    def __init__(self):
        self.root = None
        self.node_count = 0

def printTree(node):
    if node:
        printTree(node.left)
        print node.data
        printTree(node.right)

def visit(node, func):
    if node:
        printTree(node.left)
        func(node.data)
        printTree(node.right)

def travel(root):
    if root.left:
        # yield from travel(root.left)
        for x in travel(root.left):
            yield x
    yield root.data
    if root.right:
        # yield from travel(root.right)
        for y in travel(root.right):
            yield y

if __name__ == '__main__':
    nodes = []
    for x in range(7):
        nodes.append(Node(x))

    nodes[1].left  = nodes[0]
    nodes[1].right = nodes[2]
    nodes[3].left  = nodes[1]
    nodes[3].right = nodes[5]
    nodes[5].left  = nodes[4]
    nodes[5].right = nodes[6]
    root = nodes[3]

    print "embed:"
    printTree(root)

    print "visit:"
    def printer(data):
        print data

    visit(root, printer)

    print "yield:"
    for y in travel(root):
        print y