- Deterministic data structures (eg. a set that acts deterministic to the fact that addresses might be somehow randomly assigned, very useful for ensuring reproducibility)
Already cited, but it's clearly among the most elegant:
- union-find (!!!!)
and as a bonus one that is easily overlooked:
-std::deque, that when restricted to push_back() or push_front() guarantees not to ever move objects around.