C++ Notes: STL Overview

STL features: containers, iterators, and algorithms

C++'s Standard Template Library (STL), standardized in 1999, solves many standard data structure and algorithm problems. The STL is (or should be) the first choice in all programming. Altho you many need to write certain specialized data structures, or build on top of the STL structures, but you should never be writing duplicate code. The STL provides functionality in several areas: containers, iterators, and algorithms.

1. Containers

STL containers implement many or the standard ways to storing data to achieve performance goals. These are all template types. They store values, and may copy them. If you don't want values copied, use addresses of the values.

vectorLike an expandable array.
dequeDouble-Ended Queue. Like an array expandable at both front and back.
listDoubly linked-list.
mapAssociates key with single value. Balanced tree.
multimapAssociates key with multiple values. Balanced tree.
setRecords whether value belongs to it. Balanced tree.
multisetLike set but allows more than one entry with the same value.
stackAdapter to permit only LIFO (Last In, First Out) access.
queueAdapter to permit only FIFO (First In, First Out) access.
priority_queueAdapter to return element with the highest priority.
stringCharacter strings.
bitsetBit strings, including set operations.

2. Iterators

Iterators provide uniform ways to go over the elements of the STL containers, as well as arrays. There are iterators for going sequentially forward and/or backward as well as random access iterators. Iterators are used by the STL algorithms. Iterator syntax uses the ++, --, and * operators which are familiar to users of pointers.

3. Algorithms

Many common algorithms are implemented for containers and arrays. Sorting, searching, inserting, deleting, shuffling, permuting, rotating, reversing, moving, copying, counting, minimum and maximum, for each, ...


The STL contains other classes useful for numerics (eg, complex and valarray), I/O (eg, stream I/O classes), internationalization (eg, wide characters and locales), etc.

Other sources of STL information

Limited built-in C++ data structures

There are two kinds of built-in data structures in C++:

  1. Arrays - Fixed size collection of elements accessed by index/pointer.
  2. Structs/Classes - Record structure with fields accessed by name.

These are useful, but have numerous serious deficiencies (eg, performance or fixed size) or construct their own data structures using these basic features (most coding, slower development, less reusable, ...).