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 utilized through templates.
The STL is comprised of the following componentsContainers 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 in a sequential fashion. Each element holds a position and that position depends on the time and place of insertion. Adding any objects to the end of a vector means that the object will appear in the order that were inserted. Sequential containers are characterized 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 adding or removing elements from its 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 its elements in contiguous storage locations. Attempting to access and elements by offsetting a pointer to another element will result in undefined behavior. 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 – Are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions. They Operate like a doubly linked list.Compared to other standard sequence containers lists perform generally 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 thus searching can take extra time. They also consume some extra memory to keep the linking information associated to 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 perform generally 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 positionand consume extra resources to keep the linking information current.
std::array class – 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 presents significant advantages when it comes to 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 towards a particular container class and providing 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 to.
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 a sorted order, such that the one whose value is evaluated to be the highest is always first in the queue.
Iterators
Iterators are 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. Forward and backward moving.
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 provides support for its own basic operations however the standard algorithms header provides a more extensive range of functionality. One algorithm function can be used on any type of container. 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 v1cout << endl;cout << "Clear contents of vector v\n"; v.clear();// clear contents of vectorcout << "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++;
}
}