The standard template library (STL) is a set of template classes and functions that supply the programmer with common data structures and functions such as lists, stacks, arrays, sorting, etc utilised through templates.
The STL is comprised of the following components:
- Containers for storing information.
- Iterators for accessing the information stored.
- Algorithms for manipulating the content of the containers.
Containers
Containers are STL classes that are used to store data. Each container class defines a set of functions that may be applied to the container. For example, a list container includes functions that insert, delete, and merge elements. A stack includes functions that push and pop values.
STL supplies provide the following container classes:
- Sequential containers
- Associative containers
- Container Adapters
Sequential Containers
These are ordered collections used to hold data sequentially. Each element holds a position that depends on the time and place of insertion. Adding any object to the end of a vector means that the object will appear in the order that was inserted. Sequential containers are characterised by a fast insertion time but are relatively slow in find operations.
The STL provides five sequence container classes:
std::vector – The vector class implements a dynamic array and thus can grow as needed. Although a vector is dynamic, it still uses the standard array subscript notation to access its elements. Compared to the other dynamic sequence containers, vectors are very efficient at accessing elements and relatively efficient in adding or removing elements from their end. For operations that involve inserting or removing elements at positions other than the end, they perform worse than the other sequence container classes
std::deque – Similar to std::vector except that it allows for new elements to be inserted or removed at the beginning. Unlike vectors, deques are not guaranteed to store all elements in contiguous storage locations. Attempting to access elements by offsetting a pointer to another element will result in undefined behaviour. For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques are less efficient than lists and forward lists.
std::list – These are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions. Compared to other standard sequence containers, lists generally perform better in inserting, extracting, and moving elements in any position within the container. The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position and searching can take extra time. They also consume some extra memory to keep the linking information associated with each element.
std::forward_list – Similar to a std::list except that it is a singly linked list of elements that allows iteration only in one direction. Compared to other base standard sequence containers forward_list generally performs better in inserting, extracting, and moving elements in any position within the container. The main drawback of forward_lists is that like the standard list, they lack direct access to the elements by their position and consume extra resources to keep the linking information current.
std::array class – This is a templated class that provides many benefits over built-in arrays, such as maintaining the array size preventing automatic decay into a pointer, providing bounds checking, and allowing the use of C++ container operations.
Associative Containers
Associative containers utilise sorted data structures that can be quickly searched using keys. This results in slower insertion times but offers significant advantages when searching.
The associative containers supplied by STL are –
std::set
std::unordered_set
std::map
std::unordered_map
std::multiset
std::unordered_multiset
std::multimap
std::unordered_multimap
Container Adapters
Container Adapters offer limited functionality oriented toward a particular container class and provide a more relevant set of functionality. The main adapter classes are:
std::stack — Stores elements in a LIFO (last-in-first-out) fashion, allowing elements to be inserted (pushed) and removed (popped) at the top.
std::queue — Stores elements in FIFO (first-in-first-out) fashion, allowing the first element to be removed in the order they’re inserted.
std::priority_queue — Stores elements in sorted order, such that the one whose value is evaluated to be the highest is always first in the queue.
Iterators
Iterators are template classes that act like pointers. They provide the means to cycle and manipulate the contents of a container in much the same way that you would use a pointer to cycle through an array. There are five types of iterators:
Bidirectional iterator – Store and retrieve values. Moves forward and backward.
Forward iterator – Store and retrieve values. Forward moving only.
Input iterator – Retrieve, but not store values. Forward moving only.
Output iterator – Store, but not retrieve values. Forward moving only.
Random access iterator – Store and retrieve values. Elements may be accessed randomly.
STL Algorithms
Algorithms act on containers. Each container supports its basic operations however the standard algorithms header provides a more extensive range of functionality. One algorithm function can be used on any container type. Algorithms from STL are tried and tested saving time & effort when manipulating data. The algorithm library covers sorting, searching, modifying, non-modifying, and Minimum and Maximum operations.
Vector examples
The following code sample uses vectors to create and manipulate an int vector
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector <int> v; // create zero-length vector
unsigned int i;
cout << "initial size of vector v = " << v.size() << endl;// display original size of v
for(i=0; i<20; i++) v.push_back(i);
cout << "new size of vector v = " << v.size() << endl; // display new size of vector v
cout << "Current contents of vector v:\n";
for(i=0; i<v.size(); i++) cout << v[i] << " ";// display contents of vector v
cout << endl;
cout << "add 5 elements to vector v:\n";
for(i=0; i<5; i++) v.push_back(i+10);//add 5 more values to vector
cout << "new size of vector = " << v.size() << endl;// display current size of v
cout << "Current contents of vector v:\n";
for(i=0; i<v.size(); i++) cout << v[i] << " ";// display contents of vector v
cout << endl;
sort(v.begin(),
v.end());//sort contents of vector v
cout << "Sort contents of vector v and list\n";
for(i=0; i<v.size(); i++) cout << v[i] << " "; // display contents of sorted vector
cout << endl;
vector <int> v1(10,5);//create new int vector v1 and initialise elements to 5
cout << "create new int vector v1. Initialise elements to 5. Merge with vector v\n";
for(i=0; i < v1.size();i++)
v.push_back(v1[i]);// merged vector v and v1
for(i=0; i < v.size(); i++)
cout << v[i] << " ";//display contents of v1
cout << endl;
cout << "Clear contents of vector v\n"; v.clear();// clear contents of vector
cout << "new size of vector = " << v.size() << endl;
return 0;
}
The following code sample uses template lists to create and manipulate an int vector
#include <iostream>
#include <list>
using namespace std;
int main()
{
list <int> lst;// create an empty list lst
list <int> lst1; // create an empty list lst1
cout << "create random integer lists: " << endl;
int rn;
for(int a=10;a>0;a=a-1)
{
lst.push_back(rand()); //add random number to lst
lst.push_back(rand()); //add random number to lst1
}
list<int>::iterator p = lst.begin();//create pointer p and set to start of lst
cout << "output contents of lst: " << endl;
while(p != lst.end())
{ //iterate through entire lst
cout << *p << " "; //output lst value
cout << endl;
p++;
}
lst.sort();
cout << "sort lst: " << endl;
p = lst.begin();
while(p != lst.end())
{
cout << *p << " ";//output lst element
cout << endl;
p++;
}
cout << "merge and sort" << endl;
lst.merge(lst1);//merge lst and lst
lst.sort();//sort lst
p = lst.begin();
while(p != lst.end())
{
cout << *p << " ";//output lst
cout << endl;
p++;
}
}