I need a fast data structure for string lookup, should I use a vector?

[Need4Sleep]

I'm writing an an AutoCompelete program for a competition in my local college programming group, and the person with the fastest program wins. Because of this I need a data structure that will store strings(the dictionary) and be able to access these strings very fast, will a std::vector be my best bet? Or would you guys recommend any other data structure for something like this?

The code challenge problem is as follows: You must build an autocomplete program in one of these languages: Java, C++, Ruby, Python, or PHP. The metric for winning the competition is going to be based on time to complete, so optimization is important. This means that if your program executes our input set faster than anyone else you win. Just to forewarn you though, our input set is going to be exceedingly large.

[cire]

std::unordered_map would be the usual culprit for fast string look up.

[doug4]

You might want to consider a trie.

http://en.wikipedia.org/wiki/Trie

[Smac89]

I second Trie due to the fact that it states autocomplete program. However, tries can sometimes be slow due to being a huge memory consumer. A hashtable like cire pointed is also worth implementing, you just gotta choose your hash function and internal data structure that deals with collisions :)

http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

[JLBorges]

A ternary search tree is a good candidate for fast prefix based auto-complete (search for suffixes / near-neighbour suffixes).
http://en.wikipedia.org/wiki/Ternary_search_tree

For infix based auto-complete (ie. constr would suggest std::piecewise_construct as an auto complete option), a suffix array would come in handy.
http://en.wikipedia.org/wiki/Suffix_array