template, allocator et vecteur dans le nouveau Stroustrup

Version imprimable

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:

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:

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
}
 
//------------------------------------------------------------------------------

23/04/2009, 19h04
Goten

Humm, à mon avis il attend que tu utilises std::uninitialized_fill();

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

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:

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.

24/04/2009, 11h47
Goten

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
24/04/2009, 12h33
ptyxs

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.
24/04/2009, 12h40
Goten

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 ;) )

Oui j'ai regardé. J'ai ajouté un constructeur :

Code:

1
2
3
4
5
6
template<class T, class A>
vector<T,A>::vector(int n, const T& val, const A& a)
      :vector_base<T,A>(a,n)
{
  std::uninitialized_fill(this->elem,(this->elem)+n,val);
}

et un

Code:

1
2
3
4
int main()
{
    vector<int,allocator<int> > v(10);
}

ce qui donne au total :

Code:

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
#include <memory>
//------------------------------------------------------------------------------
 
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(): elem(0), sz(0), space(0) {}
  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:
    explicit vector(int n, const T& val = T(), const A& a = A());
 
 
    void reserve(int newalloc);
};
 
//------------------------------------------------------------------------------
 
template<class T, class A>
vector<T,A>::vector(int n, const T& val, const A& a)
      :vector_base<T,A>(a,n)
{
  std::uninitialized_fill(this->elem,(this->elem)+n,val);
}
 
//------------------------------------------------------------------------------
 
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
}
 
//------------------------------------------------------------------------------
 
int main()
{
    vector<int,allocator<int> > v(10);
}
 
//------------------------------------------------------------------------------

mais à la compilation j'ai ceci :

Code:

1
2
3
4
5
cassian@tux-laptop:~/Programmes/C++/stroustrup/Chapter19$ g++  essai2.cpp
essai2.cpp: In constructor ‘vector_base<T, A>::vector_base(const A&, int) [with T = int, A = allocator<int>]’:
essai2.cpp:54:   instantiated from ‘vector<T, A>::vector(int, const T&, const A&) [with T = int, A = allocator<int>]’
essai2.cpp:75:   instantiated from here
essai2.cpp:30: erreur: passing ‘const allocator<int>’ as ‘this’ argument of ‘T* allocator<T>::allocate(int) [with T = int]’ discards qualifiers

message qui me laisse perplexe...