|
J'examine parfois en classe un exemple de classe
sliste, liste simplement chaînée générique
sur la base d'un type T. Cet exemple est disponible
ici, et une version améliorée (mais moins sophistiquée
que celle présentée sur cette page-ci) est disponible
ici.
La version proposée ici est un raffinement de la version améliorée,
tenant compte de raffinements conceptuels dans le standard C++ 11.
Les modifications propres à la présente version sont en
caractères gras. Notez que j'ai réécrit les diverses
implémentations de la méthode operator==()
à l'aide d'appels à std::equal(),
dans le respect du principe DRY.
Les changements clés à slist<T>
sont :
- l'ajout d'un constructeur de mouvement (qui prend en paramètre
un slist<T>&&). Notez son
implémentation, qui déplace les attributs de la liste
originale et fait par la suite en sorte que la liste originale demeure
dans un état correct (équivalent à une liste vide)
– n'oubliez pas cette étape dans votre propre code! Une
implémentation alternative aurait été de créer
une liste vide puis de l'interchanger avec la source à l'aide
de la méthode swap();
- la dérivation de slist<T>::base_iterator<U,N>
de la classe std::iterator, qui définit
les divers typedef dont se servent les algorithmes
standards (comme std::transform(), que j'utilise dans le programme de
test ci-dessous). Ceci n'est pas nécessaire, mais ça épargne
la rédaction de beaucoup de code quelque peu fastidieux;
- l'implémentation d'une méthode
swap() prenant en paramètre sliste<T>&&
pour fins d'optimisation; et
- l'implémentation d'une affectation de mouvement.
Le programme de test utilisé se trouve ci-dessous. Remarquez quelques
raffinements, certains mineurs et d'autres moins :
- adaptation de la fonction afficher_sequence()
pour qu'elle utilise un algorithme standard plutôt que
de reposer sur une répétitive artisanale;
- ajout d'une fonction modifier() qui a
pour particularité de modifier un conteneur et d'en retourner
une copie jetable (pour mettre en relief les nuances entre construction
par copie et construction de mouvement);
- transformation d'une répétitive artisanale dans le programme
principal par un appel à la fonction std::transform();
- ajout de quelques (!) appels à la fonction
modifier() susmentionnée. Notez que recours à une
lambda
à titre de foncteur.
Impact du constructeur de mouvement
Pour voir l'impact du constructeur de mouvement sur la vitesse d'exécution
du code, exécutez (en mode Release) le programme de test
ci-dessous avec la version de sliste implémentant
ce constructeur, notez le temps requis pour les NB_TESTS
appels à modifier. Sur mon petit ordinateur portatif, cela
affiche :
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5 33
0.5 1.5 2.5 3.5 4.5 32.5
0 1 2 3 4 32
1000000 appels à modifier() en 2076 ms.
Appuyez sur une touche pour continuer...
Ensuite, commentez le constructeur de mouvement de
sliste et refaites le test. Sur mon petit ordinateur portatif,
cela affiche :
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5 33
0.5 1.5 2.5 3.5 4.5 32.5
0 1 2 3 4 32
1000000 appels à modifier() en 3127 ms.
Appuyez sur une touche pour continuer...
Dans chaque cas, les chiffres précis peuvent varier, mais l'ordre
de grandeur demeure le même : le passage par un constructeur
de mouvement (plutôt que par un constructeur de copie) pour la valeur
de retour de modifier() entraîne un
gain d'environ 33% dans le cas d'une répétitive
comme celle-là. Cela met en relief le coût des copies dans
cette section du code. Ne trouvez-vous pas que le jeu en vaut la chandelle?
Ajoutez des éléments à lst2
ou augmentez la valeur de NTESTS si
vous souhaitez mettre en relief de manière plus marquée
la différence.
|
#ifndef SLISTE_H
#define SLISTE_H
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <utility>
//
// Changements:
// - ajout d'un constructeur de mouvement (Move Constructor)
// - ajout d'une affectation de mouvement (Move Assignment)
// Dans les deux cas, nous exploitons les références sur des rvalue
//
template <class T>
class sliste
{
public:
using value_type = T;
using size_type = std::size_t;
private:
struct Noeud
{
value_type val;
Noeud *succ;
Noeud(const value_type &val)
: val{val}, succ{}
{
}
};
Noeud *tete, *queue;
size_type nelems;
public:
// O(1)
sliste() noexcept
: tete{}, queue{}, nelems{}
{
}
// O(1)
sliste(sliste &&lst) noexcept
: tete{std::move(lst.tete)},
queue{std::move(lst.queue)},
nelems{std::move(lst.nelems)}
{
lst.tete = {};
lst.queue = {};
lst.nelems = {};
}
// O(1) (dépend de la complexité de size())
bool empty() const noexcept
{ return size() == 0; }
// O(1)
size_type size() const noexcept
{ return nelems; }
private:
// O(1)
Noeud *trouver_dernier()
{ return queue; }
public:
// O(distance(debut, fin))
template <class Itt>
void append(Itt debut, Itt fin)
{
// Cette fonction peut être optimisée, du moins avec certaines
// techniques que nous verrons. Amusez-vous!
if (debut == fin) return;
push_back(*debut);
auto p = trouver_dernier();
for (++debut; debut != fin; ++debut)
{
queue = new Noeud{*debut};
p->succ = queue;
p = queue;
++nelems;
}
}
// O(1)
void push_back(const value_type &val)
{
auto p = new Noeud{val};
if(empty())
tete = queue = p;
else
{
auto q = trouver_dernier();
q->succ = queue = p;
}
++nelems;
}
// O(n)
void clear() noexcept
{
while(tete)
{
auto p = tete->succ;
delete tete;
tete = p;
}
queue = {};
nelems = {};
}
// O(n) (dépend de clear())
~sliste() noexcept
{ clear(); }
private:
template <class U, class N>
class base_iterator
: public std::iterator<
std::forward_iterator_tag, U
>
{
public:
using node_type = N;
private:
node_type *cur;
public:
// O(1)
base_iterator(node_type *p)
: cur{p}
{
}
// O(1)
bool operator==(const base_iterator &itt) const noexcept
{ return cur == itt.cur; }
// O(1) (dépend de operator==())
bool operator!=(const base_iterator &itt) const noexcept
{ return !(*this == itt); }
// O(1)
base_iterator &operator++()
{
cur = cur->succ;
return *this;
}
// O(1) (dépend de operator++(int))
base_iterator operator++(int)
{
iterator temp{*this};
operator++();
return temp;
}
// O(1)
value_type &operator*() noexcept
{ return cur->val; }
// O(1?) (dépend de T::T(const T&))
value_type operator*() const
{ return cur->val; }
// O(1?) (dépend de T::T(const T&))
value_type operator->()
{ return cur->val; }
// O(1?) (dépend de T::T(const T&))
value_type operator->() const
{ return cur->val; }
};
public:
using iterator = base_iterator<value_type, Noeud>;
using const_iterator = base_iterator<const value_type, Noeud>;
// O(1)
iterator begin() noexcept
{ return iterator{tete}; }
// O(1)
const_iterator begin() const noexcept
{ return const_iterator{tete}; }
// O(1)
iterator end() noexcept
{ return iterator{nullptr}; }
// O(1)
const_iterator end() const noexcept
{ return const_iterator{nullptr}; }
// O(n)
sliste(const sliste &lst)
: sliste{}
{
append(lst.begin(), lst.end());
}
// O(1)
void swap(sliste &lst) noexcept
{
using std::swap;
swap(tete, lst.tete);
swap(queue, lst.queue);
swap(nelems, lst.nelems);
}
// O(2n), donc O(n)
sliste &operator=(const sliste &lst)
{
sliste{lst}.swap(*this);
return *this;
}
// O(1)
sliste &operator=(sliste &&lst)
{
tete = std::move(lst.tete);
queue = std::move(lst.queue);
nelems = std::move(lst.nelems);
lst.tete = {};
lst.queue = {};
lst.nelems = {};
return *this;
}
// O(n)
template <class U>
sliste(const sliste<U> &lst)
: sliste{}
{
append(lst.begin(), lst.end());
}
// O(2n), donc O(n)
template <class U>
sliste &operator=(const sliste<U> &lst)
{
sliste{lst}.swap(*this);
return *this;
}
// O(n)
template<class Itt>
sliste(Itt debut, Itt fin)
: sliste{}
{
append(debut, fin);
}
// O(n), présumant T==T O(1)
bool operator==(const sliste &lst) const
{
return size() == lst.size() &&
std::equal(begin(), end(), lst.begin());
}
// O(n), présumant T==U O(1)
// C'est une optimisation (on aurait pu laisser l'opérateur == sur deux
// sliste<T> faire le travail avec le support du constructeur de copie,
// mais cela aurait impliqué construire une sliste<T< temporaire)
template <class U>
bool operator==(const sliste<U> &lst) const
{
return size() == lst.size() &&
std::equal(begin(), end(), lst.begin());
}
// O(n), présumant T==T O(1)
bool operator!=(const sliste &lst) const
{ return !(*this == lst); }
// O(n), présumant T==U O(1)
// C'est une optimisation (on aurait pu laisser l'opérateur == sur deux
// sliste<T> faire le travail avec le support du constructeur de copie,
// mais cela aurait impliqué construire une sliste<T> temporaire)
template <class U>
bool operator!=(const sliste<U> &lst) const
{ return !(*this == lst); }
};
#endif
|
#include "sliste.h"
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <chrono>
using namespace std;
using namespace std::chrono;
template <class Itt>
void afficher_sequence(Itt debut, Itt fin, ostream &os)
{
using value_type = typename iterator_traits<Itt>::value_type ;
copy(debut, fin, ostream_iterator<value_type>(os, " "));
os << endl;
}
// quelques tests
template <class T, class Op>
sliste<T> modifier(sliste<T> lst, Op oper)
{
transform(begin(lst), end(lst), begin(lst), oper);
return lst;
}
int main()
{
int tab[] = { 1, 2, 3, 4, 5 };
afficher_sequence(begin(tab), end(tab), cout);
sliste<int> lst0(begin(tab), end(tab)); // constructeur de séquence
afficher_sequence(begin(lst0), end(lst0), cout);
sliste<int> lst1 = lst0; // constructeur de copie
afficher_sequence(begin(lst1), end(lst1), cout);
lst1.push_back(33);
lst0 = lst1; // affectation
afficher_sequence(begin(lst0), end(lst0), cout);
sliste<float> lst2 = lst0; // constructeur de conversion (implique un warning)
transform(begin(lst2), end(lst2), begin(lst2), [](float f) {
return f - 0.5f;
});
afficher_sequence(begin(lst2), end(lst2), cout);
lst1 = lst2; // affectation de type apparenté
afficher_sequence(begin(lst1), end(lst1), cout);
enum { NTESTS = 1000000 };
auto fct = [](float f) { return -f; };
auto avant = system_clock::now();
for(int i = 0; i < NTESTS; ++i)
lst2 = modifier(lst2, fct);
auto apres = system_clock::now();
cout << NTESTS << " appels à modifier() en "
<< duration_cast<milliseconds>(apres - avant) << " ms." << endl;
}
|
