I know you're exaggerating here a bit, but come on, a hash table not able to do lookups in micro-seconds is just garbage. I expect better of any language, not just C++.
The point I was trying to make, was that from productivity point of view, there are more relevant stuff to fix in C++ than algorithm complexity of STL implementations.
Like catching up with what Java 5 standard library offers for networking and parallel/concurrent programming.