C++

Table of Contents

1 Hello

Voici un exemple sur la marche à suivre pour résoudre un problème. On traite le problème (disons numéro 42) suivant: des prénoms sont écrits sur l'entrée standard et il faut leur dire bonjour.

Exemple d'input:

Luke
Leia
Han
Chewbacca
R2D2

Output associé:

Bonjour Luke !
Bonjour Leia !
Bonjour Han !
Bonjour Chewbacca !
Bonjour R2D2 !

Il est bon de créer un fichier in pour mettre l'input. Notre programme sera dans le fichier ttrunck-42.cpp.

Le programme pourrait être le suivant

#include<iostream>
#include<string>

using namespace std;

int main(){
string s;
while(cin >> s)
  cout << "Bonjour " << s << "!\n";
}

Quelques remarques:

  • les includes servent à inclure les bibliothèques, ici de quoi faire les entrées sorties et manipuler les chaines de caractères.
  • le using namespace std sert ouvrir l'espace de nom std, cela permet d'éviter de taper std:: devant chaque fonction. C'est le mal mais pour l'ACM on a le droit. Mais j'insiste, dans la vraie vie c'est vraiment le mal.
  • la fonction principale est le main, dont le code est assez simple, tant qu'on peut lire des chaines de caractères, on les lit et on écrit sur la sortie standard Bonjour puis la chaine puis ! et un retour à la ligne

Pour tester ce programme, il faut d'abord le compiler. Le compilateur sur les machines de l'école étant g++. (Sur votre propre machine vous pouvez avoir clang++ d'installé qui a des messages d'erreurs peut-être plus explicites (mais ils restent hélas assez obscurs)). Il serait dommage de se passer des informations du compilateur, activez donc les warnings, ils peuvent détecter beaucoup d'erreurs idiotes très compliquées à repérer. g++ -Wall -Wextra ttrunck-42.cpp.

Maintenant pour tester le programme ./a.out < in. Si la sortie est simple, vous pouvez regarder si elle correspond. Dans notre cas elle est compliquée, il est alors bon de créer un fichier uva-out, d'écrire notre sortie dans un fichier ./a.out < in > out et de comparer les deux fichiers diff out uva-out. Dans notre cas on détecte ainsi une erreur.

Si vous n'utilisez pas le terminal, une bonne manière de tester vos programmes est d'inclure #include<fstream> et de définir ifstream cin("in") (il faut commenter cette dernière ligne avant de soumettre le problème). C'est à dire d'ouvrir le fichier in et de le lire via cin. Vous pouvez faire la même chose pour définir cout si vous voulez comparer votre sortie avec un fichier de référence.

2 Lecture d'entrées

En ACM la partie la plus difficile est celle des entrées sorties.

— P.R. ACM contestant

Heureusement en C++ pas mal de choses se font simplement. Les fonctions les plus utilisées seront >> et <<. getline pourra parfois nous être utile.

Dans les cas simples et fréquents, >> lit un stream et interprète les données. Il saute les caractères blancs et s'arrête à la fin du flux. Attention la position dans le flux est juste après le mot lu.

getline lit une ligne entière. Attention en le combinant avec << on peut facilement lire uniquement le caractère de retour de ligne au lieu de la ligne suivante. Dans ce cas on peut utiliser ignore pour extraire sans traiter un caractère.

Pour ne pas sauter les espaces avec << on peut lui passer le manipulateur noskipws, et pour revenir dans l'état usuel lui passer skipws.

Voilà un exemple résumant ces notions.

Sur l'entrée

12      3.23e3

Coucou@&#.       p
Paf c
c
Hello
World !
#include<iostream>
#include<string>

using namespace std;

int main(){
int n;
double d;
string s;
char c;
cin >> n >> d >> s >> c;
//n=12, d=3230, s=Coucou@&#, c=p.
cin >> noskipws;
cin >> c;
//c='\n';
getline(cin, s);
cin >> c;
//s="Paf c";
//c='c'
getline(cin, s);
//s="\n"
cin >> s;
cin.ignore();
getline(cin, s);
//s="World !"

}

