For the following problem, a sorted vector will be faster than an STL map (or STL set, use the same structure internally) as well.
Given a list of words, and then a list of queries, determine which query words were in the input list of words.
The STL map is nice when your data constantly changing. if it's static, sticking it in a vector, sorting once, and then using binary search will be faster.
The map has to do lots of fancy footwork to be able to locate and remove an item at any phase during its construction. The sorted vector doesn't have those constraints.