I used to write all my own datastructures, and used template based linked lists a LOT. I pretty much knew that I should have been using arrays / growing arrays, but I never really made the switch.
I also used template based binary trees which stored key-values for a lot of sorting stuff (inorder traversal). I never did implement balancing, and eventually I ran into a programming problem where I really needed better performance out of a typical "map" structure.
I did some tests with std::map and it totally blew my implementation away. At that point I sort of felt that enough was enough, and went through my codebase and switched everything to either std::vector or std::map, and everything performs much better as a result. I have roughly 1 million lines of code to maintain, so I reasoned that I could spend my time on better stuff than trying to maintain my own datastructures.
Other than those two fundamental structures I pretty much do everything from scratch. I do however still use C++ new / the heap / general purpose allocation.
What I'm wondering about is what would Casey's take be on getting away from STL, seeing as I only use a tiny (but performance critical) aspect of it. I pretty much know how to build a std::vector replacement (indeed I have a couple special purpose ones), but what about a replacement for std::map that performs as well as possible?
PS I really had a hard time getting used to the STL style iterators, so that would be nice to be free of again... DS