STL (Standard Template Library)
===============================

It is a collection of templates for several containers (vectors,
stacks, queues, etc.), which we will not need to implement by
ourselves.

Next we show a brief description. For more information, look up the
Jutge, section "Documentation -> Cheat sheets", which contains the
documents "C++ Reference" and "Xuleta EDA". These materials will be
available the day of the exam.

All costs in what follows (unless otherwise stated) are in the worst
case.

PAIRS
=====

Pairs allow forming pairs with a value of type T1 and another value of
type T2.

pair<T1,T2> is equivalent to

struct pair {
  T1 first;
  T2 second;
};

Values can be accessed via the fields "first" and "second".

Pairs are useful because some functions of STL need to return 2
values, and in that case pairs are used for that purpose.  Moreover,
they come handy because some operators are alredy defined:

* operator of equality == ( component-wise)
* operators of comparison (lexicographic)

Ex.

  pair<double, char> a(2.5, 'A');
  pair<double, char> b;
  b.first = 3.5;
  b.second = 'B';
  cout << (a == make_pair(2.5, 'A')) << endl;  // --> 1
  cout << (a < b) << endl;                     // --> 1

================================================================

Next we will see the following classes:

priority_queue<T>   (cua de prioritats)
set<T>              (conjunt)
map<K,V>            (diccionari)

STL is designed to offer an interface which is as uniform as
possible. In particular, some methods are common:

bool empty() const       : returns if the container is empty                       Cost: Theta(1)
unsigned int size() const: returns the number of elements stored in the container  Cost: Theta(1)



PRIORITY QUEUE
==============

A priority_queue<T> is a priority queue of T. The largest element that
was stored in the priority queue is the next one to leave.

!!! You need include the following: #include <queue>

void push(const T& x): add x                           Cost: Theta(log n)
void pop ()          : eliminates the largest element  Cost: Theta(log n)
const T& top() const : returns the largest element     Cost: Theta(1)

Ex. (read a sequence of integers and write it in decreasing order -> Heapsort)

int main() {
  priority_queue<int> pq;
  int x;
  while (cin >> x) pq.push(x);
  while (not pq.empty()) {
    cout << pq.top() << endl;
    pq.pop();
  }
}


SET
===

A set<T> is a set of T.

The elements of the set are stored in increasing order.

(internally they are implemented with balanced binary search trees)

You need to include the following: #include <set>

Let us assume that iterator is a synonym of set<T>::iterator.

An iterator it can be moved forward with ++it and backward with --it.

To access to the element pointed by an iterator it: *it

................................................................

pair<iterator,bool> insert ( const T& x );

Add x to the set.

If it was not there, returns an iterator that points where x has been put, and true.
Else returns an iterator that points to where x was, and false.

Cost: Theta(log n)

................................................................

iterator begin(): returns the iterator to the smallest element
iterator end  (): returns the iterator to the next to the largest element

Cost: Theta(1)

................................................................

iterator find ( const T& x ) const

Looks for the element x in the set.
If it finds it, returns an iterator that points to it.
Else returns end().

Cost: Theta(log n)

................................................................

void erase ( iterator it )

Removes the elements pointed by it.

Cost: Theta(1) amortized

int erase ( const T& x ):

If x belongs to the set, it eliminates it and returns 1.
Else returns 0.

Cost: Theta(log n)

Ex. (read two sequences of integers ending with 0 and write their intersection)

int main() {
  set<int> s1, s2;
  int x;
  while (cin >> x and x != 0) s1.insert(x);
  while (cin >> x and x != 0) s2.insert(x);

  for (set<int>::iterator it = s1.begin(); it != s1.end(); ++it)
    if (s2.find(*it) != s2.end())
      cout << *it << endl;
}


MAP
===

A map<K,V> is a dictionary of keys K and values V. It behaves
similarly to a set of pairs (key, value) (that is, set<pair<K,V> >) where
keys cannot be repeated.

Pairs are sorted in increasing order of key.

(internally they are implemented with balanced binary search trees)

You need include the following: #include <map>

Let us assume that iterator is a synonym of map<K,V>::iterator.

An iterator it can be moved forward with ++it and backward with --it.

To access to the pair  pointed by it: *it
To access to the key   pointed by it: (*it).first   or  it->first
To access to the value pointed by it: (*it).second  or  it->second

................................................................

pair<iterator,bool> insert ( const pair<K,V>& p );

Add the pair p to the dictionary.

If there was no pair with that key, returns an iterator that points to
where p has been put, and true.

Else returns an iterator that points to the pair with the same key that was already in the dictionary, and false

Cost: Theta(log n)

................................................................

iterator begin(): returns the iterator to the pair with the smallest key
iterator end  (): returns the iterator to the next to the pair with the largest key

Cost: Theta(1)

................................................................

iterator find ( const K& k ) const

Looks for a pair with key k.
If it finds it, returns an iterator that points to it.
Else returns end().

Cost Theta(log n)

................................................................

void erase ( iterator it )

Eliminates the pair pointed by it.

Cost: Theta(1) amortized

int erase ( const K& k ):

If there is a pair with key k, it eliminates it and returns 1
Else returns 0.

Cost: Theta(log n)

................................................................

Ex.

int main () {

  map<char,int> m;

  m.insert( pair<char,int>('a', 10) );
  m.insert( make_pair('c', 30) );
  m['d'] = 40;

//    Operator [ ] admits as an argument a key k. Then:
//
//    If there is a pair with that key, it returns a reference to the
//    field second of the pair that already existed with that key.
//
//    Else it inserts a pair with that key and the default constructor
//    of type V (for instance, for basic numeric types of C++, it
//    assigns 0). Then it returns a reference to the field second of
//    that pair.

  m.erase('c');

  for (it = m.begin(); it != m.end(); ++it)
    cout << it->first << " " << it->second << endl;
}

outputs

a 10
d 40


NEW THINGS C++11
================

* You need to compile with g++ -std=c++11

* If the compiler can infer the type of a variable in its declaration,
  then instead of the name of the type, one can write "auto".

  map<string, int> m;
  auto it = m.find("hello");

  
* Loops admit a new syntax to iterate over STL containers

  set<int> s;
  ...
  for(int x : s) cout << x << endl;
  cout << endl;

  
* No need to leave a blank space between >> in templates.

  vector<vector<int>> matrix;

  
* Initialization lists can be given to the STL containers.

  vector<int>   v = {0, 1, 2};
  set<set<int>> s = {{2,3}, {5,1,5}, {}, {3}};


UNORDERED_SET
=============

Like set, but it is no longer guaranteed that traversing the set from
begin() to end() will respect the order of the elements.

insert, find, erase work in linear time in the worst case, 
but in constant time on average.

(internally they are implemented with hash tables)

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {

  unordered_set<int> s1, s2;
  int x;

  while (cin >> x and x != 0)
    s1.insert(x);
  
  while (cin >> x and x != 0)
    s2.insert(x);

  for (auto y : s1) 
    if (s2.find(y) != s2.end()) 
      cout << x << endl;
}


UNORDERED_MAP
=============

Like map, but it is no longer guaranteed that traversing the set from
begin() to end() will respect the order of the keys.

insert, find, erase work in linear time in the worst case, 
but in constant time on average.

(internally they are implemented with hash tables)

#include <unordered_map>
#include <iostream>

using namespace std;

int main() {
  unordered_map<string, int> m;
  string x;
  while (cin >> x) ++m[x];
  for(auto p : m)
    cout << p.first << " " << p.second << endl;
}