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.

`vector`	Like an expandable array.
`deque`	Double-Ended Queue. Like an array expandable at both front and back.
`list`	Doubly linked-list.
`map`	Associates key with single value. Balanced tree.
`multimap`	Associates key with multiple values. Balanced tree.
`set`	Records whether value belongs to it. Balanced tree.
`multiset`	Like `set` but allows more than one entry with the same value.
`stack`	Adapter to permit only LIFO (Last In, First Out) access.
`queue`	Adapter to permit only FIFO (First In, First Out) access.
`priority_queue`	Adapter to return element with the highest priority.
`string`	Character strings.
`bitset`	Bit 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, ...

Other

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

Standard Template Library Online Reference.

Limited built-in C++ data structures

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

Arrays - Fixed size collection of elements accessed by index/pointer.
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, ...).