Warning, Point technique: Certains préfèrent l'usage de scanf et prinf. Si vous savez vous en servir et que vous trouvez l'usage plus simple pourquoi pas. Si c'est pour des questions de performance, le principal problème avec >> et << est qu'ils se synchronisent avec stdio. On peut désactiver se comportement en utilisant ios::sync_with_stdio(false); au début du main. Dans ce cas, suivant le compilateur les performances sont parfois en faveur de l'un parfois en faveur de l'autre (Un benchmark). Dans ce cas attention tout de même à de pas utiliser les deux en même temps.

Conclusion: à moins de vraiment savoir ce que vous faites et d'être autonome en ACM, utilisez cin >> et cout <<.

Bonus: Vous avez vu que c'est bien pratique de faire une boucle while(cin >> n) lorsqu'on ne connait pas le nombre de testcases. Parfois on demande de lire des valeurs sur une ligne sans connaitre le nombre de valeur. Dans ce cas on voudrait pouvoir faire le même genre de contruction. C'est possible, on peut convertir un string en flux et l'utiliser comme cin. Voilà un bout de code expliquant cela.

#include<iostream>
#include<string>
#include<vector>
#include<sstream>

using namespace std;

int main(){
 string data;
  while(getline(cin,data)){
    stringstream s(data);
    vector<double> S;
    int tmp;
    while(s >> tmp)
      S.push_back(tmp);
}

3 Map

Map est un conteneur permettant d'utiliser des tableaux associatifs triés par clé supportant des opérations en O(lg(n)). L'opérateur le plus utile est [key] qui permet d'accéder à la valeur stockée pour key. Attention si cette valeur n'existe pas elle est crée avec l'initialisateur par défaut (pour les int c'est 0).

Voici un exemple simple d'utilisation.

#include<iostream>
#include<map>
#include<string>

using namespace std;

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

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

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

  for(map<char,string>::iterator it=mymap.begin();it!=mymap.end();++it)
    cout << "key: " << it->first << ", value: " << it->second << '\n';

}

Qui affiche:

mymap['a'] is an element
mymap['b'] is another element
mymap['c'] is another element
mymap['d'] is 
key: a, value: an element
key: b, value: another element
key: c, value: another element
key: d, value: 

4 Vector

Vector est un conteneur pour les tableaux dynamiques. Les fonctions les plus utiles sont l'opérateur [] et la fonction push_back. push_back permet d'insérer un fin de tableau une nouvelle valeur, cela agrandi le tableau en temps constant amorti. L'opérateur [] permet d'accéder à la n^ème valeur du tableau en temps constant. Les indices commencent à partir de 0 jusqu'à la taille du vector-1. Le tri de tableau existe dans la bibliothèque de template algorithm ne réinventez pas la roue.

Voici un exemple simple d'utilisation.

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

using namespace std;


int main(){
  vector<int> t(5);
  //crée un tableau d'entier de taille 5 initialisés à 0
  vector<double> d(12,3.14);
  //crée un tableau de floatant de taille 12 initialisés à 3.14
  cout << d[0] << '\n';
  vector<char> p;
  //crée n tableau de char de taille 0
  p.push_back('z');
  //p est maintenant de taille 1 et contient 'z';
  p.push_back('a');
  //p est maintenant de taille 2 et contient 'z' puis 'a';

  //affiche le tableau p
  for(unsigned int i=0;i<p.size();++i)
    cout << p[i] << ' ';
  cout << '\n';

  sort(p.begin(), p.end());
  //p est maintenant de taille 2 et contient 'a' puis 'z';

  //affiche le tableau p
  for(vector<char>::iterator it=p.begin();it!=p.end();++it)
    cout << *it << ' ';
  cout << '\n';

}

Qui affiche:

3.14
z a 
a z 

5 Structures de donnée maison

