Savoir lire la documentation STL

En concours, vous avez le droit à la documentation STL. Prenez l'habitude de l'utiliser pour ne pas être perdu le jour du concours.

Minimum de C++ à savoir

Cf le doc de Guillaume

Généralités

Pour utiliser les objets de la STL, il faut inclure des fichiers qui portent généralement le nom de l'objet. Exemple: 

#include <vector>
Ces objets sont pour la plupart dans un namespace nommé std. Avant toute chose, on écrira donc 
using namespace std;
pour éviter d'écrire std:: devant chaque objet.

Certains objets ne font pas partie du standard de la STL mais sont dans l'extension tr1. Les headers sont dans le dossier tr1 et les objets sont dans le namespace tr1. Exemple: 

#include <tr1/unordered_map>
using namespace std ;
using namespace tr1;

L'indispensable

Paires

La paire permet de créer facilement des structures a deux champs, et définit les opérations <, <=, == pour l'ordre lexicographique.

Problème : étant données trois nombres s, p et l affichez tous les couples d'entiers positifs (x,y) tels que x+y = s et x*y = p. 
pair<int,int> somme_et_produit(int a, int b)
{
    return make_pair(a+b,a*b);
}

int maxi( pair<int,int> a )
{
   return max(a.first,a.second ) ;
}

int main()
{ 
  pair cherche ;
  scanf("%d %d",&cherche.first,&cherche.second);
  for( int x = 0 ; x <= maxi(cherche) ; x++ )
      for( int y = 0 ; y <= maxi(cherche) ; y++ )
          if( somme_et_produit(x,y) == cherche )
              printf("%d %d\n",x,y);
}

Vecteurs

vector

Problème : étant donnés un nombre x et un tableau t trié, écrire une fonction qui insére x dans t de tel sorte que t soit trié. 
void insère( vector<int> t , int x )
{
   size_t pos = 0 ;
   while( pos < t.size() && t[pos] < x )
       pos++;
   t.insert( t.begin() + pos , x ) ;
}

void insère2 (vector< int > t , int x )
{
   vector<int>::iterator pos = t.begin() ;
   while( *pos < x )
       pos++;
   t.insert( pos , x ) ;
}

Tas

priority_queue

Problèmes : voir correction de Parcours le plus court (algorithmes de graphes II) si vous ne maîtrisez pas bien cette structure.

Arbres de recherche

Ils sont implémentés sous forme d'arbres binaires équilibrés (rouges/noirs), ce qui garantit une complexité amortie des opérations en O(log n), les éléments sont stockés dans les noeuds et chaque noeud prend en mémoire, en plus de l'élement qu'il représente, trois pointeurs et un booléen.

set

Pour le problème des portes à ouvrir et fermer sur des intervalles 
#include 
#include 
#include 

const int INF = 1000*1000*1000 ;
using namespace std ;
using namespace tr1 ;

typedef set > front ;
front barrieres ;
int nb_reqs ;

int est( int deb ,int fin )
{
  front::iterator apres = barrieres.upper_bound( make_tuple(deb,fin) );
  if(get<0>(*apres) <= deb && get<1>(*apres) >= fin)
    return 1 ;
  apres--;
  return get<0>(*apres) <= deb && get<1>(*apres) >= fin ;
}

void efface( tuple & a , front::iterator & b )
{
  get<0>(a) = min( get<0>(a) , get<0>(*b) );
  get<1>(a) = max( get<1>(a) , get<1>(*b) );
  front::iterator eff = b ;
  b++;
  barrieres.erase(eff);
}

tuple recupere( tuple ou )
{
  front::iterator apres = barrieres.upper_bound( ou );
  while( get<1>(ou) + 1 >= get<0>(*apres) )
    efface(ou,apres);
  while( get<1>(*(--apres)) + 1 >= get<0>(ou)  )
    efface(ou,apres);
  return ou ;
}

