std::unordered_map<> is a hash table. If you don't need to keep the items in your map sorted by key, it's very likely that you can use unordered_map instead of map, and in many cases the resulting code will be faster (e.g., if you have lots of entries (because hash tables have better asymptotic performance), or if key comparisons are expensive).

With "lots" being "several thousand." A std::map<> with a string key uses simple string comparison, so O(1) on the average length of the string keys (almost always very short) and O(log n) searches on the number of keys. Unless you choose a custom string hash and bucket sizes very carefully, or have a huge data set you're mapping, std::map<> with std::string keys will beat std::unordered_map<> every time, in terms of speed. It will also beat it when trying to debug, because the data is ordered making it easier to find missing or incorrect values (I calculate developer time as the most expensive resource I manage).

If your key is an integral value, std::unordered_map<> is sometimes a better bet because of memory allocation characteristics, but metrics are always your friend there. Fortunately, the standard map classes are almost entirely interchangeable at the code level so switching is easy.

For smaller data sets (on the order of hundreds) a std::vector<> almost always beats any other collection in terms of memory and speed. If it's created once and treated read-only it will always beat a std::map<> for lookup speed, but std::map<> usually still has simpler code for the same functionality.

I found this a bit hard to believe, so I just tested it from with "lots" being 10/100/1000/10000/10000.
MSVC 2012 (v11) x64. Full optimizations, and all std library safety features disabled.
Test code: http://pastebin.com/Y3rDK6Un
Creates string->int associations in a map, then does string->int lookups.

Results:
At every size, unordered_map beat map, but at size 10 it was close.
At size 10, a dumb, unsorted (linear search) vector beats map/unordered_map.
At size 100, unordered_map overtakes the dumb vector.
At size 1k, the dumb vector starts getting pretty bad.

I didn't try a sorted vector.
rde::hash_map is slightly better than std::unordered_map.
A custom solution out of a game engine trounces the generic implementations... even the thread safe (multi-producer/multi-consumer) MpmcHashTable beat them at all sizes :o

n.b. CheatTable is using void*'s copied out of the words array instead of strings, and is using the pointer value itself as an integral hash value, which is cheating... It actually happens to produce the same result as the other tables here -- I guess my compiler happened to merge duplicate string literals in my words array, making a pointer comparison just happen to work as a string comparison. It's in there as a theoretical limit.

std::map             size 10, Write: 0.065574 ms, Read: 0.006733 ms. Total: 0.072307. Result = 450
std::unordered_map   size 10, Write: 0.045082 ms, Read: 0.005269 ms. Total: 0.050351. Result = 450
VectorMap            size 10, Write: 0.007026 ms, Read: 0.007319 ms. Total: 0.014344. Result = 450
rde::hash_map        size 10, Write: 0.005855 ms, Read: 0.005269 ms. Total: 0.011124. Result = 450
eight::CheatTable    size 10, Write: 0.002635 ms, Read: 0.001756 ms. Total: 0.004391. Result = 450
eight::HashTable1    size 10, Write: 0.002927 ms, Read: 0.002342 ms. Total: 0.005269. Result = 450
eight::HashTable2    size 10, Write: 0.002927 ms, Read: 0.003513 ms. Total: 0.006440. Result = 450
eight::MpmcHashTable size 10, Write: 0.004684 ms, Read: 0.003806 ms. Total: 0.008489. Result = 450

std::map             size 100, Write: 0.324942 ms, Read: 0.076405 ms. Total: 0.401348. Result = 82620
std::unordered_map   size 100, Write: 0.218970 ms, Read: 0.045960 ms. Total: 0.264931. Result = 82620
VectorMap            size 100, Write: 0.149883 ms, Read: 0.143736 ms. Total: 0.293619. Result = 82620
rde::hash_map        size 100, Write: 0.048302 ms, Read: 0.038056 ms. Total: 0.086359. Result = 82620
eight::CheatTable    size 100, Write: 0.017564 ms, Read: 0.014930 ms. Total: 0.032494. Result = 82620
eight::HashTable1    size 100, Write: 0.021370 ms, Read: 0.017564 ms. Total: 0.038935. Result = 82620
eight::HashTable2    size 100, Write: 0.030738 ms, Read: 0.030152 ms. Total: 0.060890. Result = 82620
eight::MpmcHashTable size 100, Write: 0.038056 ms, Read: 0.034251 ms. Total: 0.072307. Result = 82620

