



\documentclass[a4paper,11pt,twoside]{article} %



%langue & fontes
%------------------------------------------------------------------------------------
	\usepackage[frenchb]{babel}
	%francisation du document

	%\usepackage{ucs}
% 	\usepackage[utf8]{inputenc}
	
	\usepackage[latin1]{inputenc}
	%encodage des fichiers prenant en compte les accents dans le texte (iso 8859 pour moi)
	
	\usepackage[T1]{fontenc}
	%encodage moderne des fontes
	
% 	\usepackage{ae} 
% \usepackage[cm]{aeguill}
% 	\usepackage{aeguill}
	%pour avoir les guillemets fr
	
% 	\usepackage{pslatex}

	\usepackage{palatino}
	%autre fonte que le sobre Computer Modern de Knuth

%------------------------------------------------------------------------------------

	\newcommand{\mc}[3]{\multicolumn{#1}{#2}{#3}}

%------------------------------------------------------------------------------------

%outils
%------------------------------------------------------------------------------------
	\usepackage{url}
	\usepackage{amsmath}
	%hyperlinks

%------------------------------------------------------------------------------------
% 	\reversemarginpar 
	\newcommand{\note}[1]{\marginpar{\raggedright\footnotesize\hrule\smallskip\textit{#1}\par\smallskip\hrule}}%
% 	\newcommand{\noter}[1]{\marginpar[\raggedright\footnotesize\hrule\smallskip\textit{#1}\par\smallskip\hrule]{}}%
	%notes dans la marge 
	
	\newcommand{\removenotes}{\renewcommand{\note}[1]{}}


%------------------------------------------------------------------------------------
		
	\usepackage{geometry}
 	\geometry{ hmargin=3.5cm}%,vmargin=4cm}
	%gestion des marges	
	
	\geometry{marginparwidth=2.3cm}
	%ajuste la marge dans laquelle les notes sont Ã©crites

	\addtolength{\headheight}{3pt}
	%augmente la hauteur de la zone de header
	
	\parskip=5pt
	%set des marges avant Â§
%------------------------------------------------------------------------------------


%---------------------------------------------------------------------------------
\usepackage{ifpdf}
%------------------------------------------------------------------------------------
	\tolerance = 1414
	\hbadness = 1414
	\emergencystretch 1.5em
	\hfuzz 0.3pt
	\widowpenalty=10000
	\vfuzz \hfuzz
	\raggedbottom

		\usepackage{multirow}
	%multi ligne dans les tableaux
	\newcommand{\mr}[3]{\multirow{#1}{#2}{#3}}
	
	\usepackage{mdwtab,booktabs,footnote}


	\usepackage{listings}

	\lstloadlanguages{ [ISO]C++}
	\lstset{language=C++}
	\lstset{showstringspaces=false}

		
	\usepackage{fancyhdr}
	\pagestyle{fancyplain}

	


	\lhead{Spécification et réalisation d'une classe générique}
	\rhead{}
	\cfoot{\thepage}



%------------------------------------------------------------------------------------


%gestion des index, des tables et listes
%------------------------------------------------------------------------------------
% 	\ifpdf
% 		\usepackage[pdftex]{thumbpdf}
% 	\fi
	
	
	\ifpdf
		\usepackage[a4paper,pdftex,hyperindex=false,plainpages=false]{hyperref}		
	\else
		\usepackage[a4paper,hypertex,hyperindex=false]{hyperref}
	\fi

	\setcounter{tocdepth}{1}
%------------------------------------------------------------------------------------

\usepackage[nottoc, notlof, notlot, numbib]{tocbibind}

%Page de garde
%------------------------------------------------------------------------------------

	\ifpdf
		\hypersetup{
				pdfauthor   = {Romuald THION},%
				pdftitle    = {Spécification et réalisation d'une classe générique},%
				pdfsubject  = {Exemple de spécification rigoureuse proposée comme exemple},%
				pdfkeywords = {C++, spécification, réalisation, manuel, tests fonctionnels, classe générique, templates, STL},%
		}	
	\fi
%------------------------------------------------------------------------------------
\makesavenoteenv{tabular}


\title{Spécification et réalisation d'une  classe générique}
\author{Romuald THION}
\date{2007}

\begin{document}



\maketitle

	\begin{abstract}
	Ce document est un exemple de document de spécification et de réalisation d'une classe générique simple en C++. \`A partir d'un cahier des charges sommaire, nous définissons les fonctionnalités proposées par la classe. Une particularité de cette classe est qu'elle est paramétrée selon deux types de données. La spécification doit donc faire abstraction des types et n'utiliser que des propriétés supposées connues pour ces types. La réalisation fait appel aux templates C++ et aux concepts de la Standard Template Library (STL). La classe \emph{paire} que nous spécifions est disponible dans les utilitaires fournis par la STL.
	\end{abstract}


\tableofcontents

% \thispagestyle{plain}
\thispagestyle{empty}

	\newpage

	\section{Introduction}
	
	Vérifier la correction d'un programme, d'un algorithme, c'est s'assurer qu'il fait bien ce que l'on a prévu qu'il fasse. L'étape de spécification d'un programme est donc fondamentale en génie logiciel : un programme n'est correct que vis-à-vis de ses spécifications. C'est donc par là qu'il faut commencer pour réussir un projet informatique, c'est probablement pourquoi tout le monde s'en passe.


	Ce document a deux objectifs :


	\begin{itemize}
		\item d'une part, illustrer ce qu'est une spécification sur un cas relativement simple. Cet exemple reste \emph{un} exemple et n'est en aucun cas une forme canonique qu'il faut suivre les yeux fermés,
		\item d'autre part, introduire des notions de programmation générique (c'est à dire l'utilisation de templates) issues du standard C++~\cite{ISO14882} et utilisées dans les spécifications de la STL.% (que ce soit des conteneurs, itérateurs, algorithmes ou autres).
	\end{itemize}


	Le cas d'étude choisi est une classe générique simple : la \emph{paire}. C'est une classe auxiliaire définie dans le chapitre 20.2.2 du standard C++ ISO 14882:2003~\cite{ISO14882}.
	
% 	Afin d'illustrer cette étape%
	
% 	

	\section{Cahier des charges}

	Le cahier des charges peut être exprimé en des termes confus, ambigus voire contradictoires. Nous considérons pour cet exemple que le client a donné le cahier des charges lapidaire suivant :
	
	
	\begin{quotation}
	\textit{Nous souhaitons un outil C++ permettant de gérer des paire de données, dans le but de simplifier certains de nos développements. Nous voulons un type de données qui à partir de données existantes, crée un doublet d'éléments. \note{Cet exemple de cahier des charges est relativement artificiel.} Nous voulons pouvoir manipuler les tuples avec simplicité, comme des entiers par exemple, sans toutefois proposer toutes les opérations des entiers, on ne souhaite pas ajouter ou soustraire des doublets directement par exemple. De plus nous souhaitons que la classe soit générique, performante et qu'un minimum de conditions soient imposées quant aux données du tuple. Des outils facilitant la création de doublet arbitrairement choisis devraient être proposés.}
	\end{quotation}


	
	Un échange avec le client s'avère ici inévitable, la profusion et la diversité des termes employés à plus ou moins bon escient nécessite de clarifier la pensée de la maîtrise d'ouvrage. \note{C'est l'étape où des choix doivent être proposés au client.}La notion de \emph{paire} semble prévaloir dans les besoins, le produit que nous allons spécifier va donc être \og{} une paire\fg{}, mais de quels types de données ? Avec quelles fonctionnalités offertes ? Quelles sont les conditions acceptables sur les types d'entrée ? Nous supposons par la suite que l'étape de dialogue/négociation préalable a été menée a bien, et que le client accepte les spécifications qui suivent. 


	\section{Spécification}
% La maîtrise d'\oe{}uvre que nous représentons ici a abouti après accord aux spécifications suivantes

	L'action de \emph{spécifier} consiste à décrire avec précision les caractéristiques du produit que nous allons réaliser, dans notre cas un produit logiciel et même plus précisement une \emph{classe générique}.
	
	Nous allons tâcher de clarifier les notions évoqués, \note{Ne pas aller à l'encontre du cahier des charges.} en prenant en compte les critères demandés par le client comme la possibilité de manipuler simplement la classe et de définir un minimum de conditions en contrat. Cette section va commencer par établir les définitions des \emph{concepts} préalables à la spécification de la classe générique \emph{paire}. %(construction, relations entre objets)

	


	\subsection{Définitions des concepts}

	\note{Les spécifications pourraient être réalisées dans un autre langage de programmation que le C++, pourvu qu'il soit orienté objet à base de classes et supportant la programmation générique.}
	 Les \emph{concepts} sont des propriétés abstraites définies sur des types de données. Ces propriétés sont utilisées pour définir les contrats sur les méthodes de la paire.  Les concepts que nous présentons ici sont issus de la STL et utilisés courament dans la définition de classes de la bibliothèque standard (exemple : dans les conteneurs ou les algorithmes). Les définitions proposées permettent d'utiliser sans ambiguïtés des notions abstraites, évitant ainsi les répétitions et les risques de confusion. % Ce sont des outils majeurs de la programmation générique.		
	%\note{Ces définitions sont exposées en langue naturelle mais pourraient être aussi bien exprimées en logique mathématique.}
	
	%Notons que les spécifications pourraient être réalisées dans un autre langage de programmation que le C++, pourvu qu'il soit orienté objet à base de classes et supportant la programmation générique.% (templates).


	Soit T un \emph{type de données} :
	\begin{itemize}
	\item  T est dit \emph{assignable} s'il est possible
			\begin{enumerate}
			\item de \emph{copier} des données de ce type, définition du constructeur de copie, \verb|T(const T& t)| en C++,  \note{Nous \og{} trichons \fg{} en utilisant la dialectique et les prototypes du C++.}
			\item et d'\emph{assigner} des donnése de ce type aux variables, définition de la surcharge de l'opérateur d'affectation, \verb|T & operator=(const T& t)| en C++.
			\end{enumerate}
	
	
	
	\item T est dit \emph{constructible par défaut} si le constructeur par défaut est défini pour T, \verb|T(void)| en C++. \note{L'anti-symétrie forte , $a \mathcal{R} b $ implique $ \neg (b \mathcal{R} a)$,  d'une relation d'ordre strict est un théorème de la transitivité et de l'irréflexivité.}

% 	\note{Il pourrait être préférable, selon le cas, de se limiter au langage mathématique.}

	\item T est dit \emph{comparable} s'il est possible de comparer deux données de type T avec l'opérateur \verb|==| et si \verb|==| est une \emph{relation d'équivalence} : transitive\footnote{$a \mathcal{R} b \wedge b \mathcal{R} c$ implique $a \mathcal{R} c$}, symétrique\footnote{$a \mathcal{R} b$ implique $b \mathcal{R} a$.} et réflexive\footnote{$a \mathcal{R} a$ pour tout $a$.}.

	\item T est dit \emph{ordonnable} s'il est possible de comparer deux données de type T avec l'opérateur \verb|<| et si \verb|<| est une \emph{relation d'ordre strict} : transitive et irréflexive \footnote{$\neg (a \mathcal{R} a)$ a pour tout $a$.}. 

	\end{itemize}


	Une type T est dit \emph{convertible} en un type T$^\prime$ s'il existe une application qui à toute donnée de type T fasse correspondre une donnée de type T$^\prime$.

	\subsection{Spécification de la paire}

	
	%(et qui sont généralement repris dans toutes les structures et concepts fournis par la STL)
	\`A partir des concepts précédemment définis, \note{Le type \emph{paire} est générique.} nous allons pouvoir définir la paire proprement dite. Nous désignerons par $p$ la paire courante sur laquelle sont invoquées les méthodes.

	\subsubsection*{Définition et construction}

	\begin{itemize}
	\note{Ne connaissant pas les types de données à l'avance nous pouvons seulement supposer des propriétés que ces types respectent par contrat.}
	\item Une \emph{paire} est une \emph{classe} paramétrée selon deux types T1 et T2, donnés à la déclaration de la paire.\\
	\textbf{Contrat} : les deux types T1 et T2 sont \emph{assignables}.

	

	\item Une paire \emph{contient} deux objets : un objet de type T1, nommé \emph{premier membre}, et un autre de type T2, comme \emph{second membre}.
	\item Les deux membres d'une paire sont accessibles publiquement.

	\item Une paire est constructible grâce :
		\begin{itemize}
		\item \emph{au constructeur par défaut}, qui invoque les constructeurs par défauts respectifs des types T1 et T2 pour le premier et le second membre de $p$.\\
		\textbf{Contrat} : ce constructeur requiert que les types T1 et T2 soient \emph{constructibles par défaut}.
	
\note{On devrait également définir l'opérateur d'affectation pour les paires.}	

		\item \emph{au constructeur principal}, qui prend en paramètre un objet $a$ constant de type T1 et un objet $b$ constant de type T2. Ce constructeur copie $a$ dans le premier membre de $p$ et copie $b$ dans le second membre de $p$,



		\item \emph{au constructeur de copie}, qui prend en paramètre une paire constante $p^\prime$ de types U1 et U2. Ce constructeur copie le premier membre de $p^\prime$ dans le premier membre de $p$ et copie le second membre de $p^\prime$ dans le second membre de $p$. Les types U1 et U2 sont implicitement convertis en type T1 et T2.\\
		\textbf{Contrat} :  le type U1 doit être convertible en type T1 et le type U2 doit être convertible en type T2.
% 		\item à une 
		\end{itemize}
	\end{itemize}
	 \note{La relation d'infériorité ne paraît pas très naturelle mais a pour intérêt de ne pas faire intervenir la relation d'égalité dans sa définition.}
	\subsubsection*{Relations entre paires}


	\begin{itemize}
	
	\item Une paire $a$ est \emph{égale}  à une paire $b$ (opérateur \verb|==|) \note{Il s'agit d'un ordre lexicographique.}si et seulement si le premier membre de $a$ est égal au premier membre de $b$ et que le second membre de $a$ est égal au second membre de $b$.\\ 
	\textbf{Contrat} :  l'égalité des paires requiert que les types T1 et T2 soient \emph{comparables}.



	\item Une paire $a$ est \emph{inférieure} à une paire $b$  (opérateur \verb|<|) si et seulement si le premier membre de $a$ est inférieur au premier membre de $b$  ou si le premier membre de $b$ n'est pas inférieur au premier membre de $a$ et que le second membre de $a$ est inférieur au second membre de $b$.\\
% 		\begin{itemize}
% 			\item si le premier membre de $a$ est inférieur au premier membre de $b$
% 			\item ou si le premier membre de $b$ n'est pas inférieur au premier membre de $a$ et que le second membre de $a$ est inférieur au second membre de $b$.
% 		\end{itemize}
% % 	le premier membre de $a$ est inférieur au premier membre de $b$, et n'est \emph{pas} inférieure si le premier membre de $b$ est inférieur au premier membre de $a$. Si aucun de ces deux cas ne se présente (premiers membres égaux notamment), $a$ est inférieure à $b$ si le second membre de $a$ est inférieur au second membre de $b$.\\
	\textbf{Contrat} : l'infériorité des paires requiert que les types T1 et T2 soient \emph{ordonnables}.
	\end{itemize}

	%\note{En mathématique, la sémantique d'une formule est le \emph{sens} qu'on lui donne, comment on l'interprète.}
	Les autres relations (opérateurs \verb|!=|, \verb|>|, \verb|<=| et \verb|>=|) entre deux paires $a$ et $b$ sont définissables à partir des relations d'égalité et d'infériorité. Ces autres relations sont donc des formes syntaxiques de commodité dont les sémantiques sont définies par :
	
		\begin{itemize}
			\item $a \mathtt{!\!=} b \equiv \neg(a \mathtt{==} b)$
			\item $a \mathtt{>} b \equiv b \mathtt{<} a$\note{D'aucun préférerait $\neq$, $>$, $\leq$ et $\geq$.}
			\item $a \mathtt{<=} b \equiv \neg(b \mathtt{<} a)$
			\item $a \mathtt{>=} b \equiv \neg(a \mathtt{<} b)$
		\end{itemize}
		

	

	\note{Techniquement donc, la réalisation de cette classe peut se résumer à  un \texttt{\#include} et un \texttt{typedef}.}
	La spécification que nous proposons au client est en fait la classe \texttt{pair<T1,T2>}\footnote{\url{http://www.sgi.com/tech/stl/pair.html}}, qui fait partie des outils proposés dans le header \verb|<utility>| de la STL. Dans la suite de ce document, nous considérerons que la paire est celle de la STL définie dans le standard du C++.


	La section suivante est un exemple de manuel d'utilisation de la paire, nous y décrivons la classe et proposons des exemples d'utilisation.



% 	\newpage
	\section{Manuel d'utilisation}

	

	\subsection{Définition}

	La classe paire de la catégorie utilitaires de la STL est définie dans le header standard \verb|<utility>| et dans le header non-standard maintenu pour compatibilité \verb|<pair.h>|.

	\subsection{Description}


	Une \emph{paire} \verb|pair<T1,T2>| est une classe paramétrée selon deux types T1 et T2 \emph{assignables}, donnés à la déclaration de la paire, voir tableau~\ref{tab:types}. Une paire contient deux objets accessibles publiquement : un objet de type T1, nommé \emph{premier membre}, et un autre de type T2, comme \emph{second membre}. Le tableau~\ref{tab:members} décrit les membres de la classe paire.


	Une paire n'est pas un \emph{conteneur} au sens de la STL car elle ne respecte pas les spécifications d'un conteneur, entre autres, la paire ne fournit pas d'itérateurs sur ses éléments.

	

	\begin{table}
		\centering
		\begin{tabular}[ht]{ll}
		\textbf{Paramètre}& \textbf{Description}\\
		\toprule
		T1&Le type du premier membre de la paire\\
		T2&Le type du second membre de la paire\\		
	\bottomrule
		\end{tabular}
 		
	\caption{Paramètres de type de la classe paire}
	\label{tab:types}	
	\end{table}

	\subsection{Paramètres de type}


	


	Les types T1 et T2 doivent être \emph{assignables}. Les opérations supplémentaires requièrent des conditions supplémentaires. Le constructeur par défaut de la paire requiert que T1 et T2 soient \emph{constructibles par défaut}, l'opérateur \verb|==| requiert que T1 et T2 soient \emph{comparables}, l'opérateur \verb|<| requiert que T1 et T2 soient \emph{ordonnables}.


% 	\subsection{Membres}
% 




	\begin{table}
		\centering
		\begin{tabular}[hb]{@{}>{\scriptsize\ttfamily}p{0.45\textwidth}@{}p{0.55\textwidth}@{}}
		\normalsize\rmfamily\textbf{Membre}& \textbf{Description}\\
		\toprule
		first\_type&alias pour le premier type\\
		second\_type&alias pour le second type\\
		\midrule		
		first&le premier membre public de la paire\\
		second&le second membre public de la paire\\
		\midrule
		pair()&constructeur par défaut, requiert que T1 et T2 soient constructibles par défaut\\
		pair(const T1\& \_\_a, const T2\& \_\_b)&constructeur principal, requiert que T1 et T2 soient assignables\\
		pair(const pair<\_U1, \_U2>\& \_\_p)&constucteur de copie. Convertit implicitement U1 en T1 et U2 en T2.\\
		pair\& operator=(const pair\&)&opérateur d'affectation, par défaut\\
		\midrule
		template <class T1, class T2> bool operator==(const pair\&, const pair\&)&relation d'égalité entre paires, requiert que T1 et T2 soient comparables\\
		template <class T1, class T2> bool operator<(const pair\&, const pair\&)&relation d'infériorité entre paires, requiert que T1 et T2 soient ordonnables\\
	\bottomrule
		\end{tabular}
 		
	\caption{Membres de la classe paire}
	\label{tab:members}	
	\end{table}


	\subsection{Exemple d'utilisation}


	%\subsubsection{Valeurs de retours}




Dans la STL par exemple, la méthode \verb|insert(const value_type& x)| de la classe générique \verb|set| \note{Plus généralement tout conteneur de type Unique Associative Container dispose d'une méthode \texttt{insert} qui retourne une paire.} retourne comme type \verb|pair<iterator, bool>|. Le second membre de la paire indique si l'élément a été ajouté ou s'il existe déjà, le premier membre est un itérateur qui pointe soit là où a eu lieu l'insertion soit sur l'élément déjà existant. Il s'agit d'un exemple d'utilisation où la paire est utilisée pour retourner deux valeurs, comme dans l'exemple suivant :

	\begin{scriptsize}	
	\begin{lstlisting}
#include <utility>
...
pair<bool, double> result = do_a_calculation();
if (result.first)
  do_something_more(result.second);
else
  report_error();

	\end{lstlisting}
	\end{scriptsize}

	

	\subsection{Voir aussi}

% 	\subsection{Modèle}
% 	\verb|Assignable|, \verb|EqualityComparable| et \verb|LessThanComparable|.
	
Concepts \emph{assignable}, \emph{constructible par défaut}, \emph{ordonnable} et \emph{comparable}.


\subsection{Exemple d'application}

	L'exemple suivant illustre l'utilisation de deux paires :

	\begin{scriptsize}	
	\begin{lstlisting}
#include <iostream>		// cout
#include <cstdlib>		// EXIT_SUCCESS
#include <utility>		// pair<T1,T2>
#include <string>		// string

using namespace std;
int main()
{
	pair<string,int> r;
	// Crée une paire vide qui contient une chaîne et un entier.
	pair<string,int> p("bye", 18);
	// Une paire initialisée chaîne-entier			
		
	cout << "La paire p contient " << p.first << " et " << p.second << endl;
	// affichage : 
	//La paire p contient bye et 18

	cout << "La paire r contient " << r.first << " et " << r.second << endl;
	// affichage : 
	//La paire r contient  et 0

	r=pair<string,int>("hello", 17);
	// réaffectation de r
	cout << "La paire r contient " << r.first << " et " << r.second << endl;
	// affichage : 
	//La paire r contient hello et 17

	cout << "p et r sont elles égales ? " << ((p==r)?"oui":"non")<<endl;
	// affichage :
	//p et r sont elles égales ? non
		
	p = r; 
	//copie le contenu de r dans p
	cout << "p et r sont elles égales ? " << ((p==r)?"oui":"non")<<endl;
	// affichage :
	//p et r sont elles égales ? oui
	cout << "p est elle inférieure à r ? " << ((p<r)?"oui":"non")<<endl;
	// affichage :
	//p est elle inférieure à r ? non

	r.second++;
	//on modifie le second membre de r
	cout << "p est elle inférieure à r ? " << ((p<r)?"oui":"non")<<endl;
	// affichage :
	//p est elle inférieure à r ? oui
	
	return EXIT_SUCCESS;
}
	\end{lstlisting}
	\end{scriptsize}


	\section{Réalisation}

	
	L'étape de conception en informatique est celle où sont fait les choix pour la réalisation des spécifications, c'est dans cette étape qu'on détermine la meilleure structure de données pour avoir de bonnes performances par exemple. Dans cet exemple, la conception est quasiment inexistante, à part peut être le choix des méthodes en ligne (\verb|inline|) pour efficacité.

	\note{\`A vrai dire, l'auteur à rétro-spécifié la classe paire et traduit des documents existants.}

	La réalisation est extraite du header standard de la STL \verb|stl_pair.h|, situé (selon version de gcc, ici la 4.1.3) dans \verb|/usr/include/c++/4.1.3/bits/|. Les modifications apportées pour l'exemple concernent la suppression des informations de licence, la traduction des commentaires et la suppression de la fonction globale \verb|make_pair|.  Ce code ne respecte pas les conventions du guide de style C++ IF.



	

	 %\lstinputlisting{../Collection.cpp}

 
	%\lstset{numbers=left, numberstyle=\tiny, stepnumber=2, numbersep=5pt}
	\note{En C++, la seule différence entre une classe et une structure est la visibilité par défaut des membres.}
	\note{En C++, le mot-clef \texttt{class} utilisé dans les paramètres de template peut-être remplaçé par \texttt{typename}.}
	\begin{scriptsize}	
	\begin{lstlisting}
#ifndef _PAIR_H
#define _PAIR_H 1

namespace std
//la paire est définie dans le namespace standard de la stl
{
	// une paire contient deux objets de types arbitraires passés en paramètres
	template<class T1, class T2>
	struct pair{
		typedef T1 first_type;	//  alias pour le premier type
		typedef T2 second_type;	//  alias pour le second type
		
		T1 first;		// le premier membre de la paire
		T2 second;		// le second membre de la paire
	
		pair() : first(), second() { }
		//constructeur par défaut, requiert que
		//T1 et T2 soient constructibles par défaut
	
		pair(const T1& __a, const T2& __b) : first(__a), second(__b) { }
		//constructeur principal, requiert que
		//T1 et T2 soient assignables
		
		template<class _U1, class _U2>
		pair (const pair<_U1, _U2>& __p) :
			first(__p.first), second(__p.second) { }
		//constucteur de copie de la classe paire elle même
		//requiert que T1 et T2 soient assignables
	};//struct pair
	
	
	template<class T1, class T2>
	inline bool operator==(const pair<T1, T2>& __x, const pair<T1, T2>& __y)
		{ return __x.first == __y.first && __x.second == __y.second; }
	//deux paires sont égales ssi leurs membres respectifs sont égaux
	//requiert que T1 et T2 soient comparables
	
	template<class T1, class T2>
	inline bool operator<(const pair<T1, T2>& __x, const pair<T1, T2>& __y)
		{ return __x.first < __y.first
			|| (!(__y.first < __x.first) && __x.second < __y.second); }
	//définition membre à membre de la relation d'infériorité
	//requiert que T1 et T2 soient ordonnables

	template<class T1, class T2>
	inline bool operator!=(const pair<T1, T2>& __x, const pair<T1, T2>& __y)
		{ return !(__x == __y); }
	//définition basée sur l'opérateur ==
	
	template<class T1, class T2>
	inline bool operator>(const pair<T1, T2>& __x, const pair<T1, T2>& __y)
		{ return __y < __x; }
	//définition basée sur l'opérateur <
	
	template<class T1, class T2>
	inline bool operator<=(const pair<T1, T2>& __x, const pair<T1, T2>& __y)
		{ return !(__y < __x); }
	//définition basée sur l'opérateur <
	
	template<class T1, class T2>
	inline bool operator>=(const pair<T1, T2>& __x, const pair<T1, T2>& __y)
		{ return !(__x < __y); }
	//définition basée sur l'opérateur <
} // namespace std
#endif /* _PAIR_H */
	\end{lstlisting}
	\end{scriptsize}


\subsection{Fonction outil supplémentaire}

	Par commodité, par exemple quand on manipule des dictionnaires, une fonction globale \verb|make_pair( T1 x, T2 x)| est proposée dans la STL. Elle prend en paramètre un objet constant de type T1 et un objet constant de type T2 et retourne une paire de types T1 et T2 en utilisant le constructeur principal :


	\begin{scriptsize}	
	\begin{lstlisting}
template<class _T1, class _T2>
inline pair<_T1, _T2> make_pair(_T1 __x, _T2 __y)
	{ return pair<_T1, _T2>(__x, __y); }
	\end{lstlisting}
	\end{scriptsize}
	\note{Attention donc lors de l'utilisation de \texttt{make\_pair} avec de \og{} gros\fg{} objets.}
	Pour des raisons techniques, cette fonction prend désormais (version 2003 du standard C++~\cite{ISO14882}) ses paramètres par valeur et non par référence constante. En effet le choix initial posait des problèmes lors du passage de chaînes de caractères  constantes\footnote{\url{http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html\#181}}.


\section{Tests fonctionnels}
	
%         /libstdc++-v3/testsuite/20_util/pairs.cc

	
	
	La \verb|libstdc++| du GNU dispose d'une batterie de tests \note{Au total la batterie comporte une trentaine de tests pour la classe paire.} pour la collection de compilateurs gcc et la STL. L'outillage et les options de configurations de cette batterie sont relativement complexes et ne peuvent être détaillés ici. Les vérifications effectuées sur la paire concernent principalement les types passés en paramètres, la correction des constructeurs et des deux opérations principales. Le plan de tests croise les vérifications selon trois aspects : 

	%Cependant, nous parmi les tests effectués, on croise les vérifications 


	


	\begin{enumerate}
	\item  le fonctionnement avec comme type en paramètre :
		\begin{itemize}
		\item \verb|int|,
		\item \verb|float|,
		\item \verb|const char *|,
		\item \verb|gnu_obj|, un type construit minimal,
		\item \verb|gnu_t|, un type construit minimal générique,
		\end{itemize}

	 \item selon que les types T1 et T2 soient :
		\begin{itemize}
		\item homogènes,
		\item hétérogènes,
		\item \verb|const|,
		\item \verb|const &|,
		\end{itemize}
	
	\item pour les méthodes :
		\begin{itemize}
		 \item le constructeur principal de \verb|pair|,
		\item la fonction \verb|make_pair|,
		\item l'algorithme générique \verb|swap|, qui permet d'intervertir deux objets.
% 		\item de la méthode générique \verb|move|, qui permet de décaler des objets et qui sera introduite dans le prochain standard C++.
		\end{itemize}

	\end{enumerate}

	\note{Le header standard \texttt{<cassert>} permet d'utiliser la fonction \texttt{assert(c)} qui évalue l'expression \texttt{c} passée en paramètre. Si \texttt{c} est évaluée à faux, alors \texttt{assert} affiche un message sur la sortie d'erreur standard et appelle \texttt{abort()} qui arrête l'exécution du programme. Si \texttt{c} est évaluée à vrai, l'exécution continue.}
	\`A titre d'exemple, voici la réalisation des tests\footnote{\url{http://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/testsuite/20_util/pair}} pour le cas où les types en paramètres sont hétérogènes. \verb|VERIFY()| est une macro proche de la fonction \verb|assert()| : le test est validé si la condition en paramètre est évaluée à vrai.
%: elle vérifie que la condition passée en paramètre est vraie

	\begin{scriptsize}	
	\begin{lstlisting}
#include <utility>

class gnu_obj
{
  int i;
public:
  gnu_obj(int arg = 0): i(arg) { }
  bool operator==(const gnu_obj& rhs) const { return i == rhs.i; }
  bool operator<(const gnu_obj& rhs) const { return i < rhs.i; }
};

template<typename T>
  struct gnu_t
  {
    bool b;
  public:
    gnu_t(bool arg = 0): b(arg) { }
    bool operator==(const gnu_t& rhs) const { return b == rhs.b; }
    bool operator<(const gnu_t& rhs) const { return int(b) < int(rhs.b); }
  };

// heterogeneous
void test01()
{
  std::pair<bool, long> p_bl_1(true, 433);
  std::pair<bool, long> p_bl_2 = std::make_pair(true, 433);
  VERIFY( p_bl_1 == p_bl_2 );
  VERIFY( !(p_bl_1 < p_bl_2) );

  std::pair<const char*, float> p_sf_1("total enlightenment", 433.00);
  std::pair<const char*, float> p_sf_2 = std::make_pair("total enlightenment",
							433.00);
  VERIFY( p_sf_1 == p_sf_2 );
  VERIFY( !(p_sf_1 < p_sf_2) );

  std::pair<const char*, gnu_obj> p_sg_1("enlightenment", gnu_obj(5));
  std::pair<const char*, gnu_obj> p_sg_2 = std::make_pair("enlightenment", 
							  gnu_obj(5));
  VERIFY( p_sg_1 == p_sg_2 );
  VERIFY( !(p_sg_1 < p_sg_2) );

  std::pair<gnu_t<long>, gnu_obj> p_st_1(gnu_t<long>(false), gnu_obj(5));
  std::pair<gnu_t<long>, gnu_obj> p_st_2 = std::make_pair(gnu_t<long>(false),
							  gnu_obj(5));
  VERIFY( p_st_1 == p_st_2 );
  VERIFY( !(p_st_1 < p_st_2) );
}
	\end{lstlisting}
	\end{scriptsize}

	Tester des classes génériques peut s'avérer délicat, en raison du niveau l'abstraction élevé des spécifications. Des méthodologies de tests appliquées à la programmation générique sont proposées dans~\cite{Vandevoorde03}. La bibliothèque Boost propose notamment des outils facilitant les tests de programmes génériques\footnote{\url{http://www.boost.org/libs/libraries.htm\#Correctness}} qui permettent de vérifier des concepts~\cite{Abrahams04}.  


	\section{Remarques}

	


	\subsection{Rigueur des spécifications}
	La rigueur des spécifications présentées dans ce document dépasse largement celle attendue dans un compte rendu de TP du département et même dans l'industrie. En revanche, elle est souhaitable, voire exigée, dans les publications scientifiques, les ouvrages de référence~\cite{Stroustrup97,Breymann02} ou les standards~\cite{ISO14882}.


	

	%le constructeur principal et la fonction \verb|make_pair|

%

	\subsection{Ressources en ligne}
	La majeure partie de ce document est une traduction de la documentation de la STL \emph{originale} de Silicon Graphics disponible en ligne \footnote{\url{http://www.sgi.com/tech/stl/}}, c'est une ressource de référence. Le tableau~\ref{tab:corr} donne à ce propos les correspondances entre les termes que nous avons utilisé dans le document et ceux de la STL. La faq de la librarie standard GNU est également une documentation de référence exhaustive. Par exemple, l'implémentation de l'opérateur \verb|<| y est commentée.\footnote{\url{http://gcc.gnu.org/onlinedocs/libstdc++/20_util/howto.html\#pairlt}}
%http://www.research.att.com/~bs/


	\subsection{\'Edition du document}

	Ce document a été réalisé avec \LaTeXe{} avec l'éditeur Kile de KDE. Il est sous licence GPL. Les sources sont disponibles auprès de l'auteur.

	\begin{savenotes}

	\begin{table}
		\centering

		\begin{tabular}[b]{cc}
		\textbf{Terme du document}& \textbf{Terme de la STL}\\
	\toprule
		paire&\texttt{pair}\\%\footnote{\url{http://www.sgi.com/tech/stl/pair.html}}\\
		assignable & \texttt{Assignable} \footnote{\url{http://www.sgi.com/tech/stl/Assignable.html}}\\
	 	constructible par défaut&\texttt{DefaultConstructible} \footnote{\url{http://www.sgi.com/tech/stl/DefaultConstructible.html}}\\
		comparable&\texttt{EqualityComparable} \footnote{\url{http://www.sgi.com/tech/stl/EqualityComparable.html}}\\
		ordonnable&\texttt{LessThanComparable} \footnote{\url{http://www.sgi.com/tech/stl/LessThanComparable.html}}\\
	\bottomrule
		\end{tabular}
 		
	\caption{Correspondance entre les termes du document et ceux de la STL}
	\label{tab:corr}	
	\end{table}


	\end{savenotes}


% 	\addcontentsline{toc}{section}{Références}

 	\nocite{*}
	\bibliographystyle{unsrt}
	\bibliography{Specs_Classe_Generique}
	
	\newpage
	\section{Annexe}	

	\subsection{Pourquoi un constructeur de copie template ?}
Le constructeur de copie de la classe paire est défini ainsi :
\begin{scriptsize}	
\begin{lstlisting}
	template<class _U1, class _U2>
		pair (const pair<_U1, _U2>& __p) ...
\end{lstlisting}
\end{scriptsize}

Il s'agit d'une méthode membre générique définie dans une classe générique. La justification de ce choix est l'item 45 de~\cite{Meyers} : \emph{Use member function template to accept ``all compatible types''}. Cette technique, appelée ``generalized copy constructor'' permet de construire une paire de type  \verb|pair<T1,T2>| à partir de types \verb|pair<_U1, _U2>| \emph{quelconques}, pourvu que U1 et U2 soient convertibles en types T1 et T2 respectivement.
%  En effet, avec une fonction non générique, on ne pourrait pas consruire une paire de flottants à partir d'une paire d'entiers. La




\end{document}
