FAQ

Algorithmique

nombres de Fibonacci

Une programmation récursive basée naïvement sur la récurrence F_n+2 = F_n+1 + F_n conduit à un temps de calcul exponentiel. Une programmation itérative permet facilement d'obtenir un temps de calcul linéaire. L'utilisation des formules de convolution perment d'atteindre un temps de calcul logarithmique (cf. programme calcul des nombres de Fibonacci).

algorithmes de tri

Parmi les algorithmes de tri les plus simples se trouvent le tri par sélection et le tri par insertion. Ces deux algorithmes s'exécutent en temps quadratique O(n²). Le tri rapide est en temps O(n log n) en moyenne et en temps quadratique dans le cas le pire. Il est le plus rapide dans la pratique et il est implémenté dans les systèmes Unix. Les tri par tas et tri fusion sont aussi en temps O(n log n). Ce dernier est utilisé pour trier des grosses quantités de données.

Interpolation linéaire

Programme pour calculer la valeur prise par l'interpolation d'une fonction en un point x. La fonction f est donnée par une suite x₁, …, x_n de points et la suite f(x₁), …, f(x_n) des valeurs de f en ces points. L'indice i tel que x_i ⩽ x < x_i+1 est recherché par dichotomie en temps logarithmique.

Concepts

polymorphisme

le polymorphisme est le fait que le même code se comporte différemment suivant le type des objets qu'il manipule. Ceci est matérialise en C++ par l'intermédiaire de la surchage, de l'héritage et des méthodes virtuelles et de la programmation générique.

encapsulation

L'encapsulation consiste à cacher certains détails secondaires. Ceci se matérialise en C++ par la partie publique et la partie privée des classes. Seule la partie publique est utile à l'utilisation de la classe.

pointeur intelligent (smart pointer)

C'est un objet qui se comporte comme un pointeur avec des fonctionnalités de gestion mémoire en plus. Les pointeurs intelligents se chargent de la libération de l'espace mémoire réferencé et évitent ainsi les fuites de mémoire. Les trois classes géneriques unique_ptr<T>, shared_ptr<T> et weak_ptr<T>, ajoutées avec C++11, fournissent différentes variantes de pointeurs intelligents (cf. code). Une utilisation classique d'un pointeur intelligent est d'assurer la libération d'un objet créé dynamiquement dans une fonction.

void fun() {
  // Allocation d'un objet de type A confié au pointeur intelligent sp
  unique_ptr<A> sp(new A());
  ...
  // Utilisation de l'objet par l'intermédiaire de sp
     *sp
  ...
  // La destruction de la variable sp libère l'objet de type A
}

surcharge

C'est le fait que plusieurs fonctions puissent avoir le même nom. En C++, elles doivent se distinguer par leurs listes de paramètres c'est-à-dire le nombre de paramètres ou les types de ceux-ci.

// Maximum de deux entiers
int max(int m, int n) { return m > n ? m : n; }

// Maximum de trois entiers
int max(int m, int n, int p) { 
  return m > n ? (m > p ? m : p) : (n > p ? n : p); 
}

// Maximum de deux flottants
float max(float x, float y) { return x > y ? x : y; }

// Programme principal
int main() {
  cout << max(2, 3) << endl;
  cout << max(2, 4, 3) << endl;
  cout << max(2.3, 3.2) << endl;
}

Technique C++

méthodes fournies par le compilateur

Les méthodes suivantes sont fournies par le compilateur à la création d'une classe A.

• le construteur par défaut A() si aucun autre constructeur n'est défini dans la classe. Ce constructeur ne fait rien.
• le destructeur par défaut ~A() s'il n'est pas défini dans la classe. Ce destructeur ne fait rien.
• le constructeur de copie A(const A&) s'il n'est pas défini dans la classe. Ce constructeur copie tous les attributs, soit directement pour les types primitifs comme int ou float, soit en utilisant le constructeur de copie pour les classes. Si de plus, la classe hérite de classes de base, les constructeurs de copie de ces classes sont appelés avant de copier les attributs.
• l'opérateur d'affectation A& operator=(const A&) s'il n'est pas défini dans la classe. Cet opérateur copie tous les attributs, soit directement pour les types primitifs comme int ou float, soit en utilisant l'opérateur d'affectation pour les classes. Si de plus, la classe hérite de classes de base, les opérateurs d'affectation de ces classes sont appelés avant de copier les attributs.

// Classe avec toutes les méthodes fournies par défaut
class A { private: int v; };

// Utilisation du constructeur de copie pour initialiser le paramètre
A fun(A a) {
  return a;     // Utilisation du constructeur de copie
}               // pour copier la valeur de retour

