Sorted input warning
Inserting already sorted values is the fastest way to create the worst-case shape. If that pattern is common in your workload, this container may not be the right fit.
Performance
How tree shape affects cost
Because this library is a normal Binary Search Tree and not a self-balancing tree, performance depends heavily on insertion order and resulting tree height.
Complexity table
| Operation | Average | Worst |
|---|---|---|
| Search | O(log N) |
O(N) |
| Insert | O(log N) |
O(N) |
| Erase | O(log N) |
O(N) |
lower_bound / upper_bound |
O(log N) |
O(N) |
| Traversal | O(N) |
O(N) |
size / empty |
O(1) |
O(1) |
Balanced vs. unbalanced shape
When the tree remains relatively balanced, lookups tend to follow short paths from the root to the requested node. When values are inserted in sorted order, the structure can become skewed and behave more like a linked list.
Text
1
\
2
\
3
\
4When to use this library
- When you want a lightweight educational BST implementation.
- When you need a simple header-only dependency for experiments or teaching.
- When readable implementation code matters as much as the container surface.
When not to use this library
- When you need guaranteed logarithmic operations under arbitrary insertion order.
- When your workload naturally arrives pre-sorted or nearly sorted.
- When a standard associative container such as
std::setbetter matches your requirements.