STL Introduction

The Standard Template Library is a new C++ library that provides a set of easily composable C++ container classes and generic algorithms (template functions).

The container classes include vectors, lists, deques, sets, multisets, maps, multimaps, stacks, queues and priority queues.
The generic algorithms include a broad range of fundamental algorithms for the most common kinds of data manipulations, such as searching, sorting, merging, copying, and transforming.

At its July 1994 meeting, the ANSI/ISO C++ Standards Committee voted to adopt STL as part of the standard C++ library. The STL proposal to the committee by Alex Stepanov and Meng Lee of Hewlett-Packard Labs was based on research on generic programming and generic software libraries that Stepanov, Lee, and David Musser have been working on for several years, in Scheme, Ada, and C++.

Sequence Containers are objects that store collections of other objects in a strictly

vector<T>, which provides array-like random access to a sequence of varying length, with constant time insertions and deletions at the end
deque<T>, which provides random access to a sequence of varying length, with constant time insertions and deletions at both ends
list<T>, which provides linear time access to a sequence of varying length, with constant time insertions and deletions anywhere

Associative Containers provide for fast retrieval of objects from the collection based on keys. The size of the collection can vary at runtime. The collection is maintained in order, based on a comparison function object of type Compare (a default template parameter according to the STL standard, but a non-default template parameter in the current implementation).

set<T, Compare>, which supports unique keys (contains at most one of each key value) and provides for fast retrieval of the keys themselves.
multiset<T, Compare>, which supports duplicate keys (possibly contains multiple copies of the same key value) and provides for fast retrieval of the keys themselves.
map<Key, T, Compare>, which supports unique keys (contains at most one of each key value) and provides for fast retrieval of another type T based on the keys
multimap<Key, T, Compare>, which supports duplicate keys (possibly contains multiple copies of the same key value) and provides for fast retrieval of another type T based on the keys

All supported operations on associative containers have logarithmic time bounds (or in some cases amortized constant bounds).

A Container Adapters uses existing container classes and implements a unique interface. A container adaptor hides the public interface of the underlying container and implements its own.

stack<container<T> > is a data structure that exhibits push-down, pop-up behavior. The most recently inserted (pushed) element is the only own that can be extracted. Extraction of the logically topmost element pops that element from the stack - removes it so that the element inserted immediately before the popped element is now the next available element.
queue<container<T> > is a data structure wherein you insert elements at the end and extract elements from the beginning.
priority queue<container<T> > is a data structure wherein you insert elements at the end and extract the element that has the highest priority.