int main() {
  A a;          // Utilisation du constructeur par défaut
  A b = a;      // Utilisation du constructeur de copie
  b = a;        // Utilisation de l'opérateur d'affectation
  b = fun(a);   // Utilisations multiples
  // Utilisation du destructeur par défaut pour détruire a et b
}

Depuis la version C++11, il y aussi les méthodes suivantes.

• le constructeur de déplacement A(const A&&) s'il n'est pas défini dans la classe. Ce constructeur déplace tous les attributs
• l'opérateur de déplacement A& operator=(const A&&) s'il n'est pas défini dans la classe. Cet opérateur déplace tous les attributs

Principe d'amitié

Normalement, les méthodes d'une classe ne peuvent accéder aux membres privés et protégées d'une autre classe. Si une classe F ou une méthode f sont déclarées amies par une classe A, elles peuvent accéder aux membres privés ou protégées de A.

class A {
  friend class F;               // Classe F déclarée amie de la classe A
public:
  A(int v) : val(v) {}          // Constructeur
  int get() { return val; }     // Méthode publique de A accédant à l'attribut privé val de A
private:                        
  int val;                      // Attribut privé de A
};

class F {
public:
  F(int v) : val(v) {}          // Constructeur 
  // Utilisation normale d'une méthode publique de A
  int get(A a) { return val = a.get(); }
  // Accès à un attribut privé de A
  void set(A& a) { a.val = val; }
private:
  int val;
};
  
int main() {
  A a(-1);
  F f(1);
  f.set(a);
  cout << a.get() << endl;
}

mutable

mutable est un mot clé qui permet de qualifier un attribut d'une classe. L'attribut devient alors modifiable même par une méthode appliquée à un objet constant.

class A {
public:                 // Méthode applicable à un objet constant
  void change() const { m++; }
private:
  int n = 0;            // Attribut non modifiable par change
  mutable int m = 0;    // Attribut modifiale
};

int main() {
  const A a;            // Object constant
  a.change();
}

méthode virtuelle

Une méthode virtuelle est une méthode pour laquelle le choix de la méthode appelée se fait à l'exécution en fonction du type de l'objet sur laquelle elle est appelée. Cela s'oppose aux méthodes non virtuelles pour lesquelles le choix est fait à la compilation en fonction du type statique de la variable (cf. code).

class B {               // Classe de base
public: 
  // Méthode non virtuelle
  void nprint() { cout << "B" << endl; }
  // Méthode virtuelle
  virtual void vprint() { cout << "B" << endl; }
};

class D : public B {    // Classe dérivée
public: 
  // Redéfinition de la méthode non virtuelle
  void nprint() { cout << "D" << endl; }
  // Redéfinition de la méthode virtuelle
  void vprint() { cout << "D" << endl; }
};

// Appel des deux méthodes nprint et vprint sur un objet
void print(B& b) { b.nprint(); b.vprint(); }

int main() {
  B b;                  // Objet de type B
  D d;                  // Objet de type D
  print(b);             // Affiche B et B
  print(d);             // Affiche B et D
}

Destructeur virtuel pur

Il est possible de définir une classe avec un destructeur virtuel pur. Ceci signifie que le destructeur est virtuel et qu'en outre le destructeur n'est pas défini.

class B {               // Classe de base
public:
  virtual ~B() = 0;     // Destructeur virtuel pur
};

Le problème est qu'une telle classe B ne peut pas être utilisée. D'une part, elle ne peut pas être instanciée car son destructeur est virtuel. D'autre part, toute classe qui dérive directement ou non de B ne peut pas être instanciée non plus car son destructeur doit appeler le destructeur de sa classe de base qui n'existe pas. Pour que B ou une classe dérivée de B puissent être instanciée, il est possible d'ajouter une définition par défaut du destructeur tout en le laissant virtuel pur.

B::~B() { ... }

Dans ce cas, le fait d'être virtuel pur pour le destructeur n'a plus d'intérêt car un destructeur n'est pas hérité par une classe dérivée.

Mise en œuvre du polymorphisme (méthodes virtuelles)

L'implémentation des méthodes virtuelles et de la liaison tardive, c'est-à-dire du choix de la méthode à appeler lors de l'exécution, est généralement faite par l'intermédiaire de table de pointeurs de fonctions appelées vtable. Chaque objet d'une classe ayant au moins une méthode virtuelle contient, en plus, un pointeur vers une table. Cette table contient des pointeurs vers les méthodes virtuelles de la classe. Cette table est partagée par tous les objets de la classe.