L1: Use of STL data structures

Test Inicial d’Autoavaluació de Laboratori

Autoevaluació

If I want to run a single-file program program.cc, do I need to first compile and generate the object program.o with g++ -c program.cc, and then link to produce the executable with g++ program.o?

Answer

One could do that, but in this case it can all be done in a single line: g++ program.cc.


If I want to use any of the features of the C++ 2011 standard in my program program.cc, how should I compile it with g++?

Answer 
g++ -std=c++11 program.cc

Note that std stands for standard.


How can I tell g++ to warn me against everything that is found suspicious during compilation?

Answer 
g++ -Wall program.cc

Note that Wall stands for Warning all. It is wise to always use the -Wall flag.


How can I tell g++ to optimize the generated code?

Answer

For instance, with

g++ -O2 program.cc

nearly all supported optimizations not involving a space-speed tradeoff are performed. Note that O stands for Optimization.


I have an executable a.out and want to read data from a file sample.inp rather than from the keyboard, and write the output on a new file sample.out instead of to the screen. How can I do that?

Answer 
./a.out < sample.inp > sample.out


How can I find the differences between two files sample.out and sample.cor?

Answer

For example:

diff sample.out sample.cor


In C++, how can I create a bidimensional matrix matrix of ints with n rows and m columns, all of them initialized to 1?

Answer

The standard library of C++ does not have a built-in type “matrix”. A way to create the matrix is by creating a vector of n rows, each of which is a vector of m integers initialized to 1. By using the standard template class vector<T> and the constructor vector<T>(size, init) (which creates a vector of size copies of init):

vector<int> row(m, 1); 
vector<vector<int>> matrix(n, row);

Equivalently (and better) in a single line:

vector<vector<int>> matrix(n, vector<int>(m, 1));


I have to sort a vector v of ints increasingly. Should I write my own sorting procedure?

Answer

No (unless there is another reason for doing so). Use the sort procedure of the standard C++ library:

#include <algorithm> 

//...

sort(v.begin(), v.end());


And what if I have to sort decreasingly?

Answer

The sort procedure admits a third parameter: the sorting criterion. It is a function or a function object that takes as parameters two objects of the container (in this case, two ints) and returns true when the first argument should come before the second one. For instance, in this case:

#include <algorithm> 

bool before(int a, int b) { return a > b;} 

// ...

sort(v.begin(), v.end(), before);

Function objects of class greater<int>, available in the standard library, behave essentially the same as the aforementioned function before, and give an elegant solution:

#include <algorithm> 

// ...

sort(v.begin(), v.end(), greater<int>());

Another example of function before, now defined over structs:

// first small surnames, in case of tie big names, in case of tie the younger one 
bool before(const Info& a, const Info& b) {
  if (a.surname != b.surname) 
    return a.surname < b.surname; 
  if (a.name  != b.name) 
    return a.name > b.name;
return a.age < b.age; 
}


Let s be a stack<pair<int,int>. Can the following code be written more compactly? (assuming that aux is not used any more)

pair<int,int> aux; 
aux.first = 1; 
aux.second = 2;
s.push(aux);
Answer

One can make the compiler generate the adequate temporary object by calling a constructor of pair<int,int>. For example, any of the following would do:

s.push(pair<int,int>(1, 2)); 
s.push(make pair(1, 2));
s.push({1, 2}); // This is C++11


When I compile my program program.cc I get the output below. Where is the error?

