1) std::vector, std::deque, std::list, std::map (a volte). Sono container autoincrementanti per lo storage dei dati. Le prestazioni dipende da quello che devi fare. Per accessi random (in stile array C, lo std::vector è indicato, ma superata una certa dimensione si autodimensione copiando per valore il contenuto in un nuovo buffer.
la std::list invece consente solo accessi sequenziali, quindi se devi accedere ad un elemento in mezzo ai due estremi ci mette di più, ma ha il vantaggio di non riallocarsi in automatico. La std::deque è una via di mezzo.

2) Non mi sembra che lo standard preveda hashtable. So che la Stl di SGI ne preveda una però, ma non l'ho mai usata.
Però con la std::map, puoi usare delle stringhe come chiave.