Changes between Version 1 and Version 2 of 2010CaoTme1

Timestamp:

Feb 19, 2010, 1:23:07 AM (15 years ago)

Author:

jpc

Comment:

--

2010CaoTme1

@@ -1 @@
-= Objets simples en C++ =
 
+= Mon Premier Objet en C++ =
+
+== La Classe Vector ==
+
+L'objectif de la classe {{{vector}}} est de fournir des objets se comportants de
+façon identiques aux tableaux C, mais avec l'avantage d'une gestion transparente
+de l'allocation mémoire. Dans le cadre de ce TME, nous travaillerons sur un
+tableau d'entier.
+
+=== Construction ===
+
+Un {{{Vector}}} devra pouvoir être construit à partir de rien (il sera vide)
+ou à partir d'un tableau C ordinaire. On fournira aussi une implémentation
+du constructeur par copie.
+
+{{{
+  int  ordered[] = { 0, 1, 2, 3, 5 };
+  Vector v1 ( ordered, 5 );
+}}}
+
+En plus des construct
+ 
+=== Stratégie d'allocation mémoire ===
+
+Plutôt que d'allouer un tableau sous-jacent de la taille exacte du nombre des
+éléments contenus, le {{{Vector}}} réserve à l'avance de l'espace libre.
+Ceci afin de limiter le nombre d'opérations de réallocation ainsi que de
+trop fragmenter la mémoire.
+
+Nous sommes donc amenés à distinguer deux quantitées:
+ * Le nombres d'élements réellement utilisés du {{{Vector}}}, ce nombre sera
+   indiqué par la méthode {{{size()}}}.
+ * Le nombres d'élements que peut contenir le {{{Vector}}} ''sans avoir à être
+   ré-alloué''. Nombre indiqué par la méthode {{{capacity()}}}.
+
+Le tableau sous-jacent du {{{Vector}}} aura une taille strictement croissante.
+Il se ré-allouera dans des zones mémoires de plus en plus grandes.
+
+  '''Attention:''' lors d'une ré-allocation, la zone mémoire précédemment occupée
+  doit être libérée, ainsi qu'a la destuction de l'objet.
+
+La taille du vecteur doublera (sur un multiple de 2) à chaque réallocation. Ce qui
+revient à dire qu'un {{{Vector}}} ne pourra avoir que des tailles de: 0, 1, 2, 4, 8,
+16, 32, 64, ...
+
+Cas particulier: si l'on connaît la taille ''à priori'' du vecteur, on dispose d'une
+méthode {{{resize(size_t)}}} pour le dimensionner directement à la bonne taille.
+
+L'allocation mémoire sera gérée grâce aux deux méthodes privées suivantes:
+ * {{{_resize(size_t)}}}, assure la ré-allocation pour n'importe quelle capacité,
+   ne fait rien si on demande une diminition de celle-çi. Dans ce dernier cas,
+   on affichera le message d'avertissement suivant:
+     {{{[WARNING] Vector::_resize() cowardly refusing to shrink (16 to 7)}}}
+ * {{{_growPolicy(size_t newcapacity)}}}, calcule la nouvelle capacité nécessaire pour
+   pouvoir stocker {{{newcapacity}}}.
+ 
+=== Ajout, retrait et accès aux éléments ===
+
+Dans un premier temps, l'ajout et le retrait d'élément se fera uniquement en fin
+de tableau avec les méthodes suivantes:
+ * {{{void  push_back(int)}}}, ajoute un élément.
+ * {{{int   pop_back()}}}, renvoie et retire le dernier élément. Dans le cas ou le {{{Vector}}}
+   est vide, afficher le message suivant:
+     {{{[ERROR] Vector::pop_back(): vector is empty."}}}
+
+L'accès aux éléments se fera par l'intermédiaire de l'opérateur d'accès indexé.
+Si l'index est hors borne, afficher le message:
+  {{{[ERROR] Vector::operator[](): Index 12 is out of bound (10)"}}}
+
+=== Identificateur ===
+
+On désire, de plus marquer chaque {{{Vector}}} avec un identificateur unique,
+proposer une mécanique. La méthode {{{size_t id()} renverra l'identificateur
+du vecteur.
+
+=== Affichage d'un {{{Vector}}} dans un flot de sortie ===
+
+Ajouter la mécanique nécessaire à l'affichage d'un vecteur dans un flot. On désire
+obtenir l'affichage suivant:
+  {{{<Vector id:0 5/8 [0 1 2 3 5]>}}}
+Ou les informations sont respectivement, l'indentificateur du vecteur, le nombre
+d'élements actuellement contenus, la capacité puis les valeurs des éléments.
+ 
+=== Echange du contenu de deux {{{Vector}}} ===
+
+On réalisera une fonction {{{void swap(Vector&)}}} qui échangera le contenu de deux
+vecteurs. Astuce: comment utiliser cette fonction pour libérer la mémoire occupée
+par un vecteur?
+
+=== Petit Programme de test ===
+
+{{{
+#include <iostream>
+using namespace std;
+
+#include "Vector.h"
+
+int main ( int argc, char* argv[] )
+{
+  int  ordered[] = { 0, 1, 2, 3, 5 };
+  Vector v1 ( ordered, 5 );
+
+  cout << "v1[0] = " << v1[0] << endl;
+  cout << "v1[5] = " << v1[5] << endl;
+  cout << "v1 " << v1 << endl;
+
+  Vector v2;
+  v2.reserve ( 5 );
+  for ( size_t i=0 ; i<5 ; ++i ) v2.push_back ( 4-i );
+  cout << "v2 " << v2 << endl;
+  v2.push_back ( 5 );
+  cout << "v2 " << v2 << endl;
+  for ( size_t i=0 ; i<8 ; ++i ) v2.pop_back ();
+  cout << "v2 " << v2 << endl;
+
+  cout << "Number of allocated vectors:" << Vector::getMaxId() << endl;
+
+  return 0;
+}
+}}}
+
+
+== Iterateur ==
+
+En première approximation, un ''iterateur'' (ou {{iterator}}) est une classe
+conçue de façon à imiter le comportement d'un pointeur.
+
+La classe {{{iterator}} comportera deux membres:
+ * {{{_vector}}}, le vecteur auquel il se rapporte. Peut être {{{NULL}} s'il n'est
+   apparié à aucun {{{Vector}}}
+ * {{{_index}}}, l'élement actuellement pointé dans le vecteur. Si l'itérateur est
+   invalide, on renverra le message suivant:
+     [ERROR] Vector::iterator::operator*(): invalid iterator.
+
+La class {{{Vector}}} s'enrichi alors de deux méthodes supplémentaires:
+ * {{{iterator begin()}}}, renvoie un iterateur sur le premier élément du
+   vecteur.
+ * {{{iterator end()}}}, renvoie un iterateur pointant sur un élement situé
+   ''virtuellement'' après le dernier élément du vecteur.
+
+Considérant le code suivant:
+{{{
+  Vector::iterator it  = v1.begin ();
+  Vector::iterator end = v1.end   ();
+
+  cout << "v1:";
+  for ( ; it != end ; ++it ) {
+    cout << " " << *it;
+  }
+  cout << endl;
+
+  it  = v1.begin();
+  it += 3;
+  cout << "iterator begin()+3 on v1: " << *it << endl;
+  while ( not v1.empty() ) v1.pop_back ();
+  cout << "iterator begin()+3 on v1: " << *it << endl;
+}}}
+Ecrire le code des itérateurs de vecteurs.
+
+=== Classes imbriqués ===
+
+Il est possible d'imbriquer une classe dans une autre, mise en pratique dans le
+cas d'un itérateur:
+{{{
+class Vector {
+  public:
+    class Iterator {
+       public:
+         Iterator ( Vector* v=NULL, size_t index=0 );
+    };
+  // ...
+};
+
+Vector::Iterator::Iterator ( Vector* v, size_t index )
+{ }
+}}}
+
+Il faut simplement répéter le préfix {{{Vector::}}} devant les définitions des
+fonctions membres à l'extérieur de la classe.