The basic issue is that we didn't want to include external libraries, because it's a pain to debug, pain to build on multiple platforms and there are licensing issues.
Also we don't use so many datastructures, so we rolled our own and we are happy with them. For example we have an intrusive treemap, that has a function for returning the middle of a sorted key which is useful when you want to split a keyspace into two. Not sure if any of STL/Boost supports that.
Your solutions looks good, you are hired! ;) Seriously, we know that it is not that hard, but still the applicants have problems with it.