Skip to content

Instantly share code, notes, and snippets.

@chenshuo
Last active October 9, 2021 07:48
Show Gist options
  • Save chenshuo/4574621 to your computer and use it in GitHub Desktop.
Save chenshuo/4574621 to your computer and use it in GitHub Desktop.
STL tree structure and benchmark.
#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;
}
}
#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));
}
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment