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

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.

Ecrire et tester les fonctions d'insertion et de deletion en position quelconque de liste:

• iterator insert(iterator,int), insère avant l'itérateur.
• iterator erase(iterator), efface l'élement pointé par l'itérateur.

Tri a bulle

Soit la classe foncteur suivante:

class Compare {
  public:
    bool operator() ( int& lhs, int& rhs );
};

Ecrire le corps de la fonction de tri à bulle en ne faisant appel qu'aux itérateurs.

void sort ( Vector::iterator begin, Vector::iterator end, Compare );