libstructs

Educational C++17 implementations of core data structures used in systems and networking, with GoogleTest coverage and small benchmarks.

Build (Linux / WSL2)

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel
ctest --test-dir build --output-on-failure
./build/benchmarks/bench_hashmap

Structures

Structure	Typical op complexity	Networking tie-in
HashMap (Robin Hood)	Avg O(1) insert/lookup/erase	MAC tables, ARP caches
StringTrie / IPTrie	O(key bits / chars)	Longest-prefix IP lookup
LRUCache	O(1) get/put	Flow / ARP caches with eviction
RingBuffer / SPSCRingBuffer	O(1) push/pop	Packet and notification queues
AVLTree	O(log n) insert/erase/find	Ordered route indexes
MinHeap	O(log n) push/pop; O(log n) decrease-key	Dijkstra / SPF queues
BloomFilter	O(k) per op	Duplicate detection, filters

Benchmarks

Run the bench_* binaries locally; record numbers in your own environment for the README table when presenting.

What I learned

• Robin Hood hashing cuts variance in probe lengths versus plain linear probing.
• Lock-free SPSC queues need clear acquire/release pairing so the consumer never sees a value before it is constructed.
• AVL rebalancing invariants are easier to reason about when delete reuses subtree extract_min without leaking nodes.

License

MIT — see source headers for educational use.