|
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. L'exemple en question, pour être utilisable, mériterait
un certain nombre d'améliorations.
La version proposée à droite de la même classe inclut
la plupart des améliorations attendues.
Le programme de test utilisé se trouve ci-dessous. Il s'agit du
même programme de test que pour la version
de base.
Notez qu'une version encore plus sophistiquée de cette classe
et du programme de test est disponible
ici.
|
#ifndef SLISTE_H
#define SLISTE_H
#include <cstdlib>
#include <algorithm>
//
// Changements:
// - ajout (et utilisation) d'un append(debut, fin) générique
// - ajout d'un marqueur de fin de liste, pour fins de push_back() O(1)
// - ajout des opérateurs de comparaison == et !=
// - raffinement des itérateurs pour versions const et non-const (subtil)
//
// Chaque sliste<T> est un sizeof(sliste<T>::Noeud*) plus grosse que
// dans la version précédente, et quelques opérations ont un coût très
// légèrement plus élevé qu'avant (un pointeur de plus à tenir à jour),
// mais le gain de performance global obtenu est considérable!
//
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) (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();
++debut;
for (; 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:
using value_type = typename
sliste<U>::value_type;
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(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>
using namespace std;
template <class Itt>
void afficher_sequence(Itt debut, Itt fin, ostream &os)
{
for (; debut != fin; ++debut)
os << *debut << ' ';
os << endl;
}
// quelques tests
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)
for (auto & elem : lst2)
elem -= 0.5f;
afficher_sequence(begin(lst2), end(lst2), cout);
lst1 = lst2; // affectation de type apparenté
afficher_sequence(begin(lst1), end(lst1), cout);
}
|
