C++/STL

STL refers to the Standard Template Library, a collection of data structures that can be used in any program. Common classes available in the STL include the dynamic array (vector), linked list (list), the stack, the queue, and the deque (think "deck of cards"). When creating an instance of these aggregate data types, which are templated, one must specify what class is intended to be stored in that data structure.

Example:

list<myClass> listOfMyClass; // create a list to store objects of type myClass, named listOfMyClass.
myClass elem1, elem2, elem3;
listOfMyClass.push_back(elem1);
listOfMyClass.push_back(elem2);
listOfMyClass.push_back(elem3);

The Standard Template Library

The Standard Template Library (STL) is a standard. This is important to note when trying to learn how to use the library. At first, the conventions in the library may seem unfamiliar and strange; however, because the library is based on the same underlying principles, once you learn how to properly use one class in the STL, knowing how to use another STL class is relatively easy.

The first and, possibly, the most common use of the STL for programmers learning C++ are using the container classes. An example container class is the std::vector<> template, which is one of the simplest and most versatile used classes in the library.

Iterator

An iterator is a special pointer designed for use with the STL containers shown below.

Iterators can traverse the contents of a container, using either the ++ or -- operators.

vector

A vector is a variable sized array.

{
  std::vector<int> example;

  example.push_back(25);
}

The vector supports the following methods:

• push_back(<type>): adds an element to the end
• pop_back(): destroys the last element
• size(): Returns size of vector
• resize(): Resizes the vector
• insert(position, value): Inserts an item
  • insert(position, number, value): Adds number values.
  • insert(position, start, end): Inserts values between start and end.

To get iterators to the beginning or end:

• begin()
• end(): returns an iterator to the end of the vector (not readable)
• rbegin(): Returns a reverse iterator
• rend(): Returns a reverse iterator pointing to the end

bitset

The bitset is a statically sized storage container that handles boolean values.

{
  bitset<12> bits;
}

The bits can be accessed as if they were an array, but the following functions are available:

• set(pos, value=true): sets the bit at pos to value.
• reset(pos): sets the bit at pos to false.
• flip(pos): toggles the bit at pos.

All three functions return a reference to the current bitset.

If a variable-sized container is needed, deque<bool> should be used instead.

stack

The stack is a data structure that serves as a first-in, last-out storage. That is, items most recently entered onto the stack will be retrieved first.

The push method adds an element to the structure, top provides a reference to the latest element added, and pop removes the topmost element. You can check the size of the stack with size and see if there are elements through the empty method.

queue

A queue is a data structure that serves as a first-in, first-out storage system. It allows items to be processed in order.

priority_queue

A priority queue is a data structure that causes elements to be returned based on a weak ordering system. In particular, the greatest value in the list is removed first.

deque

A deque is a double-ended queue. In this structure, elements may be added or removed at the beginning or end.

The most common methods are:

• back
• front
• pop_back
• pop_front
• push_back
• push_front

While you can use the insert and erase funtions to arbitrarly add or remove elements, this structure is most efficiently used for elements at the front or back.

list

The list structure is a double linked list. It is efficient at iterating through elements within the structure, but is slow when randomly accessing elements.

The methods :

• back
• front
• pop_back
• pop_front
• push_back
• push_front
• splice: Moves elements from one list into a specified position.
• remove, remove_if: Removes matching elements from the list.
• unique: Removes duplicate entries.
• merge: Merges two sorted lists.
• sort: Sorts the elements in a list.

map

A map is a container, where elements are accessed by a key. While effective for random access and arbitrary insertion and removal, it is not designed for sequential access.

{
  std::map<std::string, std::string> example;

  example.insert(std::make_pair<std::string, std::string>("color", "red"));
  example.insert(std::make_pair<std::string, std::string>("size", "medium"));
}

std::map<std::string, std::string>::iterator it = example.begin();

for(; it != example.end(); it++) }
    std::cout << it->color << "::" << it->size << std::end;
}

The methods incldue:

• operator [x]: Finds and returns element with key x, creating a new element if necessary.
• find: Searches for and returns an element with a given key, returning map::end if not found.
• erase: Removes an element.

The iterators for a map will provide a pair that contains a key and the element for that key.

• first: References a key
• second: References the value.

multimap

A variation of map, where several values may be given the same key.

The methods inlcude:

• find: Searches for and returns an element with a given key, returning multimap::end if not found. Note that only one element is returned.
• erase: Removes an element.
• insert: Adds an element.
• count: Provides the number of elements associates with a given key.
• equal_range: Returns an iterator for a list of elements matching a key.

set

A set is a container, where elements are accessed by a key. Unlike the map, a set is usually implemented as a binary tree.

The methods incldue:

• operator [x]: Finds and returns element with key x, creating a new element if necessary.
• find: Searches for and returns an element with a given key, returning map::end if not found.
• erase: Removes an element.

The iterators for a set will provide a pair that contains a key and the element for that key.

• first: References a key
• second: References the value.

multiset

A variation of set, where several values may be given the same key.

The methods inlcude:

• find: Searches for and returns an element with a given key, returning multimap::end if not found. Note that only one element is returned.
• erase: Removes an element.
• insert: Adds an element.
• count: Provides the number of elements associates with a given key.
• equal_range: Returns an iterator for a list of elements matching a key.

complex

Complex is a template class that supports operating on complex numbers, i.e. those that have a real and imaginary part. The constructor allows complex numbers with components of any type that supports the required underlying mathematical operations but has specializations to efficiently handle float, double and long double. The constructors are written to prevent implicit conversions that aren't known to be safe, so float to double would be safe but not double to float is not and so would have to be done explicitly. However the assignment operator does not have this requirement and will do implicit conversion where the conversion on the components is defined.

The only comparison functions defined are equality and non-equality (== and !=). The arithmetic operations of addition, subtraction, multiplication and division (+, -, *, /) and the assignments notations (like *=) are defined as are unary positive and negative signs (e.g. the unary negative in c + -k ). Certain transcendental functions are defined for complex numbers such as exponent, log (base e and base 10), trigonometric and hyperbolic trigonometric functions.

valarray

std::valarray is a container that holds an array of values, and designed for operations that affect all elements in the array. Operations may include basic arithmetic, or may apply a function to each element of the array.

{
    std::valarray<int> varr = {1, 2, 3, 4};

    varr = varr + 1; 
}

When performing a valarray operator with another valarray, the number of elements should be the same (different-sized arrays may cause undefined behavior), or be based on a single instance of the number.

Lessons

Topics in C++
Beginners	Data Structures	Advanced
Part of the School of Computer Science