Skip to the content of the web site.

The Standard Template Library (STL)

The standard template library has a number of containers that you can use. Containers are data structures that allow you to store, access and remove data. This page discusses how to use some of these.

std::queue
std::stack
std::set
std::multiset
std::array
std::vector
std::map

Queues

Suppose you are tasked with dealing with data one item at a time, but the data arrives faster than you can deal with it. In this case, it is common to deal with the data on a first-come—first-served basis. The data structure for dealing with this is a queue.

The std::queue class is in the standard queue library:

#include <queue>

To declare a queue that stores a specific data type, you use

     std::queue<typename> variable_name{};

For example,

     std::queue<double> a_queue{};

declares a_queue to be an instance of this class that stores doubles.

You can add a new value to a queue by using the push(...) member function, as follows:

     a_queue.push( 173 );

The empty() member function returns true if the queue is empty:

     // This will print '0' as 173 is currently in the queue
     std::cout << a_queue.empty() << std::endl;

The front() member function will return the value that is at the front of the queue. If the queue is empty, the returned value is undefined:

     // This will print '173', as that is currently the first (and only)
     // value in the queue
     std::cout << a_queue.front() << std::endl;

The pop() member function will remove what is currently at the front of the queue from that queue:

     // This will pop the front object, after which the queue will be empty,
     // so the second statement will print a '1'
     a_queue.pop();
     std::cout << a_queue.empty() << std::endl;

The size() member function will return the number of objects that are currently in the queue.

You can read more about queues at C++.com.

You can now go to an example of a queue on repl.it.

Stack

Suppose you are tasked with storing a sequence of operations that were performed by allowing the user to undo those operations. In this case, if you want to undo an operation, you must undo the last operation performed. This is the opposite of a queue, and we call this data structure a stack. Think of a stack of plates: new plates are put on top of a stack and when you need a plate, you take the last plate that was put onto the stack. In this case, we are dealing with data in a last-come—first-served basis.

The std::stack class is in the standard stack library:

#include <stack>

To declare a stack that stores a specific data type, you use

     std::stack<typename> variable_name{};

For example,

     std::stack<double> a_stack{};

declares a_stack to be an instance of this class that stores doubles.

The only difference in the member functions of a stack and a queue is that the object at the top of the stack is accessed through the top() member function.

You can read more about stacks at C++.com.

You can now go to an example of a stack on repl.it.

Set

A set is a container that allows you store values, but will only keep one copy per value. For example, suppose like to have a raffle where each individual is only able to enter once, but someone may try to enter multiple times. If all identifiers of the individuals are entered into a set, duplicate entries will be eliminated.

The std::set class is in the standard set library:

#include <set>

To declare a set that stores a specific data type, you use

     std::stack<typename> variable_name{};

The empty() member function returns true if the set is empty and false otherwise; and the size() member function returns the number of objects currently in the set.

The insert(...) member function allows you to insert a new object into the set, while the erase(...) member function will allow to to remove an object from the set (if the object is not in the set, nothing happens).

The count(...) member function returns the number of instances that the argument has in the set, and of course, this will be either 0 or 1.

The clear() member function erases all objects in the set.

Almost all other operations on sets use iterators. This is a topic we will touch on later; however, if you want to loop through all the entries of a set, you can use:

     // This is a special type of loop not previously discussed
     for ( auto k : set_name ) {
     	std::cout << k << std::endl;
     }

You can read more about sets at C++.com.

You can now go to an example of a set on repl.it.

Warning: it is likely that you do not want to use a set to store double, because you may consider 39523.23597823592 and 39523.23597823593 to be the same, but a std::set will consider them to be two distinct floating-point numbers.

Multiset

A multi-set is identical to a set, only that multiple copies are allowed. Thus, the only real difference is that count(...) may return a value greater than one if the same object was inserted multiple times, and erase(...) will erase all instances of the object in the multi-set.

The std::multiset class is in the same library as std::set:

#include <set>

If you want to remove only one instance of an object in a multi-set, you must find one instance and then pass that instance to erase:

    if ( multiset_name.count( k ) > 0 ) {
        multiset_name.erase( multiset_name.find( k ) );
    }

This uses iterators, but does not currently require you to understand them. If you use this and there are no instances of k in the multi-set, your program will crash.

You can read more about multi-sets at C++.com.

You can now go to an example of a multi-set on repl.it.

Arrays

If you simply have to store an array of N objects, and you know the value of N at compile time, you can use the array class.

The std::array class is in the standard array library:

#include <array>

To declare an array that stores N items of a specific data type, you use

     std::array<typename, N> variable_name{};

For example,

     std::array<double, 10> an_array{};

The ten entries of this array are indexed from 0 to 9.

To access or modify what is at index k of the array, you may use one of two techniques:

     std::cout << an_array[k] << std::endl;
     std::cout << an_array.at( k ) << std::endl;

If k is greater than or equal to N, the first variation will try to access that entry, which will cause serious difficult-to-find bugs or even terminations of your program. The second (using the member function at(...)) will throw an exception you can catch. The sample code will show you how you can do this.

You can read more about arrays at C++.com.

You can now go to an example of an array on repl.it.

Vectors

The array class described above requires that the size of the array is fixed. If there is a possibility that the array size may change, you want to use the std::vector class.

To be completed.

You can read more about vectors at C++.com.

Maps

Previously, we discussed how a std::set can store a collection of objects. A map allows you to store pairs of objects, keyed off the first value. For example, I may want to store the grade of every student on one quiz, so I would store 20123456 associated with the grade of 94. I could then ask: what is the grade linked with 20123456, I could change it, and if I entered a second grade for that same uWaterloo Student ID Number, it would overwrite the first. If a student dropped the course, I could erase that uWaterloo Student ID Number from the container, and it would also erase the associated grade. All this is done by std::map.

To be completed.

You can read more about maps at C++.com.

Douglas Wilhelm Harder, M.Math., LEL

The Standard Template Library (STL)

Queues

Stack

Set

Multiset

Arrays

Vectors

Maps