Differences

This shows you the differences between two versions of the page.

--- in204:tds:sujets:td4:part1 [2019/10/15 09:29]
bmonsuez [Question n°1.2]
+++ in204:tds:sujets:td4:part1 [2022/11/18 10:49] (current)
@@ Line 90: / Line 90: @@
 </code>
 <hidden Explication & correction>
 <code cpp>
@@ Line 107: / Line 108: @@
         const Allocator& alloc = Allocator() );
 </code>
-</hidden>
 Le compilateur identifie ''int[]'' comme étant un ''int*'' qui se respecte les exigences définies par  [[https://en.cppreference.com/w/cpp/named_req/InputIterator|input iterator]]. Comme le tableau contient 8 éléments, ''myints+8'' définit un pointeur qui pointe sur l'élément qui se trouverait à l'indice ''8'', soit ''myints[8]''. Cependant, cet élément n'existe pas ! C'est bien un élément situé après le dernier élément dans le tableau ''myints'' qui est ''myints[8]'' et qui est référencé par le pointeur ''myints+7''. En conséquence, ''myints+8'' marque bien la fin de la séquence, puisque c'est l'itérateur qui suit le dernier itérateur valide de la séquence.
@@ Line 126: / Line 126: @@
 </code>
-à l'exception que l'itérateur ''up' ayant pour type ''std::vector<int>::iterator'' doit supporter l'opération ''-'' dite différence de position. Cette opération n'est pas disponible pour tous les types d'itérateurs . Elle n'est en fait que disponible pour les itérateurs qui respectent les exigences définies par [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|random access iterator]], ce qui est le cas pour l'itérateur de ''std::vector<int>::iterator'' défini dans [[https://en.cppreference.com/w/cpp/container/vector|std::vector]].
+à l'exception que l'itérateur ''up'' ayant pour type ''std::vector<int>::iterator'' doit supporter l'opération ''-'' dite différence de position. Cette opération n'est pas disponible pour tous les types d'itérateurs . Elle n'est en fait que disponible pour les itérateurs qui respectent les exigences définies par [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|random access iterator]], ce qui est le cas pour l'itérateur de ''std::vector<int>::iterator'' défini dans [[https://en.cppreference.com/w/cpp/container/vector|std::vector]].
 Si nous souhaitons utiliser un autre containeur comme par exemple le containeur [[https://en.cppreference.com/w/cpp/container/set|std::set]], nous pouvons écrire le code suivant :
@@ Line 157: / Line 157: @@
 </code>
+En fait, cette boucle peut-être effectuée par un appel à la fonction  [[https://en.cppreference.com/w/cpp/iterator/distance|std::distance]] définie dans le fichie d'entête [[https://en.cppreference.com/w/cpp/header/algorithm|<algorithm>]], ce qui réduit le code précédent à :
+<code cpp>
+	std::set<int> intSet(v.begin(), v.end());
+	auto upSet = upper(intSet.begin(), intSet.end(), 20);
+        std::cout << "First value greater than 20  at position "
+                  << std::distance(v.begin(), upSet) << std::endl;
+</code>
+L'intérêt de faire appel à la fonction [[https://en.cppreference.com/w/cpp/iterator/distance|std::distance]] qui a pour protopye :
+<code cpp>
+template<class inputIterator>
+typename std::iterator_traits<inputIterator>::difference_type
+    distance(inputIterator first, inputIterator last);
+</code
+est de laisser le compilateur sélectonner l'algorithme le plus efficace pour calculer le nombre d'itérations nécessaires pour aller du premier itérateur ''first'' au second itérateur ''last''. Si les itérateurs sont des itérateurs respectant les exigences relatives à un [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|random access iterator]], dans ce cas, le code exécuté sera équivalent à :
+<code cpp>
+    return last - first;
+</code>
+Par contre si l'itérateur n'est pas un [[https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator|random access iterator]], l'itérateur est supposé être un [[https://en.cppreference.com/w/cpp/named_req/InputIterator|input iterator]] et en conséquence le code exécuté est similaire au suivant :
+<code cpp>
+    std::iterator_traits<inputIterator>::difference_type position = 0; //upSet - v.begin()
+    for(auto it = intSet.begin(); it != upSet; it++) { position ++; }
+    return position.
+</code>
+En fait, la classe [[https://en.cppreference.com/w/cpp/iterator/iterator_traits|std::iterator_traits]] permet d'accéder plus simplement et de manière homogène aux champs des itérateurs ou des éléments assimilés à des itérateurs comme les pointeurs. Cette classe expose plusieurs définitions de type et notamment la définition de type qui s'avère être ''iterator_category'' qui identifie le type de l'itérateur.
+Ainsi le code de la fonction ''std::distance'' devient :
+<code cpp>
+namespace {
+    template<class inputIterator, class iteratorTag>
+    typename std::iterator_traits<inputIterator>::difference_type
+        distance(inputIterator first, inputIterator last, iteratorTag)
+    {
+        std::iterator_traits<inputIterator>::difference_type position = 0; //upSet - v.begin()
+        for(auto it = intSet.begin(); it != upSet; it++) { position ++; }
+        return position.
+    }
+    template<class inputIterator>
+    typename std::iterator_traits<inputIterator>::difference_type
+        distance(inputIterator first, inputIterator last, std::random_access_iterator_tag)
+    {
+        return last - first;
+    }
+}
+template<class inputIterator>
+typename std::iterator_traits<inputIterator>::difference_type
+    distance(inputIterator first, inputIterator last)
+{
+    return distance(first, last,
+        std::iterator_traits<inputIterator>::iterator_category());
+}
+</code>
+Quand on appelle la fonction ''distance'', elle appelle la fonction distance qui prend trois arguments, le dernier étant un objet ayant un type identifiant le type d'itérateur. Deux fonctions ''distances'' internes (ie. dans un espace de nom anoyme) sont définies:
+  * <code cpp>
+    template<class inputIterator, class iteratorTag>
+    typename std::iterator_traits<inputIterator>::difference_type
+        distance(inputIterator first, inputIterator last, iteratorTag)
+</code>Cette fonction est la fonction générique qui fonctionne pour l'intégralité des différents type d'itérateurs ''iteratorTag''.
+  * <code cpp>
+    template<class inputIterator>
+    typename std::iterator_traits<inputIterator>::difference_type
+        distance(inputIterator first, inputIterator last, std::random_access_iterator_tag)
+</code>Cette fonction est la version spécialisée pour le type ''iteratorTag'' qui doit être égal à [[https://en.cppreference.com/w/cpp/iterator/iterator_tags|std::random_access_iterator_tag]].
+Comme la version spécialisée est prioritaire sur la version générique, si l'itérateur définit ''iterator_category'' comme étant [[https://en.cppreference.com/w/cpp/iterator/iterator_tags|std::random_access_iterator_tag]], c'est la version spécialisée de la fonction qui sera appelé, sinon la version générique, ce qui permet d'avoir recours à la méthode optimale pour calculer la distance.
+</hidden>
 ===== Question n°2 =====
@@ Line 214: / Line 289: @@
 using namespace std;
-int testSortAndUpper()
+void testSortAndUpper()
 {
+    std::vector<int> v{ 10, 20, 30, 30, 20, 10, 10, 20 };
     // Appel de la fonction "upper' sur le vecteur en commençant par le premier élément
     // et en terminant avec le dernier.
@@ Line 231: / Line 307: @@
-int testSortHeapAndUpper()
+void testSortHeapAndUpper()
 {
+    std::vector<int> v{ 10, 20, 30, 30, 20, 10, 10, 20 };
+    std::make_heap(v.begin(), v.end());
     // Appel de la fonction "upper' sur le vecteur en commençant par le premier élément
     // et en terminant avec le dernier.

Cours

User Tools

Site Tools

Differences

Page Tools