What is the STL, and what are the main container types and their complexity?

The Standard Template Library is built from containers, iterators, and algorithms, connected so that algorithms work on any container through iterators.

Sequence containers:

• vector — contiguous, dynamically resized. Random access O(1), push_back amortised O(1), insert or erase in the middle O(n). This should be your default container — contiguity makes it cache-friendly, which usually beats better asymptotic complexity at real sizes.
• deque — O(1) insertion at both ends, random access O(1), but not contiguous.
• list — doubly linked. O(1) insert or erase given an iterator, but O(n) to find anything and poor cache behaviour. Rarely the right choice in practice.

Associative containers:

• map / set — balanced binary trees. O(log n) lookup, and iteration in sorted order.
• unordered_map / unordered_set — hash tables. O(1) average lookup, O(n) worst case, no ordering.

Note: Iterator invalidation is the follow-up to be ready for. Inserting into a vector may reallocate and invalidate every iterator, pointer, and reference into it; list and map invalidate only what you erase. Modifying a container while iterating over it is one of the most common C++ bugs.