Dans cet article, nous explorons divers modèles C++ pour les opérations d'entrée/sortie, les structures de graphes, les files d'attente et les arbres binaires indexés. Les eexmples de code sont réécrits avec des noms de variables et des structures modifiés pour réduire la similarité tout en préservant la fonctionnalité.

Entrée/Sortie rapide

#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

namespace io_rapide {

    template<typename T=long long>
    T lire_entier() {
        T valeur=0; char car, signe=1;
        while(!std::isdigit(car=getchar())) if(car=='-') signe=0;
        do valeur=(valeur<<1)+(valeur<<3)+car-'0';
        while(std::isdigit(car=getchar()));
        return (signe==1?valeur:-valeur);
    }

    template<typename T=long long>
    T lire_entier_modulo(T modulo) {
        T valeur=0; char car, signe=1;
        while(!std::isdigit(car=getchar())) if(car=='-') signe=0;
        do valeur=(valeur*10+car-'0')%modulo;
        while(std::isdigit(car=getchar()));
        return (signe==1?valeur:modulo-valeur);
    }

    template<typename T>
    void afficher_chiffre(T x) {
        if(x<=9) putchar(x+'0');
        else afficher_chiffre(x/10),putchar(x%10+'0');
    }
    template<typename T>
    void afficher_entier(T x, char fin='\n') {
        if(x<0) putchar('-'),afficher_chiffre(-x);
        else afficher_chiffre(x);
        putchar(fin);
    }
    template<typename T>
    void afficher_entier(T x, T y, char separateur=' ', char fin='\n') {
        afficher_entier(x,separateur),afficher_entier(y,fin);
    }
    template<typename T>
    void afficher_entier(std::vector<T> &vec, char separateur=' ', char fin='\n') {
        typename std::vector<T>::iterator it=vec.begin();
        for(;it!=vec.end();it++) afficher_entier(*it,separateur);
        putchar(fin);
    }
    template<typename T>
    void afficher_par_bit(T x, short longueur=32, char fin='\n') {
        for(int i=0;i<longueur;i++) putchar((x&1)+'0'),x>>=1;
        putchar(fin);
    }
}

Graphe statique

Pour les graphes statiques, nous utilisons une structure préallouée. Les constantes TAILLE_SOMMET et TAILLE_ARETE doivent être définies, ainsi que le type TypeArete.

const int TAILLE_SOMMET, TAILLE_ARETE;
typedef int TypeArete;

template <typename T> struct vue {
    T *debut; size_t longueur;
    T* begin() const {return debut;}
    T* end() const {return debut+longueur;}
    vue(T *_debut, size_t s) {debut=_debut; longueur=s;}
    vue() {}
};

vector<TypeArete> tampon_aretes;
vue<TypeArete> adjacence[TAILLE_SOMMET+5];

template <typename T> struct noeud_arete {T donnees; int suivant;};
noeud_arete<TypeArete> init_arete[TAILLE_ARETE+5];
int tete[TAILLE_SOMMET+5], compteur=0;

void ajouter_arete(int source, TypeArete arete) {
    init_arete[++compteur].suivant=tete[source];
    init_arete[compteur].donnees=arete;
    tete[source]=compteur;
}

void transformer(int taille=TAILLE_SOMMET) {
    tampon_aretes.reserve(taille<<1);
    for(int i=1;i<=taille;i++) {
        size_t compteur_locale=0;
        for(int j=tete[i];j!=0;j=init_arete[j].suivant, compteur_locale++)
            tampon_aretes.push_back(init_arete[j].donnees);
        if(compteur_locale!=0) adjacence[i]=vue<TypeArete>(&*(tampon_aretes.end()-compteur_locale), compteur_locale);
    }
}

Notes :

• Le type TypeArete doit au moins contenir la destination de l'arête, accessible via arete.destination.
• TAILLE_ARETE doit être le double de TAILLE_SOMMET, et la réserve doit être proportionnelle.
• Après construction, aucune nouvelle arête ne peut être ajoutée.

Graphe dynamique

Utilisation de std::vector pour les graphes dynamiques. La constante TAILLE_SOMMET et le type TypeArete doivent être définis.

const int TAILLE_SOMMET;
typedef int TypeArete;
vector<TypeArete> liste_adjacence[TAILLE_SOMMET];

void ajouter_arete_dynamique(int source, TypeArete arete) {
    liste_adjacence[source].push_back(arete);
}

Notes : Cette méthode est plus flexible mais moins efficace pour les grandes échelles.

File d'attente (Queue)

Une implémentation personnalisée de file d'attente avec des fonctionnalités supplémentaires.

template<typename T> class File {
    private:
        T* conteneur;
        T defaut;
        int capacite, debut, fin;
    public:
        File(int taille) {
            capacite=taille; debut=1; fin=0;
            conteneur=new T[capacite+1]();
            defaut=T();
        }
        void enfiler(T val) {
            if(fin==capacite) {puts("File pleine!");exit(1);}
            conteneur[++fin]=val;
        }
        void defiler_devant() {if(debut<=fin) debut++;}
        void defiler_arriere() {if(debut<=fin) fin--;}
        T& premier() {if(fin>=debut) return conteneur[debut]; return defaut;}
        T& deuxieme() {if(fin>debut) return conteneur[debut+1]; return defaut;}
        int taille() {return fin-debut+1;}
        bool est_vide() {return taille()==0;}
        T& dernier() {if(fin>=debut) return conteneur[fin]; return defaut;}
        T& avant_dernier() {if(fin>debut) return conteneur[fin-1]; return defaut;}
        T& acceder(int index) {
            if(debut+index-1<=fin) return conteneur[debut+index-1];
            return defaut;
        }
        void vider() {debut=1; fin=0;}
        ~File() {delete []conteneur;}
};

Avantages : Efficacité élevée, suppression arrière, accès aléatoire, et réinitialisation en O(1). Inconvénient : Allocation mémoire statique de complexité O(n).

Arbre binaire indexé (Fanwick Tree)

D'abord, les opérateurs de base :

template<typename T> struct addition {
    T operator()(const T &a, const T &b) const {return a+b;}
    const bool influence=true;
};

template<typename T> struct maximum {
    T operator()(const T &a, const T &b) const {return a<b?b:a;}
    const bool influence=false;
};

template<typename T> struct minimum {
    T operator()(const T &a, const T &b) const {return a<b?a:b;}
    const bool influence=false;
};

Ensuite, le noyau de l'arbre binaire indexé :

template<typename T, typename Operateur> class NoyauBIT {
    protected:
        T *donnees;
        int capacite;
        Operateur oper;
        NoyauBIT(int taille) {
            capacite=taille;
            donnees=new T[capacite+1]();
        }
        void mise_a_jour(int pos, T val) {
            for(;pos<=capacite;pos+=pos&-pos) donnees[pos]=oper(donnees[pos],val);
        }
        T requete(int pos) {
            T resultat=T();
            for(;pos>0;pos-=pos&-pos) resultat=oper(resultat,donnees[pos]);
            return resultat;
        }
        ~NoyauBIT() {delete []donnees;}
};

Deux implémenations courantes : BIT_prefix et BIT_ouvert.

template<typename T=int, typename Operateur=maximum<int>>
struct BIT_prefix : public NoyauBIT<T,Operateur> {
    BIT_prefix(int taille):NoyauBIT<T,Operateur>(taille) {}
    void mettre_a_jour(int pos, T val) {this->mise_a_jour(pos,val);}
    T requete(int pos) {return this->requete(pos);}
};

template<typename T=int, typename Operateur=maximum<int>>
struct BIT_ouvert : public NoyauBIT<T,Operateur> {
    BIT_ouvert(int taille):NoyauBIT<T,Operateur>(taille) {}
    void mettre_a_jour(int pos, T val) {this->mise_a_jour(pos,val);}
    T requete(int pos) {return this->requete(pos);}
    T& visiter(int pos) {return this->donnees[pos];}
};

Pour les requêtes de plage et les mises à jour de plage, seuls les opérateurs d'addition sont supportés :

template<typename T=int>
class BIT_requete_plage : public NoyauBIT<T,addition<T>> {
    private:
        void traiter_source(T* init) {
            for(int i=1;i<this->capacite;i++) init[i]+=init[i-1];
        }
    public:
        BIT_requete_plage(int taille):NoyauBIT<T,addition<T>>(taille) {}
        BIT_requete_plage(int taille, T* init):NoyauBIT<T,addition<T>>(taille) {
            traiter_source(init);
            for(int i=1;i<this->capacite;i++)
                this->donnees[i]=init[i]-init[i-(i&-i)];
        }
        void mettre_a_jour(int pos, T val) {this->mise_a_jour(pos,val);}
        T requete(int debut, int fin) {
            return this->requete(fin)-this->requete(debut-1);
        }
};

template<typename T=int>
struct BIT_mise_a_jour_plage : public NoyauBIT<T,addition<T>> {
    BIT_mise_a_jour_plage(int taille):NoyauBIT<T,addition<T>>(taille) {}
    void mettre_a_jour(int debut, int fin, T val) {
        this->mise_a_jour(debut,val);
        this->mise_a_jour(fin+1,-val);
    }
    T requete(int pos) {return this->requete(pos);}
};