(std::map and std::set are usually implemented with a Red-Black tree.)

(a) STL's map and set weren't implemented in an hour.

(b) Abstract data types (and, more generally, code libraries) predate C++ by decades.

Six years ago, I took over as lead dev for a product now counting and statistically modeling a significant percentage of all the packets traveling across the backbones of virtually every tier 1 ISP in the world. One of the first things I did there, coming off 3 years of C++ development, was to backport the STLport Red-Black tree, from the "map" template to an "rbtree.c" library.

My rbtree.c is faster than STLport's, and far easier to use. You don't need to read Meyers and keep a cheat sheet to avoid iterator invalidation to use it.

    * Binary search trees
    * AVL trees
    * Red-black trees

Thanks for the pointer, it's neat. I really like how my approach turned out; the STLport red-black tree is well done. Backporting it to C only took a couple hours.