\documentclass[a4paper,10pt,twoside]{scrreprt}
%\usepackage[mag=1440]{geometry}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage{listings}
\usepackage{tikz}
\usepackage{fancyhdr}



\pagestyle{fancy}
\fancyhf{}
%\newcommand{\partmark}[1]{\markboth{Partie~\Roman{part}:\hspace{1em} #1}{}}
%\renewcommand{\chaptermark}[1]{\markboth{Chap. \thechapter\hspace{1em} #1}}
%\renewcommand{\sectionmark}[1]{\markright{\S \thesection\hspace{1em} #1}}
\fancyhead[RE]{{page \thepage\hspace{2em}}}
\fancyhead[LE]{{\small\sffamily\nouppercase{\leftmark}}}
%\fancyhead[RE,LO]{}
\fancyhead[LO]{{\hspace{2em}page \thepage}}
\fancyhead[RO]{{\small\sffamily\nouppercase{Introduction au
     \texttt{C++} par Kévin Santugini}}}
%\fancyhead[LO]{{\small\sffamily\nouppercase{\rightmark}}}



\usetikzlibrary{arrows}

\addtolength{\oddsidemargin}{-3.5em}
\addtolength{\evensidemargin}{-7em}
\addtolength{\textwidth}{6em}
\title{Introduction au C++}
\author{Kévin Santugini}
\date{1\ier{} septembre 2011}

\lowertitleback{%
  © Copyright 2011 par Kévin Santugini

  \noindent
  Cette \oe{}uvre est mise à disposition sous licence Attribution -
  Partage dans les Mêmes Conditions 3.0 France. 
  Pour voir une copie de cette licence, visitez
  http://creativecommons.org/licenses/by-sa/3.0/fr/ ou 
  écrivez à Creative Commons, 444 Castro Street, Suite 900, Mountain View, California, 94041, USA.
}


\begin{document}
\lstset{language=c++,identifierstyle=\ttfamily}
\renewcommand{\labelitemi}{\textbullet}
\maketitle
\begin{abstract}
Ce document constitue une ``courte introduction''
au langage C++, langage dérivé du \texttt{C} 
et conçu par Bjarne Stroustrup dans les années 80.
Le \texttt{C++} a été standardisé officiellement en 1998.
Un nouveau standard a été adopté en 2011. Dans ce polycopié,
nous traitons le standard 1998, le standard 2011 est encore trop
récent et les compilateurs ne sont pas encore prêts.

Il n'est pas strictement nécessaire de connaître le \texttt{C}
pour apprendre le \texttt{C++}. Cependant, une certaine familiarité 
avec le \texttt{C} et en particulier avec sa syntaxe \og{}déconcertante\fg{} 
de déclaration de types peut être utile. En effet, on ne programme pas 
en \texttt{C++} comme on programme en \texttt{C}. Le moindre programme
en \texttt{C}, un tant soit peu complexe, réclame l'utilisation manuelle 
de l'allocation dynamique, même pour des opérations courantes
comme la gestion de chaînes de caractères. Ceci peut être très souvent 
évité en \texttt{C++}.


Le langage \texttt{C++} tout en étant compatible à 99\% avec le \texttt{C} 
ajoute énormément de fonctionnalités. Le \texttt{C} est avant tout un 
langage procédural. Le \texttt{C++} est un langage supportant.
\begin{enumerate}
\item La programmation procédurale.
\item La programmation modulaire.
\item La programmation orientée objet.
\item La programmation générique.
\end{enumerate}

Certains principes de base ont guidé la conception du \texttt{C++}:
\begin{itemize}
\item Aussi compatible que possible avec le \texttt{C} mais pas plus.
\item \og{}zero-overhead principle\fg{}: les fonctionnalités non utilisées
ne doivent pas induire de perte de performance. 
\item \og{}le programmeur sait ce qu'il fait\fg{},
principe hérité du \texttt{C} qui veut que l'on ne restreigne pas
excessivement ce que le programmeur a le droit de faire. Aussi connu
comme \og{}Si le langage empêche le programmeur de faire quelque chose de
stupide, il l'empêche aussi de faire quelque chose de très intelligent\fg{}.
\end{itemize}
\end{abstract}




\tableofcontents

\chapter{Généralités sur la programmation}
Pour programmer, il est utile de connaître quelques généralités
trop peu souvent expliquées car \og{}allant de soi\fg{}. Leur 
méconnaissance peut donner lieu à de désagréables surprises.

\section{Du fichier source à l'exécutable}
Les programmes informatiques sont écrits dans un langage informatique.
La plupart de ces langages ne sont pas compréhensible directement
par la machine\footnote{Il est possible
d'écrire un exécutable directement avec un éditeur hexadécimal 
mais ce n'est guère recommandé.}. Pour pouvoir utiliser le programme,
l'exécuter, il faut soit le compiler soit l'interpréter.

\subsection{La compilation}
La compilation est l'opération qui consiste à
traduire un fichier source, \textit{i.e.} un fichier contenant le
programme dans un format humainement lisible, 
en un exécutable qui lui, contient le programme sous une forme
directement utilisable par la machine. Cette opération est effectuée par 
un compilateur. 

Une fois créé l'exécutable, le compilateur n'est plus nécessaire au
déroulement du programme. 

\subsection{L'interprétation}
Une autre possibilité d'exécuter un programme est de l'interpréter.
Un interpréteur exécute le programme au moment même où il lit
le source. Contrairement à ce qui se passe
pour la compilation, l'interpréteur est nécessaire chaque fois 
que l'on souhaite utiliser le programme. Il est plus performant
de compiler un programme que de l'interpréter. 

\subsection{Langages interprétés et langages compilés} 
Rien n'empêche en théorie de créer à la fois un interpréteur
et un compilateur pour un même langage. Cependant, dans la pratique,
la plupart des langages sont soit utilisés avec un compilateur
soit avec un interpréteur. C'est pourquoi on parle le plus souvent
de langages compilés et de langages interprétés. 

Le C++ est un langage compilé. Nous nous concentrerons sur les langages
compilés pour le reste de ce chapitre. En particulier,
nous nous concentrerons sur cette question, primordiale en 
\texttt{C++} \textbf{qu'est-ce qui doit-être
connu au moment de la compilation et qu'est ce qui peut attendre
l'exécution?}

\section{Le typage}
\subsection{Qu'est ce que le typage ?}
Imaginons deux variables $x$ et $y$ flottants stockées sur 32 bits
ainsi que deux variables entières $m$ et $n$ elles aussi stockées 
sur 32 bits. Supposons que les représentations binaires
de $x$ et de $n$ soient identiques et que les représentations
binaires de $y$ et de $m$ soient aussi identiques alors 
il n'est pas vrai en général que les représentations binaires de 
$x+y$ et de $m+n$
soient aussi identiques. L'addition flottante et l'addition
entière sont des opérations différentes sur la machine. Cependant,
dans la plupart des langages, ces opérations sont représentées
par le même opérateur $+$. C'est au moment de la compilation, 
suivant le type de chaque variable que le compilateur 
décide de traduire l'opération $+$ par l'opération
machine appropriée.

Outre cette facilité de programmation, un autre intérêt du typage
est de permettre au compilateur de repérer un certain nombre
d'erreurs: un compilateur signalera des opérations entre
des types incompatibles. Par exemple, un compilateur détectera
et vous avertira si par mégarde vous avez programmer une opération
n'ayant aucun sens comme la division d'un entier par une chaîne de caractères.


Des exemples courants de types sont 
\begin{itemize}
\item booléen
\item nombre entier
\item nombre flottant
\item caractère
\item chaîne de caractères
\end{itemize}
La liste est loin d'être exhaustive. Il serait d'ailleurs
illusoire d'essayer d'en établir une.


\subsection{Langages non typés}
Dans un langage non typé, c'est au programmeur
de se rappeler ce que représente chaque variable, et même de
combien d'octets une variable occupe. Parmi les langages non typés, 
on compte l'assembleur.

\subsection{Typage statique et typage dynamique}
Dans un langage compilé, si le typage est dynamique: 
chaque variable contient au moment de l'exécution 
son type de manière explicite. Cela signifie qu'il est 
possible de modifier son type en cours d'exécution
et que le type d'une variable n'a pas à être connu
au moment de la compilation. 

Si le typage est statique, toute information sur le typage aura disparu
après la compilation. À chaque ligne du code source, 
il est impératif que \textbf{le type d'une 
variable soit connu au moment de la compilation}. 
On ne peut pas changer le type d'une variable en cours d'exécution 
dans un langage statiquement typé. 

Cette dernière condition apparemment anodine rend la programmation dans
un langage statiquement typé plus contraignante.  En contrepartie, un langage statiquement typé sera plus performant.

\subsection{Typage explicite et typage implicite}
Suivant le langage, le typage peut être explicite ou implicite.
Dans un langage implicite, le type d'une variable peut être
 déduit lors de sa première apparition à gauche du signe assignation.
C'est très courant pour les langages interprétés et beaucoup moins 
pour les langages langages compilés\footnote{En FORTRAN, le typage est implicite par défaut, je ne connais pas d'autres exemples de langages 
compilés avec un typage implicite.}.

\subsection{Typage et \texttt{C++}}
Le \texttt{C++} est un langage statiquement typé. Cela rend possible
une meilleure performance lors de l'exécution mais en contrepartie les
langages statiquement typés peuvent être plus délicats à programmer.


\section{La compilation séparée et l'édition de liens}
Un grand programme sera avantageusement écrit en plusieurs fichiers.
Si un compilateur devait relire chaque fichier 
source avant de créer l'exécutable chaque fois que l'on modifie
un seul fichier source,  la \textbf{compilation}
serait une opération prohibitivement coûteuse. Heureusement,
certains langages supportent ce qu'on appelle la compilation séparée:
chaque fichier source peut être compilé séparément en un fichier
objet. Une seconde opération appelée \textbf{édition de liens} permet
alors de regrouper tous les fichiers objets en un seul exécutable. 
Voir figure~\ref{fig:CompilationSeparee}. L'édition de lien est une opération beaucoup moins
coûteuse que la compilation. Il est donc beaucoup plus rapide
d'éditer les liens de plusieurs fichiers objets que de compiler l'ensemble 
des fichiers sources d'un coup. 

\begin{figure}
\begin{center}
\begin{tikzpicture}
\draw (4,0) rectangle (7,1);
\node at (5.5,0.5)  {Exécutable}; 

\draw (0,3) rectangle (3,6.5);
\node at (1.5,5) {Code objet 1}; 
\node at (1.5,3.5) {\texttt{file1.o}}; 
\draw (4,3) rectangle (7,6.5);
\node at (5.5,5) {Code objet 2}; 
\node at (5.5,3.5) {\texttt{file2.o}}; 
\draw (8,3) rectangle (11,6.5);
\node at (9.5,5) {Code objet 3}; 
\node at (9.5,3.5) {\texttt{file3.o}}; 

\draw[<-, line width= 2pt] (5,1) -- (1.5 ,3);
\draw[<-, line width= 2pt] (5.5,1) -- (5.5 ,3);
\draw[<-, line width= 2pt] (6,1) -- (9.5 ,3);


\draw (0,8) rectangle (3,11.5);
\node at (1.5,10) {Code source 1}; 
\node at (1.5,8.5) {\texttt{file1.cc}}; 
\draw (4,8) rectangle (7,11.5);
\node at (5.5,10) {Code source 2}; 
\node at (5.5,8.5) {\texttt{file2.cc}}; 
\draw (8,8) rectangle (11,11.5);
\node at (9.5,10) {Code source 3}; 
\node at (9.5,8.5) {\texttt{file3.cc}}; 


\draw[<-, line width= 2pt] (1.5,6.5) -- (1.5 ,8);
\draw[<-, line width= 2pt] (5.5,6.5) -- (5.5 ,8);
\draw[<-, line width= 2pt] (9.5,6.5) -- (9.5 ,8);

\node at (5.5,2) {\huge Édition de liens};

\node at (1.5,7.25) {\Large Compilation};
\node at (5.5,7.25) {\Large Compilation};
\node at (9.5,7.25) {\Large Compilation};
\end{tikzpicture}
\caption{Du source à l'exécutable: compilation séparée}\label{fig:CompilationSeparee}
\end{center}
\end{figure}

\section{Dans quelle catégorie se situe le \texttt{C++}}
Comme son prédecesseur le \texttt{C}, le \texttt{C++} est un langage compilé 
statiquement typé. Le typage est explicite: chaque variable doit 
être préalablement déclarée avant toute 
utilisation. Le typage est cependant rendu plus souple par 
l'existence de nombreuses
conversions implicites entre types. Il est par exemple possible
d'ajouter un entier et un flottant sans convertir explicitemet
l'entier en flottant.



\chapter{Les bases en \texttt{C++}}
Le langage \texttt{C++} est constitué de deux parties: le langage
proprement dit \og{}core\fg{} et sa bibliothèque standard.
Un principe de départ du \texttt{C++} était de ne pas alourdir 
le langage \og{}core\fg{} et de déléguer au maximum les 
fonctionnalités à la bibliothèque standard.
En particulier, le \texttt{C++} ne définit pas un type 
\og{}chaîne de caractères\fg{}\footnote{Si on ne 
compte pas le \lstinline$char*$ hérité du \texttt{C}.}:
mais sa bibliothèque standard en fournit une. 

\section{Mes premiers programmes en C++}
Nous allons commencer par donner quelques exemples
de programmes écrits en \texttt{C++}.
\subsection{Un programme qui ne fait rien ou presque}
\begin{lstlisting}
/*Mon premier programme*/
int main () 
{
  return(0); //L'unique instruction du programme
}
\end{lstlisting}
Ceci définit un programme ne faisant rien et qui retourne
$0$. En voici l'analyse détaillée.

Tout se qui se trouve entre les caractères
\lstinline$/*$  et \lstinline$*/$ 
est ignoré par le compilateur
et constitue donc un commentaire\footnote{Pour la lisibilité d'un programme, il est important 
de commenter son code. Cependant, il ne faut pas prendre 
les commentaires de ce polycopié comme des exemples de bon commentaires
pour un code réel. Ceux de ce polycopié ont pour but d'expliquer la signification
d'une fonctionnalité du \texttt{C++}. Dans un code réel, il ne faut pas
mettre de commentaires qui expliquent ce qui est évident en regardant le code.
Par exemple, 
\lstinline$x=0; //x vaut maintenant 0$
ne servirait à rien dans un code réel.}. Il en va de même 
pour tout ce qui se trouve entre un \og{}//\fg{} et un retour
à la ligne. 

La ligne \lstinline$int main ()$ déclare une fonction 
\lstinline$main$ retournant un entier (\lstinline$int$) et ne prenant aucun 
argument: la liste des arguments qui se trouve entre la parenthèse 
ouvrante et la parenthèse fermante est vide. Le corps de la fonction
\lstinline$main$ est située entre \lstinline ${$ et \lstinline$}$. Il 
contient pour seule instruction \lstinline$return(0)$. L'instruction \lstinline$return$ est
utilisée pour spécifier la valeur de retour, \textit{i.e}
le résultat, de la fonction.
 
La fonction \lstinline$main$ est toujours la première fonction appelée
dans un programme \texttt{C++}. Dans un programme \texttt{C++}, 
il doit toujours y avoir une et une seule fonction appelée
\lstinline$main$. C'est ce qu'on appelle le point d'entrée du programme.
\textit{A contrario}, il ne doit jamais y avoir de fonction
\lstinline$main$ dans une bibliothèque. 

\subsection{Le programme Bonjour}\label{subsect:Bonjour}
Donnons un exemple très légèrement plus compliqué.
\begin{lstlisting}
/* Mon premier programme qui fait quelque chose */
#include <iostream>
int main () 
{
  std::cout << "Bonjour\n";
  return(0);
}
\end{lstlisting}
Ce programme sort \og{}Bonjour\fg{} sur la sortie standard
qui est la sortie à l'écran en mode texte.

À la première ligne du programme, on observe l'instruction
\lstinline$#include<iostream>$. Moralement\footnote{Cette directive
  \lstinline$#include$ est en réalité très primitive, il ne s'agit ni
  plus ni moins que d'une inclusion textuelle caractère par caractère
  du fichier \texttt{iostream} effectuée par le préprocesseur avant la
compilation proprement dite. Un mécanisme moins primitif, dit de modules,
est prévu dans un addendum au \texttt{C++} 2011.}, cette ligne sert 
à charger les fonctions d'entrée sorties
de la bibliothèque standard: en effet, il n'y a pas d'instruction
d'entrée sortie dans le langage c\oe{}ur du \texttt{C++}. 


Le signe \og{}\lstinline$\n$\fg{} 
est le code pour indiquer un retour à la ligne dans une chaîne de caractères. 
Le guillemet double \lstinline$"$ marque à la fois le début et la fin d'une chaîne de caractères.
La variable \lstinline$std::cout$ est déclarée dans le fichier 
\lstinline$iostream$\footnote{iostream est un header}:
elle correspond à la sortie standard. Le \lstinline$<<$ est 
l'opérateur de sortie\footnote{il s'agit là d'une addition de la bibliothèque
standard, dans le langage \texttt{C++} \og{}core\fg{}, les opérateurs
\lstinline{<<} et \lstinline{>>} sont des opérateurs
de \og{}bit shifting\fg{}.}.
Par exemple,
\begin{lstlisting}
/* Exemple d'utilisation de l'opérateur d'output */
#include <iostream>
int main () 
{
  std::cout << "2*3=" << 6 << "\n";
  return(0);
}
\end{lstlisting}
Lors de l'exécution, le programme sort:
\begin{lstlisting}
2*3=6
\end{lstlisting}
Pour des programmes plus compliqués, nous aurons besoin
d'utiliser des variables.


\section{Types prédéfinis, variables}
Comme dans presque tout langage, le \texttt{C++} permet de
définir des variables et de modifier leur valeur au cours du programme.

Voici un exemple simple de programme où intervient des variables:
\begin{lstlisting}
#include <iostream>
int main()
{
  int d;
  std::cin >> d;
  std::cout << 2*d;
  return(0);
}
\end{lstlisting}
On déclare une variable entière puis on lit dans cette variable la valeur
de l'entier entré au clavier (entrée standard). 
Enfin, on imprime à l'écran (sortie standard) le double de cette 
valeur. L'opérateur \lstinline$>>$ est symétrique de l'opérateur \lstinline$<<$.
Le premier est utilisé pour l'entrée des données à partir d'un flux 
(ici \lstinline$std::cin$), le second
représente l'envoi de donnée dans un flux (ici \lstinline$std::cout$). 


\subsection{Déclaration}
En \texttt{C++}, les variables doivent être explicitement déclarées
avant leur première utilisation.  
Voici quelques déclarations simples de variables.
\begin{lstlisting}
int n; 			// n : entier signé
long m; 		// m :  entier long signé
short s; 		// s : entier court signé
unsigned int u;		// u : entier non signé
unsigned long ul;	// ul : entier long non signé
unsigned short us;	// us : entier court non signé

signed char sc 		// sc : caractère signé
unsigned char sc 	// sc : caractère non signé
char c 			// c  : caractère, on ne sait 
			// pas s'il est signé ou non.

float a;        // a : nombre flottant simple précision
double b;       // b : nombre flottant double précision
long double x;  // x : nombre flottant de précision 
		//     au moins double

bool l; // l est un booléen
\end{lstlisting}
Il s'agit là de tous les types simples prédéfinis en \texttt{C++}. 

On peut aussi initialiser les variables au moment de leur déclaration:
\begin{lstlisting}
bool b1= true;
bool b2= false;

int a = 0;
int b = a;

char c ='a'; 	// 'a' est un caractère;
		// "a" est une chaîne de caractère.

float x=1.0;
float y= 1.4e-2;
\end{lstlisting}
\lstinline$true$, \lstinline$false$, \lstinline$1.0$, \lstinline$0$, 
\lstinline$'a'$ et \lstinline$1.4e-2$ sont 
ce que l'on appelle des littéraux: \textit{i.e.} 
une suite de caractères qui représente une valeur fixe d'un type donné.
En \texttt{C++98}, un littéral représente forcément un type prédéfini.

Voici un autre programme légèrement plus utile
\begin{lstlisting}
#include <iostream>
#include <string>
int main ()
{
  std::string mon_prenom;
  std::cout << "Entrez votre prénom\n";
  std::cin >> mon_prenom;
  std::cout << "Bonjour, " << mon_prenom << "\n";
}    
\end{lstlisting}
Ici, nous introduisons un autre type \lstinline$std::string$ qui est le
type de chaîne de caractères défini par la bibliothèque standard.
Ce n'est pas un type prédéfini du \texttt{C++}.
Le préfixe \lstinline$std::$ indique que le type string à utiliser
est celui défini dans la bibliothèque standard\footnote{\lstinline$std$ 
est un namespace. C'est celui réservé pour la bibliothèque standard. 
Nous reparlerons des namespaces plus loin.}. 

Vous vous demandez peut-être quel est le type du littéral
chaîne de caractère "Bonjour". En effet, cela ne peut être
\lstinline$std::string$ car ce dernier type n'est pas un type de
base mais un type défini par la bibliothèque standard. 
Le type de "Bonjour" est un \lstinline$char*$, pointeur\footnote{
Ce pointeur pointe vers une région de la mémoire qui contient 
le premier caractère de la chaîne, les caractères suivants de 
la chaîne se trouvent derrière dans la mémoire. La fin d'une 
chaîne de caractères est indiqué par le caractère ayant la 
valeur \lstinline$0$ (et non \lstinline$'0'$).}
sur un caractère. Mais peu importe car la conversion 
vers \lstinline$std::string$
est implicite. Et les opérations sur \lstinline$std::string$
sont beaucoup plus faciles à utiliser que les vieilles fonctions
sur les \lstinline$char*$ héritées du \texttt{C}.

\subsection{L'assignation}
Après qu'une variable a été déclarée, on peut lui assigner
d'autres valeurs. Le signe pour l'assignation en \texttt{C++}
est le \lstinline$=$. Supposons que les variables
\lstinline$a$ et \lstinline$b$ aient préalablement été 
déclarées comme entières.
\begin{lstlisting}
a=0.0; // a vaut maintenant 0.0
b=1.0; // b vaut maintenant 1.0
b=a;   //b vaut maintenant 1.0
\end{lstlisting}

On peut assigner un entier à un flottant directement.
La conversion est implicite (il ne s'agit pas d'une assignation bit
par bit):
\begin{lstlisting}
float x=0.0;
int a = 2;
x=a; //x vaut maintenant 2.0
\end{lstlisting}

\section{Fonctions}\label{sect:fonctions}
Dans un programme réel, on ne met pas tout
son code dans la fonction \lstinline$main$, qui nous le rappelons
constitue le point d'entrée du programme. Il est recommandé de séparer
son code en fonctions.

\subsection{Définition et appel de fonctions}
Voici un exemple de fonction
qui écrit \og{}Bonjour\fg{} à l'écran:
\begin{lstlisting}
void print_Bonjour(void) 
{
  std::cout << "Bonjour\n";
}
\end{lstlisting}
Cette fonction ne retourne aucune valeur: c'est indiqué par
le mot-clef \lstinline$void$ devant le nom de la fonction.
Elle ne prend aussi aucun argument, c'est indiqué par le 
\lstinline$void$\footnote{Le \lstinline$void$ entre
les parenthèses n'est nullement nécessaire, 
\lstinline$void print_Bonjour()$ aurait eu la même signification
en \texttt{C++} mais pas en \texttt{C}.} entre parenthèses.

On peut alors écrire une fonction \lstinline$main$
qui appelle cette fonction:
\begin{lstlisting}
int main()
{
  print_Bonjour();// Appel de fonction indiqué par ()
  return(0);
}
\end{lstlisting}


La définition d'une fonction a la forme générale:
\begin{lstlisting}
typeretour nomfonction (type1 arg1, type2 arg2)
{
  Corps de la fonction (instructions,...)
}
\end{lstlisting}
Le nombre d'arguments étant évidemment libre, ici $2$
n'est qu'un exemple.

Pour appeler une fonction, il suffit d'écrire son nom puis de placer
entre parenthèse les arguments:
\begin{lstlisting}
/* A l'interieur d'une autre fonction */
  nomfonction(val1,val2); //nomfonction est appelé avec
                          //val1 et val2 comme arguments
/* Reste du code*/
\end{lstlisting}
Bien entendu, le compilateur va vérifier que  \lstinline$val1$ et
\lstinline$val2$ sont compatibles avec les types \lstinline$type1$ et \lstinline$type2$.

\subsection{Valeur de retour et \lstinline$return$}
Nous avons vu que la fonction \lstinline$main$ contenait une
instruction \lstinline$return$. À quoi correspond cette instruction ?
C'est cette instruction qui spécifie la valeur de retour.

Certaines fonctions 
Voici un autre exemple de fonction 
 prenant en argument un flottant double précision et retournant un double:
\begin{lstlisting}
double square (double x)
{
  double machin = 1;
  machin = x*x;
  return(machin);
}
\end{lstlisting}
Le type situé sur la première lign avant le nom de la fonction est le
type de retour, \textit{i.e.}, le type du résultat de la fonction. Ce
qu'il y a dans le \lstinline$return$ est la valeur de retour de la
fonction. Ici, \lstinline$machin$ est la valeur retournée. Cette
instruction est nécessaire pour que l'instruction
\begin{lstlisting}
double y = square(x);
\end{lstlisting}
ait le résultat escompté. Nous aurions aussi pu définir la fonction de
la manière suivante
\begin{lstlisting}
double square (double x)
{
  return(x*x);
}
\end{lstlisting}

Les novices en programmation et en \texttt{C++} confondent parfois deux opérations bien
distinctes: il est primordial de bien distinguer le concept de retour
d'une valeur et le concept d'affichage: le \lstinline$return$
n'affiche rien à l'écran, et les fonctions d'affichage de la
section~\ref{subsect:Bonjour} ne retournent rien à la fonction appelante.

\subsection{Le cas particulier de la fonction \lstinline$main$}
Par convention, la fonction \lstinline$main$ est le point d'entrée du
programme. Cela signifie qu'au moment de l'exécution d'un programme, 
la fonction \lstinline$main$ est la première fonction à être appelée\footnote{En
 toute rigueur, les variables globales sont initialisées avant l'appel
 à la fonction \lstinline$main$ mais laissons ce détail de côté.}. La fonction \lstinline$main$ doit avoir \lstinline$int$
comme type de retour. La fonction \lstinline$main$ peut prendre soit zéro argument,
soit deux arguments. Nous ne considérerons\footnote{L'étudiant
intéressé par l'autre cas pourra effectuer une recherche sur
\lstinline$argc$ et \lstinline$argv$.} que le cas où la fonction
\lstinline$main$ ne prend aucun argument en entrée. La fonction
\lstinline$main$  a pour forme
\begin{lstlisting}
int main()
{
/* Corps de la fonction */
return(0);
}
\end{lstlisting}
Vous vous demandez peut-être à quoi correspond la valeur de retour puisque la
fonction \lstinline$main$ ne sera jamais appelé par une autre
fonction. Quelle intérêt y a-t-il à retourner une valeur à la fonction
appelante s'il n'y a pas de fonction appelante. La réponse est que
cette valeur est retournée au système d'exploitation.

Pour la fonction \lstinline$main$ et \textbf{uniquement} pour la
fonction \lstinline$main$, la convention veut que la valeur de retour
est un code d'erreur retournée par le programme au système
d'exploitation. La valeur $0$ signifiant que le programme s'est arrêtée normalement
sans erreur. Rappelons le, cette convention ne vaut que pour la
fonction \lstinline$main$ et pour aucune autre fonction.


\subsection{Passage des arguments par valeurs ou par références}
Par défaut, les arguments d'une fonction sont passés par valeur:
\begin{lstlisting}
void valeur(int b)
{
  b=5;
}

int main()
{
  int a=3;
  valeur(a);
  std::cout << a <<'\n';
}
\end{lstlisting}

Compilons ce programme et exécutons le. Le nombre imprimé
est $3$! La fonction valeur n'a reçu en argument qu'une copie 
de  \lstinline$a$ 
et ne change que la valeur de cette copie.
Dans la fonction \lstinline$main$, la valeur de \lstinline$a$
ne change pas.

Il est cependant possible de passer les arguments par référence.
Pour cela, il suffit de rajouter \lstinline{&} dans le type
de l'argument
\begin{lstlisting}
void reference(int& b)
{
  b=5;
}

int main()
{
  int a=3;
  reference(a);
  std::cout << a <<'\n';
}
\end{lstlisting}
imprime $5$ à l'écran car le passage a eu lieu par référence.

Pour des considérations d'efficacité, on peut aussi passer par référence
de gros objets tout en déclarant que leur valeur ne doit pas être modifiée.
Pour cela on rajoute le mot-clef \lstinline{const} devant le type
de l'argument. Cela permet au compilateur de mieux vérifier  le code
et aide au débogage.
\begin{lstlisting}
void const_reference(const int& b)
{
  b=5;
}
\end{lstlisting}
provoque une erreur et un diagnostic à la compilation.
Cette forme est surtout utilisée pour passer un gros objet telle une matrice 
ou un conteneur: le passage par référence coûtera un petit nombre d'octets:
$4$ octets sur une machine $32$ bits, $8$ sur une $64$ bits.
En comparaison, le passage par valeur imposerait de recopier toute la matrice
ou tout le conteneur soit potentiellement plusieurs milliers
d'entiers.



\subsection{Surdéfinition des fonctions}
Il est possible en \texttt{C++} de surdéfinir les fonctions
avec des listes d'arguments différentes:
\begin{lstlisting}
int max(int, int);
double max(double, double);
\end{lstlisting}
déclare deux fonctions \lstinline$max$. Le choix de la bonne fonction
sera effectué par le compilateur:
\begin{lstlisting}
max(3.0,5.0); //max(double,double)
max(3,5);     //max(int,int)
max(3,5.0);   //max(double,double)
\end{lstlisting}
Le troisième choix a lieu en raison des règles de conversions 
implicites. Elles sont compliquées mais donnent en général 
ce que l'on souhaite.

\subsection{Prototypes de fonctions}\label{subsect:prototypes}
Le \texttt{C++} est un langage typé statiquement. Pour améliorer
la correction d'erreurs, le \texttt{C++} impose que toute
fonction soit déclarée avant son premier appel.
Il n'impose pas qu'elle soit déjà définie. La définition
peut apparaître plus tard ou même se trouver dans un autre  fichier.

En particulier, le programme suivant est malformée
\begin{lstlisting}
#include<iostream>
/* La fonction main est le point d'entrée du programme */
int main() 
{
  int n= max(1.0,2.0);//Erreur fonction max non déclarée à ce point
  return(0);
}

/*Définition de la fonction max */
int max(int a, int b)
{
  if(a<b) {
    return b;
  } else {
    return a;
  }
}
\end{lstlisting}
Pour remédier à ce problème, on peut soit placer la définition de la
fonction \lstinline$max$ avant celle de la fonction \lstinline$main$
ou déclarer sans la définir la fonction \lstinline$max$ avant le \lstinline$main$.
Voici comment déclarer la fonction \lstinline$max$:
\begin{lstlisting}
int max(int, int);// Noter le point virgule
\end{lstlisting}
C'est ce que l'on appelle un prototype de fonction. Il déclare une fonction
sans la définir. Il déclare ici qu'il existe une fonction 
\lstinline$max$ qui prend deux arguments de type \lstinline$int$
et qui retourne un \lstinline$int$. Pour rendre bien formé le programme
ci-dessus, il suffit de rajouter le prototype de la fonction
\lstinline$max$ avant le \lstinline$main$.


\section{Expressions}
Une expression est une instruction de type
\begin{lstlisting}
2*a+5;
2+3*4-2;
a<=5;
a==b;//comparaison d'égalité
\end{lstlisting}

\subsection{Expressions arithmétiques}
On compte en \texttt{C++} plusieurs opérations arithmétique.
Il y en a cinq binaires \lstinline$+$,
\lstinline$-$, \lstinline$*$, \lstinline$/$,
et le modulo \lstinline$%$. Il y a aussi deux opérateurs préfixes
unitaires, la négation \lstinline{-} et le \lstinline{+} qui ne fait
rien pour les types prédéfinis. Voici quelques exemples:
\begin{lstlisting}
-3+2*5;
1*2*3*4*5*6*7*8*9; // factorielle de 9
1+(2*4-5)*5-12;
-4*5+3;
\end{lstlisting}
Les expressions peuvent contenir des parenthèses et modifier
l'ordre de priorité des opérations. Pour les opérations 
arithmétiques, les priorités sont les priorités mathématiques
usuelles: les \lstinline$+$ et le \lstinline$-$ (négation) \textbf{unitaires}
sont prioritaires sur les opérateurs binaires \lstinline$*$ (multiplication),
\lstinline$/$ (division) et \lstinline$%$ (modulo) 
qui sont eux même prioritaires
sur les opérateurs binaires \lstinline$+$ (addition) et 
\lstinline$-$ (soustraction). L'assignation \lstinline$=$
a heureusement une priorité plus basse que celle de tous les
opérateurs arithmétiques.

Les expressions arithmétiques sont très
courantes dans le membre droit d'une assignation.
Voici l'exemple d'une itération de l'algorithme de Newton pour la 
fonction $x\mapsto x*x-3$ 
\begin{lstlisting}
x=x-(x*x-3)/(2*x);
\end{lstlisting}


\textbf{Remarquez qu'il n'y a pas d'opérateurs arithmétiques pour 
la puissance en \texttt{C++}}. Il faut utiliser la fonction 
\lstinline$std::pow$ de la bibliothèque standard\footnote{Pour pouvoir l'utiliser,
il faut d'abord inclure le header \lstinline$<cmath>$.}.

\subsection{Expressions relationnelles}
Les expressions relationnelles sont plutôt utilisées 
dans les conditions d'arrêt de boucle et dans les instructions 
\lstinline$if$ dont nous parlerons ultérieurement.
En effet, ces opérateurs retournent un booléen (type \lstinline$bool$)
qui vaut soit \lstinline$true$  soit \lstinline$false$.

Il y a six opérateurs relationnels binaires. 
Le test d'égalité \footnote{Ne pas confondre
avec l'assignation \lstinline$=$. C'est l'erreur classique du débutant.} \lstinline$==$, et le test d'inégalité
\lstinline$!=$ sont les deux premiers.
\begin{lstlisting}
5==5;      //vrai
5==6;      //faux
5!=6;      //vrai
5!=5;      //faux
int a = 4;
a==4;      //vrai
a!=4;      //faux
\end{lstlisting}

Quatre autres opérateurs relationnels existent:
le test inférieur strict \lstinline$<$,
le test supérieur strict  \lstinline$<$,
le test inférieur ou égale \lstinline$<=$ et
le test supérieur ou égale, opérateur \lstinline$>=$.
Voici quelques exemples d'utilisation:
\begin{lstlisting}
int a=3;	
int b=4;	
a<b;		//vrai
a>b;		//faux
a<=b;		//vrai
a>=b;		//faux
a<3;		//faux
a<=3;		//vrai
a>=3;		//vrai
\end{lstlisting}

L'exemple suivant imprime à l'écran si le nombre \lstinline$a$
est pair.
\begin{lstlisting}
int a;
...
std::cout << ((a%2)==0) << '\n';
\end{lstlisting}

\subsection{Expressions logiques}
Il y a 2 opérateurs logiques binaires:
le OU logique \lstinline$||$ et
le ET logique, opérateur \lstinline$&&$.
Et il y a un seul opérateur logique unitaire préfixe:
le NON logique, opérateur \lstinline$!$;
ce dernier est préfixe: \lstinline$!a$ vaut \lstinline$true$ si
\lstinline$a$ vaut \lstinline$false$ et inversement.
Voici quelque exemples:
\begin{lstlisting}
true||false;     //true
true ||true;     //true
true&&false;     //false
!true;           //false
!(false||false); //true
\end{lstlisting}

\subsection{Les assignations}
Nous avons déjà vu le symbole d'assignation \lstinline$=$.
Il y en a d'autres liés aux opérations arithmétiques:
\begin{lstlisting}
int a = 2; // a vaut 2
a+=4; // a vaut 6
a-=1; // a vaut 5
a*=8; // a vaut 40
a/=5; // a vaut 8
a/3;  // a vaut 2
\end{lstlisting}
Et enfin, il y a aussi les opérations \lstinline$++$
et \lstinline$--$  qui incrémentent et décrémentent
respectivement la valeur d'une variable.
\begin{lstlisting}
int i=0;
i++;     //i vaut 1
++i;     //i vaut 2
--i;     //i vaut 1
--i;     //i vaut 0
\end{lstlisting}

La différence entre les opérateurs \lstinline$--, ++$ préfixes
et postfixes est que pour les opérateurs préfixes, l'incrémentation
a lieu avant l'assignation alors que pour les opérateurs postfixes,
elle a lieu après.
\begin{lstlisting}
int i=0;
int b=4;
i=--b;   //i vaut 3, b vaut 3
i=b--;   //i vaut 3, b vaut 2
i=b++;   //i vaut 2, b vaut 3
i=++b;   //i vaut 4, b vaut 4
\end{lstlisting}

\section{Les structures de contrôle}
Comme dans tout langage de programmation\footnote{À l'exception
de l'assembleur}, \texttt{C++} propose des structures de contrôle.

\subsection{L'instruction if}
L'instruction \lstinline$if$ est la première structure de contrôle 
que nous étudierons en \texttt{C++}. Elle nous permettra de créer
des programmes plus intéressants.

L'instruction \lstinline$if$ s'emploie en général
avec des expressions relationnels et des expressions logiques.
La forme générale de la structure \lstinline$if$ est:
\begin{lstlisting}
if(condition) {
  //Ce qui se passe si condition est vrai.
} 
\end{lstlisting}
Voici un exemple:
\begin{lstlisting}
void simplesort(double& a, double& b) {
  if(b<a) {
    double tmp=a;
    a=b;
    b=a;
  }
}
\end{lstlisting}

Une instruction \lstinline$if$ peut aussi contenir des \lstinline{else}.
\begin{lstlisting}
if(condition) {
  //Ce qui se passe si condition est vrai.
} else {
  // Ce qui se passe sinon
}
\end{lstlisting}
et comme exemple une étape de dichotomie pour le sinus:
\begin{lstlisting}
double a=3;
double b=3.5;
double x=(a+b)/2;
if(sin(a)*sin(x)<0) {
  x=b;
} 
else {
  x=a;
}
x=(a+b)/2;
\end{lstlisting}
Naturellement, pour avoir une dichotomie complète, il est nécessaire
 de rajouter une boucle autour de ce code.

Nous pouvons aussi avoir des \lstinline$else if$ 
\begin{lstlisting}
if(condition1) {
  ...
} 
else if(condition2) {
  ...
} 
else if(condition3) {
  ...
}
else {
  ...
}
\end{lstlisting}

\subsection{Le switch}
Le switch est une forme plus efficace que 
\lstinline$if else if else if else if$.
Voici ce que l'on pourrait coder:
\begin{lstlisting}
double dynamic_operation (char c, double a, double b)
{
  double x;
  if(c=='+') {
    x=a+b; 
  }
  else if (c=='-') {
    x=a-b;
  }
  else if (c='/') {
    x=a/b;
  }
  else if (c='*') {
    x=a*b;
  }
  else {
    ...// Erreur
  }
  return x;
}
\end{lstlisting}
Il est cependant plus efficace d'utiliser un \lstinline$switch$:
\begin{lstlisting}
double dynamic_operation (char c, double a, double b)
{
  switch(c) {
  case '+':
    x=a+b;
    break; // break est nécessaire ici
  case '-':
    x=a-b;
    break; // break est nécessaire ici
  case '/':
    x=a/b;
    break; // break est nécessaire ici
  case '*':
    x=a*b;
    break; // break est nécessaire ici
  default:
     ... //Erreur
  }
  return x;
}
\end{lstlisting}
S'il n'y avait pas de \lstinline$break$, les instructions
dans les \lstinline$case$ qui suivent celui atteint seraient 
elles aussi exécutées!! Faîtes attention!

Les switch sont plus rapides que les \lstinline$if$ 
mais présentent un certain nombre 
de contraintes:
\begin{enumerate}
\item Seul des tests d'égalité peuvent être exécutés.
\item Seul un type prédéfini peut être testé.
\item Les valeurs de test (derrière \lstinline$case$)
doivent être constantes.
\end{enumerate}
C'est une volonté d'optimisation du code qui dicte ces contraintes,
cela rend le switch plus rapide que la série de 
\lstinline$if, else if, else if, else$ équivalente.

\subsection{La boucle \lstinline$while$}
La boucle \lstinline$while$ est la boucle la plus simple
en \texttt{C++}, sa syntaxe est
\begin{lstlisting}
while(condition) {
  // Instructions
}
\end{lstlisting}
Ce qui se trouve entre les accolades est appelée \og{}Corps de la boucle\fg{}.

Voici une boucle qui imprime les nombres de 
$1$ à $9$:
\begin{lstlisting}
int i=1;
while(i<=9) {
  std::cout << i << "\n";
  i++;
}
\end{lstlisting}
et maintenant une boucle de dichotomie
\begin{lstlisting}
double a=3;
double b=3.5;

while(abs(b-a)>1e-6) {
 if(sin(a)*sin(x)<0) {
  x=b;
 } 
 else {
   x=a;
 }
 x=(a+b)/2;
}
\end{lstlisting}

\subsection{La boucle \lstinline$do while$}
La boucle \lstinline$do while$ s'écrit
\begin{lstlisting}
do {
  // Instructions 
} while(condition)
\end{lstlisting}
Par rapport à une boucle \lstinline$while$, la différence est
que le corps de la boucle est assuré d'être exécuté 
au moins une fois.


\subsection{La boucle \lstinline$for$}
La boucle \lstinline$for$ est plus complète que la boucle 
\lstinline$while$. Sa forme générale est
\begin{lstlisting}
for(initialisation; condition ; executionfin) {
  //Corps de la boucle
}
\end{lstlisting}
qui équivaut\footnote{En toute rigueur, ce n'est que presque vrai. Il
  y a une petite nuance technique due à l'existence de l'instruction
  \lstinline$continue$ que nous n'abordons pas dans ce polycopié.} à
\begin{lstlisting}
initialisation
while(condition) {
  //Corps de la boucle
  Executionfin
}
\end{lstlisting}
Elle est surtout utilisée pour incrémenter des indices 
automatiquement
\begin{lstlisting}
int i;
for(i=0; i<10 ; i++) {
   std::cout << i << '\n';
}
// La variable i existe toujours
\end{lstlisting}
imprime les nombres de 0 à 9 à l'écran, tout comme
\begin{lstlisting}

for(int i=0; i<10 ; i++) {
   std::cout << i << '\n';
}
// La variable i n'existe plus
\end{lstlisting}

\section{Conclusion}
Dans ce chapitre, nous avons vu introduit les bases de syntaxe nécessaires
à la programmation en \texttt{C++}. Nous aborderons des sujets plus avancés
dans les chapitres ultérieurs.

\chapter{Les variables}
Dans ce chapitre, nous introduisons 
les types composés et définis par l'utilisateur. Ces types sont
construit à partir des types de base. Nous choisissons délibérément de ne pas introduire les
tableaux prédéfinies par le langage \texttt{C++}
et héritées du \texttt{C}: utilisez \lstinline$std::vector$ 
de la STL à la place, voir le chapitre~\ref{chap:conteneurs}.

Nous nous attardons ensuite sur la notion 
de durée de vie d'une variable: où dans un programme
une variable est-elle accessible ?


\section{Les pointeurs}
Les types peuvent être composés. 
En particulier, il est possible de déclarer des pointeurs
\begin{lstlisting}
int* p;   // p est un pointeur sur un entier.
float* q; // q est un pointeur sur un 
          // flottant simple précision.
\end{lstlisting}
Un pointeur est une variable contenant l'adresse d'une autre variable.
Le contenu du pointeur \lstinline$q$ est alors accédé par 
\lstinline$*q$ et l'adresse
d'une variable \lstinline$x$ est accédé par \lstinline$&x$:
\begin{lstlisting}
float  x=1.0; // x vaut 1.0
float  y=2.0; // y vaut 2.0
float *q;
q=&x;   // q pointe maintenant vers la variable x;
*q=3.0; // x vaut 3.0
q=&y;   // q pointe maintenant vers la variable y;
*q=4.0;   // y vaut maintenant 4.0
x=*q;   // x vaut maintenant 3.0
\end{lstlisting}
L'opérateur unitaire préfixe\lstinline$*$  est appelé opérateur
de déréférencement.

Un pointeur ayant la valeur nulle ne pointe vers aucune zone mémoire
et le déréférencement du pointeur nul donne toujours lieu à un
\og{}segmentation fault\fg{}. Le pointeur nul a pour nom
\lstinline$NULL$ en \texttt{C}, \lstinline$0$ en \texttt{C++98}
et \lstinline$nullptr$ en \texttt{C++2011}.

En \texttt{C} et en \texttt{C++}, il est possible de faire de
l'arithmétique sur les pointeurs. Si \lstinline$T$ est un type
quelconque alors les opérations suivante sont syntactiquement correctes.
\begin{lstlisting}
T* p;
// Initialisation de p ...
*p;     // Contenu pointé par p
p[0];
*(p+1);  // Contenu à l'adresse mémoire p+taillememoire(T)
p[1];  // Contenu à l'adresse mémoire p+taillememoire(T)
\end{lstlisting}
Ces opérations prennent en compte la taille mémoire de l'objet \lstinline$T$.
Attention, c'est dangereux, il faut vraiment savoir ce que l'on fait
pour utiliser l'arithmétique sur les pointeurs.

\section{Les références}
Les références ressemblent aux pointeurs. 
\begin{lstlisting}
int   x=1;   
int   y=3;   
int&  r=x; // r est une référence vers x
r=2;       // x vaut maintenant 2
r=y;       // x vaut maintenant 3
	   // r reste une référence sur x
           // r ne devient pas une référence sur y
r=0;       // x vaut maintenant 0
           // y reste inchangé
\end{lstlisting}
Une façon de voir les références est de les imaginer comme des pointeurs
constants pointant toujours vers la même variable
et qui sont automatiquement déréférencés par le compilateur. Un autre
façon de voir les références est de considérer qu'une référence n'est
en réalité qu'un alias pour une autre variable. L'association d'une
référence à une variable donnée ne peut avoir lieu que lors de
l'initialisation de la référence. Les références sont principalement utilisées 
pour spécifier que le passage d'arguments à une fonction doit être fait par référence.


\section{Les structures}\label{sect:structures}
Les structures sont l'ancêtre des classes, voir chapitre~\ref{chap:classes}. Ce sont
des types contenant plusieurs variables de types différent. Elles sont
définis en utilisant le mot-clef \lstinline$struct$.
\begin{lstlisting}
struct point {
  double x; //x est le premier membre de point
  double y; //y est le deuxième membre de point
};
\end{lstlisting}
Les sous-variables d'une structure sont communément appelées ses
membres. Ici, la structure \lstinline$point$ a deux membres:
\lstinline$x$ et \lstinline $y$. Cela signifie que chaque variable du
type \lstinline$point$ contiendra exactement deux double.

Pour déclarer une variable de type \lstinline$point$, on utilise la
même syntaxe que pour les types prédéfinis:
\begin{lstlisting} 
point A; //A est un point 
A.x=5.0;   //Le membre x de A vaut 5.0 
A.y=3;   //Le membre y de A vaut 3.0
\end{lstlisting} 
et on a construit le point $A$ du plan de coordonnées $(5,3)$.
L'opérateur \og{}\lstinline$.$\fg{} est l'opérateur de sélection
en \texttt{C++}. On peut aussi déclarer un pointeur sur une
structure:
\begin{lstlisting}
point A;
point* q; 
q=&A;
*q.x=3.0;   // erreur: *(q.x) et non (*q).x
(*q).x=4.0;   // OK mais lourd en parenthèses
q->x=5;   // équivaut à (*q).x=5
\end{lstlisting}
Il faut alors soit mettre des parenthèses soit
utiliser l'opérateur de sélection \lstinline$->$
pour les pointeurs sur les structures. 

Si on souhaite définir le type plus tard, on peut 
se contenter de déclarer la structure sans la définir:
\begin{lstlisting}
struct point A; // Structure A déclarée mais non définie.
\end{lstlisting}

Dans une structure, on peut uniquement  avoir des membres 
dont le type est déjà défini, y compris 
d'autres structures. Par exemple, une fois la structure
\lstinline$point$ définie, on peut définir
la structure \lstinline$triangle$:
\begin{lstlisting}
struct triangle {
  point A;
  point B;
  point C;
};
\end{lstlisting} 

Par contre, une structure ne peut être récursive, on ne peut déclarer 
un membre dont le type n'est pas complètement défini. Cette contrainte 
provient du typage statique qui impose que le compilateur connaisse la taille
en octets des types. Il est par contre possible de placer des pointeurs 
vers des structures qui ne sont que déclarées. En effet, la taille
d'un pointeur ou d'une référence est fixe: $4$ octets sur les machines $32$ bits et $8$ octets
sur la machines $64$ bits.  Par exemple,
\begin{lstlisting}
struct recursive {
  recursive next; //Illégal recursive n'est pas encore définie
  recursive* opt; //Légal recursive est déclarée
  recursive& up; //Légal recursive est déclarée
};
\end{lstlisting}



\section{Pointeurs sur des fonctions}
Il est possible en \texttt{C++} de manipuler 
des pointeurs sur des fonctions. Cela peut être utile par
exemple pour l'algorithme de la dichotomie
que l'on ne souhaite pas réécrire chaque fois qu'on l'applique 
à une nouvelle fonction.

Voici une déclaration de pointeur sur une fonction.
\begin{lstlisting}
double (*f) (double);
\end{lstlisting}

Et voici l'algorithme de la dichotomie
\begin{lstlisting}
double dichotomie(double (*f)(double) , double a, double b)
{
  double x=(a+b)/2.0;
  
  while(abs(b-a)>1e-6) {
    if((*f)(a)*(*f)(x)<0) {
      b=x;
    } else {
      a=x;
    }
    x=(a+b)/2.0;
  }
}
\end{lstlisting}
et comment on appelle dichotomie depuis une autre fonction:
\begin{lstlisting}
...
dichotomie(0,1, &fun);
...
\end{lstlisting}
où \lstinline$fun$ est une fonction qui prend un \lstinline$double$
en argument et qui retourne un \lstinline$double$.

\section{Déclarations compliquées}
Le \texttt{C++} a un système de déclaration assez compliqué
hérité du \texttt{C}. Voici quelques exemples de déclarations
compliquées
\begin{lstlisting}
/*pointeur sur un pointeur sur un char */
char** p; 

/* 
  pointeur sur une fonction prenant un entier 
  et un flottant comme argument et retournant 
  un pointeur sur un entier
*/
int* (*fun) (int, float); 

/* 
  fonction prenant un entier et un flottant comme 
  argument et retournant un pointeur sur un pointeur 
  sur un entier
*/
int** fun (int, float); 

/* Pointeur sur une fonction retournant un caractère 
  et prenant en argument un entier et un pointeur 
  sur une fonction ne prenant aucun argument et 
  retournant un caractère.
*/
char (*fun)( int, char (*)());
\end{lstlisting}

\section{Les typedefs}
La syntaxe compliquée de déclaration de type en \texttt{C++}
peut être simplifiée par l'utilisation du \lstinline$typedef$
qui permet de donner un alias, un synonyme à un type.
\begin{lstlisting}
typedef int Int; 
Int a; //a est un int;

typedef double (*fonctionreel)(double);

double dichotomie(double,double,fonctionreel);
\end{lstlisting}
Ce qui rend la définition de dichotomie plus lisible.
Un \lstinline$typedef$ créé un synonyme pour un type, il
ne créé pas de nouveau type:
\begin{lstlisting}
typedef int Int;
int a=0;
Int b=0;
/* a et b ont exactement le même type */
a=b;//Légal
b=a;//Légal
\end{lstlisting}

\section{Durée de vie d'une variable}
La durée de vie d'une variable, aussi appelée étendue(scope en
anglais) d'une variable est un concept très important. En effet, il
existe plusieurs types de variables qui se distinguent principalement
par leur étendues.

\subsection{Variables globales}
Une variable globale est une variable déclarée
à l'extérieur du corps d'une fonction. Elle existe dans tout le programme,
est accessible par toutes les fonctions et ne disparaît que lorsque
le programme s'arrête. Il est extrêmement tentant de rendre toutes 
les variables globales car cela semble rendre plus facile la programmation.
 Cependant c'est trompeur: cela rend le programme difficile à 
lire\footnote{Avoir un programme lisible est important, on code autant pour les autres programmeurs que pour le compilateur} et 
pratiquement impossible à maintenir. Pour cette raison, il est en général préférable d'éviter l'utilisation 
de variables globales. 

Pour définir une variable globale \lstinline$xglobal$ de type \lstinline$int$, on écrit 
\begin{lstlisting}
int xglobal;
\end{lstlisting}
à l'extérieur de toute fonction. Cette définition ne doit apparaître qu'une seule fois dans le programme. En effet,
sinon le compilateur réserverait plusieurs fois de la place mémoire pour la variable
\lstinline$xglobal$.

Pour que la variable soit accessible depuis les fonctions
définies en dehors du fichier, on doit la déclarer:
\begin{lstlisting}
extern int xglobal;
\end{lstlisting}
Le mot-clef \lstinline$extern$ indique qu'il s'agit là non d'une
définition mais d'une simple déclaration. De préférence, cette déclaration aura lieu dans un header. 

Nous voyons là la première nuance entre la notion de déclaration et la
notion de définition. Une déclaration indique au compilateur qu'une
variable ou un objet existe déjà mais ne demande pas au compilateur de
réserver de la place mémoire pour cette variable. Elle permet au
compilateur de vérifier que les opérations faites sur la variable sont
bien licites. Une définition au contraire demande au compilateur de
réserver de l'espace mémoire pour la variable. Aussi, une variable
globale ne doit être dédinie qu'une seule fois par programme. Par
contre, la même variable peut être déclarée autant de fois que l'on souhaite.

Une variable globale peut être déclarée \lstinline$static$.
Cela signifie qu'elle n'est accessible que par les fonctions
définies dans le même fichier. C'est une fonctionnalité considérée obsolète
et remplacée par les namespaces et notablement le namespace anonyme.

\subsection{Variables locales}
Une variable locale est une variable déclarée dans le corps d'une fonction.
Elle n'est accessible que depuis cette fonction dès sa déclaration
et disparaît une fois que l'on sort du plus petit 
bloc \lstinline${ }$ contenant la déclaration de la variable.
\begin{lstlisting}
if(condition) {
  int x=0;
} else {
  int x=1;
}
int b=x; //OOPS, x n'existe plus.
\end{lstlisting}


\begin{lstlisting}
int f (int)
{
  ...
  int x;
  {
    int y;
    ...
  }
// y cesse d'exister
// x existe toujours.
...
}
\end{lstlisting}

\subsection{Variables locales statiques}
Une variable déclarée dans le corps d'une fonction peut être déclarée statique:
\begin{lstlisting}
void f ()
{
  static int x=0;
  std::cout << x <<'\n';
  x=x+1;
}
\end{lstlisting}
Dans ce cas, la variable n'est accessible que dans la fonction où elle est déclarée mais la valeur de la variable statique sera conservée
entre les diverses exécutions de la fonction. Par exemple, l'instruction
\begin{lstlisting}
int i;
for(i=0;i<4;i++) {
  f();
}
\end{lstlisting}
affichera à l'écran
\begin{lstlisting}
0
1
2
3
\end{lstlisting}
Attention, la valeur de la variable \lstinline$x$ n'est conservée que
parce qu'elle a été déclarée \lstinline$static$.

\subsection{Les variables dynamiques}
Une variable dynamique est une variable explicitement allouée. Les variables 
dynamiques perdurent jusqu'à ce qu'elles soit explicitement 
desallouées par le programmeur.

Ces variables sont appelées dynamiques car l'espace mémoire nécessaire
à la conservation est réservée au cours de l'exécution
et non au cours de la compilation comme pour les autres variables 
(locales, globales et statiques). En particulier, cela permet
de créer des tableaux ou des matrices dont la taille change à 
chaque exécution du programme ce qui n'est pas possible sans recompilation
si on utilise des variables non dynamiques.

En \texttt{C++},
on alloue dynamiquement une variable avec l'opérateur \lstinline$new$
(qui remplace la fonction \lstinline$malloc$ du \texttt{C}). On 
désalloue dynamiquement avec l'opérateur \lstinline$delete$
\begin{lstlisting}
double* p;
double* q;
{
  double x;
  p = new double; // Alloue un seul double en mémoire dynamique.
  q = &x;
} // x cesse d'exister
*q = 1.0; // OOPS q pointe vers une variable qui a disparu
*p = 0.0; // OK
delete p;
*p = 1.0;  // OOPS *p a été effacé
\end{lstlisting}

On peut aussi allouer une grande quantité de mémoire d'un coup
avec les opérateurs \lstinline$new[]$ et \lstinline$delete[]$:
\begin{lstlisting}
double* p;
p= new double[100]; // Alloue 100 double
P[0] = 1.0;  //le premier double alloué
p[5] = 4.0; 
P[99] = 2.0; // le dernier double alloué 
delete[] p;     // Rend au système la région de 
		// mémoire précédemment allouée
\end{lstlisting}
Attention, l'opérateurs \lstinline$new[]$ n'initialise pas la zone mémoire à 0.0
pour les types prédéfinis. Il n'y a pas besoin de se rappeler 
combien de double ont été allouées pour faire un \lstinline$delete[]$
de toute la région: la taille de la région est conservée en mémoire
automatiquement. 

Un bug classique et difficile à corriger lorsque l'on alloue de la mémoire 
est la ``fuite de mémoire'': on alloue de la mémoire puis on oublie de la libérer(désallouer) quand on ne s'en sert plus . Plus le programme est destiné à tourner longtemps plus cette ``fuite'' s'aggrave et devient problématique. Un programme qui laisse fuire de la mémoire court le risque d'en allouer plus que le système ne peut en fournir et d'être arrêté d'office par le système (lors de l'arrêt d'un programme, la mémoire est de toute façon retournée au système).

L'allocation dynamique est à cantonner au code de 
bas-niveau\footnote{L'expression \og{}bas-niveau\fg{} est à prendre au
  sens code proche de la machine. À opposer à l'expression
  \og{}haut-niveau\fg{} qui signifie un code proche de l'abstraction
  idéaliséee de l'algorithme.}. 
En \texttt{C++}, on peut souvent éviter d'utiliser \textbf{directement} 
l'allocation dynamique en utilisant la bibliothèque standard, 
en particulier pour les chaînes de caractères et les conteneurs.





\chapter{Les conteneurs en C++: la STL}\label{chap:conteneurs}
Il est très important dans les programmes réels
d'avoir des conteneurs efficaces. Un conteneur
est un type qui contient plusieurs variables d'un même type. 
Le conteneur de base du
\texttt{C++} (hérité du C) est très primitif et nous choisissons
de ne pas en parler dans ce document. En effet, 
la bibliothèque standard contient la 
STL\footnote{Standard Template Library}, une bibliothèque de 
conteneurs très efficace. 


\section{Les tableaux}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\draw(0,0.3) rectangle (12,1.7);
\draw (2,0.3) -- (2,1.7);
\draw (4,0.3) -- (4,1.7);
\draw (6,0.3) -- (6,1.7);
\draw (8,0.3) -- (8,1.7);
\draw (10,0.3) -- (10,1.7);
\node at (1,1) {\lstinline$tab[0]$};
\node at (3,1) {\lstinline$tab[1]$};
\node at (5,1) {\lstinline$tab[2]$};
\node at (7,1) {\lstinline$tab[3]$};
\node at (9,1) {\lstinline$tab[4]$};
\node at (11,1) {\lstinline$tab[5]$};
\end{tikzpicture}
\end{center}
\caption{Stockage machine d'un tableau}\label{fig:tableau}
\end{figure}
Un tableau est un type qui contient un certain
nombre de variables du même type. Il est préférable
d'utiliser les tableaux fournies par la bibliothèque standard
à ceux héritées du \texttt{C}. Un tableau est simplement une région contiguë dans la mémoire
de l'ordinateur qui contient plusieurs variables du même type,  voir figure~\ref{fig:tableau}.


Voici un exemple d'utilisation:
\begin{lstlisting}
std::vector<int> x(20);     // Un tableau de 20 entiers
for(int i=0;i<20;i++) {
  x[i]=i*i;
}
x.size() ; // retourne la taille du tableau x;
x.resize(40) ; // Le tableau contient 40 éléments.
x.resize(10) ; // Le tableau est tronquée
\end{lstlisting}
Attention l'accès aux valeurs d'un tableau par \lstinline$x[i]$
ne vérifie pas si on déborde ou non du tableau. Pour un accès moins rapide
mais sûre qui vérifie les bornes du tableau,
utiliser \lstinline$x.at(i)$

\begin{lstlisting}
std::vector<std::string> S; // un tableau vide de chaînes
                            // de caractères
std::string s;
do {
  std::cin >>s;   // Ligne d'entrée à l'écran dans s;
  S.push_back(s); // Rajoute s en fin de tableau. 
		  // La taille du tableau augmente de $1$.
} while (s!="\n");
  
sort(s.begin(),s.end()); 
                  // Chaînes triées par ordre alphabétique.

for(int i=0; i<S.size(); ++i) {
  std::cout << "Bonjour " << S[i] << '\n';
}
\end{lstlisting}
Lorsque l'on utilise 
\lstinline$push_back()$il est possible que le tableau 
devienne trop grand
et ne tienne plus dans la région mémoire allouée
il sera déplacée automatiquement dans une région où il y a suffisamment 
de place. Pour un grand tableau, cela peut-être très coûteux.


En \texttt{C++}, on peut simplement déclarer un tableau de \lstinline$T$
par \lstinline$std::vector<T>$
\begin{lstlisting}
#include <vector>
std::vector<int>    tableaudentiers;
std::vector<float>  tableaudeflottants;  
\end{lstlisting}
Et nous avons respectivement un tableau d'entiers 
et un tableau de flottants. On peut mettre presque
n'importe quel type entre \lstinline$<$
et \lstinline$>$. La clef d'un \lstinline$std::vector$
ne peut alors qu'être un entier.

\begin{lstlisting}
std::vector<double> a;          // a a pour taille 0
std::vector<double> b(3);       // b a pour taille 3
			// et chaque élément vaut 0.0	
std::vector<double> c(4, 1.0);  // c a pour taille 4
			// et chaque élément vaut 1.0

a.size(); // retourne la taille de a;
a[2]=5.0 ;   // assigne 5.0 au troisième élément de a
a[0]=5.0 ;   // assigne 5.0 au premier élément de a
a.at(2)=5.0; // pareil mais vérification que a.size()<=3.
a.push_back(3.0); // rajoute 3.0 à la fin de a
\end{lstlisting}
Quand un tableau devient trop grand (après des 
\lstinline$push_back()$), il faut le déplacer.
Cela est fait automatiquement mais cela prend 
du temps. En effet, il risque de ne pas
y avoir de place dans la mémoire après le tableau pour 
les nouveaux éléments. Pour éviter cela, on peut
réserver de la place:
\begin{lstlisting}
a.reserve(100); // réserve 100 places
a.capacity(); // retourne la capacité du tableau a
\end{lstlisting}
Il ne faut pas confondre la capacité et la taille d'un tableau.
Les tableaux sont efficaces pour l'accès aléatoire mais l'insertion
coûte chère sauf en fin de tableau s'il y a assez de réserve.

\section{Les listes}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\draw(0,0) rectangle (3,3);
\draw (0,1) -- (3,1);
\draw (0,2) -- (3,2);
\node at (1.5,0.5) {\lstinline$Lien* next$};
\draw[->] (3,0.5) -- (3.5,0.5) -- (3.5,3.5) -- (5.5,3.5) -- (5.5,3);
\node at (1.5,1.5) {\lstinline$Lien* prev=0$};
\node at (1.5,2.5) {\lstinline$T Valeur$};


\draw(4.5,0) rectangle (7.5,3);
\draw (4.5,1) -- (7.5,1);
\draw (4.5,2) -- (7.5,2);
\node at (6,0.5) {\lstinline$Lien* next$};
\draw[->] (7.5,0.5) -- (8,0.5) -- (8,3.5) -- (10,3.5) -- (10,3);
\node at (6,1.5) {\lstinline$Lien* prev$};
\draw[->] (4.5,1.5) -- (4,1.5) -- (4,4) -- (2,4) -- (2,3);
\node at (6,2.5) {\lstinline$T Valeur$};

\draw(9,0) rectangle (12,3);
\draw (9,1) -- (12,1);
\draw (9,2) -- (12,2);
\node at (10.5,0.5) {\lstinline$Lien* next=0$};
\node at (10.5,1.5) {\lstinline$Lien* prev$};
\draw[->] (9,1.5) -- (8.5,1.5) -- (8.5,4) -- (6.5,4) -- (6.5,3);
\node at (10.5,2.5) {\lstinline$T Valeur$};

\draw (4.5,5) rectangle (7.5,7);
\draw (4.5,6) -- (7.5,6);
\node at (6, 6.5) {\lstinline$Lien* head$};
\draw [->](4.5,6.5) -- (1,6.5) -- (1,3);
\node at (6, 5.5) {\lstinline$Lien* tail$};
\draw [->](7.5,5.5) -- (11,5.5) -- (11,3);
\end{tikzpicture}
\end{center}
\caption{Stockage machine d'une liste}\label{fig:ListesLiens}
\end{figure}
Une liste est stockée de manière différente. Chaque élément
de la liste contient en plus de sa valeur des liens\footnote{Ce sont en général
des pointeurs, nous en parlerons ultérieurement}
vers les éléments précédents et suivants, voir figure~\ref{fig:ListesLiens}. La liste contient juste un accès
au premier et au dernier élément.
Pour déclarer une liste on utilise \lstinline$std::list<T>$ où $T$ est un type:
\begin{lstlisting}
std::list<int> listedentiers;
std::list<float> listedeflottants;
\end{lstlisting}
Comme pour un \lstinline$vector$, on peut mettre presque
n'importe quel type entre \lstinline$<$
et \lstinline$>$. Pour accéder aux éléments d'une liste,
on emploie un itérateur:
\begin{lstlisting}
std::list<int>::iterator p = listedentier.begin();
*p; // premier élément
p++;
p++;
*p; //troisième élément
p!=listedentier.end(); //Est-on en fin de la liste ?
\end{lstlisting}
Les listes sont très efficaces pour l'insertion
et la suppression d'éléments mais la recherche est coûteuse.



\section{Les arbres}
\begin{figure}
\begin{center}
  \begin{tikzpicture}[grow=down, level/.style={sibling distance=40mm/#1}]
    \node[rectangle,draw] {\lstinline$val["d"]$}
    child {
      node[rectangle,draw] {\lstinline$val["b"]$}
      child {
        node[rectangle,draw] {\lstinline$val["a"]$}
      }
      child {
        node[rectangle,draw] {\lstinline$val["c"]$}
      }
    }
    child{
      node[rectangle,draw] {\lstinline$val["f"]$}
      child {
        node[rectangle,draw] {\lstinline$val["e"]$}
      }
      child {
        node[rectangle,draw] {\lstinline$val["g"]$}
      }    
    };
\end{tikzpicture}
\end{center}
\caption{Un arbre equilibré indicé par des chaînes de caractères}\label{fig:arbres}
\end{figure}

Un arbre est une structure de données en informatique
où chaque élément contient un lien vers un ascendant
et deux liens (ou plus) vers des descendants, voir
figure~\ref{fig:arbres}. 
Si l'arbre est équilibré, la profondeur de l'arbre est environ $\log_2(N)$ où $N$ est le nombre
de noeuds. Si le type qui servira de clef 
que l'on souhaite mettre dans le conteneur a 
un ordre, il est possible de placer les valeurs dans l'arbre de manière 
ordonnée. La recherche dans un arbre ordonnée est proportionneul à la
profondeur de l'arbre qui s'il est équilibre est en $O(\log_2(N)$. Heureusement,
il existe des algorithmes pour maintenir un arbre ordonné équilibré
lors de l'insertion de nouveaux éléments. 

La complexité de toutes les opérations sur un arbre sera de
$O(\log_2(N)$. Des trois conteneurs vus ici, c'est le plus complexe à
programmer. Heureusement, nous n'avons pas à le faire car d'autres
l'ont fait pour nous. Il suffit d'utiliser les arbres fournis par la
bibliothèque standard.

Pour déclarer une variable de type arbre on utilise \lstinline$std::list<clef,T>$ où 
\lstinline$clef$
est un type avec un ordre et \lstinline$T$ est un type:
\begin{lstlisting}
std::map<std::string,int>   listedentiers;
std::map<std::string,float> listedeflottants;
listedentiers["ici"]=3;
int a= listedentiers["ici"];
\end{lstlisting}


\section{Conclusion}
Il faut bien se rappeler que la mémoire d'un ordinateur moderne est contiguë.
Cela rend les performances des conteneurs différentes: aucun des conteneurs n'est
optimal pour toutes les opérations. L'insertion dans une liste est rapide
mais la recherche est en temps linéaire. La recherche dans un tableau 
triée est rapide mais l'insertion est coûteuse en temps linéaire.
Pour un arbre, toutes les opérations sont en temps logarithmique.

Tous les conteneurs ne sont pas abordés dans ce chapitre. Nous avons
présenté les trois les plus courant. Il y en a bien d'autres. Parmi eux, on
peut citer les tableaux hashés\footnote{Introduits dans la bibliothèque
  standard en \texttt{C++2011} sous le nom \lstinline$unordered_map$.}.


\chapter{Programmation modulaire et organisation d'un programme}
Maintenant que nous avons vu les structures de contrôle et les
différents types de variables, nous allons pouvoir 
créer des programmes non triviaux. 

La plupart des codes créés lors de l'apprentissage d'un langage sont
courts et il n'y a pas besoin de les organiser pour qu'ils fonctionnent.
Cependant, il est courant que les codes industriels atteignent
$10000$ lignes de codes et même $100000$ lignes de code. Sans discipline et sans organisation,
autant de lignes de codes ne peuvent être maintenues. Il est donc
important de prendre de bonnes habitudes dès maintenant.

La programmation modulaire est  une façon d'organiser un code.
Dans la programmation modulaire, les fonctionnalités d'un programme
sont séparées en fonctions et les fonctions apparentés sont regroupées 
dans un même fichier, dans un même \lstinline$namespace$, voir
section~\ref{subsect:namespaces}
ou dans un même module. Les différents modules sont alors
aussi indépendant que  possible les uns des autres.  Pour cela, on 
utilise soit les namespaces, soit la séparation du code source en plusieurs 
fichiers.

Le support pour les modules eux-mêmes
ne viendra en \texttt{C++} que dans un addendum technique au
\texttt{C++2011}. Il faudra donc attendre encore quelques années. 
Il est cependant possible, dès à présent, de programmer modulairement avec
de la discipline en utilisant les headers, les namespaces et la directive
\lstinline$#include$. Pour l'instant, nous devons donc fabriquer les
headers à la main. Une fois l'addendum technique écrit et approuvé,
cela sera heureusement inutile. Malheureusement, il n'est pas encore
sorti à ce jour.

\section{Un court exemple}\label{sect:modulairecourtexemple}
Nous allons créer un court programme de calcul de la factorielle et
montrer comment on peut l'organiser. C'est une fonction mathématique,
elle ne posera pas beaucoup de problèmes informatiques. En effet,
les fonctions mathématiques simples sont parmi 
les plus simples à concevoir:
elles prennent un nombre fini et bien déterminé d'arguments, 
retourne un type bien déterminé,
et surtout n'ont pratiquement jamais besoin d'accéder à
une variable globale qui relate l'état d'un programme.

\subsection{Un code désorganisé}
Prenons l'exemple d'un programme qui calcule la factorielle d'un nombre 
entré au clavier. On peut facilement tout mettre dans la fonction
\lstinline$main$
\begin{lstlisting}[title={Fichier \texttt{main.cc}: Version \lstinline$main$ fourre tout}, frame=single]
int main ()
{
  unsigned int d;
  std::cout << "Entrez un entier : ";
  std::cin  >> d;

  unsigned int res=1;
  for(unsigned int i=1;i<=d;++i) {
    res*=i;
  }
 std::cout << res << "\n";
  return (0);
}
\end{lstlisting}
Comme le programme est court, cela ne pose pas de gros problèmes.
Mais une telle organisation deviendra un cauchemar pour les codes
grands de millions de lignes. C'est déjà beaucoup mieux. 
 
\subsection{Séparation en fonctions}
Une meilleure organisation est de séparer les 
le calcul de la factorielle de la gestion des entrées sorties. Nous allons
laisser la gestion des entrées sorties dans la fonction
\lstinline$main$
et placer le calcul de la factorielle dans la fonction \lstinline$factorielle$.
Voici le code complet dans un seul fichier
\begin{lstlisting}[title={Fichier \texttt{main.cc}: Version fonctions séparées}, frame=single]
/* Implémente la fonction factorielle avec une boucle*/
#include <iostream>
unsigned int factorielle (unsigned int n) 
{
  unsigned int res =1;
  for(int i=0;i<;i++) {
    res=res*i;
  }
  return(res);
}  

int main ()
{
  unsigned int d;
  std::cout << "Entrez un entier : ";
  std::cin  >> d;

  unsigned int res=factoriel(d);
  std::cout << res << "\n";
  return (0);
}
\end{lstlisting}
Cependant, il est préférable de séparer les 
fonctions non apparentées en plusieurs fichiers.


\subsection{Séparation en plusieurs fichiers}\label{subsect:ModulairePlusieursFichiers}
Le \texttt{C++}  est un langage à compilation séparée. Quand le
compilateur lit un fichier source, il n'a aucune idée de ce qui se
trouve dans les autres fichier sources. Aussi si dans 
\texttt{main.cc}, nous avons
\begin{lstlisting}[title={Fichier \texttt{main.cc}: Version erronée avec fichiers séparés}, frame=single]
#include<iostream>
/*Point d'entrée du programme*/
int main()
{
  unsigned int d;
  std::cout << "Entrez un entier : ";
  std::cin  >> d;

  unsigned int res=factorielle(d); // Erreur, le compilateur 
                                   // ne sait pas que factorielle
                                   // est une fonction.
  std::cout << res << "\n";
  return (0);
}
\end{lstlisting}
 et que la fonction \lstinline$factorielle$ est définie dans
 \texttt{maths.cc}:
\begin{lstlisting}[title={Fichier \texttt{maths.cc}: Version fichiers séparés}, frame=single]
unsigned int factorielle (unsigned int n) 
{
  unsigned int res =1;
  for(int i=0;i<;i++) {
    res=res*i;
  }
  return(res);
}
\end{lstlisting}
alors nous obtenons une erreur. En effet, le compilateur compile
séparément les fichiers \texttt{maths.cc} et \texttt{main.cc}. Quand
il compile le fichier \texttt{main.cc}, le compilateur n'a aucune idée
de ce qui se trouve dans \texttt{maths.cc}. 

Pour résoudre le problème, il suffit de rajouter le prototype,
voir section~\ref{subsect:prototypes}, de la fonction \lstinline$factorielle$
avant la fonction \lstinline$main$. Voici le nouveau fichier
\texttt{main.cc}:
\begin{lstlisting}[title={Fichier \texttt{main.cc}: Version correcte avec fichiers séparés}, frame=single]
#include<iostream>
/* Prototype de la fonction factorielle */
unsigned int factorielle(unsigned int);

/*Point d'entrée du programme*/ 
int main()
{
  unsigned int d;
  std::cout << "Entrez un entier : ";
  std::cin  >> d;

  unsigned int res=factorielle(d); // OK, grâce au prototype, le 
                                   // compilateur a suffisamment
                                   // d'informations pour valider
                                   // cette instruction
  std::cout << res << "\n";
  return (0);
}
\end{lstlisting}
C'est déjà mieux que la précédente organisation.

Cependant, rajouter les prototypes à la main de toutes les fonctions
appelées dans un fichier mais définies dans un autre fichier est non
seulement fastidieux mais aussi une potentielle source d'erreurs.
Pour remédier à ce problème, on utilise les headers.


\section{Les headers}
À chaque fichier source, correspond en général un header. Un header
est juste un autre fichier qui contient du code souce et qui est
destiné à être inclu par d'autres fichier de code source. Les headers
ont par convention une extension en \texttt{.h} ou \texttt{.hh}. Les
headers ne sont pas destinés à être compilés directement mais destinés à être inclu
textuellement dans une étape qui précède la compilation. 
Il y a deux écoles pour les
fichiers de headers: soit on créé un header unique fourre-tout pour
tout le programme, soit on en créé un par fichier source. 
Dans un header, on place ce que le compilateur doit savoir quand il
compile un autre fichier faisant appel aux fonctionnalité du (d'un
des) fichier source associé au header. Nous donnerons plus loin les
détails à la section~\ref{subsect:QuoiHeaders}. Les headers sont
nécessaires car le \texttt{C++} pratique la compilation séparée.

\subsection{Généralités sur les headers}
Nous avons déjà rencontré ces
headers, \lstinline$<iostream>$ et \lstinline$<cmath>$ sont des
headers. Ces headers interviennent par l'intermédiaire de la directive
\lstinline$#include#$. Ainsi au début d'un fichier source, on trouve
courramment cette directive:
\begin{lstlisting}
#include<iostream>
#include<cmath>
/* Reste du code */
\end{lstlisting}

Lors de la compilation, tout se passe comme si le contenu 
du fichier \texttt{iostream} et du fichier \texttt{cmath} était copié
collé à la place 
de \lstinline$#include<iostream>$ et de \lstinline$#include<cmath>$.
Moralement, si on veut utiliser les fonctions d'entrées sorties de la
bibliothèque standard, on rajoute la directive
\lstinline$#include<iostream>$
en début de fichier et si on souhaite utiliser le fonctions
mathématiques de la bibliothèque standard, on rajoute la la directive
\lstinline$#include<cmath>$
en début de fichier. On peut le voir comme  un mécanisme très primitif
de chargement d'un module.

En plus des headers standard, le programmeur peut créer ses propres
headers. À la différence des headers standard, les headers du
programmeur doivent, dans les directives \lstinline$#include$, être 
délimités par des guillemets doubles \lstinline$"$ et non des signes
d'inégalités \lstinline$< >$
\begin{lstlisting}
#include <headerstandard>
#include "headernonstandard"
\end{lstlisting}

Ces headers sont nécessaires. En effet, le \texttt{C++} compile séparément chacun des fichiers sources.
Une fonction \lstinline{main} définie dans un fichier \texttt{main.cc} 
peut avoir besoin d'appeler 
une autre fonction \lstinline{print_result} 
définie dans un autre fichier \texttt{output.cc}.
Pour pouvoir appeler cette fonction depuis \texttt{main.cc}, il faut que 
qu'elle ait été déclarée (prototypée) dans le fichier
\texttt{main.cc} avant son premier appel. 
Pour cela, le mieux est d'inclure
le header \texttt{output.h} où on aura préalablement 
prototypé toutes les fonctions
définies dans \texttt{output.cc}. 


Revenons maintenant à l'exemple de la
section~\ref{sect:modulairecourtexemple}.

\subsection{Création d'un header}
Dans l'exemple de la section~\ref{sect:modulairecourtexemple},
nous en étions à chercher un moyen d'éviter de réécrire à la main 
le prototype de la fonction \lstinline$factorielle$ dans le fichier 
\texttt{main.cc}. Pour cela, nous devons créer un header nous même.
Nous allons
créer un header \texttt{maths.h} contenant les prototypes, voir
section~\ref{subsect:prototypes}, de toutes les fonctions définies
dans \texttt{maths.cc}. Ici, nous aurons dans \texttt{maths.h}, le
prototype de la fonction \lstinline$factorielle$:
\begin{lstlisting}[title={Fichier \texttt{maths.h}: Version avec header}, frame=single]
unsigned int factorielle(unsigned int);
\end{lstlisting}

Même si ce n'est pas toujours nécessaire, il est préférable d'inclure
le header associé à un fichier source dans ce fichier source: cela
permet au compilateur de repérer certaines erreurs et de vous en avertir.  
\begin{lstlisting}[title={Fichier \texttt{maths.cc}: Version avec header}, frame=single]
#include "maths.h"
unsigned int factorielle (unsigned int n) 
{
  unsigned int res =1;
  for(int i=0;i<;i++) {
    res=res*i;
  }
  return(res);
}
\end{lstlisting}
Enfin, le fichier \texttt{main.cc} est modifié pour utiliser un header
et supprimer le prototype rajouté à la main:
\begin{lstlisting}[title={Fichier \texttt{main.cc}: Version correcte avec header}, frame=single]
#include<iostream>
#include "maths.h"

/*Point d'entrée du programme*/ 
int main()
{
  unsigned int d;
  std::cout << "Entrez un entier : ";
  std::cin  >> d;

  unsigned int res=factorielle(d); // OK, grâce au prototype, le 
                                   // compilateur a suffisamment
                                   // d'informations pour valider
                                   // cette instruction
  std::cout << res << "\n";
  return (0);
}
\end{lstlisting}
Et nous avons maintenant organisé correctement le code d'un petit
programme. Cela n'a pas l'air très utile pour un programme aussi court
mais il est préférable de prendre les bonnes habitudes dès maintenant.

\subsection{Que mettre dans un header?}\label{subsect:QuoiHeaders}
Tout d'abord, signalons que si on a de la chance, l'addendum technique
sur les modules au \texttt{C++2011} sortira bientôt. Une fois sorti,
la question sera obsolète car ce qui remplacera les headers sera
automatiquement créé par le compilateur. Malheureusement, à ce jour,
il n'est pas encore sorti. Nous somme donc, pour l'instant, obligés de créer les headers
à la main et d'apprendre ce qui doit être et ce qui ne doit pas être mis dedans.

Dans un header, on place en général
\begin{enumerate}
\item Des prototypes de fonctions.
\item Des définitions de classe. 
\item Des déclarations de variables global, \textit{i.e.} avec le
 mot-clef \lstinline$extern$.
\item Des template, c'est un sujet avancé, voir le chapitre~\ref{chap:template}.
\end{enumerate}

Dans un header, on ne met généralement  pas
\begin{enumerate}
\item Des définitions de variables globales, \textit{i.e.} sans le
 mot-clef \lstinline$extern$.
\item Des définitions de fonctions, \textit{i.e.} avec un corps de
 fonction.
\item Des définitions de fonctions membres définies en dehors de 
la classe.
\end{enumerate}




\section{Quelques règles de bonne conduite}
Certaines de ces règles peuvent probablement être ignorées si vous savez ce que 
vous faîtes. Cependant pour ignorer ces règles, il faut soit avoir une bonne
raison, soit suivre d'autres règles. 

\subsection{Placer le \lstinline$main$ à part}
Dans un programme, il ne peut y avoir qu'une seule fonction
\lstinline$main$. Il est préférable de placer la fonction \lstinline$main$
dans un fichier à part avec peut-être quelques fonctions auxiliaires
qui sont propres au programme et n'ont aucun potentiel de
réutilisation.

Attention, il ne doit \textbf{jamais} y avoir de fonction
\lstinline$main$ dans une bibliothèque. En effet, supposer que vous programmiez une bibliothèque de résolution
d'équation aux dérivées partielles. Si le fichier contenant la
fonction \lstinline$EulerExplicite$ contient aussi une fonction
\lstinline$main$, la fonction \lstinline$EulerExplicite$ ne pourra
jamais être utilisée par aucun programme 

\subsection{Organiser vos fichiers}
Les fonctionnalités apparentées sont de préferences regroupées
dans un même fichier ou dans un même namespace. Les fonctionnalités qui n'ont aucune parenté
entre elles vont dans des fichier différents.  

De plus, nommez vos fichiers avec soin. Mettez vous à la place de
celui récupère votre code et qui trouve dans le répertoire de votre
projet les fichiers \texttt{truc.cc}, \texttt{chose.cc},
\texttt{machin.cc}, \texttt{machinchose.cc}, \texttt{stuff.cc} 
ou encore \texttt{exo.cc}. Ce genre de nom de
fichier est à bannir. Un nom de fichier doit informer sur son contenu.

\section{Les namespaces}\label{subsect:namespaces}
Les namespaces sont des régions de code qui peuvent
contenir toutes les autres constructions du \texttt{C++}.
Elles offrent une autre possibilité d'organiser son code.

\subsection{Le namespace anonyme}
La première fonctionnalité des namespaces est le \lstinline$namespace$ anonyme.
les types, variables et fonctions définis 
   dans le namespace anonyme ne peuvent être 
   accéder que depuis le même fichier: cela
   remplace une des nombreuses utilisation du mot-clef \lstinline$static$.
\begin{lstlisting}
namespace {
  int a;
  int n;
}
\end{lstlisting}

\subsection{Les namespaces non anonymes}
Une autre fonctionnalité est de pouvoir faire coexister plusieurs types
ayant le même nom dans un même programme. Imaginer que dans un programme
coexiste deux bibliothèques de calcul symbolique
et que chacune d'entre elle ait choisi l'identifiant
\lstinline$expr$ pour le type expression. Si les bibliothèques sont
déclarées dans la zone globale, il y aura
conflit. Si chacune
des bibliothèques est définie dans un namespace
nommé différemment, il n'y aura aucun problème:
\begin{lstlisting}
namespace mes_expressions {
  struct expression { 
    //...
  }
  // Définitions de variables
  // Définitions de fonctions
}

namespace les_expressions_du_voisin {
  struct expression { 
    //...
  }
  // Définitions de variables
  // Définitions de fonctions
}
\end{lstlisting}
Et on peut déclarer dans le programme des expressions
de type différent avec
\begin{lstlisting}
mes_expressions::expr e1;
les_expressions_du_voisin e2;
\end{lstlisting}


\section{Conclusion}
Organiser son code est primordial pour des programmes longs de plusieurs
millions de lignes de code écrit en coopération par une équipe. Pour
l'instant, en \texttt{C++}, cela signifie qu'il faut savoir créer des
headers. Espérons que cela ne soit plus le cas à l'avenir. 

Il est
aussi très important d'être discipliné quandon programme en
équipe. En effet, les morceaux disjoints d'un même programme écrit par
des personnes différentes doivent être compatible. Pour assurer cette
compatibilité, le seul moyen est de respecter à la lettre la
spécification des interfaces données par le chef du projet: en
particulier il faut respecter le nom des
fonctions, ordre des arguments des fonctions, nom des classes, nom des
fichiers headers, nom des fichiers sources chosies par le chef du
projet. Ceci, même si vous n'aimez pas les choix du chef de
projet. Sans cette discipline, les morceaux du programme codés par des
personnes différentes ne s'imbriqueraient pas correctement.



\chapter{Les classes et la programmation orientée objet}\label{chap:classes}
Par rapport au \texttt{C}, l'ajout le plus visible en \texttt{C++} est
la notion de classe. Les classes sont à la base de la programmation
orientée objet mais il ne suffit pas de créer une classe pour faire de
la programmation orientée objet.


\section{Les classes}
Nous avons introduit le concept de structure à la
section~\ref{sect:structures}. Les classes généralisent cette notion.
La notion de classe permet aux programmeurs de définir de nouveaux
types pouvant être utilisé avec les mêmes facilités que les types
prédéfinies. Ces nouveaux types peuvent
alors être dotés en plus d'un certain nombre d'opération et de
fonctions membres. \textit{I.E.} une classe n'est pas seulement
définie par les sous-variables qui la constituent mais aussi par l'interface
fournie à ses utilisateurs.

\subsection{L'encapsulation}
Dans la programmation modulaire, si l'on fait attention
à diviser un programmes en plusieurs modules,
toute les fonctions
sont autorisées à modifier tous les membres d'un type
et à accéder à toutes les variables, y compris les variables internes
d'un autre module. Par convention, les programmeurs disciplinés s'abstiennent
d'accéder directement aux données et appellent
des fonctions spécialisées. 
En cas de bug, le nombre de fonctions à
vérifier demeure alors beaucoup plus restreint, ce qui est primordial 
dans un grand programme. Cependant, le compilateur ne fait
rien pour imposer cette contrainte et un programmeur
peu attentif pourrait alors modifier directement un membre interne
d'un type composé.

Ce n'est pas très grave pour un type simple comme un point
de deux coordonnées:
\begin{lstlisting}
struct point {
  int x;
  int y;
};
\end{lstlisting}
C'est beaucoup plus gênant pour une liste doublement chaînée.
\begin{lstlisting}
struct lien {
  int val;
  lien* next;
  lien* prev;
};

struct liste {
  lien* tete;
  lien* fin;
}
\end{lstlisting}
Il est impératif pour qu'elle fonctionne que les liens 
\lstinline$next$ et \lstinline$prev$ soient cohérents.
Il faut respecter un invariant: si \lstinline$p$ est un 
\lstinline$lien*$ et si \lstinline$p->next$ est non nul
alors \lstinline$(p->next)->prev$ doit être égal
à \lstinline$p$. C'est ce que l'on appelle un invariant.

Si toutes les fonctions peuvent y accéder et qu'un programmeur décide
d'accéder directement aux membres de \lstinline$lien$ 
et qu'il commet une erreur 
(ou que la bibliothèque de liste change son implémentation interne),
on peut se retrouver avec un programme qui fera n'importe quoi
et la cause de l'erreur risque d'être difficile à identifier.

\subsection{Définition d'une classe}
Pour cette raison, le \texttt{C++} introduit les classes
qui sont une généralisation des structures hérités du \texttt{C}. 
Une classe se définit comme une structure, voir section~\ref{sect:structures} mais
on utilise le mot-clef \lstinline$class$ à la place de
\lstinline$struct$. Voici un exemple à vocation purement pédagogique 
\begin{lstlisting}
class point {
public: // Tous les membres déclarés après sont public
  double x; // x est un membre public
private: // Tous les membres déclarés après sont privés
  double y; // y est un membre privé
};
\end{lstlisting}
Nous remarquons ici les mots-clefs \lstinline$private$ et
\lstinline$public$. 
Ces mots clefs spécifient\footnote{il existe une troisième spécification \lstinline$protected$
mais nous n'en parlerons pas dans ce document.}
 si un membre d'une classe est un membre privé
ou un membre public. Les membres publics sont directement accessibles
par toute fonction tandis que les membres privés ne le sont
qu'indirectement. Par défaut, en l'absence des mot-clefs
\lstinline$private$ et \lstinline$public$, les
membres sont privés. Essayons maintenant d'accéder aux données
\begin{lstlisting}
point A; //A est un point
A.x=5.0; //OK, x est public
A.y=3;   //Erreur, y est privé
\end{lstlisting}
Comment peut-on modifier le membre \lstinline$y$ ? Certaines fonctions
ont le droit de modifier les membres privés d'une classe: les
fonctions membres et les fonctions amies. Nous commençons par décrire
ce qu'est une fonction membre.

\subsection{Fonctions membres}
Les classes peuvent aussi avoir des fonctions comme membre. On
appelera fonctions membres ces fonctions. De même, on appellera
données membres, les membres qui sont des variables. Reprenons la
définition de la classe \lstinline$point$
\begin{lstlisting}
class point {
public:
  double x;
  double y;
private:
  double get_x() {return x;}  // déclarée et définie.
  double& get_y() {return y;}   // pareil et retourne une référence.
  point rotate(float angle) const;    // déclarée et non définie.
};
\end{lstlisting}
La classe \lstinline$point$ a deux données membres: \lstinline$x$ et
\lstinline$y$. Cette classe dispose aussi de trois fonctions membres:
\lstinline$get_x()$, \lstinline$get_y()$ et
\lstinline$rotate(float)$. Les fonctions membres d'une classe sont
autorisées à modifier les données privées des variables de cette classe. 
De cette manière, on limite le nombre de fonctions autorisées à
modifier la machinerie interne d'une variable d'une classe donnée.

Pour appeler une fonction membre, on utilise
l'opérateur de sélection \og{}\lstinline$.$\fg{}:
\begin{lstlisting}
point A;	      // OK
A.x=2.5;	      // OK
A.y=2.2;	      // OK
double a=A.get_x();   // OK
double b=A.get_y();   // OK
A.get_x()=2.2;	      // Erreur, get_x() ne renvoie pas une référence
A.get_y()=2.2;        // OK
\end{lstlisting}
L'instruction \lstinline$A.get_x()=2.2$ est une erreur 
car \lstinline$get_x()$ ne retourne pas une référence mais 
une valeur: la ligne a autant de sens que \lstinline$1.0=2.2$!!!
Dans un code réel, la fonction membre \lstinline$get_x()$ renverrait
elle aussi une référence.

Ici, et pour la plupart des classes que vous rencontrerez, 
les données membres sont privées et les fonctions membres sont
publics. Rien n'interdit de déclarer privée une fonction membre,
elle ne pourrait alors être appelée que depuis une autre fonction membre
(ou depuis une fonction amie, notion non encore
introduite). Cependant, cela n'est pas très courant.

Les fonctions membres \lstinline$get_x()$ et \lstinline$get_y()$
ont été définies à l'intérieur de la classe. Ce n'est pas le cas de 
la fonction \lstinline$rotate(float)$. Pour le faire
à l'extérieur de la classe, on procède de cette manière
\begin{lstlisting}
/* Définition de rotate pour point */
point point::rotate(double angle) const
{
  point B;
  B.x=cos(angle)*x-sin(angle)*y;
  B.y=sin(angle)*x-cos(angle)*y;
  return B;
} 
\end{lstlisting}
Le mot-clef \lstinline$const$ signifie que la fonction
\lstinline$rotate$ ne modifie pas la variable de type
\lstinline$point$ depuis laquelle elle est appelée. Le compilateur
vérifiera que c'est bien le cas. 


La syntaxe générale pour définir une fonction membre à l'extérieur de
la classe est la suivante:
\begin{lstlisting}
/* Définition de rotate pour point */
typederetour nomclasse::nomfonctionmembre(/*liste arguments*/) const 
                                                //const est optionnel
{
  /*Corps de la fonction*/
} 
\end{lstlisting}

Remarquez que les données membres
de la variable depuis laquelle la fonction membre \lstinline$rotate()$ est appelée sont accédées
directement sans l'opérateur de sélection \og{}\lstinline$.$\fg{}. Les membres
des autres variables du même type ou nom sont accédés de manière
usuelle avec l'opérateur de sélection \og{}\lstinline$.$\fg{}. Par exemple, lors
de l'appel \lstinline$A.rotate(3.14)$, le membre \lstinline$A.x$ est
connu comme \lstinline$x$ sans aucun préfixe dans le corps de la
fonction membre \lstinline$rotate()$. Mais que fait-on quand on veut
accéder à \lstinline$A$ lui même dans le corps de la fonction ? Nous
répondons à cette question dans la section suivante.

\subsection{Le pointeur \lstinline$this$}
Nous venons de voir dans les exemples précédents que les fonctions membres
ont un accès direct aux membres de la variable depuis laquelle elles
sont appelées. Pour accéder à la variable elle-même, il faut utiliser
le pointeur \lstinline$this$ qui contient l'adresse de la  variable
elle-même. Voici un exemple de classe l'utilisant. Cette classe est
inutile et a un but purement pédagogique
\begin{lstlisting}
class exemple {
private: //inutile private par défaut
  int n;
public:
  exemple* adresse() {return this;}
  void setn_1(int m) { n=m;} 
  void setn_2(int m) { this->n=m;} 
  void setn_2(int m) { (*this).n=m;} 
};
\end{lstlisting}
Alors, on peut l'utiliser de la manière suivante
\begin{lstlisting}
exemple A;
exemple* p;
p=A.adresse(); // équivalent à p=&A;
A.setn_1(2);   // A.n vaut 2
A.setn_2(3);   // A.n vaut 3
A.setn_3(5);   // A.n vaut 5
\end{lstlisting}

Signalons enfin que le pointeur \lstinline$this$ \textbf{ne peut être accédé
que} depuis une fonction membre.

Nous verrons des exemples d'utilisation de \lstinline$this$ moins
artificiels plus loin dans ce polycopié.

\subsection{Fonctions et classes amies}
Considérons une
classe de vecteurs mathématiques \lstinline$mathvector$ et d'une
classe de matrices \lstinline$matrice$. Pour effectuer le
produit matrice vecteurs de ces deux objets, il faut pouvoir accéder
aux données membres de ces deux classes. Mais il n'est pas possible
pour une fontion d'être membre de deux classes différentes.

La solution est d'utiliser une fonction dite amie. Les fonctions amies
sont des fonctions normales mais qui ont accès aux membres privés
des classes dont elles sont amis. Nous avons besoin de la fonction suivante.
\begin{lstlisting}
mathvector 
produit_matrice_vecteur (const matrice& a, const mathvector& b)  
{
  //Algorithme de produit matrice vecteur
}
\end{lstlisting}
Pour qu'elle ait accès aux membres privés des variables de type
\lstinline$matrice$ et \lstinline$mathvector$, il suffit de la
déclarer ami dans les deux classes. Rien de plus facile, il suffit de
rajouter le prototype de cette fonction précédé du mot-clef
\lstinline$friend$ dans les deux classes.
\begin{lstlisting}
class matrice {
private:
  //....
public:
  //....
  friend mathvector 
  produit_matrice_vecteur (const matrice& a, const mathvector& b);
};

class mathvector {
private:
  //....
public:
  // ....
  friend mathvector
  produit_matrice_vecteur (const matrice& a, const mathvector& b);
};
\end{lstlisting}
Les fonctions amies ne sont pas des fonctions membres, elles sont
appelées comme des fonctions normales:
\begin{lstlisting}
matrice A;
mathvector x;
//...
mathvector b;
b=produit_matrice_vecteur(A,x);
\end{lstlisting}
Remarquez l'absence d'opérateur de sélection \og{}\lstinline$.$\fg{}.

Le concept de classe amie existe aussi:
\begin{lstlisting}
class A {
  //...
};

class B {
  //...
  friend class A; // Toutes les fonctions membres 
                  // de A ont maintenant accès aux
                  // données privées de B;
};
\end{lstlisting}
Les fonctions et les classes amies sont une alternative aux fonctions
membres quand il s'agit d'accéder aux données privées.


\subsection{Constructeurs}\label{subsect:constructeurs}
Les constructeurs sont une notion primordiales en \texttt{C++}.
Il est très important de comprendre ce qu'est un constructeur. Aussi, nous
laissons leur syntaxe à plus tard. Un constructeur est une fonction
membre d'une classe qui initialise la variable au moment même de
la définition de cette variable. 

\subsubsection{Motivation}
Pour justifier le concept de
constructeur, observons comment on programmerait sans constructeurs.
Supposons que nous ayons plusieurs classes, disons $3$, \lstinline$type1$,
\lstinline$type2$, \lstinline$type3$. Les variables de ces types
nécessitent une initialisation avant d'être utilisée. On programme
alors des fonctions \lstinline$init_type1$, \lstinline$init_type2$
et \lstinline$init_type3$. Voici comment, nous les utiliserions
\begin{lstlisting}
type1 var1;
init_type1(var1); 
type2 var2;
init_type2(var2, arg21); 
type3 var3;
init_type3(var3, arg31, arg32, arg33, arg34);
\end{lstlisting}
Mais cette manière de programmer est dangereuse: il est bien trop
facile d'oublier une initialisation et pour certaines classes,
particulièrement les classes utilisant l'allocation dynamique et  pour
les classes contenant des pointeurs, cela peut être dramatique. On
peut se retrouver avec des variables dans un état indéfini et avoir un
programme qui fait n'importe quoi. Par exemple, si un pointeur est mal
défini, on peut avoir une erreur de segmentation. Ce genre d'erreur
peut être difficile à repérer dans un long programme. La solution
est d'utiliser les constructeurs, ainsi définition de la variable et
initialisation auront lieu sur la même ligne et il n'y aura aucun
risque d'oubli. Il serait préférable de pouvoir simplement écrire
\begin{lstlisting}
type1 var1;
type2 var2(var2, arg21);
type3 var3(var3, arg31, arg32, arg33, arg34);
\end{lstlisting}
et que les variables \lstinline$var1$, \lstinline$var2$ et
\lstinline$var3$ soient initialisées comme si on avait appelé les
fonctions \lstinline$init_$. C'est exactement ce que font les constructeurs.


\subsubsection{Syntaxe de déclaration des constructeurs}
Les constructeurs sont reconnus comme constructeurs car ce sont des fonctions membres 
qui porte le même nom que la classe à laquelle ils appartiennent.
Ils ne retournent rien, aussi c'est un des rare cas où une
fonction est déclaré sans type de retour. La syntaxe générale pour
déclarer un constructeur est
\begin{lstlisting}
class nom_classe {
private:
  //Données
public:
  nom_classe (liste  arguments) ;
  //Autres fonctions membres
};
\end{lstlisting}
Puis, pour définir un constructeur en dehors de la classe
\begin{lstlisting}
nom_classe::nom_classe (/*liste arguments*/)
{
 //Corps de la fonction
}
\end{lstlisting}
Puis pour utiliser ce constructeur, il suffira
d'écrire
\begin{lstlisting}
nom_classe var(/*liste arguments*/); //Initialisation faite par le constructeur
\end{lstlisting}

Il peut y avoir plusieurs constructeurs pour une même classe. Deux
constructeurs sont particulièrement importants: le constructeur par
défaut et le constructeur par copie.

\subsubsection{Le constructeur par défaut}
Si aucun autre constructeur n'est définie, le constructeur par défaut
sera créé automatiquement par le compilateur. Le constructeur par
défaut est celui qui est appelée lorsqu'on déclare une variable sans
aucun argument. 
La syntaxe générale pour déclarer un constructeur par défaut est
\begin{lstlisting}
class nom_classe {
private:
  //Données
public:
  nom_classe () ; // Constructeur par défaut
  //Autres fonctions membres
};
\end{lstlisting} 
Pour initaliser une variable avec le constructeur par défaut, il
suffit de la déclarer sans aucun argument
\begin{lstlisting}
nom_classe var;
\end{lstlisting} 
c'est le constructeur par défaut qui est appelé et qui initialise \lstinline$var$.

\subsubsection{Le constructeur par copie}
Le constructeur par copie permet d'initialiser une variable d'un type
par une variable du même type. Ce constructeur prend une référence
constante sur la classe dont il est fonction membre comme argument.
En voici la syntaxe générale:
\begin{lstlisting}
class nom_classe {
private:
  //Données
public:
  nom_classe (const nom_classe&) ; // Constructeur par défaut
  //Autres fonctions membres
};
\end{lstlisting} 
En particulier, si \lstinline$var$ est une variable préexistante de type
\lstinline$nom_classe$, alors lors des déclarations
\begin{lstlisting}
nom_classe var1(var);
nom_classe var2=var;
\end{lstlisting} 
c'est le constructeur par copie qui est appelé et qui initialise
\lstinline$var1$ et \lstinline$var2$.


\subsubsection{Exemple}
Prenons la classe \lstinline$matrice$, cette classe a besoin d'allouer
dynamiquement de la mémoire. En effet, on ne connait pas forcément lors de la
compilation la taille des variables de type \lstinline$matrice$ et
donc la quantité de mémoire dont elles auront besoin
Voici comment créer des constructeurs pour cette classe:
\begin{lstlisting}
class matrice
{
private:
  int m;
  int n;
  double *q; 
public:
  matrice(int _m, int _n) {
    m=_m;
    n=_n;
    q= new double[m*n]; // allocation de mémoire
  }
  matrice(int _m, int _n, double val) {
    m=_m;
    n=_n;
    q= new double[m*n]; // allocation de mémoire
    for(int i=0;i<m*n;++i)
      q[i]=val;
  }
  matrice(const matrice& b) {
    m=b.m;
    n=b.n;
    /* Attention, on ne peut assigner b.q à q */
    q= new double[m*n]; // allocation de mémoire
    for(int i=0;i<m*n;++i) {
      q[i]=b.q[i];
    }
 }
  // Destructeur, voir section sur les destructeurs
  //autre fonctions membres
};
\end{lstlisting}


\subsection{Destructeurs}
Les destructeurs sont le contraire des constructeurs. Ils servent à
nettoyer une variable quand celle-ci cesse d'exister. En effet,
certaines classes aquièrent des ressources lors de leur
construction. Ces ressources peuvent être de l'espace mémoire,
des accès réseaux, des ouvertures de fichiers ou encore des locks.
Le plus souvent, c'est de l'espace mémoire. Quand la variable atteint
sa fin de vie, elle doit libérer ces ressources. Cela est fait avec un destructeur.
Les destructeurs sont appelés automatiquement quand une variable 
atteint la fin de son existence. Comme les constructeurs, les
destructeurs ne renvoient aucun argument. Contrairement aux constructeurs, une
classe ne peut avoir qu'un unique destructeur et il ne prend 
aucun argument. Le destructeur se déclare comme
un constructeur mais précédé de \lstinline$~$. Voici la syntaxe
générale
\begin{lstlisting}
class nom_classe {
private:
  //Données
public:
  ~nom_classe () ;
  //Autres fonctions membres
};
\end{lstlisting}
Puis pour définir un constructeur en dehors de la classe
\begin{lstlisting}
nom_classe::~nom_classe (liste  arguments)
{
 //Corps de la fonction
}
\end{lstlisting}


Reprenons l'exemple de la classe matrice
qui alloue de la mémoire dynamique lors de la construction.
Il va falloir libérer cette mémoire dans le destructeur. 
\begin{lstlisting}
class matrice
{
private:
  int m;
  int n;
  double *q; 
public:
  // Constructeurs, voir section précédente
  ~matrice() {delete[] q;} //libération de la mémoire 
  //autre fonctions membres
};
\end{lstlisting}
Nous rappelons
que les variables allouées dynamiquement existent jusqu'à ce qu'elles aient été 
explicitement détruites. C'est cette allocation dynamique qui justifie 
l'importance des destructeurs
\begin{lstlisting}
{
  matrice m(4,4);
  
  // ...

}//~matrice() est appelé automatiquement avant le }
\end{lstlisting}

Le destructeur d'une variable est toujours appelé automatiquement lorsque
la variable arrive en fin de vie. Il ne faut donc \textbf{jamais
  appeler explicitement un destructeur}. Ce principe vaut même pour les
variables dynamique. En effet les opérateurs \lstinline$delete$
et \lstinline$delete[]$ appelent eux aussi automatiquement\footnote{Et
même au cas où vous surdéfinisseriez ces opérateurs \lstinline$delete$
et \lstinline$delete[]$, l'appel
au destructeur est automatiquement rajouté et n'a pas à être ajouté
manuellement dans le corps de fonction de ces opérateurs.} les
destructeurs. Ce principe de ne jamais appeler explicitement un
destructeur ne souffre qu'une unique exception que nous n'aborderons
pas dans ce polycopié.

\subsection{Exemple: une classe de complexes}
Nous allons maintenant regarder un exemple de classe.
\begin{lstlisting}
class complexe {
private: //Non nécessaire, privé par défaut
  double re;
  double im
public:
  complexe() ; // Un constructeur
  complexe(double _re); // Un constructeur
  complexe(double _re, double _im); // Un constructeur
  complexe(const complexe&); // Le constructor par copie
  double& real();
  double& imag();
  complexe operator*(complexe b); 
  complexe operator=(const complexe&); // L'assignation par copie
}
\end{lstlisting}
est un exemple de classe. Nous rappelons que les fonctions
non membres ne peuvent accéder aux membres privés. Le but est de
fabriquer une classe complexe qui puisse être utilisée de manière naturelle.
\begin{lstlisting}
complexe a;
a.re=2; //erreur re est privé 
double c= a.re; //erreur re est privé 
\end{lstlisting}

Voici comment on souhaite pouvoir utiliser les constructeurs de la
classe \lstinline$complexe$. Rappelons que les  
constructeurs servent à initialiser une variable au moment même de sa création.
Par exemple, lorsque l'on déclare:
\begin{lstlisting}
complexe z; // complexe::complexe() est appelée
complexe z2(1.0); // complexe::complexe(double) est appelée 
complexe z2=1.0); // complexe::complexe(double) est appelée 
complexe z3(1.0,2.0); // complexe::complexe(double,double) est appelée

complexe z4(z);  // Constructeur par copie
                 // complexe::complexe(const complexe&) 

/*Attention */
complexe z5=z;  // Constructeur par copie
                // complexe::complexe(const complexe&) 
 
z2=z;		// Assignation par copie
                // complexe::operator=(const complexe&) 
\end{lstlisting}
Ne pas confondre le constructeur par copie et l' assignation par copie..


\subsection{Surdéfinition des opérateurs}
En \texttt{C++}, il est possible de surdéfinir les opérateurs 
pour des classes définies par l'utilisateur. Cela signifie qu'il est
possible de spécifier la signification des opérateurs arithmétiques
\lstinline$+$ , \lstinline$-$, \lstinline$*$, \lstinline$/$, des
opérateurs de comparaisons, et de presque tous les opérateurs
pour les classes définies par l'utilisateur. Il n'est pas possible
de changer la priorité des opérateurs. Il n'est pas possible de
changer le sens d'un opérateur pour les types prédéfinis.
Voici comment on surdéfinit les opérateurs d'assignation \lstinline$=$ et
de multiplication \lstinline$*$ pour la classe
\lstinline$complexe$. On souhaite que les instructions suivantes
soient licites:
\begin{lstlisting}
complexe a;
complexe b;
...
complexe z=a*b;
complexe z2;
z2=z;
\end{lstlisting}
Autrement dit, on souhaite pouvoir utiliser les complexes avec les
notations mathématiques usuelles. Pour cela, il faut surdéfinir les
opérateurs arithmétiques:
\begin{lstlisting}
class complexe {
  double re, im;
public:
  //...
  complexe operator* (const complexe& b) const;
  complexe& operator= (const complexe& b);
}
\end{lstlisting}
Ici, si vous suivez, vous devez vous demandez pourquoi ces opérateurs
ne prennent qu'un seul argument et non deux. La réponse est qu'il
s'agit ici de fonctions membres. Le premier argument est comme pour
toute fonction membre passée implicitement. Ainsi, si \lstinline$z1$ et \lstinline$z2$ sont des
variables de classe \lstinline$complexe$, l'instruction
\lstinline$z1=z2$ est équivalente à \lstinline$z1.operator=(z2)$.
De même, l'instruction
\lstinline$z1*z2$ est équivalente à \lstinline$z1.operator*(z2)$.
Ces deux formes longues sont licites mais ne sont pas utilisées en pratique.
Ainsi, dans les deux cas, les données membres de \lstinline$z1$ sont
accessibles directement sans préfixe dans la définition de ces deux
opérateurs membres:
\begin{lstlisting}
complexe complexe::operator*(const complexe& b)  const
{
 return(complexe(re*b.re-im*b.im,re*b.im+im*b.re);
}

complexe& complexe::operator=(const complexe& b)  
{
  re=b.re;
  im=b.im;
  return(*this);
}
\end{lstlisting}
Le fait que l'opérateur \lstinline$=$ retourne une référence sur un
\lstinline$complexe$ et qu'il retourne \lstinline$return(*this)$ est
nécessaire.  C'est le cas pour tous les opérateurs d'assignation et
\textbf{seulement les opérateurs d'assignation}, \textit{i.e.} pour
\lstinline$=$,
\lstinline$+=$,
\lstinline$-=$,
\lstinline$*=$, et
\lstinline$/=$.
%et\lstinline$%=$. 
Nous n'expliquerons pas pourquoi dans ce polycopié.



Il est aussi possible de
surdéfinir les opérateurs par des fonctions non membres
\begin{lstlisting}
mathvector 
operator*(const matrice& a, const mathvector& b)  
{
  //..
}
\end{lstlisting}
Il suffira de déclarer cet opérateur \lstinline$friend$ dans les classes
\lstinline$mathvector$ et \lstinline$matrice$:
\begin{lstlisting}
class matrice {
//
public:
  friend mathvector 
  operator*(const matrice& a, const mathvector& b);
};

class mathvector {
//
public:
  friend mathvector 
  operator*(const matrice& a, const mathvector& b);
};
\end{lstlisting}
Remarquer que lorsque un opérateur est définie comme une fonction
normale et non comme une fonction membre, aucun argument n'est passé
implicitement et le nombre d'arguments est celui donnée par l'intuition.

On peut surdéfinir presque tous les opérateurs.
Les plus courants sont les opérateurs arithmétiques,
le déréférencement (\lstinline$*$ préfixe) et 
l'assignation. 

\subsection{Assignation et constructeurs}
L'assignation, effectuée par \lstinline$operator=$, et la
construction, effectuée par un constructeur, sont deux notions différentes.
Il est très important de s'en rappeler. Pour les classes simples,
c'est peu apparent. Regardons un exemple où c'est évident.
Reprenons l'exemple de la classe de matrice de la section
\ref{subsect:constructeurs}. Lors de la construction, on aquiert de la
mémoire . Lors de l'assignation \lstinline$A=B$, la matrice
\lstinline$A$ a déjà acquise de la mémoire. Si on programmait
l'assignation comme la construction, on aurait ce que l'on appelle 
une fuite de mémoire. Si on impose comme
condition que l'assignatioon entre deux matrice n'est licite que si
les tailles de \lstinline$A$ et de \lstinline$B$ coïncident, alors il
n'est pas besoin d'acquérir de la mémoire lors de l'assignation et 
l'opérateur \lstinline$=$ peut être définie de la manière suivante:
\begin{lstlisting}
matrice& matrice::operator=(const matrice& b)
{
  if(m==b.m && n==b.n) {
    for(int i=0;i<m*n;++i) {
      q[i]=b.q[i];
    }
  } else {
     //Gestion d'erreur
  }
  return (*this);// Nécessaire pour que A=B=C fonctionne
}
\end{lstlisting}

\subsection{Conclusion sur les classes}
Les classes constituent le principal ajout du \texttt{C++} par rapport
au \texttt{C}, elles constituent un outil puissant qui permet d'isoler
l'utilisateur d'une bibliothéque des détails internes à la classe.
Il est primordial pour le programmeur \texttt{C++} de savoir
programmer des classes concrètes.


\section{La programmation orientée objet}
La programmation orientée objet ne se limite pas à
la simple création de classes et l'encapsulation.
Dans la programmation orientée objet, on se concentre
sur la création d'objet, sur la création de classes
et leur \textbf{hiérarchisation}. On essaie
de regrouper les éléments communs d'une classe
dans une classe de base.

Avant d'écrire les algorithmes, on créé des classes
et on définit leur comportement:
on commence d'abord par spécifier l'interface
et par écrire les déclarations des fonctions membres. 
On implémente la classe ensuite.

\subsection{L'héritage}
Une classe peut être dérivé d'une autre et hériter
tous ses membres. Voici un exemple,
\begin{lstlisting}
class habitation {
  std::string nom;
  int pieces;
public:
habitation(std::string _nom, int _pieces);
void print();
};


class maison: public habitation {
  int nombreetages;
public:
maison(std::string _nom, int _pieces, int _etages);
void print(); // Redéclaration de print() 
}

void habitation::print()
 { 
  std::cout << "Habitation :" << nom << '\n'
  	    << '\t' << pieces << "pièces" << '\n'
}


void maison::print()
 { 
   habitation::print();
   std::cout << '\t' << etages << "étages" << '\n';

   /* 
      Illégale car maison ne peut accéder 
      aux privés d'habitation 
   */
   std::cout << '\t' << pieces/etages 
             << "pieces par etages" << '\n';
}
\end{lstlisting}
La classe maison hérite de tous les membres de la classe 
\lstinline$habitation$ et est une classe hérité
de \lstinline$habitation$. Les fonctions membres de \lstinline$maison$
ne peuvent accéder aux  membres privés de \lstinline$habitation$!!

\subsection{Pointeurs et conversions implicites?}
Les pointeurs de type maison peuvent être convertis directement
en pointeurs de type habitation sans conversion explicite.
La réciproque n'est pas vraie.
\begin{lstlisting}
maison a;
habitation b;

habitation*p=&a; // OK
maison*q=&b ;    // Erreur
\end{lstlisting}
Mais \lstinline$p->print()$ va appelé le \lstinline$print$
d'\lstinline$habitation$. Et le nombre d'étages ne sera pas affiché.
En effet, le typage est statique
et à la compilation, le compilateur ne peut deviner si 
\lstinline$p$ est non seulement une \lstinline$habitation$
mais aussi une \lstinline$maison$! Pour cela nous introduisons
les fonctions virtuelles.

\subsection{Héritage public ou privé ?}
Nous avons pour l'instant toujours
déclare la classe de base \lstinline$public$. Nous aurions
aussi pu la déclarer \lstinline$private$: 
\begin{lstlisting}
class A { public: void print() {std::cout << "n"}};
class B: public A {};
class C: private A {};
A a; a.print(); // OK
B b; b.print(); // OK print hérité de A et public.
C b; c.print(); // erreur la base A est privé
\end{lstlisting}
Les membres publics de \lstinline$C$ 
peuvent accéder aux membres publics de \lstinline$A$
mais l'interface de \lstinline$A$ dans \lstinline$C$ est maintenant privé .

\subsection{Constructeurs et héritage}
Nous introduisons ici une syntaxe un peu surprenante. En effet, 
comment construisons nous une classe dérivée. Il nous faut un constructeur.
\begin{lstlisting}
class A {
private:
  A(); //Pas de constucteur par défaut.
public:
  A(double); // Un autre constructeur.
};

class B: public A {
private:
  B();
}; 

B::B() 
{
    //?? Je veux appeler le constructeur A(1.0).
}
\end{lstlisting}
Nous ne pouvons pas appeler un constructeur de la classe de base 
depuis le corps du constructeur. En effet, une fois dans le corps
de la fonctions, les classes de bases
et les membres ont déjà été initialisées par défaut.
Nous devons utiliser une autre syntaxe
qui permet d'appeler les constructeurs.
\begin{lstlisting}
B::B() : A(1.0) 
{
// Autres instructions
}
\end{lstlisting}


Cette syntaxe est non seulement utilisé pour les classe de bases mais
aussi pour les membres d'une classe. Cette syntaxe est d'ailleurs impérative
pour les références qui doivent être initialisées.
\begin{lstlisting}
class C: public A {
  float& r;
  double& x;
// ....
public:
  C (double a, float& b, double& x) : A(a), r(a), x(c){}
}
\end{lstlisting}

\subsection{Les fonctions virtuelles}
Supposons que l'on déclare
\begin{lstlisting}
class habitation {
//...
public:
virtual print(); // Voir définition plus haut
}
class maison: public habitation {
//...
public:
virtual print(); // Voir définition plus haut
}
\end{lstlisting}
Alors dans ce cas
\begin{lstlisting}
maison a;
habitation b;

habitation* p;
p=&a; 
p->print();//

p=&b; // OK
p->print(); // 
\end{lstlisting}
Cela vient que si une classe contient une fonction virtuelle,
elle est considérée classe virtuelle et un champ
est placée dans la représentation binaire de la 
classe par le compilateur qui précise le type exact de l'objet.
Pour une classe virtuelle, il y a typage dynamique et la bonne fonction
sera choisie lors de l'exécution. Cela ralentit l'exécution mais
c'est nécessaire si on a besoin de polymorphisme dynamique
où le type n'est pas prévisible lors de la compilation.

\subsection{Un exemple de programmation objet}
Supposons que l'on ait un programme géométrique
qui dessine des figures. La façon objet de le programmer est d'avoir une
classe abstraite \lstinline$figure$ et d'en dériver toutes les classes
de figures particulières:
\begin{lstlisting}
class figure {
public:
  virtual void dessiner() = 0 ;
  virtuel void rotation(double)=0 ;
}
\end{lstlisting}
Le \lstinline$=0$ signifie que la fonction est virtuelle pure
et qu'elle devra être redéclarée dans les classes dérivées.
Une classe qui contient une fonction virtuelle pure
est appelée classe abstraite et
ne peut être instanciée:
\begin{lstlisting}
figure A; // Erreur. A contient des foncions 
          // virtuelles pures
\end{lstlisting}
On peut alors dériver cette classe:
\begin{lstlisting}
class triangle : public figure {
  point A, B, C;
public:
  virtual void dessiner()       { /* code */ } 
  virtuel void rotation (double angle) { /* code */ } 
}

class cercle : public figure {
  point centre;
  double rayon;
public:
  virtual void dessiner()       { /* code */ } 
  virtuel void rotation (double angle) { /* code */ } 
}
\end{lstlisting}
Pour avoir un ensemble de figures, 
on utiliserait par exemple
\lstinline$std::list<figure*>$.

\section{Conclusion}
Dans la pratique, la très grande
majorité des classes que l'on est amenées à programmer sont des classes
concrètes autocontenues. Pour se lancer dans la programmation orientée objet
au sens pure du terme, il faut d'abord bien maîtriser la
programmation de ces classes concrètes. La programmation orientée
objet trouve sa force quand on a besoin de polymophisme, \textit{i.e.}
de variables pouvant changer de type, à l'exécution.

\chapter{Les templates et la programmation générique} 
Il est courant qu'un même algorithme soit programmé plusieurs fois
pour des raisons purement informatique. Programmer un même algorithme
plusieurs fois est source d'erreur. Il serait intéressant de pouvoir
écrire un algorithme sous forme abstraite et laisser le compilateur
l'adapter aux différents types. C'est possible en utilisant ce que
l'on appelle la programmation générique. Ce type de programmation fait
principalement appel à ce que l'on appelle les \og{}templates\fg{}.

\section{Un exemple simple}
Beaucoup de fonctions portant le même nom 
implémente le même algorithme 
et ne diffèrent que par le type de leur arguments. 
Par exemple, regardons la fonction \lstinline$max$:
\begin{lstlisting}
int max(int a, int b)
{
  if (a>b)
  {
    return a;
  }
  else {
    return b;
  }
}

float max(float a, float b)
{
  if (a>b)
  {
    return a;
  }
  else {
    return b;
  }
}
\end{lstlisting}
Et il faudrait écrire toutes les versions
pour tous les types prédéfinis et tous ceux définis par l'utilisateur
alors que le corps de la fonction aura toujours la même structure.
Peut-on réduire le nombre de copier-coller ? C'est possible
avec les template.

\begin{lstlisting}
template<typeneame LessThanComparable>

LessThanComparable 
max(LessThanComparable a, LessThanComparable b)
{
  if(a>b) {
    return a;
  }
  else {
    return b;
  }
}
\end{lstlisting}
Maintenant tout appel à la fonction
\lstinline{max} avec deux arguments de même type
va générer une nouvelle fonction \lstinline{max}
à partir du template. Supposons que l'on ait un type
\lstinline$mot$ pour lequel
on a défini une relation d'ordre alphabétique~\lstinline{<}
alors \lstinline$max(mot1,mot2)$ retourne le mot le plus
à la fin du dictionnaire. La fonction \lstinline$max(mot,mot)$
est instanciée au premier appel de la fonction \lstinline$max$ pour le 
type \lstinline$mot$.

\section{Les classes templates}
Une classe peut aussi bénéficier des templates.
Essayons de programmer une liste pour un type arbitraire 
\lstinline$T$:
\begin{lstlisting}
template <typename T>
class ma_liste<T> {
  struct lien {
    lien* next;
    T val;
  };
  lien* tete;
  lien** fin;
  lien* current;
public:
  //Constructeurs
  //Acces
};
\end{lstlisting}
On peut alors déclarer des listes de types différents sans recopier
$50$ fois la même définition.
\begin{lstlisting}
ma_liste<int> liste_entiers;
ma_liste<float> liste_flottants;
ma_liste<char> liste_caracteres;
\end{lstlisting}
Cette liste est très primitive et n'a qu'un usage pédagogique. 
Utilisez la liste de la STL \lstinline$std::list$ dans un vrai programme. 

\section{Spécialisation et surdéfinition des fonctions template}
Cette section est technique et peut être sautée en première lecture.

Les fonctions en \texttt{C++} peuvent partager le même nom.
La résolution de la fonction à utiliser dépend uniquement du nombre 
et du type des arguments. Par exemple, on peut avoir décidé
de spécialiser un template pour un type particulier.
\begin{lstlisting}
template<typename T> fun (T a)
{
  // Corps de la fonction
}

template<typename T> fun(T* a)
{
  // Corps de la fonction
}

fun(int* a)
{
  // Corps de la fonction
}
\end{lstlisting}
La deuxième fonction \lstinline$fun$ 
est appelée une spécialisation partielle.
La troisième est une spécialisation totale pour le type 
\lstinline$int*$. Les appels suivants sont résolus comme suit:
\begin{lstlisting}
int n;
float* p;
int* q;
fun(n) ; // Utilise le template fun(T a)
fun(p) ; // Utilise le template fun(T* a)
fun(q) ; // Utilise le non template fun(int a)
\end{lstlisting}
Les règles de résolution sont extrêmement compliquées mais elles
donnent en général ce que l'on souhaite: la fonction la plus spécifique
est utilisée: bon nombre d'arguments et chaque argument a un ensemble
de types acceptables inclus dans celui de toutes les autres fonctions.
Par exemple si on a défini les template

\begin{lstlisting}
template<typename T, typename U> fun (T a, U b)
{
  // Corps de la fonction
}

template<typename T, typename U> fun(T* a, U b)
{
  // Corps de la fonction
}

template<typename T, typename U> fun(T a, U* b)
{
  // Corps de la fonction
}
\end{lstlisting}
alors l'appel à \lstinline$fun$ dans
\begin{lstlisting}
double* p;
double* q;
// ...
fun(p,q);
\end{lstlisting}
ne pourra être résolu: aucune des spécialisations n'est plus spécifique
que l'autre pour \textbf{tous} les arguments: la deuxième spécialisation
l'est plus pour le premier argument et la troisième plus pour le deuxième 
argument.

\section{La programmation générique: l'exemple de la STL}\label{chap:template}
Vous avez déjà vu sans le savoir un exemple de programmation
générique: la STL qui est la bibliothèque standard de conteneurs
en \texttt{C++}. La STL a été écrite et conçue par Alex Stepanov. 
La STL n'est pas orientée objet: il n'y a pas de classe
de base abstraite dont hérite chacun des conteneurs. La STL
est un exemple de programmation générique. Pour comprendre
la STL, il faut avant tout comprendre la notion d'itérateurs.

Voyons d'abord comment on ferait une recherche linéaire sur un tableau contigû:
\begin{lstlisting}
unsigned int find(tableau t, int u) 
{
  unsigned int i;
  for(i=0; i<t.size()&& t[i]!=u;i++) 
    ;// do nothing
  return(i);
}
\end{lstlisting}
et comment on ferait typiquement cette même recherche sur une liste
simplement chaînée
\begin{lstlisting}
link* find(liste l, int u) 
{
  for(link* p=liste->head; p!=0 && p->val!=u;p=p->next) 
    ;// do nothing
  return p;
}
\end{lstlisting}
La principale différence vient de la façon dont on itère
sur une liste et de la façon dont on itère sur un tableau.
On avance contigument dans la mémoire dans un tableau 
et on suit des liens dans une liste. Si on pouvait 
avoir une abstraction de l'itération, on pourrait 
utiliser les template pour programmer en une seule fois
find pour tous les conteneurs. Cette abstraction est appelée
itérateur et ce concept est la base du fonctionnement de la 
STL.

Un itérateur est une abstraction: tout type qui se comporte comme
un itérateur est un itérateur. On peut voir un itérateur comme un pointeur
qui se comporte intelligemment. Un itérateur est un objet qui 
pointe vers un élément d'un conteneur. De plus, il existe un certain
nombre d'opérations sur cet itérateur. Les plus utilisées sont
les opérateurs \lstinline$++$ et \lstinline$--$ qui avancent
et reculent respectivement l'itérateur. Les opérateurs de comparaison
\lstinline$==$ et \lstinline$!=$ qui teste
si deux itérateurs sont égaux. Enfin, s'inspirant de la notation de pointeur,
l'opérateur unitaire préfixe \lstinline$*$ retourne le contenu de l'élément
vers lequel pointe l'itérateur.
Pour obtenir un itérateur depuis un conteneur, on dispose des
fonctions membres \lstinline$begin()$ 
qui pointe vers le premier élément
du conteneur et \lstinline$end()$ qui pointe 
vers le non-élément qui se trouve derrière le dernier élément
du conteneur.


Maintenant pour chaque conteneur de la STL, on définit un itérateur
et en utilisant les template, on peut définir pratiquement
n'importe quel algorithme sur les conteneurs en une seule fois pour
tous les conteneurs!
\begin{lstlisting}
template <class Iter,class ValT>
Iter find(Iter first, Iter last, ValT>
{
  Iter p;
  for(p=first;p!=last;p++) {
    if(*p==ValT)
      break;
  }
}
\end{lstlisting} 
et maintenant on peut appeler find grâce à
\begin{lstlisting}
std::vector<int> a;
std::list<float> b;
// Code 
find(a.begin(),a.end(),0);
find(b.begin(),b.end(),0.0);
\end{lstlisting}

La plupart de ces algorithmes sont déjà dans la bibliothèque standard:
utilisez-les! Ce n'est pas peine de les reprogrammer (sauf à titre
pédagogique pour apprendre le \texttt{C++}).

\section{Conclusion}
La programmation générique est un outil très puissant dont nous avons
à peine effleurer la surface. Elle est cependant assez déroutante au
début. Elle permet d'éviter beaucoup de copier coller sans perte de
performance à l'exécution. Un de ses désavantages est qu'elle limite
l'intérêt de la compilation séparée car les template, outil utilisé
partout en programmation générique, doivent être placé dans les
headers. La programmation générique est donc chère en temps de compilation.


\chapter{Conseils et conclusion}
Voici quelques conseils pour la suite.
Limiter le nombre de variables globales. Cela rend la programmation
plus simple au début mais la maintenance deviendra un cauchemar
à terme. Séparer au maximum le code
de haut-niveau et le code de bas-niveau. Créer des fonctions 
paramétrables et limiter le copier-coller. Maintenir le 
\og{}single point of truth\fg{}: si je veux modifier mon programme, une 
petite modification devrait avoir à intervenir dans le moins de 
fichiers possibles et dans le moins d'endroits différents: 
si vous utilisez une constante quelque part, déclarez un 
paramètre \lstinline$const int parametre=10$
et utiliser la constante 
\lstinline$parametre$. 
Si vous modifiez ensuite cette valeur plus tard, 
vous n'aurez alors qu'à la modifier en un seul endroit. 

Nous n'avons fait qu'effleurer le langage \texttt{C++} qui est un
langage énorme. Le moindre livre d'introduction au \texttt{C++} fait
facilement mille pages. Aussi, reste-t-il beaucoup de points qui n'ont
pas pu être abordés ici. Parmi ces points, on trouve entre autres
les exceptions qui sont un moyen de gérer les erreurs, l'héritage multiple, et
les fonctions classes(qui peuvent remplacer les pointeurs sur les fonctions). 
\end{document}

