1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 |
- /////////////////////////////////////////////////////////////////////////////
- //
- // (C) Copyright Ion Gaztanaga 2006-2013
- //
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //
- // See http://www.boost.org/libs/intrusive for documentation.
- //
- /////////////////////////////////////////////////////////////////////////////
- //[doc_rbtree_algorithms_code
- #include <boost/intrusive/rbtree_algorithms.hpp>
- #include <cassert>
- struct my_node
- {
- my_node(int i = 0)
- : int_(i)
- {}
- my_node *parent_, *left_, *right_;
- int color_;
- //other members
- int int_;
- };
- //Define our own rbtree_node_traits
- struct my_rbtree_node_traits
- {
- typedef my_node node;
- typedef my_node * node_ptr;
- typedef const my_node * const_node_ptr;
- typedef int color;
- static node_ptr get_parent(const_node_ptr n) { return n->parent_; }
- static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; }
- static node_ptr get_left(const_node_ptr n) { return n->left_; }
- static void set_left(node_ptr n, node_ptr left) { n->left_ = left; }
- static node_ptr get_right(const_node_ptr n) { return n->right_; }
- static void set_right(node_ptr n, node_ptr right) { n->right_ = right; }
- static color get_color(const_node_ptr n) { return n->color_; }
- static void set_color(node_ptr n, color c) { n->color_ = c; }
- static color black() { return color(0); }
- static color red() { return color(1); }
- };
- struct node_ptr_compare
- {
- bool operator()(const my_node *a, const my_node *b)
- { return a->int_ < b->int_; }
- };
- int main()
- {
- typedef boost::intrusive::rbtree_algorithms<my_rbtree_node_traits> algo;
- my_node header, two(2), three(3);
- //Create an empty rbtree container:
- //"header" will be the header node of the tree
- algo::init_header(&header);
- //Now insert node "two" in the tree using the sorting functor
- algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());
- //Now insert node "three" in the tree using the sorting functor
- algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());
- //Now take the first node (the left node of the header)
- my_node *n = header.left_;
- assert(n == &two);
- //Now go to the next node
- n = algo::next_node(n);
- assert(n == &three);
- //Erase a node just using a pointer to it
- algo::unlink(&two);
- //Erase a node using also the header (faster)
- algo::erase(&header, &three);
- return 0;
- }
- //]
|