user@machine:$ g++ program.cc
   program.cc: In function ‘int main()’:
   program.cc:10:8: error: no match for ‘operator<<’ (operand types are ‘std::ostream
   {aka std::basic_ostream<char>}’ and ‘std::vector<int>’)
      cout << v << endl;
           ^
   In file included from /usr/include/c++/5/iostream:39:0,
                    from program.cc:1:
   /usr/include/c++/5/ostream:108:7: note: candidate: std::basic_ostream<_CharT,
   _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ostream<_
   _Traits>::__ostream_type& (*)(std::basic_ostream<_CharT, _Traits>::__ostream_type&))
   [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT,
   _Traits>::__ostream_type = std::basic_ostream<char>]
          operator<<(__ostream_type& (*__pf)(__ostream_type&))
          ^
   /usr/include/c++/5/ostream:108:7: note:   no known conversion for argument
   1 from ‘std::vector<int>’ to ‘std::basic_ostream<char>::__ostream_type&
   (*)(std::basic_ostream<char>::__ostream_type&) {aka std::basic_ostream<char>&
   (*)(std::basic_ostream<char>&)}’
   /usr/include/c++/5/ostream:117:7: note: candidate: std::basic_ostream<_CharT,
   _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ostream<_
   _Traits>::__ios_type& (*)(std::basic_ostream<_CharT, _Traits>::__ios_type&))
   [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT,
   _Traits>::__ostream_type = std::basic_ostream<char>; std::basic_ostream<_CharT,
   _Traits>::__ios_type = std::basic_ios<char>]
          operator<<(__ios_type& (*__pf)(__ios_type&))
          ^
   /usr/include/c++/5/ostream:117:7: note:   no known conversion for argument
   1 from ‘std::vector<int>’ to ‘std::basic_ostream<char>::__ios_type& (*)(std::basic_ostream<cha
   {aka std::basic_ios<char>& (*)(std::basic_ios<char>&)}’
   /usr/include/c++/5/ostream:127:7: note: candidate: std::basic_ostream<_CharT,
   _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::ios_base&
   (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>;
   std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
          operator<<(ios_base& (*__pf) (ios_base&))
  ...
Answer

Do not get overwhelmed by lengthy error reports. Focus on the (very) first lines. Here

program.cc:10:8: error: no match for ‘operator<<’ (operand types are ‘std::ostream
{aka std::basic_ostream<char>}’ and ‘std::vector<int>’)
   cout << v << endl;

is telling us that at line 10, column 8, the operator << is misused.


(Credits and pdf version of this section: Test Inicial d’Autoavaluació de Laboratori)

La Llibreria STL

(el contenido de esta seccion es el mismo de Página principal de EDA \(\rightarrow\) Material Docent \(\rightarrow\) STL)

La llibreria STL (Standard Template Library) és una col·lecció de plantilles per a diversos contenidors (vectors, piles, cues, etc.) que ja no caldrà que implementem. La STL està pensada per oferir una interfície el més uniforme possible. En particular, hi ha diversos mètodes que són comuns:

bool empty() const
diu si el contenidor és buit
Cost: \(\Theta(1)\)
unsigned int size() const
retorna la mida del contenidor
Cost: \(\Theta(1)\)

A continuació es fa un descripció breu. Podeu trobar més informació a la web cppreference.com i al Jutge, secció “Documentation -> Cheat sheets”, on hi ha els documents C++ reference i “Xuleta EDA”. Aquest ultim material estarà disponible el dia de l’examen.

Tots els costos que donarem (a no ser que es digui el contrari) són en el cas pitjor.

A continuació veurem les següents classes:

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

pair

Els pairs permeten formar parells amb un valor de tipus T1 i un valor de tipus T2.

pair<T1,T2> és equivalent a

struct pair {
  T1 first;
  T2 second;
};

S’accedeix als valors amb els camps first i second.

Els pairs són útils perquè algunes funcions de la STL necessiten retornar 2 valors, i en aquest cas s’utilitzen pairs per fer-ho. A més, també van bé perquè tenen alguns operadors ja definits:

  • operador d’igualtat == (component a component)
  • operadors de comparació (lexicogràficament)

Exemplo

  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

priority_queue

Una priority_queue<T> és una cua de prioritats de T. L’element més gran guardat a la cua de prioritats és el primer que surt.

Cal fer: #include <queue>

void push(const T& x)
afegeix x
Cost: \(\Theta(\log n)\)
void pop()
elimina l’element més gran
Cost: \(\Theta(\log n)\)
const T& top() const
retorna l’element més gran
Cost: \(\Theta(1)\)

Exemplo (Heapsort) llegeix una seqüència d’enters i l’escriu ordenada de forma decreixent

#include <queue>

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

Un set<T> és un conjunt de T. Els elements del conjunt es guarden ordenats de menor a major. (internament estan implementats amb arbres binaris de cerca balancejats)

Cal fer: #include <set>

Assumim que iterator és sinònim de set<T>::iterator.

Un iterator it es mou cap endavant amb ++it i cap endarrera amb --it

Per accedir a l’element apuntat per un iterator it: *it

pair<iterator,bool> insert ( const T& x );
Afegeix x al conjunt. Si no hi era, retorna un iterador que apunta on s’ha ficat x, i true. Sinó retorna un iterador que apunta on ja hi havia x, i false.
Cost: \(\Theta(\log n)\)
iterator begin()
retorna l’iterador a l’element més petit
Cost: \(\Theta(1)\)
iterator end()
retorna l’iterador al següent de l’element més gran
Cost: \(\Theta(1)\)
iterator find(const T& x) const
Busca l’element x al conjunt. Si el troba, retorna un iterador que hi apunta. Sinó retorna end().
Cost \(\Theta(\log n)\)
void erase(iterator it)
Elimina l’element apuntat per it.
Cost: \(\Theta(1)\) amortit
int erase(const T& x)
Si x pertany al conjunt, l’elimina i retorna 1. Sinó retorna 0.
Cost: \(\Theta(\log n)\)

Exemplo llegeix dues seqüències d’enters acabades en zero i escriu seva intersecció

#include <set>

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

Un map<K,V> és un diccionari de claus K i valors V. Es comporta de manera semblant a un conjunt de parells (clau, valor) (és a dir, set<pair<K,V>>) on no es poden repetir claus.

Els parells estan ordenats per clau de menor a major.

(internament estan implementats amb arbres binaris de cerca balancejats)

Cal fer: #include <map>

Assumim que iterator és sinònim de map<K,V>::iterator.

Un iterator it es mou cap endavant amb ++it i cap endarrera amb --it
Per accedir al parell apuntat per it: *it
Per accedir a la clau apuntada per it: (*it).first o it->first
Per accedir al valor apuntat per it: (*it).second o it->second

pair<iterator,bool> insert(const pair<K,V>& p);
Afegeix el parell p. Si no hi havia cap parell amb aquesta clau, retorna un iterador que apunta on s’ha ficat p, i true. Sinó retorna l’iterador que apunta al parell que ja hi havia amb la mateixa clau, i false.
Cost: \(\Theta(\log n)\)
iterator begin()
retorna l’iterador al parell amb clau més petita
Cost: \(\Theta(1)\)
iterator end()
retorna l’iterador al següent al parell amb clau més gran
Cost: \(\Theta(1)\)
iterator find(const K& k) const
Busca un parell amb clau k. Si el troba, retorna un iterador que hi apunta. Sinó retorna end().
Cost \(\Theta(\log n)\)
void erase(iterator it)
Elimina el parell apuntat per it.
Cost: \(\Theta(1)\) amortit
int erase ( const K& k )
Si hi ha un parell amb clau k, l’elimina i retorna 1. Sinó retorna 0.
Cost: \(\Theta(\log n)\)

Exemplo.

#include <map>

typedef pair<char,int> P;
typedef map<char,int> M;

int main(){

  M m;

  m.insert( P('a', 10) );
  m.insert( make_pair('c', 30) );
  m['d'] = 40;

  //    L'operador [ ] admet com a argument una clau k. Llavors:
  //
  //    Si ja hi havia un parell amb la clau, es retorna una referència al
  //    camp second (valor) del parell que ja existia amb aquesta clau.
  //
  //    Sino, s'inserta un parell amb aquesta clau i el constructor per
  //    defecte del tipus V (per ex., per a tipus bàsics de C++
  //    numèrics, assigna a 0). Llavors es retorna una referència al
  //    camp second (valor) d'aquest parell.

  m.erase('c');

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

té sortida

a 10
d 40

“NOVETATS” C++11

  • Cal compilar amb g++ -std=c++11

  • Si el compilador pot inferir el tipus d’una variable a la declaració, en lloc de posar el tipus de la variable, es pot escriure auto. 
    map<string, int> m;
auto it = m.find("hello");
  • Els bucles for s’han modificat per poder iterar fàcilment sobre col·leccions.
    Exemplo 
    set<int> s;
...
for(int x : s) cout << x << endl;
cout << endl;
  • Ja no cal posar un espai entre els >> dels templates.
    Exemplo. 
    vector<vector<int>> matrix;
  • Es poden donar llistes d’inicialitzacions a contenidors de la STL.
    Exemplo. 
    vector<int>   v = {0, 1, 2};
set<set<int>> s = { {2,3}, {5,1,5}, {}, {3} };

unordered_set

Com el set, però no es garanteix que recórrer el set des de begin() fins a end() respecti l’ordre dels elements.

insert, find, erase funcionen en temps \(\Theta(n)\) en el cas pitjor, però temps \(\Theta(1)\) en mitjana.
(internament estan implementats amb taules de hash)

Exemplo.

#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 << y << endl;
}

unordered_map

Com el map, però no es garanteix que recórrer el map des de begin() fins a end() respecti l’ordre de les claus.

insert, find, erase funcionen en temps \(\Theta(n)\) en el cas pitjor, però en temps \(\Theta(1)\) en mitjana.
(internament estan implementats amb taules de hash)

Exemplo.

#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;
}

Ejemplos

Página principal de EDA \(\rightarrow\) Material Docent \(\rightarrow\) Algorismes en C++ \(\rightarrow\) Chapter 1: STL Usage Examples

Jutge.org Jutge.org

Posible flujo de trabajo

  • descargar el archivo .zip zip de el problema de el Jutge.org Jutge.org que se quiere resolver
  • unzip el archivo
  • en la carpeta obtenida teneis:
    • un file .pdf con el enunciado del problema,
    • uno o más files de texto con ejemplos de input sample.inp
    • los correspondiente outputs correctos sample.cor
  • crear un file con el vuestro codigo sorgente C++ para resolver el problema
  • compilar el codigo sorgente con g++ -std=c++11.
    Posibles flags utiles: -Wall -Wextra -Wno-overflow -Wpedantic -Werror -D_GLIBCXX_DEBUG
  • testar el ejecutable en los ejemplos:
    por ejemplo con ./a.out < sample.inp > output
  • testar que el file de output sea correcto:
    por ejemplo con diff output sample.cor
  • una vez que estais convencidos que vuestra solucion es correcta, enviarla al Jutge
    • no enviar al Jutge soluciones que no sean correctas en los ejemplos que teneis!
    • no intentar re-escribir a mano los ejemplos de input

Problemas sobre STL

Los problemas de el apartado EDA Curs 2023/2024 Q2 \(\rightarrow\) Use of STL data structures.

P50709 Collection of numbers
P40902 Casino
P69781 Collatz pseudo-sequences (2) :exclamation:
P84415 Bag of words
P37064 Dynamic median :exclamation:
P59282 Statistical measures
P69932 The longest sequence :exclamation:
P60296 Role Classification
P60219 Easy game?
P62653 Ticket distribution
P63584 K-th element (~ Problem 4.11 you will see in the problem class P5)
:exclamation: = the problem might be harder than the rest

Problemas resueltos en clase

P60296 Role Classification

Possible C++ code to start problem P60296 
//STL - Role classification
#include<iostream>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

int main(){
    set<string> logged;
    map<string,int> elo;
    string op;
    while(cin >> op){
        string player1;
        cin >> player1;
        if (op == "LOGIN"){
            // do something
        }
        else if (op == "LOGOUT"){
            // do something
        }
        else if (op == "PLAY"){
            // do something
        }
        else{// op == GET_ELO
            // do something
        }
    }
    cout << endl << "RANKING" << endl;
            // do something

}
Possible solution 
//STL - Role classification
#include<iostream>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

int main(){
    string cmd;
    set<string> logged;
    map<string,int> elo;

    while(cin >> cmd){
        string player1;
        cin >> player1;
        if (cmd == "LOGIN"){
            logged.insert(player1);
         if (not elo.count(player1)) elo[player1] = 1200;
     }
        else if (cmd == "LOGOUT") logged.erase(player1);
        else if (cmd == "GET_ELO") cout << player1 << ' ' << elo[player1] << endl;
        else{// case of PLAY
            string player2;
            cin >> player2;
            if (not logged.count(player1) or not logged.count(player2)) cout << "player(s) not connected" << endl;
            else{
            elo[player1] +=10;
                elo[player2] = max(elo[player2]-10,1200);
            }
        }
    }
    cout << endl << "RANKING" << endl;
    vector<pair<int,string>> v;
    for (auto p : elo) v.emplace_back(-p.second,p.first);
    sort(v.begin(),v.end());
    for (auto p :v) cout << p.second << ' ' << -p.first << endl;
}


P59282 Statistical measures

Possible C++ code to start problem P59282 
//STL - Satistical measures
#include<iostream>
#include<queue>
#include<limits>
#include<iomanip>

using namespace std;

const auto MININFTY = numeric_limits<int>::lowest();

int main(){
    string op;
    priority_queue<int,vector<int>,greater<int>> q;
    int sum = 0;
    int max = MININFTY;
    while (cin >> op){
        if (op == "delete"){ 
            // do something
        }
        else{// case of "number"
            // do something 
        } 
        int sz = q.size();
        if (sz == 0) cout << "no elements" << endl;
        else{
            // do something
            // to output a double x with 4 digits of precision use 
            // cout << fixed << setprecision(4) << x
        }
    }
}
Possible solution 
//STL - Satistical measures
#include<iostream>
#include<queue>
#include<limits>
#include<iomanip>

using namespace std;

const auto MININFTY = numeric_limits<int>::lowest();

int main(){
    string op;
    priority_queue<int,vector<int>,greater<int>> q;
    int sum = 0;
    int max = MININFTY;
    while (cin >> op){
        if (op == "delete"){ 
            if (not q.empty()){
                sum -=q.top();
                q.pop();
                if (q.empty()) max = MININFTY;
            }
        }
        else{// case of "number"
            int value;
            cin >> value;
            q.push(value);
            sum +=value;
            if (value > max) max = value; 
        } 
        int sz = q.size();
        if (sz == 0) cout << "no elements" << endl;
        else{
            double avg = double(sum) / sz;
            cout << "minimum: " << q.top();
            cout << ", maximum: " << max;
            cout << ", average: " << fixed << setprecision(4) << avg << endl;
        }
    }
}