std::map             size 1000, Write: 1.337533 ms, Read: 0.902227 ms. Total: 2.239761. Result = 9816120
std::unordered_map   size 1000, Write: 0.694089 ms, Read: 0.432671 ms. Total: 1.126760. Result = 9816120
VectorMap            size 1000, Write: 1.533962 ms, Read: 1.538061 ms. Total: 3.072023. Result = 9816120
rde::hash_map        size 1000, Write: 0.392858 ms, Read: 0.375587 ms. Total: 0.768445. Result = 9816120
eight::CheatTable    size 1000, Write: 0.152225 ms, Read: 0.147249 ms. Total: 0.299474. Result = 9816120
eight::HashTable1    size 1000, Write: 0.162764 ms, Read: 0.152811 ms. Total: 0.315575. Result = 9816120
eight::HashTable2    size 1000, Write: 0.368561 ms, Read: 0.280446 ms. Total: 0.649007. Result = 9816120
eight::MpmcHashTable size 1000, Write: 0.329626 ms, Read: 0.327870 ms. Total: 0.657496. Result = 9816120

std::map             size 10000, Write: 8.002951 ms, Read: 7.517586 ms. Total: 15.520537. Result = 998151120
std::unordered_map   size 10000, Write: 4.751770 ms, Read: 4.338713 ms. Total: 9.090483. Result = 998151120
VectorMap            size 10000, Write: 14.235112 ms, Read: 14.102500 ms. Total: 28.337612. Result = 998151120
rde::hash_map        size 10000, Write: 3.685315 ms, Read: 3.499425 ms. Total: 7.184740. Result = 998151120
eight::CheatTable    size 10000, Write: 0.809429 ms, Read: 0.824066 ms. Total: 1.633494. Result = 998151120
eight::HashTable1    size 10000, Write: 1.470145 ms, Read: 1.417744 ms. Total: 2.887889. Result = 998151120
eight::HashTable2    size 10000, Write: 2.505569 ms, Read: 2.508790 ms. Total: 5.014359. Result = 998151120
eight::MpmcHashTable size 10000, Write: 2.883498 ms, Read: 2.860371 ms. Total: 5.743869. Result = 998151120

std::map             size 100000, Write: 71.047925 ms, Read: 68.560212 ms. Total: 139.608137. Result = 1197253312
std::unordered_map   size 100000, Write: 42.130100 ms, Read: 41.244851 ms. Total: 83.374951. Result = 1197253312
VectorMap            size 100000, Write: 142.025591 ms, Read: 142.070088 ms. Total: 284.095679. Result = 1197253312
rde::hash_map        size 100000, Write: 36.894136 ms, Read: 36.317437 ms. Total: 73.211573. Result = 1197253312
eight::CheatTable    size 100000, Write: 8.363608 ms, Read: 8.631758 ms. Total: 16.995366. Result = 1197253312
eight::HashTable1    size 100000, Write: 13.579372 ms, Read: 13.788097 ms. Total: 27.367469. Result = 1197253312
eight::HashTable2    size 100000, Write: 25.309208 ms, Read: 25.565356 ms. Total: 50.874563. Result = 1197253312
eight::MpmcHashTable size 100000, Write: 29.521164 ms, Read: 29.549560 ms. Total: 59.070723. Result = 1197253312

Result is in there to see if the different structures happen to agree on the result of the test, and to thwart the optimizer.