STL MAP

STL 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 mappedvalue 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.
• Internally, the elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion set on construction.
• They are especially designed to be efficient accessing its elements by their key (unlike sequence containers, which are more efficient accessing elements by their relative or absolute position).
• Maps are also unique among associative containers in that the implement the direct access operator (operator[]) which allows for direct access of the mapped value.

EXAMPLE:

// accessing mapped values
# include < iostream >
# include < map >
# include < string >
using namespace std;

int main ()
{
  map< char,string > mymap;

  mymap['a']="an element";
  mymap['b']="another element";
  mymap['c']=mymap['b'];

  cout << "mymap['a'] is " << mymap['a'] << endl;
  cout << "mymap['b'] is " << mymap['b'] << endl;
  cout << "mymap['c'] is " << mymap['c'] << endl;
  cout << "mymap['d'] is " << mymap['d'] << endl;

  cout << "mymap now contains " << (int) mymap.size() << " elements." << endl;

  return 0;
}

Notice how the last access (to element 'd') inserts a new element in the set with that key and initialized to its default value (an empty string) even though it is accessed only to retrieve its value. Member function map::find does not produce this effect.
Output:

mymap['a'] is an element
mymap['b'] is another element
mymap['c'] is another element
mymap['d'] is
mymap now contains 4 elements.

STL SET

STL SET

• Sets are a kind of associative containers that stores unique elements, and in which the elements themselves are the keys.
• Associative containers are containers especially designed to be efficient accessing its elements by their key (unlike sequence containers, which are more efficient accessing elements by their relative or absolute position). 
• The elements in a set are always sorted from lower to higher following a specific strict weak ordering criterion set on container construction.
• Sets are typically implemented as binary search trees.
• This container class supports bidirectional iterators.

EXAMPLE

// set::find
# include < iostream >
# include < set >
using namespace std;

int main ()
{
  set< int > myset;
  set< int >::iterator it;

  // set some initial values:
  for (int i=1; i<=5; i++) myset.insert(i*10);    // set: 10 20 30 40 50

  it=myset.find(20);
  myset.erase (it);
  myset.erase (myset.find(40));

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

  return 0;
}

Output:

myset contains: 10 30 50

STL QUEUE

STL QUEUE

• queues are a type of container adaptors.
• 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".
• The underlying container may be one of the standard container class template or some other specifically designed container class. The only requirement is that it supports the following operations:

1. front()
2. back()
3. push_back()
4. pop_front()

• Therefore, the standard container class templates deque and list can be used. By default, if no container class is specified for a particular queue class, the standard container class template deque is used.

Example:

// queue::front
# include < iostream >
# include < queue >
using namespace std;

int main ()
{
  queue< int > myqueue;

  myqueue.push(77);
  myqueue.push(16);

  myqueue.front() -= myqueue.back();    // 77-16=61

  cout << "myqueue.front() is now " << myqueue.front() << endl;

  return 0;
}

Output:

myqueue.front() is now 61

STL STACK

STL STACK

• Stacks are a type of container adaptors.
• Operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from the end of the container.
• Stacks 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 its elements. Elements are pushed/popped from the "back" of the specific container, which is known as the top of the stack.
• The underlying container may be any of the standard container class templates or some other specifically designed container class. The only requirement is that it supports the following operations:

1. back()
2. push_back()
3. pop_back()

• Therefore, the standard container class templates vector, deque and list can be used. By default, if no container class is specified for a particular stack class, the standard container class template deque is used.

EXAMPLE

// stack::top
# include < iostream >
# include < stack >
using namespace std;

int main ()
{
  stack< int > mystack;

  mystack.push(10);
  mystack.push(20);

  mystack.top() -= 5;

  cout << "mystack.top() is now " << mystack.top() << endl;

  return 0;
}

Output:

mystack.top() is now 15

STL DEQUE a.k.a. DECK

STL DEQUE

• Acronym of double-ended queue.
• Double-ended queues are a kind of sequence containers. As such, their elements are ordered following a strict linear sequence.
• They allow for the individual elements to be accessed through random access iterators, with storage always handled automatically (expanding and contracting as needed).
• Individual elements can be accessed by their position index.
• Iteration over the elements can be performed in any order.
• Elements can be efficiently added and removed from any of its ends (either the beginning or the end of the sequence).

