Introduction to Standard Template Library (STL)

The standard template library (STL) is a set of template classes and functions that supply the programmer with

• Containers for storing information 
• Iterators for accessing the information stored 
• Algorithms for manipulating the content of the containers

STL Containers

Containers are STL classes that are used to store data. STL supplies two types of container classes:

• Sequential containers
• Associative container

As sequential containers hold the  data in a sequential fashion, like arrays, they have fast insertion time, but are relatively slow in find operations.

The STL sequential containers are

1. std::vector

Operates like a dynamic array and grows at the end. Can resize itself which suit the application’s run time requirements.

2. std::deque 

Similar to std::vector except insertion deletion at both end of array.

3. std::list 

Operates like a doubly linked list. Think of this like a chain where an object is a link in the chain. You can add or remove links—that is, objects—at any position

4. std::forward_list

Similar to a std::list except that it is a singly linked list of elements that allows you to iterate only in one direction.

Associative containers

Associative containers are those that store data in a sorted fashion akin to a dictionary. This results in slower insertion times, but presents significant advantages when it comes to searching.

The associative containers supplied by STL are

std::set

Stores unique values sorted on insertion in a container featuring logarithmic complexity

std::unordered_set

Stores unique values sorted on insertion in a container featuring near constant complexity. Available starting C++11

std::map

Stores key-value pairs sorted by their unique keys in a container with logarithmic complexity

std::unordered_map 

Stores key-value pairs sorted by their unique keys in a container with near constant complexity. Available starting C++11

std::multiset 

Akin to a set. Additionally, supports the ability to store multiple items having the same value; that is, the value doesn’t need to be unique

std::unordered_multiset 

Akin to a unordered_set. Additionally, supports the ability to store multiple items having the same value; that is, the value doesn’t need to be unique. Available starting C++11.

std::multimap—Akin to a map. Additionally, supports the ability to store key-value pairs where keys don’t need to be unique.

std::unordered_multimap 

Akin to a unordered_map. Additionally, supports the ability to store key-value pairs where keys don’t need to be unique. Available starting C++11.

Container adapters 

Container adapters are variants of sequential and associative containers that have limited functionality and are intended to fulfill a particular purpose. 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 a sorted order, such that the one whose value is evaluated to be the highest is always first in the queue.

Iterator

The simplest example of an iterator is a pointer. Given a pointer to the first element in an array, you can increment it and point to the next element or, in many cases, manipulate the element at that location. Iterators in STL are template classes that in some ways are a generalization of pointers. These are template classes that give the programmer a handle by which he can work with and manipulate STL containers and perform operations on them. 

STL algorithms

Finding, sorting, reversing, and the like are standard programming requirements in day 2 day life of programmers. We can use STL algorithms to do these task more efficiently.

Some of the most used STL algorithms are

std::find

Helps find a value in a collection

std::find_if

Helps find a value in a collection on the basis of a specific

user-defined predicate

std::reverse 

Reverses a collection

std::remove_if

Helps remove an item from a collection on the basis of a

user-defined predicate

std::transform

Helps apply a user-defined transformation function to elements in a container

Let’s see how iterators seamlessly connect containers and the STL algorithms using an example

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;  

int main()

{
vector<string> myvector;  // a vector of stings.


// push some strings in the vector.
myvector.push_back("T");
myvector.push_back("a");
myvector.push_back("n");
myvector.push_back("a");
myvector.push_back("j");
myvector.push_back("i");

vector<string>::iterator it;  // declare an iterator to a vector of strings
int n = 2;  // nth element to be found.
int i = 0;  // counter.

// now start at the from begining
// and keep iterating over the element till you find
// nth element..or reach the end of vector.
for(it = myvector.begin(); it != myvector.end(); it++,i++ )    {
    // found nth element..print and break.
    if(i == n) {
        cout<< *it << endl;  // prints n.

        break;
    }
}

// other easier ways of doing the same.
// using operator[]
cout<<myvector[n]<<endl;  // prints n.

// using the at method
cout << myvector.at(n) << endl;  // prints n.

vector <string>::iterator elFound = find (myvector.begin (),myvector.end (), "n");
int elPos = distance (myvector.begin (), elFound);
cout << " found in the vector at position: " << elPos << endl;
return 0;
}

That's all for now !!