Ygg (short for Yggdrasil) is a C++17 implementation of several intrusive data structures:

• several balanced binary search trees:
  • a red-black Tree
  • a Zip Tree
  • a weight balanced tree (aka BB[α]-tree)
• an Interval Tree
• a Doubly-Linked List
• a Dynamic Segment Tree (which is something between a segment tree and an interval map)
  • … based on a Red-Black Tree
  • … based on a Zip Tree

If you need a Red-Black-Tree, a Zip Tree, a Segment Tree or an Interval Tree in your C++ application, and for some reason the existing implementations (like std::set or boost::instrusive::rbtree) are not suited for you, Ygg may be the answer. Also, I do not know of any other implementation of the “Dynamic Segment Tree” (if you know something similar, please let me know!)

See the list of features below for why Ygg is awesome!

If you’re not sure whether one of these data structures is the right data structure for your application, check out the datastructure overview in the Documentation.

Features

• It’s intrusive! Like the containers in boost::intrusive, Ygg follows a ‘bring your own data structure’ approach. Depending on your use case, this can save a lot of time by avoiding memory allocation and copying stuff around.
• You can be notified when stuff happens. Want to do something to the tree nodes every time a tree rotation happens? Need to know whenever two nodes swap places in the tree? Look no further. Ygg will call methods specified by you on several occasions. In fact, that’s how the Interval Tree (the augmented tree version from Cormen et al.) is implemented.
• It’s pretty fast. Doing benchmarks correctly is pretty difficult. However, performance should not be too far away from boost::intrusive::rbtree. Comparing against std::set is unfair - std::set loses because it needs to do memory allocation.