Ah. C++ was mentioned in a different sub-thread. I may be wrong but I don't think the C++ standard says anything about red-black trees. It just provides big-

Ah. C++ was mentioned in a different sub-thread. I may be wrong but I don't think the C++ standard says anything about red-black trees. It just provides big-O bounds on operations that mean that you need to pick some sort of balanced binary tree to implement std::set and std::map. C++ containers are usually suboptimal compared to writing the code you actually need for the situation you're really in. In most programs you have a lot of situations where you can just use a pretty basic data structure like a linked list or a dynamic array and the performance characteristics don't matter much. Then you have one big data structure or a couple of big data structures that need to use something a bit esoteric. Those are where you should probably just write your own. For example, a text editor is going to have a lot of collections of things. But most of them are very small, and AVL tree vs RB tree vs B-tree simply does not matter. But the buffer representation itself will be some sort of custom data structure: maybe a piece table, a piece tree, a gap buffer, or a rope, or maybe something new. Either way, it's not going to be a reusable data structure. What I'm saying is that in practice, there's very little actual value in having generic data structures beyond the very most basics. See Go, see C. So I don't think the facility for implementing 'optimal' generic data structures as libraries is particularly useful, and in practice they're suboptimal anyway.