Кратко:
- в STL есть след. основные понятия: контейнер (хранит данные), итератор (адресация данных внутри контейнера) и алгоритм (что-то делает с данными при помощи итераторов)
- на алгоритмы накладываются требования алгоритмической сложности, например sort() -- O(N log(N))
- на контейнеры и итераторы -- требования по public interface (например каждый контейнер должен иметь методы begin()/end())
- реализация -- персонально для каждого компилятора может быть своя
- map<> -- фактически бинарное дерево с данными вида <ключ, значение>. Поиск -- по аналогии с поиском в бинарном взвешенном дереве. Имеет смысл посмотреть hash_map<> (который в большинстве случаев, кроме клинических, на порядки быстрее). Проблема в том, что hash_map -- не стандартизирован, но все равно есть в практически каждой реализации STL
- list<> -- двусвязный список
А еще будет гораздо лучше, если почитать вот это:
http://www.sgi.com/tech/stl/
(начни с introduction to the STL) там же и примеры