STL(Standard Template Library)

The Standard Template Libraries (STL's) are a set of C++ template classes to provide common programming data structures and functions such as doubly linked lists (list), paired arrays (map), expandable arrays (vector), large string storage and manipulation (rope), etc.

STL can be categorized into the following groupings:

• Container classes:
  
  
  
  
  
  
  • Sequences:
    
    
    
    
    
    
    • vector: (this tutorial) Dynamic array of variables, struct or objects. Insert data at the end.
      
      
    • deque: Array which supports insertion/removal of elements at beginning or end of array
    • list: (this tutorial) Linked list of variables, struct or objects. Insert/remove anywhere.
  • Associative Containers:
    
    
    
    
    
    
    • set (duplicate data not allowed in set), multiset (duplication allowed): Collection of ordered data in a balanced binary tree structure. Fast search.
    • mqp(unique keys), multimap (duplicate keys allowed): Associative key-value pair held in balanced binary tree structure.
  • Container adapters:
    
    
    
    
    
    
    • stack LIFO
    • queue FIFO
    • priority_queue returns element with highest priority.
  • String:
    
    
    
    
    
    
    • string: Character strings and manipulation
    • rope: String storage and manipulation
  • bitset: Contains a more intuitive method of storing and manipulating bits.
• Operations/Utilities:
  
  
  
  
  
  
  • iterator: (examples in this tutorial) STL class to represent position in an STL container. An iterator is declared to be associated with a single container class type.
  • algorithm: Routines to find, count, sort, search, ... elements in container classes
  • auto_ptr: Class to manage memory pointers and avoid memory leaks.
  •  
  
  
  

1.) Vector
Vectors are a kind of sequence containers. As such, their elements are ordered following a strict linear sequence.

Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.
Vectors are good at:

• Accessing individual elements by their position index (constant time).
• Iterating over the elements in any order (linear time).
• Add and remove elements from its end (constant amortized time).

Example 

// vector::begin
#include 
#include 
using namespace std;

int main ()
{
  vector<int> myvector;
  for (int i=1; i<=5; i++) myvector.push_back(i);

  vector<int>::iterator it;

  cout << "myvector contains:";
  for ( it=myvector.begin() ; it < myvector.end(); it++ )
    cout << " " << *it;

  cout << endl;

  return 0;

}

Output:

myvector contains: 1 2 3 4 5 

*******************************************************************

 
// comparing size, capacity and max_size
#include 
#include 
using namespace std;

int main ()
{
  vector<int> myvector;

  // set some content in the vector:
  for (int i=0; i<100; i++) myvector.push_back(i);

  cout << "size: " << (int) myvector.size() << "\n";
  cout << "capacity: " << (int) myvector.capacity() << "\n";
  cout << "max_size: " << (int) myvector.max_size() << "\n";
  return 0;
}

A possible output for this program could be:

size: 100
capacity: 141
max_size: 1073741823

************************************************************************

// vector::push_back
#include 
#include 
using namespace std;

int main ()
{
  vector<int> myvector;
  int myint;

  cout << "Please enter some integers (enter 0 to end):\n";

  do {
    cin >> myint;
    myvector.push_back (myint);
  } while (myint);

  cout << "myvector stores " << (int) myvector.size() << " numbers.\n";

  return 0;
}

*****************************************************************************

list

List
Lists are a kind of sequence containers. As such, their elements are ordered following a linear sequence.

List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept by the association to each element of a link to the element preceding it and a link to the element following it.

This provides the following advantages to list containers:

• Efficient insertion and removal of elements anywhere in the container (constant time).
• Efficient moving elements and block of elements within the container or even between different containers (constant time).
• Iterating over the elements in forward or reverse order (linear time).

Example

// inserting into a list
#include 
#include 
#include 
using namespace std;

int main ()
{
  list<int> mylist;
  list<int>::iterator it;

  // set some initial values:
  for (int i=1; i<=5; i++) mylist.push_back(i); // 1 2 3 4 5

  it = mylist.begin();
  ++it;       // it points now to number 2           ^

  mylist.insert (it,10);                        // 1 10 2 3 4 5

  // "it" still points to number 2                      ^
  mylist.insert (it,2,20);                      // 1 10 20 20 2 3 4 5

  --it;       // it points now to the second 20            ^

  vector<int> myvector (2,30);
  mylist.insert (it,myvector.begin(),myvector.end());
                                                // 1 10 20 30 30 20 2 3 4 5
                                                //               ^
  cout << "mylist contains:";
  for (it=mylist.begin(); it!=mylist.end(); it++)
    cout << " " << *it;
  cout << endl;

  return 0;
}

 Output:

mylist contains: 1 10 20 30 30 20 2 3 4 5

********************************************************************************

// list::begin
#include 
#include 
using namespace std;

int main ()
{
  int myints[] = {75,23,65,42,13};
  list<int> mylist (myints,myints+5);

  list<int>::iterator it;

  cout << "mylist contains:";
  for ( it=mylist.begin() ; it != mylist.end(); it++ )
    cout << " " << *it;

  cout << endl;

  return 0;
} 

Output:

mylist contains: 75 23 65 42 13

***************************************************************************

// reversing vector
#include 
#include 
using namespace std;