int main()
{
  barrieres.insert( make_tuple(-INF,-INF) );
  barrieres.insert( make_tuple(+INF,+INF) );
  scanf("%d",&nb_reqs) ;
  for( int req = 0 ; req < nb_reqs ; req ++ )
    {
      char type[3] ;
      int deb , fin ;
      scanf("%s %d %d",type,&deb,&fin);
      if( type[0] == 'T' )
        printf("%d\n",est(deb,fin));
      if( type[0] == 'S' )
        {
          int ndeb,nfin ;
          tie(ndeb,nfin) = recupere( make_tuple(deb,fin) );
          if( ndeb < deb  )
            barrieres.insert( make_tuple(ndeb,deb-1) ) ;
          if( nfin > fin )
            barrieres.insert( make_tuple(fin+1,nfin) ) ;
        }
      if( type[0] == 'A' )
        barrieres.insert( recupere(make_tuple(deb,fin) ) ) ;        
    }
  return 0;
}

map

Même structure que set mais permet d'associer une valeur à une clé. S'utilise de façon similaire sauf :

#include #include const int INF = 1000*1000*1000 ; using namespace std ; map barrieres ; int nb_reqs ; int est( pair ou ) { map::iterator apres = barrieres.upper_bound( ou.first ) ; apres--; return (*apres).first <= ou.first && (*apres).second >= ou.second ; } void efface( pair & a , map::iterator & b) { a.first = min( a.first , (*b).first ) ; a.second = max(a.second, (*b).second) ; map::iterator eff = b ; b++ ; barrieres.erase(eff); } pair recupere( pair ou ) { map::iterator apres = barrieres.upper_bound( ou.first ) ; while( ou.second + 1 >= (*apres).first ) efface( ou , apres ) ; while( ou.first <= (*(--apres)).second + 1 ) efface( ou , apres ) ; return ou ; } int main() { barrieres[-INF] = -INF ; barrieres[+INF] = +INF ; scanf("%d",&nb_reqs) ; for( int req = 0 ; req < nb_reqs ; req ++ ) { char type[3] ; pair ou , nouv ; scanf("%s %d %d",type,&ou.first,&ou.second); if( type[0] == 'T' ) printf("%d\n",est(ou)); if( type[0] == 'S' ) { nouv = recupere( ou ); if( nouv.first < ou.first ) barrieres.insert( make_pair(nouv.first,ou.first-1) ) ; if( nouv.second > ou.second ) barrieres.insert( make_pair(ou.second+1,nouv.second) ) ; } if( type[0] == 'A' ) barrieres.insert( recupere(ou) ) ; } return 0; }

Tables de hachage

Les tables de hachage de la STL ne sont pas standards et s'appellent unordered, on fera donc attention à utiliser les headers tr1/unordered_set et tr1/unordered_map, et le namespace tr1.

unordered_set

S'utilise presque comme set.

unordered_map

Même structure que unordered_set mais permet d'associer une valeur à une clé. S'utilise presque comme map.

Comment faire une bonne fonction de hachage ?

Bonne : simple, rapide à exécuter et qui assure une distribution uniforme afin de minimiser les collisions.

Si on a des variables vi, i=1..n avec vi dans [| 0 ; mi - 1 |] alors un bon hachage est
h = ((...(((v1m2 + v2)m3 + v3)m4 + v4) ... )mn + vn) % p
où p est un nombre premier supérieur à maxi mi.

Exemple : TODO

Cas particulier : avec des variables vi, 1=1..n avec vi dans [| 0 ; B - 1 |] alors un bon hachage est
h = ((...(((v1B + v2)B + v3)B + v4) ... )B + vn) % P
avec p premier supérieur à B.
Pour optimiser les multiplications, on peut prendre pour B une puissance de 2.

Exemple : TODO

Nombres premiers utiles : TODO , 10^9+7 , 10^6+3
Savoir utiliser bc et factor.

Autres structures

deque

S'utilise presque comme vector.

Remarque: Se prononce [dek].

Minimum et maximum

queue

Une queue utilise une deque mais restreint les opérations à celles d'une file FIFO. Elle n'existe que pour faciliter la compréhension.

stack

Une stack utilise une deque mais restreint les opérations à celles d'une pile LIFO. Elle n'existe que pour faciliter la compréhension.

Utiliser un vector à la place d'une queue pour une stack est plus efficace. Si on veut se restreindre aux opérations d'une pile, on peut utiliser la déclaration suivante : stack<Type, vector<Type> > pile;

list

Liste doublement chaînée.

slist

Liste simplement chaînée. À utiliser si on a pas besoin de traverser la liste dans les deux sens.

Algorithmes

Tris et rangs

sort

Exemples : Remarque: pour trier une liste, utiliser liste.sort();.

min_element

Exemples : Remarques :