Much more importantly, vectors are almost always the wrong answer (with a handful of exceptions). Consider a perfectly balanced tree with even 1k elements -- it will have height log2(1k) ~ 10, so approximately 11 reads, almost certainly from main memory, to access an element.
Exceptions are things like you have to iterate through elements in some order, a very high ratio of inserts/deletes to queries, etc -- the obvious stuff.
My apologies. But, I maintain that trees have their uses. I would never use a hashmap to implement a priority queue, and i'd never use a tree to implement associative arrays!