IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage C++ Discussion :

template, allocator et vecteur dans le nouveau Stroustrup


Sujet :

Langage C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre très actif
    Profil pro
    professeur des universités à la retraite
    Inscrit en
    Août 2008
    Messages
    364
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : professeur des universités à la retraite

    Informations forums :
    Inscription : Août 2008
    Messages : 364
    Par défaut template, allocator et vecteur dans le nouveau Stroustrup
    J'étudie le livre récent de Stroustrup :
    Programming, Principles and practise using C++
    dans l'ensemble, ça se passe très bien, mais je bloque un peu sur le paragraphe 19.5.5 du Chapitre 19, qui propose une implémentation (à finalité didactique) de la classe vector.

    J'ai recopié ci-dessous le code concernant ce paragraphe, mis en ligne par l'auteur (http://www.stroustrup.com/Programming/). Je peine à en faire une version compilable et exécutable. Je voudrais rajouter un main tout bête du genre :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    main()
    {
    vector<int> v(4);
    v.reserve(10);
    }
    et pour cela il faudrait placer dans les //... de la classe vector, un constructeur vector(int n) ..., mais pour l'instant je dois dire que je sèche...
    Des idées ?



    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    //
    // This is example code from Chapter 19.5.5 "RAII for vector" of
    // "Programming -- Principles and Practice Using C++" by Bjarne Stroustrup
    //
     
    //------------------------------------------------------------------------------
     
    template<class T> class allocator {
    public:
        // ...
        T* allocate(int n);                 // allocate space for n objects of type T
        void deallocate(T* p, int n);       // deallocate n objects of type T starting at p
     
        void construct(T* p, const T& v);   // construct a T with the value v in p
        void destroy(T* p);                 // destroy the T in p
    };
     
    //------------------------------------------------------------------------------
     
    template<class T, class A>
    struct vector_base {
        A alloc;                            // allocator
        T* elem;                            // start of allocation
        int sz;                             // number of elements
        int space;                          // amount of allocated space
     
        vector_base(const A& a, int n)
            : alloc(a), elem(a.allocate(n)), sz(n), space(n) { }
        ~vector_base() { alloc.deallocate(elem,space); }
    };
     
    //------------------------------------------------------------------------------
     
    template<class T, class A>
    void swap(vector_base<T,A>& a, vector_base<T,A>& b);
     
    //------------------------------------------------------------------------------
     
    template<class T, class A = allocator<T> >
    class vector : private vector_base<T,A> {
    public:
        // ...
        void reserve(int newalloc);
    };
     
    //------------------------------------------------------------------------------
     
    template<class T, class A>
    void vector<T,A>::reserve(int newalloc)
    {
        if (newalloc<=this->space) return;  // never decrease allocation
        vector_base<T,A> b(this->alloc,newalloc); // allocate new space
        for (int i=0; i<this->sz; ++i) this->alloc.construct(&b.elem[i],this->elem[i]); // copy
        for (int i=0; i<this->sz; ++i) this->alloc.destroy(&this->elem[i]); // destroy old 
        swap< vector_base<T,A> >(*this,b);  // swap representations
    }
     
    //------------------------------------------------------------------------------

  2. #2
    Membre Expert
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 34
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Par défaut
    Humm, à mon avis il attend que tu utilises std::uninitialized_fill();

    D'ailleurs je déclarerais le constructeur en explicit là...

  3. #3
    Membre très actif
    Profil pro
    professeur des universités à la retraite
    Inscrit en
    Août 2008
    Messages
    364
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : professeur des universités à la retraite

    Informations forums :
    Inscription : Août 2008
    Messages : 364
    Par défaut
    A noter que ceci n'est pas un exercice, mais simplement le texte du code illustrant ce paragraphe 19.5.5 du livre, il n'y a donc pas à proprement parler d'attente de l'auteur. Je voudrais juste rajouter à ce code le minimum nécessaire pour qu'il puisse compiler et s'exécuter avec un main() simplissime du genre de celui que j'ai donné plus haut.

    Je resitue le sens de tout cela : il s'agit de proposer, pour l'implémentation d'une classe vecteur, une version de la fonction reserve() - fonction qui alloue l'espace nécessaire au vecteur - qui permette d'éviter des fuites de mémoire.

    La première version proposée par Stroustrup, au paragraphe 19.3.6, p.667., était ceci :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    template<class T, class A> 
    void vector<T,A>::reserve(int newalloc)
    {
        if (newalloc<=space) return;        // never decrease allocation
        T* p = alloc.allocate(newalloc);    // allocate new space
        for (int i=0; i<sz; ++i) alloc.construct(&p[i],elem[i]); // copy
        for (int i=0; i<sz; ++i) alloc.destroy(&elem[i]);        // destroy
        alloc.deallocate(elem,space);       // deallocate old space
        elem = p;
        space = newalloc;    
    }
    le risque que l'auteur souligne, pour cette version, est que la fonction alloc.construct() peut lever une exception, ce qui aurait pour conséquence que l'espace précédemment alloué pour le pointeur p ne serait jamais libéré.

    Pour éviter cela, Stroustrup propose en 19.5.5 le code que j'ai recopié plus haut : la classe vector() est dérivée, par héritage privé, d'une classe vector_base() qui contient les éléments constitutifs du vecteur (sa taille (sz), son espace réservé (space = taille + espace de réserve non initialisé), le pointeur elem vers les données et l'allocateur alloc).

    La fonction reserve() nouvelle manière, fait allouer l'espace par le constructeur de vector_base(). La fonction crée un objet de type vector_base() dont le constructeur alloue l'espace nécessaire. De ce fait, si une exception était levée avant la fin de la fonction reserve(), alors le destructeur de cet objet serait automatiquement appelé et l'espace alloué serait libéré.
    Ensuite, on permute, avec la fonction swap(), le contenu de cet objet vector_base() avec le contenu de l'objet vector() qui appelle la fonction reserve(). On a donc finalement réussi à allouer l'espace nécessaire à l'objet vector() sans risquer de fuite de mémoire.

    Tout ceci constitue un exemple de la technique dite "RAII" (= Resource Acquisition Is Initialization) destinée à se prémunir contre les fuites de mémoire.

    EDIT Comme toujours dans ce livre, le code proposé utilise ce que le lecteur connait au point où le code est proposé (ici on présuppose donc seulement connu le contenu des 19 premiers chapitres du livre), le code ne prétend donc pas être un 'modèle' indépassable, mais un outil pédagogique utilisé à un moment donné d'un parcours d'enseignement.

  4. #4
    Membre Expert
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 34
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Par défaut
    Et je maintiens, ici le mieux dans le constructeur est d'utilisé std::uninitialized_fill(). Dans cette optique d'avoir un code exception safety .
    Tiens un papier de BS sur le sujet : (ça doit être proche de ce que tu trouves dans ton livre) :
    http://www.research.att.com/~bs/except.pdf

  5. #5
    Membre très actif
    Profil pro
    professeur des universités à la retraite
    Inscrit en
    Août 2008
    Messages
    364
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : professeur des universités à la retraite

    Informations forums :
    Inscription : Août 2008
    Messages : 364
    Par défaut
    Au stade où j'en suis et pour l'instant, mon objectif n'est pas "le mieux", simplement de comprendre comment faire de ce code-ci quelque chose qui compile et s'exécute...
    Cela dit, merci pour la référence, que je regarderai.
    EDIT je viens de jeter un coup d'oeil, ça a l'air très intéressant et tout à fait en rapport. Re-merci.

  6. #6
    Membre Expert
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 34
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Par défaut
    Et un peu de documentation sur la fonction que je te propose (histoire de comprendre pourquoi elle va bien avec la conception choisie ) :
    std::uninitialized_fill()

    Et pour le constructeur de recopie :
    std::uninitialized_copy()


    Dans le papier que je t'es passé il détail pourquoi c'est le choix le plus efficace et pourquoi faire autrement peut conduire a des catastrophes. (il en parle au début dans une 'implémentation naive' du constructeur )

Discussions similaires

  1. [VBA-E] Enregistrer la feuille d'un template dans un nouveau doc
    Par titouille dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 08/04/2007, 07h52
  2. copier une feuille dans un nouveau doc excel
    Par alkmehd dans le forum Access
    Réponses: 1
    Dernier message: 24/09/2005, 11h01
  3. [template et linker]problème dans le main
    Par Andu dans le forum C++
    Réponses: 19
    Dernier message: 27/06/2005, 17h47
  4. donée de plusieur vecteur dans une structure ??
    Par lipczynski dans le forum C++
    Réponses: 5
    Dernier message: 13/08/2004, 08h17

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo