DynSetTree (dynamic set) with multiple BST backends in Aleph-w. More...

#include <iostream>
#include <iomanip>
#include <chrono>
#include <vector>
#include <algorithm>
#include <tclap/CmdLine.h>
#include <tpl_dynSetTree.H>
#include <cstdlib>

Include dependency graph for dynset_trees.C:

Classes
struct	TimingResult

Typedefs
using	AvlSet = DynSetTree< int, Avl_Tree >

using	RbSet = DynSetTree< int, Rb_Tree >

using	SplaySet = DynSetTree< int, Splay_Tree >

using	TreapSet = DynSetTree< int, Treap >

using	RandSet = DynSetTree< int, Rand_Tree >

using	AvlRkSet = DynSetTree< int, Avl_Tree_Rk >

using	TreapRkSet = DynSetTree< int, Treap_Rk >

Functions
template<typename Set >
TimingResult	benchmark_set (const string &name, const vector< int > &data, bool verbose)

void	demonstrate_basic_operations ()

void	demonstrate_tree_types ()

void	demonstrate_ranked_operations ()

void	demonstrate_functional_features ()

void	run_performance_comparison (size_t n, unsigned int seed, bool verbose)

int	main (int argc, char *argv[])

Detailed Description

DynSetTree (dynamic set) with multiple BST backends in Aleph-w.

Overview

This example demonstrates DynSetTree, a uniform set interface whose underlying ordered structure is selected via template parameter.

It highlights:

Basic set operations (insert/search/remove/iteration).
Comparing multiple tree backends under the same API.
Optional rank-capable backends (order statistics).
A simple performance benchmark (insert/search/remove timings + structural stats).

Data model used by this example

Key type: int
Container abstraction: DynSetTree<int, TreeBackend>
Comparator: default Aleph::less<int>

Tree backends shown here

Standard (non-ranked) backends:

Avl_Tree, Rb_Tree, Splay_Tree, Treap, Rand_Tree

Ranked backends used by this file:

Avl_Tree_Rk, Treap_Rk

Note: Aleph-w also provides other ranked variants (e.g. Rb_Tree_Rk, Splay_Tree_Rk), but this example does not instantiate them.

Usage / CLI

This example uses TCLAP. Options:

--count / -n <size_t>: number of elements used for the performance test (default: 100000).
--seed / -s <unsigned>: RNG seed (0 means use time(); default: 0).
--all / -a: run all demonstrations (not only the performance benchmark).
--verbose / -v: print extra per-tree statistics.
--help: show help.

# Performance benchmark only (default behavior)
./dynset_trees
 
# Control dataset size and seed
./dynset_trees --count 10000 --seed 42
 
# Run all demos + benchmark
./dynset_trees --all --count 10000
 
# Verbose per-tree statistics
./dynset_trees --count 50000 --seed 42 --verbose
 
# Show help
./dynset_trees --help

Complexity

Expected/typical per-operation complexities by backend:

AVL / RB: O(log n) worst-case
Splay: O(log n) amortized
Treap / Rand tree: O(log n) expected

The benchmark section measures these costs empirically for one workload (random keys).

Pitfalls and edge cases

Random-key benchmarks may not match real workloads (ordered inserts, locality, skewed distributions).
Timing results depend on build flags and CPU frequency scaling.