Supposons que vous vouliez une structure de donnée pour représenter un cercle. Vous voulez également pouvoir utiliser des vector<cercle> ainsi que d'autre conteneur de cercles. Il faut pour cela créer votre propre structure de donnée. Le mot clé est struct et il faut également définir un constructeur (une fonction membre sans type de retour du même nom que votre struct). Attention il y a un ; à la fin de la déclaration. Voici un exemple:

#include<iostream>
#include<vector>

using namespace std;

struct mycercle{
  int x,y,r; 

  mycercle(int a, int b){
    x=a;
    y=b;
    r=0;
  }

  mycercle(int a, int b, int c){
    x=a;
    y=b;
    r=c;
  }

  //Déclaration équivalente
  /*
 mycercle(int a, int b, int c=0){
    x=a;
    y=b;
    r=c;
  }
  */

  //Une autre déclaration équivalente
  //mycercle(int a, int b, int c=0):x(a),y(b),r(c){} 
};

void affiche(mycercle c){
  cout << "Le cercle a pour centre " << c.x << ','
       << c.y << " et pour rayon " << c.r << endl;
} 

int main(){
  mycercle C1(0,0,2);
  affiche(C1);
//Le cercle a pour centre 0,0 et pour rayon 2
  mycercle C2(2,7);
  affiche(C2);
//Le cercle a pour centre 2,7 et pour rayon 0
  vector<mycercle> t1;
  //vector<mycercle> t2(5);
  //Ne fonctionne pas car il n'y a pas de constructeur par défaut
  //il faut au choix donner des valeurs par défaut à tous les paramètres
  //du constructeur ou faire un constructeur sans paramètre
}

6 Permutation

La librairie standard contient l'algorithme de permutation suivante (next_permutation). Par exemple étant donné un vector representant une permutation, il est facile de le modifier afin d'avoir la permutation suivante dans l'ordre lexicographique. Cette fonction fonctionne en temps amorti constant. Elle renvoit un booleen indiquant s'il existait une permutation plus grande. Si ce n'est pas le cas elel renvoit false et rearrange le tableau pourqu'il contienne la plus petite permutation. Attention si vous souhaitez énumérer toutes les permutations il faut que votre tableau soit trié au préalable, et même s'il contient des doublons à chaque itération de next_permutation vous aurez un tableau différent.

Voyons un exemple:

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

using namespace std;

const int N=3;

//affiche toutes les permutations renvoit le compte
int permu(vector<int> & t){
  int res=0;
  do{
    ++res;
    for(vector<int>::iterator it=t.begin();it!=t.end();++it)
      cout << *it << ' ';
    cout << endl;
  }while(next_permutation(t.begin(), t.end()));
  return res;
}

int main(){
  vector<int> t(N);
  for(int i=0;i<N;++i)
    t[i]=N-i;

  int a=permu(t);
  //a=1, t est anti trié donc c'est déja la plus grande permutation
  sort(t.begin(),t.end());
  int b=permu(t);
  //b=6, c'est le résultat attendu
  int c=permu(t);
  //c=6, attention si on a déja la plus grande permutation,
  //next_permutation renvoit false et transforme le tableau
  //en la plus petite permutation. Donc à la fin de /b=../ le
  //tableau est trié.

  t[0]=0, t[1]=0;
  sort(t.begin(),t.end());
  int d=permu(t);
  //d=3, deux éléments sont identiques, il n'y a donc que 3
  //permutations distinctes

  cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
}

7 Encore des Vectors

Deux détails sur l'utilisation efficace des vectors. Par défaut si un paramètre de votre fonction est un vector il sera copié à chaque appel. Ceci est couteux, si vous n'avez pas besoin de ce comportement pensez à le passer par référence.

Un exemple de ce comportement:

#include<iostream>
#include<vector>

using namespace std;

const int N=1e7;

//changement pour passage par référence
//void aux(vector<int> & t){
void aux(vector<int> t){
  t[17*42]=0;
}

