This project provides scapegoat tree-based alternatives to all STL ordered associative containers: set, map, multiset, multimap and 1 more, intervalmap.

The scapegoat tree is the simplest and least resource-demanding self-balancing binary search tree. Because of their low overhead, use of the <=> operator (2 comparisons for the price of 1) and because they share common properties with all other BST-based containers, the scapegoat tree-based sg:: containers sometimes outperform std:: containers, while requiring less resources.

Any BST implementation can serve as a basis for an ìntervalmap implementation, but choosing the scapegoat tree conserves some resources and, hopefully, makes for a more robust implementation. set, map, multiset and multimap are stepping stones, in a way, towards an ìntervalmap implementation.

g++ -std=c++20 -Ofast set.cpp -o s
g++ -std=c++20 -Ofast map.cpp -o m