|
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, nécessite
un certain nombre d'améliorations.
La version proposée à droite est celle que je propose habituellement
en classe.
Le programme de test utilisé se trouve ci-dessous. Le même
programme de test sera utilisé pour la version plus sophistiquée
que vous trouverez ici, et sera
raffiné pour une version encore plus sophistiquée que
vous trouverez ici.
|
#ifndef SLISTE_H
#define SLISTE_H
#include <cstdlib>
#include <algorithm>
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;
size_type nelems;
public:
// O(1)
sliste() noexcept
: tete{}, 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(n) --> raffiner pour que ce soit O(1)
Noeud *trouver_dernier()
{
if (empty()) return 0;
auto p = tete;
while (p->succ)
p = p->succ;
return p;
}
public:
// O(n) (dépend de trouver_dernier())
// Si trouver_dernier() est O(1), push_back() l'est aussi
void push_back(const value_type &val)
{
auto p = new Noeud{val};
if(empty())
tete = p;
else
{
auto q = trouver_dernier();
q->succ = p;
}
++nelems;
}
// O(n)
void clear() noexcept
{
while(tete)
{
auto p = tete->succ;
delete tete;
tete = p;
}
nelems = 0;
}
// O(n) (dépend de clear())
~sliste() noexcept
{ clear(); }
class iterator
{
Noeud *cur;
public:
// O(1)
iterator(Noeud *p)
: cur{p}
{
}
// O(1)
bool operator==(const iterator &itt) const noexcept
{ return cur == itt.cur; }
// O(1) (dépend de operator==())
bool operator!=(const iterator &itt) const noexcept
{ return !(*this == itt); }
// O(1)
iterator &operator++()
{
cur = cur->succ;
return *this;
}
// O(1) (dépend de operator++(int))
iterator operator++(int)
{
iterator temp{*this};
operator++();
return temp;
}
// O(1)
value_type &operator*() noexcept
{ return cur->val; }
// O(1?) (dépend de la complexité de T::T(const T&))
value_type operator*() const
{ return cur->val; }
// O(1?) (dépend de la complexité de T::T(const T&))
value_type operator->()
{ return cur->val; }
// O(1?) (dépend de la complexité de T::T(const T&))
value_type operator->() const
{ return cur->val; }
};
// O(1) (dépend de iterator::iterator(Noeud*))
iterator begin() noexcept
{ return iterator{tete}; }
// O(1) (dépend de iterator::iterator(Noeud*))
// Pas gentil; faudrait retourner un const_iterator
iterator begin() const noexcept
{ return iterator{tete}; }
// O(1) (dépend de iterator::iterator(Noeud*))
iterator end() noexcept
{ return iterator{nullptr}; }
// O(1) (dépend de iterator::iterator(Noeud*))
// Pas gentil; faudrait retourner un const_iterator
iterator end() const noexcept
{ return iterator{nullptr}; }
// O(n^2), à cause de push_back() qui est O(n)
// Rendre trouver_dernier() O(1), donc rendre push_back() O(1),
// rendrait cette méthode O(n), un gain considérable!
// Serait mieux avec un const_iterator...
sliste(const sliste &lst)
: sliste{}
{
for (auto i = lst.begin(); i != lst.end(); ++i)
push_back(*i);
}
// O(1)
void swap(sliste &lst) noexcept
{
using std::swap;
swap(tete, lst.tete);
swap(nelems, lst.nelems);
}
// O(n^2+n), donc O(n^2) car dépend du constructeur de copie
// et du destructeur. Raffiner le constructeur de copie rend
// ceci O(2n), donc O(n)
sliste &operator=(const sliste &lst)
{
sliste{lst}.swap(*this);
return *this;
}
// O(n^2), à cause de push_back() qui est O(n)
// Rendre trouver_dernier() O(1), donc rendre push_back() O(1),
// rendrait cette méthode O(n), un gain considérable!
// Serait mieux avec un const_iterator...
template <class U>
sliste(const sliste<U> &lst)
: sliste{}
{
for (auto i = lst.begin(); i != lst.end(); ++i)
push_back(*i);
}
// O(n^2+n), donc O(n^2) car dépend du constructeur de copie
// et du destructeur. Raffiner le constructeur de copie rend
// ceci O(2n), donc O(n)
template <class U>
sliste &operator=(const sliste<U> &lst)
{
sliste{lst}.swap(*this);
return *this;
}
// O(n^2), à cause de push_back() qui est O(n)
// Rendre trouver_dernier() O(1), donc rendre push_back() O(1),
// rendrait cette méthode O(n), un gain considérable!
template<class Itt>
sliste(Itt debut, Itt fin)
: sliste{}
{
for (; debut != fin; ++debut)
push_back(*debut);
}
// EXERCICES:
// - raffiner trouver_dernier() pour qu'il soit O(1) (ceci
// implique quelques changements ici et là
// - coder == et !=, pour comparer deux sliste<T>, et pour
// comparer une sliste<T> et une sliste<U>
// - offrir iterator et const_iterator
// - ajouter append(debut,fin) pour rendre plus efficaces les
// ajouts en bloc à la fin d'une liste
};
#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);
}
|