COMPARISON TO VECTORS


Therefore they provide a similar functionality as the one provided by vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence and not only at its end. On the drawback side, unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics.

Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.


Example:

// deque::empty
# include < iostream >
# include < deque >
using namespace std;

int main ()
{
  deque< int > mydeque;
  int sum (0);

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

  while (!mydeque.empty())
  {
     sum += mydeque.front();
     mydeque.pop_front();
  }

  cout << "total: " << sum << endl;
  
  return 0;
}

STL LIST

STL 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.
• 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).

COMPARISON TO OTHER SEQUENCE CONTAINERS- DEQUEUES AND VECTORS

Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The main drawback of lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

Example:

// swap lists
# include < iostream >
# include < list >
using namespace std;

main ()
{
  list< int > first (3,100);   // three ints with a value of 100
  list< int > second (5,200);  // five ints with a value of 200
  list< int >::iterator it;

  first.swap(second);

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

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

  cout << endl;

  return 0;
}

STL VECTOR

STL VECTOR:

• Vectors are a kind of sequence containers
• 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. But unlike regular arrays, storage in vectors is handled automatically, allowing it to be expanded and contracted as needed.
• 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).
• Compared to arrays, they provide almost the same performance for these tasks, plus they have the ability to be easily resized. Although, they usually consume more memory than arrays when their capacity is handled automatically (this is in order to accomodate for extra storage space for future growth).

COMPARISON TO OTHER SEQUENCE CONTAINERS- DEQUEUE & LISTS


vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than "dequeues" and "lists", and have less consistent iterators and references than "lists".




OTHER RELEVANT INFORMATION, IF YOU CARE TO READ


vectors -like all containers- have a "size", which represents the amount of elements contained in the vector. But vectors, also have a "capacity", which determines the amount of storage space they have allocated, and which can be either equal or greater than the actual "size". The extra amount of storage allocated is not used, but is reserved for the vector to be used in the case it grows. This way, the vector does not have to reallocate storage on each occasion it grows, but only when this extra space is exhausted and a new element is inserted (which should only happen in logarithmic frequence in relation with its size).

// vector::empty
# include < iostream >
# include < vector >
using namespace std;

int main ()
{
  vector< int > myvector;
  int sum (0);

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

  while (!myvector.empty())
  {
     sum += myvector.back();
     myvector.pop_back();
  }

  cout << "total: " << sum << endl;
  
  return 0;
}

STL LIST- SPLICE

Move elements from list to list

Moves elements from list x into the list container at the specified position, effectively inserting the specified elements into the container and removing them from x.

This increases the container size by the amount of elements inserted, and reduces the size of x by the same amount ( whenever x is not the same as *this ).

The operation does not involve the construction or destruction of any element object and, except for the third version, it is performed in constant time.

The iterators that pointed to moved elements are no longer valid.


// splicing lists
#include < iostream >
#include < list >
using namespace std;

int main ()
{
list< int > mylist1, mylist2;
list::iterator it;

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

for (int i=1; i<=3; i++)
mylist2.push_back(i*10); // mylist2: 10 20 30

it = mylist1.begin();
++it; // points to 2

mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4
// mylist2 (empty)
// "it" still points to 2 (the 5th element)

mylist2.splice (mylist2.begin(),mylist1, it);
// mylist1: 1 10 20 30 3 4
// mylist2: 2
// "it" is now invalid.
it = mylist1.begin();
advance(it,3); // "it" points now to 30

mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
// mylist1: 30 3 4 1 10 20

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

cout << "\nmylist2 contains:";
for (it=mylist2.begin(); it!=mylist2.end(); it++)
cout << " " << *it;
cout << endl;

return 0;
}

Output:
mylist1 contains: 30 3 4 1 10 20
mylist2 contains: 2

STL LIST C++ -- insert(), erase() & assign()

insert:

Insert elements


The list container is extended by inserting new elements before the element at position.

This effectively increases the container size by the amount of elements inserted.

