User Tools

Site Tools


in204:tds:sujets:td4:part2

This is an old revision of the document!


Partie II – Création d’itérateurs

TD4

Nous considérons un ensemble de nombres entiers correspondant à un interval fermé entre [minValue, maxValue] défini par la classe suivante :

class interval
{
private:
	int minValue;
	int maxValue;
 
public:
	typedef int value_type;
	typedef size_t size_type;
        typedef ptrdiff_t difference_type;
 
	interval(int theMinValue, int theMaxValue) : 
		minValue(theMinValue), maxValue(theMaxValue) 
	{}
	interval(const interval& anotherInterval):
		minValue(anotherInterval.minValue), 			 		  
                maxValue(anotherInterval.maxValue)
	{}
	interval& operator = (const interval& anotherInterval)
	{
		minValue = anotherInterval.minValue;
		maxValue = anotherInterval.maxValue;
		return *this;
	}
	size_type size() const
	{
		return (size_type)(maxValue - minValue);
	}
	int operator[](size_type anIndex) const
	{
		if (anIndex > size())
			throw std::out_of_range("Index out of range");
		return minValue + (int)anIndex;
	}
	bool operator == (const interval& anotherInterval) const
	{
		return anotherInterval.maxValue == maxValue &&
			anotherInterval.minValue == minValue;
	}
	bool operator != (const interval& anotherInterval) const
	{
		return anotherInterval.maxValue != maxValue ||
			anotherInterval.minValue != minValue;
	}
};

Nous souhaitons pouvoir définir des itérateurs pour pouvoir itérer sur cet interval. Pour ce faire, nous devons ajouter au moins les méthodes suivantes et champs suivants :

	friend class interval_iterator;
	typedef interval_iterator const_iterator;
	const_iterator begin() const noexcept;
	const_iterator end() const noexcept;

En supposant que la classe itérateur s’appelle interval_iterator. Il ne reste plus qu’à créer une classe interval_iterator dont le squelette serait le suivant :

class interval_iterator
	: public std::iterator <std::forward_iterator_tag, int>
{
private:
	friend class interval;
	const interval* mInterval; // Référence à l'interval.
	int mCurrent; // la valeur courante dont on fait référence.
 
	interval_iterator(const interval& anInterval, int aCurrentValue) : 
		mInterval(&anInterval), mCurrent(aCurrentValue) {}
 
public:
	interval_iterator(const interval_iterator& anotherIterator):
		mInterval(anotherIterator.mInterval),
		mCurrent(anotherIterator.mCurrent) {}
 
	interval_iterator& operator = (interval_iterator& anotherIterator)
	{
		mInterval = anotherIterator.mInterval;
		mCurrent = anotherIterator.mCurrent;
		return *this;
	}
 
	const reference operator*() const;
	const pointer operator->() const;
	interval_iterator& operator++();
	interval_iterator& operator++(int);
	bool operator ==(const interval_iterator&) const;
	bool operator !=(const interval_iterator&) const;
 
};

Question 1.0

Complétez les classes interval et interval_iterator afin de pouvoir supporter les itérateurs.

Correction Complétion de la classe interval

Correction Complétion de la classe interval

Correction Complétion de la classe interval_iterator

