fork(2) download
copy 
  1. #include <cstdio>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace std;
  4. using namespace __gnu_pbds;
  5.  
  6. // we will use this class, it is able to do everything
  7. // simple map<int, int> can do, and as we can see, much more!
  8. typedef tree<int, int, less<int>, rb_tree_tag> Tree;
  9. // another choice is to use splay_tree_tag for splay tree implementation
  10.  
  11. void print_tree(Tree::node_iterator it, Tree::node_iterator null, int indent = 0)
  12. {
  13.     if (it == null)
  14.         return;
  15.     // that's how we can access left child and right child
  16.     // as I understand, there is no way to access parent node
  17.     print_tree(it.get_l_child(), null, indent + 1);
  18.     for (int i = 0; i < indent; i++)
  19.         printf("    ");
  20.     printf("(%d %d)\n", (**it).first, (**it).second);
  21.     // of course this is equal to:
  22.     // printf("(%d %d)\n", (*it)->first, (*it)->second);
  23.     print_tree(it.get_r_child(), null, indent + 1);
  24. }
  25.  
  26. int main()
  27. {
  28.     Tree X;
  29.     // we can use X like usual map container
  30.     for (int i = 0; i < 15; i++)
  31.         X[i * i] = i ^ (i + 1);
  32.     // we can iterate over it using iterators, begin() and end()
  33.     for (Tree::iterator it = X.begin(); it != X.end(); it++)
  34.         printf("%d %d\n", it->first, it->second);
  35.     /* output:
  36.      * 0 1
  37.      * 1 3
  38.      * 4 1
  39.      * 9 7
  40.      * 16 1
  41.      * 25 3
  42.      * 36 1
  43.      * 49 15
  44.      * 64 1
  45.      * 81 3
  46.      * 100 1
  47.      * 121 7
  48.      * 144 1
  49.      * 169 3
  50.      * 196 1
  51.      */
  52.     // but implementation gives us cool interface to access nodes of the tree!
  53.     Tree::node_iterator root = X.node_begin();
  54.     // for example we can print value at the root of the tree
  55.     // root has type node_iterator
  56.     // *root has type point_iterator == iterator (these two types are synonimic for trees)
  57.     // **root has containing type (pair<int, int> in our case)
  58.     printf("%d %d\n", (**root).first, (**root).second);
  59.     // output: 9 7 
  60.     // let's traverse the tree using methods get_l_node() and get_r_node()
  61.     print_tree(root, X.node_end()); // X.node_end() defines null (leaf terminator) for this tree
  62.     /* output:
  63.      *         (0 1)
  64.      *     (1 3)
  65.      *         (4 1)
  66.      * (9 7)
  67.      *            (16 1)
  68.      *         (25 3)
  69.      *             (36 1)
  70.      *     (49 15)
  71.      *             (64 1)
  72.      *         (81 3)
  73.      *                 (100 1)
  74.      *             (121 7)
  75.      *                     (144 1)
  76.      *                 (169 3)
  77.      *                     (196 1)
  78.      */
  79.     Tree Y;
  80.     // Now we are going to split by the key 42 
  81.     // (42 and greater are moving to the right operand Y, other keys remain in X tree)
  82.     X.split(42, Y);
  83.     print_tree(X.node_begin(), X.node_end());
  84.     /* output:
  85.      *         (0 1)
  86.      *     (1 3)
  87.      *         (4 1)
  88.      * (9 7)
  89.      *         (16 1)
  90.      *     (25 3)
  91.      *         (36 1)
  92.      */
  93.     print_tree(X.node_begin(), X.node_end());
  94.     /* output:
  95.      *         (0 1)
  96.      *     (1 3)
  97.      *         (4 1)
  98.      * (9 7)
  99.      *         (16 1)
  100.      *     (25 3)
  101.      *         (36 1)
  102.      */
  103.     // notice that both parts are absolutely balanced!
  104.     // we can merge them back
  105.     X.join(Y);
  106.     printf("%d\n", (int)X.size());
  107.     // output: 15 
  108.     // we can find lower bound for a key in this tree
  109.     Tree::iterator it = (X.lower_bound(42));
  110.     // it returns a usual iterator, not a node_iterator
  111.     // it's easy to understand that it is more formally correct: one can possibly
  112.     // use this tree as usual map, and it will be a big surprise, that lower_bound
  113.     // returns some strange node_iterator type instead of usual iterator
  114.     printf("%d %d\n", it->first, it->second);
  115.     // output: 49 15 
  116.     // but now some strange effect: we can simply cast node_iterator to iterator
  117.     // with dereferensing (*node_iterator = iterator), but I didn't found
  118.     // any other way to do the reverse cast (from iterator to node_iterator) except this:
  119.     Tree::node_iterator n_it = it.m_p_nd;
  120.     printf("%d %d\n", (*n_it)->first, (*n_it)->second);
  121.     // output: 49 15
  122.     // .m_p_nd field is left public, that is strange for c++-library style, but
  123.     // I don't know other ways to convert iterator to node_iterator. Any ideas?
  124.  
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1
1 3
4 1
9 7
16 1
25 3
36 1
49 15
64 1
81 3
100 1
121 7
144 1
169 3
196 1
9 7
        (0 1)
    (1 3)
        (4 1)
(9 7)
            (16 1)
        (25 3)
            (36 1)
    (49 15)
            (64 1)
        (81 3)
                (100 1)
            (121 7)
                    (144 1)
                (169 3)
                    (196 1)
        (0 1)
    (1 3)
        (4 1)
(9 7)
        (16 1)
    (25 3)
        (36 1)
        (0 1)
    (1 3)
        (4 1)
(9 7)
        (16 1)
    (25 3)
        (36 1)
15
49 15
49 15
https://ideone.com/JlJ86R
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!