lists are sequence containers specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence. Compared to the other base sequence containers (vector and deque), lists are the most efficient container doing insertions at some position other than the beginning or the end of the sequence, and, unlike in these, all of the previously obtained iterators and references remain valid after the insertion and refer to the same elements they were referring before.

#include < iostream >
#include < list >
#include < vector >
using namespace std;

int main ()
{
list < int > mylist;
list::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 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

erase:
Erase elements

Removes from the list container either a single element (position) or a range of elements ([first,last)).

This effectively reduces the list size by the number of elements removed, calling each element's destructor before.

lists are sequence containers specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence. Compared to the other base sequence containers (vector and deque), lists are the most efficient container erasing at some position other than the beginning or the end of the sequence, and, unlike in these, all of the previously obtained iterators and references remain valid after the erasing operation and refer to the same elements they were referring before (except, naturally, for those referring to erased elements).

// erasing from list
#include < iostream >
#include < list >
using namespace std;

int main ()
{
unsigned int i;
list< unsigned int > mylist;
list< unsigned int >::iterator it1,it2;

// set some values:
for (i=1; i<10; i++) mylist.push_back(i*10);

// 10 20 30 40 50 60 70 80 90
it1 = it2 = mylist.begin(); // ^^
advance (it2,6); // ^ ^
++it1; // ^ ^

it1 = mylist.erase (it1); // 10 30 40 50 60 70 80 90
// ^ ^

it2 = mylist.erase (it2); // 10 30 40 50 60 80 90
// ^ ^

++it1; // ^ ^
--it2; // ^ ^

mylist.erase (it1,it2); // 10 30 60 80 90
// ^

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

return 0;
}

Output:
mylist contains: 10 30 60 80 90


assign:
Assign new content to container

Assigns new content to the container, dropping all the elements contained in the container object before the call and replacing them by those specified by the parameters:

// list::assign
#include < iostream >
#include < list >
using namespace std;

int main ()
{
list< int > first;
list< int > second;

first.assign (7,100); // 7 ints with value 100

second.assign (first.begin(),first.end()); // a copy of first

int myints[]={1776,7,4};
first.assign (myints,myints+3); // assigning from array

cout << "Size of first: " << int (first.size()) << endl;
cout << "Size of second: " << int (second.size()) << endl;
return 0;
}

Output:
Size of first: 3
Size of second: 7

STL LIST- SWAP()

list::swap

Swap content

Exchanges the content of the vector by the content of lst, which is another list object containing elements of the same type. Sizes may differ.

// swap lists
#include
#include
using namespace std;

main ()
{
list first (3,100);
// three ints with a value of 100
list second (5,200);
// five ints with a value of 200
list::iterator it;

first.swap(second);

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

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

cout << endl;

return 0;
}


Output:
first contains: 200 200 200 200 200
second contains: 100 100 100

STL ITERATORS- ADVANCE & DISTANCE

ADVANCE:
Belongs to

Advance iterator
Advances the iterator i by n elements.

If i is a Random Access Iterator, the function uses once operator+ or operator-, otherwise, the function uses repeatedly the increase or decrease operator (operator++ or operator--) until n elements have been advanced.

Return value:none

// advance example
#include
#include
#include
using namespace std;

int main () {
list mylist;
for (int i=0; i<10; i++) mylist.push_back (i*10);

list::iterator it = mylist.begin();

advance (it,5);

cout << "The sixth element in mylist is: " << *it << endl;

return 0;
}
OUTPUT:
The sixth element in mylist is: 50



DISTANCE:
Return distance between iterators

Calculates the number of elements between first and last.

If i is a Random Access Iterator, the function uses operator- to calculate this. Otherwise, the function uses repeatedly the increase or decrease operator (operator++ or operator--) until this distance is calculated.

Return value:
The number of increments or decrements needed to get from first to last.

// distance example
#include
#include
#include
using namespace std;

int main () {
list mylist;
for (int i=0; i<10; i++) mylist.push_back (i*10);

list::iterator first = mylist.begin();
list::iterator last = mylist.end();

cout << "The distance is: " << distance(first,last) << endl;

return 0;
}

Output

The distance is: 10