STL components:

- Containers

  - Sequential containers: vector, deque, list
  - Associative containers: map, multimap, set, multiset
  - C++0X: unsorted associative containers (hash)

- Algorithms

  - Nonmodifying sequential algorithms
  - Modifying sequential algorithms
  - Sorted container algorithms

- Adaptors
  - Container adaptors: stack, queue, priority_queue
  - Others: iterator adaptors, inserters, etc.

- Functors, binders, ...

- Allocators



Types defined in a container:


template <class T, class A = allocator<T> > class std::vector {
public:
    // types:

    typedef T value_type;           // type of element
    typedef A allocator_type;       // type of memory manager
    typedef typename A::size_type size_type;
    typedef typename A::difference_type difference_type;

    typedef implementation_dependent1 iterator;         // T*
    typedef implementation_dependent2 const_iterator;   // const T*
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    typedef typename A::pointer pointer;        // pointer to element
    typedef typename A::const_pointer const_pointer;
    typedef typename A::reference reference;    // reference to element
    typedef typename A::const_reference const_reference;

    // ...
};


Usage of types declared in a container
makes you be able to write generic code


template<class C> typename C::value_type sum(const C& c)
{
    typename C::value_type s = 0;
    typename C::const_iterator p = c.begin();   // start at the beginning
    while (p!=c.end()) {                        // continue until the end
        s += *p;        // get value of element
        ++p;            // make p point to next element
    }
    return s;
}



Iterators and references


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // iterators:

    iterator begin();           // points to first element
    const_iterator begin() const;
    iterator end();             // points to one-past-last element
    const_iterator end() const;

    reverse_iterator rbegin();  // points to first element of reverse sequence
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();    // points to one-past-last element
    const_reverse_iterator rend() const;

    // ...
};


Usage of reverse iterator


template<class C> typename C::iterator find_last(C& c, typename C::value_type v)
{
    typename C::reverse_iterator ri = find(c.rbegin(),c.rend(),v);
    if (ri == c.rend()) return c.end(); // use c.end() to indicate "not found"
    typename C::iterator i = ri.base();
    return --i;
}



template<class C> typename C::iterator find_last(C& c, typename C::value_type v)
{
    typename C::iterator p = c.end();   // search backwards from end
    while (p!=c.begin())
        if (*--p==v) return p;
    return c.end();             // use c.end() to indicate "not found"
}



template<class C> typename C::iterator find_last(C& c, typename C::value_type v)
{
    typename C::reverse_iterator p = c.rbegin();    // view sequence in reverse
    while (p!=c.rend()) {
        if (*p==v) {
            typename C::iterator i = p.base();
            return --i;
        }
        ++p;            // note: increment, not decrement (--)
    }
    return c.end(); // use c.end() to indicate "not found"
}

  

  i = ri.base();


         rend()      ri   rbegin()
           |          |       |
           V          V       V
              -------------------
             | 1 | 2 | 3 | 4 | 5 |
              -------------------
               ^           ^       ^
               |           |       |
             begin()       i     end()





Constructors and assignments


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // constructors, etc.:

    explicit vector(const A& = A());
    explicit vector(size_type n, const T& val = T(), const A& = A());   // n copies of val
    template <class In>     // In must be an input iterator
    vector(In first, In last, const A& = A());  // copy from [first:last[
    vector(const vector& x);

    ~vector();  // destructor

    vector& operator=(const vector& x); // assignment operator

    template <class In>                 // In must be an input iterator (_iter.oper_)
    void assign(In first, In last);     // copy from [first:last[
    void assign(size_type n, const T& val); // n copies of val

    // ...
};



Use of constructors

vector<Record> vr(10000);

void f(int s1, int s2)
{
    vector<int> vi(s1);
    vector<double>* p = new vector<double>(s2);
}


void f(const list<X>& lst)
{
    vector<X> v1(lst.begin(),lst.end());    // copy elements from list
    char p[] = "despair";
    vector<char> v2(p,&p[sizeof(p)-1]);     // copy characters from C-style string
}



vector<int> v1(10);         // ok: vector of 10 ints
vector<int> v2 = vector<int>(10);   // ok: vector of 10 ints
vector<int> v3 = v2;            // ok: v3 is a copy of v2
vector<int> v4 = 10;            // error: attempted implicit conversion of 10 to vector<int>