int main ()
{
  list<int> mylist;
  list<int>::iterator it;

  for (int i=1; i<10; i++) mylist.push_back(i);

  mylist.reverse();

  cout << "mylist contains:";
  for (it=mylist.begin(); it!=mylist.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}
 

Output:

mylist contains: 9 8 7 6 5 4 3 2 1

********************************************************************************

Member Function of List are as follows

list::assign

list::back

list::begin

list::clear

list::empty

list::end

list::erase

list::front

list::get_allocator

list::insert

list::max_size

list::merge

list::operator=

list::pop_back

list::pop_front

list::push_back

list::push_front

list::rbegin

list::remove

list::remove_if

list::rend

list::resize

list::reverse

list::size

list::sort

list::splice

list::swap

list::unique

****************************************************************************

Map
Maps are a kind of associative containers that stores elements formed by the combination of a key value and a mapped value.

In a map, the key value is generally used to uniquely identify the element, while the mapped value is some sort of value associated to this key. Types of key and mapped value may differ. For example, a typical example of a map is a telephone guide where the name is the key and the telephone number is the mapped value.


Example:

// map::begin/end
#include 
#include 
using namespace std;

int main ()
{
  map<char,int> mymap;
  map<char,int>::iterator it;

  mymap['b'] = 100;
  mymap['a'] = 200;
  mymap['c'] = 300;

  // show content:
  for ( it=mymap.begin() ; it != mymap.end(); it++ )
    cout << (*it).first << " => " << (*it).second << endl;

  return 0;
}

output 

a => 200
b => 100
c => 300
**************************************************************************

Multiple-key map
Maps are a kind of associative containers that stores elements formed by the combination of a key value and a mapped value, much like map containers, but allowing different elements to have the same key value.

Example:

// multimap::begin/end
#include 
#include 
using namespace std;

int main ()
{
  multimap<char,int> mymultimap;
  multimap<char,int>::iterator it;

  mymultimap.insert (pair<char,int>('a',10));
  mymultimap.insert (pair<char,int>('b',20));
  mymultimap.insert (pair<char,int>('b',150));

  // show content:
  for ( it=mymultimap.begin() ; it != mymultimap.end(); it++ )
    cout << (*it).first << " => " << (*it).second << endl;

  return 0;
}

Output:

a => 10
b => 20
b => 150

 ****************************************************************************
Multiple-key set
Multisets are associative containers with the same properties as set containers, but allowing for multiple keys with equal values.

// multiset::begin/end
#include 
#include 
using namespace std;

int main ()
{
  int myints[] = {42,71,71,71,12};
  multiset<int> mymultiset (myints,myints+5);

  multiset<int>::iterator it;

  cout << "mymultiset contains:";
  for ( it=mymultiset.begin() ; it != mymultiset.end(); it++ )
    cout << " " << *it;

  cout << endl;

  return 0;
}

Output

mymultiset contains: 12 42 71 71 71

**********************************************************************************

Priority queue
Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering condition.

This context is similar to a heap where only the max heap element can be retrieved (the one at the top in the priority queue) and elements can be inserted indefinitely.

The following operations: 
     
    front(),push_back(),pop_back()

// priority_queue::push/pop
#include 
#include 
using namespace std;

int main ()
{
  priority_queue<int> mypq;

  mypq.push(30);
  mypq.push(100);
  mypq.push(25);
  mypq.push(40);

  cout << "Popping out elements...";
  while (!mypq.empty())
  {
     cout << " " << mypq.top();
     mypq.pop();
  }
  cout << endl;

  return 0;
}

 Ouput

Popping out elements... 100 40 30 25

***************************************************************************

FIFO queue
queues are a type of container adaptors, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.

queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access it elements. Elements are pushed into the "back" of the specific container and popped from its "front".

// queue::push/pop
#include 
#include 
using namespace std;

int main ()
{
  queue<int> myqueue;
  int myint;

  cout << "Please enter some integers (enter 0 to end):\n";

  do {
    cin >> myint;
    myqueue.push (myint);
  } while (myint);

  cout << "myqueue contains: ";
  while (!myqueue.empty())
  {
    cout << " " << myqueue.front();
    myqueue.pop();
  }

  return 0;
}

*****************************************************************************

Set
Sets are a kind of associative containers that stores unique elements, and in which the elements themselves are the keys.

// set::begin/end
#include 
#include 
using namespace std;

int main ()
{
  int myints[] = {75,23,65,42,13};
  set<int> myset (myints,myints+5);

  set<int>::iterator it;

  cout << "myset contains:";
  for ( it=myset.begin() ; it != myset.end(); it++ )
    cout << " " << *it;

  cout << endl;

  return 0;
}

Output:

myset contains: 13 23 42 65 75

*********************************************************************************

LIFO stack
Stacks are a type of container adaptors, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from the end of the container.

// stack::push/pop
#include 
#include 
using namespace std;

int main ()
{
  stack<int> mystack;

  for (int i=0; i<5; ++i) mystack.push(i);

  cout << "Popping out elements...";
  while (!mystack.empty())
  {
     cout << " " << mystack.top();
     mystack.pop();
  }
  cout << endl;

  return 0;
}

Output:

Popping out elements... 4 3 2 1 0

******************************************************************************