Correction Complétion de la classe interval_iterator

  • En ce qui concerne les déclarations des opérateurs et fonctions membres, nous devons définir les opérateurs suivants :
    reference operator*(); 	// retourne la valeur à laquelle l'itérateur fait référence.
    pointer operator->();           // retourne un pointeur sur la valeur à laquelle l'itérateur fait référence.
    iterator& operator++();         // avance à la valeur suivante de la séquence et retourne l'itérateur courant
    iterator operator++(int);       // copie l'itérateur à la position actuelle, avance l'itérateur courant 
                                    // à la valeur suivante de la séquence et retourne la copie de l'itérateur.
     
    bool operator ==(iterator) const;
                                    // compare si l'itérateur courant et l'itérateur passé en argument 
                                    // font référence à la même valeur,
    bool operator !=(iterator, iterator) const;
                                    // compare si l'itérateur courant et l'itérateur passé en argument 
                                    // ne font pas référence à la même valeur,
     


    En ce qui concerne l'opérateur *, il s'agit de l'opération de déréférencement qui va retourner une référence sur la valeur à laquelle l'itérateur fait référence et qui est défini par mCurrent. Le code de cette fonction s'écrit :

        reference operator*() const 
        {
            return mCurrent;
        }


    Par similitude l'opérateur qui retourne un pointeur sur la valeur référencée par l'itérateur va retourner un pointeur sur le champ interne mCurrent.

        reference operator->() const 
        {
            return &mCurrent;
        }



    Il faut désormais implanter les opérateurs d'incrémentation de l'itérateur (ie. pour passer à la valeur suivante). C'est l'opérateur ++ qui a est sélectionné, cependant cet opérateur possède deux syntaxes : (1) ++it qui signifie applique l'opération ++ à l'objet it et retourne une référence à cet objet après que l'opération ++ a été effectuée; (2) it++ qui signifie fait une copie de l'objet copy, applique l'opération à l'objet it et retourne l'objet copy comme résultat de l'opération. L'opérateur operator ++() correspond à la première synataxe, l'opérateur operator ++(int) correspond à la seconde syntaxe. Ce qui se traduit par :

        iterator& operator()
        {
            // Passe à la valeur suivant si nous ne sommes pas
            // déjà à la fin de l'interval.
            if(mCurrent < mInterval->maxValue)
                mCurrent ++;
            return *this;
        }
        iterator operator()
        {
            iterator it(*this); // Crée une copie de l'itérateur.
            ++(*this);          // Incrément l'itérateur courant en appellant
                                // l'opérateur iterator& operator()
            return it;          // Retourne la copie de l'itérateur (avant modification).
        }


    Il ne reste plus qu'à implanter les opérateurs relatifs à la comparaison. Deux itérateurs sont égaux s'ils font références à la même valeur située dans le même containeur. Dans ce cas, nous devons avoir les champs mCurrent et mInterval qui doivent être égaux.

        bool operator ==(const iterator& anotherIterator) const
        {
            return mCurrent == anotherIterator.mCurrent && 
              *mInterval == *anotherIterator.mInterval;
        }
        bool operator !=(const iterator& anotherIterator) const
        {
            return mCurrent != anotherIterator.mCurrent || 
              *mInterval != *anotherIterator.mInterval;
        }
  • Enfin, l'itérateur doit aussi être constructible par recopie, supporter l'affection et supporter les permutations), ce qui impose de définir en complément le constructeur de recopie, les fonctions membres swap et l'opérateur = comme suit:
    public:
        // Définition du constructeur de recopie.
        // Crée un itérateur qui fait référence au même élément que l'itérateur
        // passé en argument.
        interval_iterator(const interval_iterator& anotherIterator):
            mCurrent(anotherIterator.mCurrent), mInterval(anotherIterator.mInterval)
        {}
        // Définition de l'opération d'affectation consistant à ce que 
        // l'itérateur courant fait référence au même élément que l'itérateur
        // passé en argument.
        iterator operator=(const interval_iterator& anotherIterator)
        {
            mCurrent = anotherIterator.mCurrent;
            mInterval = anotherIterator.mInterval;
        } 
        // Opération de permutation. 
        // A la fin de l'opération, 
        // - anotherIterator fait référence à l'élément 
        // qui était référencé par l'itérateur courant avant l'opération,
        // - l'itérateur courant  fait référence à l'élément 
        // qui était référencé par l'itérateur anotherIterator avant l'opération,
        void swap(interval_iterator& anotherIterator)
        {
            std::swap(mCurrent, anotherInterator.mCurrent);
            std::swpa(mInterval, anotherIterator.mInterval);
        }


    Et normalement l'ensemble des éléments ont été définis pour à la classe interval_iterator pour que ce dernier puisse répondre aux exigences auxquelles un itérateur de type forward iterator doit répondre.

  • Question 2.0

    Tester le bon fonctionnement de classe avec le code suivant :

    #include"interval.hpp"
    #include<algorithm>
    #include<iostream>
    #include<vector>
     
    template<class inputIterator>
    void print(inputIterator beginIt, inputIterator endIt)
    {
        if(beginIt == endIt)
        {
            std::cout << "[]" << std::endl;
            return;
        }    
        for(;;)
        {
            std::cout << *beginIt;
            beginIt++;
            if(beginIt == endIt)
                break;
            std::cout << ", ";
        }
        std::cout << "]" << std::endl;
        return;
    }
     
    void testInterval()
    {
        interval inter(5, 15);
        std::cout << "Contenu de l'interval : "; 
        print(inter.begin(), inter.end());
        // Recherche du plus grand élément.
        auto maxIt = max_element(inter.begin(), inter.end());
        std::cout << "Element maximal de la séquence: " << *maxIt << std::endl;
        // Duplication des valeurs dans un vecteur
        std::vector<int> vec(inter.begin(), inter.end());
        std::cout << "Contenu du vecteur : "; 
        print(vec.begin(), vec.end());
    }
     
    int main()
    {
        testInterval();
        return 0;
    }

    Explications

    Explications

    • Dans le cas de la fonction testInterval(), le code
          interval inter(5, 15);
       

      crée un interval allant de 5 à 15. Nous appelons la fonction print en passant l'itérateur référençant la première valeur contenue dans l'interval ainsi que l'itérateur marquant la fin de la séquence et nous vérifions que la fonction print peut bien afficher les valeurs contenues dans l'interval.

          print(inter.begin(), inter.end());

      . Nous vérifions en utilisant une fonction max_element de la bibliothèque standard qui recherche le plus grand élément d'une séquence que notre containeur fonctionne aussi avec des fonctions de la bibliothèque standard.

          auto maxIt = max_element(inter.begin(), inter.end());
          std::cout << "Element maximal de la séquence: " << *maxIt << std::endl;

      Nous affichons l'élément retourné qui est bien entendu la borne supérieure de l'interval. Enfin, nous créons un vecteur auquel nous affectons l'ensemble des valeurs contenues dans l'interval inter. Et nous vérifions que notre fonction print fonctionne aussi avec un containeur de type std::vector.

          // Duplication des valeurs dans un vecteur
          std::vector<int> vec(inter.begin(), inter.end());
          std::cout << "Contenu du vecteur : "; 
          print(vec.begin(), vec.end());
    in204/tds/sujets/td4/part2.1601448231.txt.gz · Last modified: 2020/09/30 06:43 by bmonsuez

    Page Tools