void f1(vector<int>&);      // common style
void f2(const vector<int>&);// common style
void f3(vector<int>);       // rare style

void h()
{
    vector<int> v(10000);
    // ...
    f1(v);  // pass a reference
    f2(v);  // pass a reference
    f3(v);  // copy the 10000 elements into a new vector for f3() to use
}



Direct access for sequential containers


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // element access:

    // only for vector and dequeue
    reference operator[](size_type n);  // unchecked access
    const_reference operator[](size_type n) const;

    // only for vector and dequeue
    reference at(size_type n);          // checked access
    const_reference at(size_type n) const;

    reference front();      // first element
    const_reference front() const;
    reference back();       // last element
    const_reference back() const;

    // ...
};
        


Stack operations


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // stack operations:

    // not for vector
    void push_front(const T& x); // add to the beginning
    void pop_front();            // remove first element

    void push_back(const T& x); // add to end
    void pop_back();            // remove last element
    // ...
};



void f()
{
    vector<int> v;
    v.pop_back();   // undefined effect: the state of v becomes undefined
    v.push_back(7); // undefined effect (the state of v is undefined), probably bad
}


List operations


template <class T, class A = allocator<T> > class vector {
public:
    // list operations:

    iterator insert(iterator pos, const T& x);          // add x before pos
    void insert(iterator pos, size_type n, const T& x); // add n copies of x before pos
    template <class In>                       // In must be an input iterator
    void insert(iterator pos, In first, In last);   // insert elements from sequence

    iterator erase(iterator pos);   // remove element at pos
    iterator erase(iterator first, iterator last);  // erase sequence
    void clear();                   // erase all elements

    // ...
};



Usage of list operations


void duplicate_elements(vector<string>& f)
{
    for(vector<string>::iterator p = f.begin(); p!=f.end(); ++p) f.insert(p,*p);    // No!
}

template<class C> void f(C& c)
{
    c.erase(c.begin()+7);   // ok (if c's iterators support + )
    c.erase(&c[7]);         // not general
    c.erase(c+7);           // error: adding 7 to a container makes no sense

    c.erase(c.back());      // error: c.back() is a reference, not an iterator
    c.erase(c.end()-2);     // ok (second to last element)
    c.erase(c.rbegin()+2);  // error: vector::reverse_iterator and vector::iterator
                            //  are different types
    c.erase((c.rbegin()+2).base()); // obscure, but ok
}



Size and Capacity


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // capacity:

    size_type size() const;         // number of elements
    bool empty() const { return size()==0; }
    size_type max_size() const;     // size of the largest possible vector
    void resize(size_type sz, T val = T()); // added elements initialized by val

    size_type capacity() const; // size of the memory (in number of elements) allocated
    void reserve(size_type n);  // make room for a total of n elements; don't initialize
                                // throw a length_error if n>max_size()
    // ...
};


Different containers have different memory usage characteristics:

                          ______________________________________
                         |
                         |
                         |
               __________|  
              |
            __|
vector   __|
                           ________
                          |        |
                  ________|        |____
                 |                      |
             ____|                      |______      ______
            |                                  |    |      |
          _ |                                  |____|      |_____
         |
dequeue  |                      _
                             __| |_
                           _|      |_
                    __   _|          |_
                  _|  |_|              |_
                _|                       |____
             __|                              |_     _______
           _|                                   |___|       |_____
list     _|






The swap() trick for reduce vector's memory:


    vector<int>  v;

    v.push_back(1); ....

    vector<int>(v).swap(v);



template <class T, class A = allocator<T> > class vector {
public:
    // ...

    void swap(vector&);
};

template <class T, class A> void std::swap(vector<T,A>& x, vector<T,A>& y)
{
    x.swap(y);
}

template <class T, class A>
bool std::operator==(const vector<T,A>& x, const vector<T,A>& y);

template <class T, class A>
inline bool std::operator<(const vector<T,A>& x, const vector<T,A>& y)
{
    return lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());  
}



Container adaptors:


template <class T, class C = deque<T> > class std::stack {
protected:
    C c;
public:
    typedef typename C::value_type value_type;
    typedef typename C::size_type size_type;
    typedef C container_type;

    explicit stack(const C& a = C()) : c(a) { }

    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }

    value_type& top() { return c.back(); }
    const value_type& top() const { return c.back(); }

    void push(const value_type& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
};


Queue and priority_queue are similar.