int main(){
  vector<int> t(N,42);
  for(int i=0;i<1000;++i)
    aux(t);
  cout << t[17*42] << endl;
//time ./a.out mets 30 sec pour afficher 42
//Avec le changement, ./a.out mets 0 sec pour afficher 0
}

Si vous utilisez un vector comme un ensemble (dans certain cas c'est plus efficace que d'utiliser un (multi)set) et que vous voulez supprimer un élément central. Il est beaucoup plus rapide de le swapper avec le dernier élement et de supprimer le dernier élément.

8 Programmation Dynamique

L'idée de la programmation dynamique est principalement de mémoriser les valeurs déjà calculée. L'exemple le plus naif serait le calcul des nombre de Fibonacci (u_n=un-1+un-2). Si on garde en mémoire les valeurs des précédent termes on a un temps de calcul linéaire, sinon on a un temps de calcul exponentiel.

Souvent on crée un tableau contenant les résulats intermédiaires et on le remplit. En pratique il est pourtant souvent plus simple de proceder recursivement, voyons ces deux approches:

#include<iostream>
#include<vector>

using namespace std;

int fib1(int n){
  vector<int> t(n+1);
  t[0]=1;
  //ne marche pas si n==0
  t[1]=1;
  for(int i=2;i<=n;++i)
    t[i]=t[i-1]+t[i-2];
  return t[n];
}

int fib2(int n, vector<int> & mem){ //attention a bien passer la mémoire par référence
  //cas de base
  if(n==0 || n==1) return 1;
  //cas on le calcul est connu
  if(mem[n]!=-1) return mem[n];
  //sinon on fait le calcul
  int res=fib2(n-1, mem)+fib2(n-2, mem);
  mem[n]=res;//bien penser à mettre à jour la mémoire
  return res;
}

int main(){
  vector<int> mem(100,-1);//on supose ici que la suite ne fibonacci ne prend jamais la valeur -1
  cout << fib1(12) << ' ' << fib2(12,mem) << '\n';
}

L'approche récursive est vivement recommandée (en pratique si le tableau est creux c'est bien plus rapide, et dans le cas contraire avec un bon compilateur le surcout est négligeable).

Cependant le nombre d'appels récursif peut dans certains cas provoquer un runtime error. Dans ce cas il est facile de "derecursifier" le programme en ajoutant une boucle dans laquelle on appelle la fonction sur des valeurs intermédiaires.

9 GMP

Parfois on a besoin de grands entiers (plus que long long). Si le problème est à faire en ligne (i.e. il faut envoyer le code) il faut coder soit même ses grands entiers. Sinon (google code jam, projecteuler,…) on peut utiliser la gmplib. Avec les bindings c++. C'est installé par défault en salle europe, sous debian-like normalement les packages libgmp-dev et libgmpxx4ldbl installent tout. Enfin pour les autres l'installation via compilation marche assez bien. Dans ce cas pensez à activer les bindings c++.

GMP définit plusieurs classes (integers, rationals, floats) celle qui nous intéresse ici est mpz_class pour les entiers. Globalement tout marche comme avec des int. Voici un court exemple et je vous laisse regarder la doc pour en savoir plus.

#include<iostream>
#include<gmpxx.h>

using namespace std;

typedef mpz_class big_int;

big_int fact(int n){
big_int res=1;
for(int i=1;i<=n;++i)
res*=i;
return res;
}

int main(){
  cout << fact(100) << endl;
}

Pour compiler g++ -Wall -Wextra -lgmpxx fact.cpp.

10 OpenMP

Dans les concours offline mais en temps limité, une solution (de la dernière chance) est d'utiliser OpenMP pour paralleliser les testcases.

La solution la plus facile est d'ajouter #pragma omp parallel for devant le for à paralleliser. Puis de compiler avec g++ -fopenmp (cela depend du compilateur, avec icc le flag est -openmp, et clang ne supporte pas openmp). Sans le flag '-fopenmp', le programme s'execute séquentiellement, il n'y a donc pas de risque à ajouter les #pragma.