3 ms·
Surely you're not implying that vectors, hash tables, and sets are hard to write in C.
by thomasptacek 19y ago
Surely you're not implying that vectors, hash tables, and sets are hard to write in C.
- jey 19y agoOK, then I want you to write me an efficient implementation of Red-Black tree deletion, and do it within an hour. (std::map and std::set are usually implemented with a Red-Black tree.)
- thomasptacek 19y agoWhat a silly argument. (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.
- portLAN 19y agolibavl. Next?
- thomasptacek 19y agoEww. Better to use C++ than AVL trees.
- portLAN 19y agohttp://www.stanford.edu/~blp/avl/ http://www.stanford.edu/~blp/avl/ * Binary search trees * AVL trees * Red-black trees
- thomasptacek 19y agoOh. This is a library under straight GPL. You can't use it in non-GPL code. No wonder I hadn't heard of it before. 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.