This test creates a container, inserts random integers into the the container, and then checks the order-statistics of the container's values. (If the container is one of pb_ds 's trees, it does this with the order_of_key method of tree_order_statistics_node_update ; otherwise, it uses the find method and std::distance .) It measures the average time for such queries as a function of the number of values inserted.
(The test was executed with tree_order_statistics_timing_test 200 200 2100)
The test checks the performance difference of policies based on node-invariant as opposed to a external functions. (see Design::Associative Containers::Tree-Based Containers::Node Invariants .)
Figures NTG, NTM, and NTL show the results for the native and tree-based containers in g++, msvc++, and local, respectively.
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
In this test, the native red-black tree can support order-statistics queries only externally, by performing a find (alternatively, lower_bound or upper_bound ) and then using std::distance . This is clearly linear, and it is not that surprising that the cost is high.
pb_ds 's tree-based containers use in this test the order_of_key method of tree_order_statistics_node_update. This method has only linear complexity in the length of the root-node path. Unfortunately, the average path of a splay tree (tree with Tag = splay_tree_tag ) can be higher than logarithmic; the longest path of a red-black tree (tree with Tag = rb_tree_tag ) is logarithmic in the number of elements. Consequently, the splay tree has worse performance than the red-black tree.