Analyse du code source et du cadre de travail
Les versions antérieures de la STL, comme SGI-STL30, ne comprenaient pas unordered_map et unordered_set, qui ont été introduites après C++11. Cependant, elles implémentaient des tables de hachage sous les noms hash_map et hash_set, en tant que conteneurs non standard. Le code source correspondant se trouve dans les fichiers stl_hash_map, stl_hash_set et stl_hashtable.h. L'architecture de base de hash_map et hash_set est extraite ci-dessous pour référence.
Cadre de base
Nous allons encapsuler une table de hachage implémentée avec la méthode du chaînage pour créer nos propres contenuers.
Implémentation simulation
Puisque unordered_set stocke une clé simple tandis qu'unordered_map stocke une paire clé-valeur, nous utilisons un paramètre de template générique pour le type de données. De plus, pour les opérations d'insertion, de recherche et de suppression, nous avons besoin d'extraire la clé, ce qui est réalisé via des foncteurs spécifiques à chaque conteneur.
Implémentation de l'itérateur
Un itérateur est encapsulé pour la table de hachage, que unordered_map et unordered_set réutiliesnt. L'itérateur contient un pointeur vers un nœud pour parcourir les éléments. La structure de base est définie ci-dessous.
Implémentation de l'opérateur ++
L'opérateur ++ avance l'itérateur au nœud suivant. Si le nœud courant a un suivant dans le même seau, on s'y déplace. Sinon, on cherche le prochain seau non vide. Pour cela, nous devons recalculer l'indice de hachage, ce qui nécessite un pointeur vers la table de hachage et les foncteurs appropriés.
Self& operator++()
{
if (courant->suivant)
{
courant = courant->suivant;
}
else
{
ExtracteurCle extracteur;
FonctionHachage hachage;
size_t indice_seau = hachage(extracteur(courant->donnee)) % table_hachage->seaux.size();
++indice_seau;
while (indice_seau < table_hachage->seaux.size())
{
courant = table_hachage->seaux[indice_seau];
if (courant)
break;
else
++indice_seau;
}
if (indice_seau == table_hachage->seaux.size())
{
courant = nullptr;
}
}
return *this;
}
Les fonctions begin() et end() sont simples à implémenter.
Améliorations
La fonction Insert retourne une paire contenant un itérateur et un booléen indiquant le succès. L'opérateur [] pour unordered_map est implémenté comme suit :
V& operator[](const K& cle)
{
paire<iterator bool=""> resultat = inserer({ cle, V() });
return resultat.premier->second;
}</iterator>
Code complet
HashTable.h
namespace seau_hachage
{
template<class t="">
struct NoeudHachage
{
T _donnee;
NoeudHachage<t>* _suivant;
NoeudHachage(const T& donnee)
:_donnee(donnee), _suivant(nullptr)
{}
};
// Déclaration anticipée
template<class class="" extracteurcle="" fonctionhachage="" k="" t="">
class TableHachage;
template<class class="" extracteurcle="" fonctionhachage="" k="" ptr="" ref="" t="">
struct IterateurHT
{
typedef NoeudHachage<t> Noeud;
typedef TableHachage<k extracteurcle="" fonctionhachage="" t=""> HT;
typedef IterateurHT<k extracteurcle="" fonctionhachage="" ptr="" ref="" t=""> Self;
Noeud* courant;
const HT* table_hachage;
IterateurHT(Noeud* noeud, const HT* ht)
:courant(noeud), table_hachage(ht)
{}
Ref operator*()
{
return courant->_donnee;
}
Ptr operator->()
{
return &(courant->_donnee);
}
bool operator!=(const Self& autre)
{
return courant != autre.courant;
}
Self& operator++()
{
if (courant->_suivant)
{
courant = courant->_suivant;
}
else
{
ExtracteurCle extracteur;
FonctionHachage hachage;
size_t indice_seau = hachage(extracteur(courant->_donnee)) % table_hachage->_seaux.size();
++indice_seau;
while (indice_seau < table_hachage->_seaux.size())
{
courant = table_hachage->_seaux[indice_seau];
if (courant)
break;
else
++indice_seau;
}
if (indice_seau == table_hachage->_seaux.size())
{
courant = nullptr;
}
}
return *this;
}
};
template<class class="" extracteurcle="" fonctionhachage="" k="" t="">
class TableHachage
{
template<class class="" extracteurcle="" fonctionhachage="" k="" ptr="" ref="" t="">
friend struct IterateurHT;
typedef NoeudHachage<t> Noeud;
public:
typedef IterateurHT<k extracteurcle="" fonctionhachage="" t=""> Iterator;
typedef IterateurHT<k const="" extracteurcle="" fonctionhachage="" t=""> ConstIterator;
Iterator Debut()
{
if (_n == 0)
return Fin();
for (size_t i = 0; i < _seaux.size(); i++)
{
Noeud* courant = _seaux[i];
if (courant)
{
return Iterator(courant, this);
}
}
return Fin();
}
Iterator Fin()
{
return Iterator(nullptr, this);
}
ConstIterator Debut() const
{
if (_n == 0)
return Fin();
for (size_t i = 0; i < _seaux.size(); i++)
{
Noeud* courant = _seaux[i];
if (courant)
{
return ConstIterator(courant, this);
}
}
return Fin();
}
ConstIterator Fin() const
{
return ConstIterator(nullptr, this);
}
TableHachage()
:_seaux(prochain_premier(0)), _n(0)
{}
~TableHachage()
{
for (size_t i = 0; i < _seaux.size(); i++)
{
Noeud* courant = _seaux[i];
while (courant)
{
Noeud* suivant = courant->_suivant;
delete courant;
courant = suivant;
}
_seaux[i] = nullptr;
}
}
paire<iterator bool=""> Inserer(const T& donnee)
{
ExtracteurCle extracteur;
Iterator it = Trouver(extracteur(donnee));
if (it != Fin())
return { it, false };
FonctionHachage hachage;
if (_n == _seaux.size())
{
vector<noeud> nouveaux_seaux(prochain_premier(_seaux.size() + 1));
for (size_t i = 0; i < _seaux.size(); i++)
{
Noeud* courant = _seaux[i];
while (courant)
{
Noeud* suivant = courant->_suivant;
size_t indice = hachage(extracteur(courant->_donnee)) % nouveaux_seaux.size();
courant->_suivant = nouveaux_seaux[indice];
nouveaux_seaux[indice] = courant;
courant = suivant;
}
_seaux[i] = nullptr;
}
_seaux.swap(nouveaux_seaux);
}
size_t indice = hachage(extracteur(donnee)) % _seaux.size();
Noeud* nouveau_noeud = new Noeud(donnee);
nouveau_noeud->_suivant = _seaux[indice];
_seaux[indice] = nouveau_noeud;
++_n;
return { Iterator(nouveau_noeud, this), true };
}
Iterator Trouver(const K& cle)
{
ExtracteurCle extracteur;
FonctionHachage hachage;
size_t indice = hachage(cle) % _seaux.size();
Noeud* courant = _seaux[indice];
while (courant)
{
if (extracteur(courant->_donnee) == cle)
{
return Iterator(courant, this);
}
courant = courant->_suivant;
}
return Fin();
}
bool Supprimer(const K& cle)
{
ExtracteurCle extracteur;
size_t indice = cle % _seaux.size();
Noeud* precedent = nullptr;
Noeud* courant = _seaux[indice];
while (courant)
{
if (extracteur(courant->_donnee) == cle)
{
if (precedent == nullptr)
{
_seaux[indice] = courant->_suivant;
}
else
{
precedent->_suivant = courant->_suivant;
}
delete courant;
--_n;
return true;
}
else
{
precedent = courant;
courant = courant->_suivant;
}
}
return false;
}
private:
vector<noeud> _seaux;
size_t _n = 0;
};
}</noeud></noeud></iterator></k></k></t></class></class></k></k></t></class></class></t></class>
unordered_set.h
template<class class="" fonctionhachage="Hacheur<K" k="">>
class unordered_set
{
struct ExtracteurCleSet
{
const K& operator()(const K& cle)
{
return cle;
}
};
public:
typedef typename seau_hachage::TableHachage<k const="" extracteurcleset="" fonctionhachage="" k="">::Iterator iterator;
typedef typename seau_hachage::TableHachage<k const="" extracteurcleset="" fonctionhachage="" k="">::ConstIterator const_iterator;
iterator begin()
{
return _ht.Debut();
}
iterator end()
{
return _ht.Fin();
}
const_iterator begin() const
{
return _ht.Debut();
}
const_iterator end() const
{
return _ht.Fin();
}
paire<iterator bool=""> insert(const K& cle)
{
return _ht.Inserer(cle);
}
iterator Find(const K& cle)
{
return _ht.Trouver(cle);
}
bool Erase(const K& cle)
{
return _ht.Supprimer(cle);
}
private:
seau_hachage::TableHachage<k const="" extracteurcleset="" fonctionhachage="" k=""> _ht;
};</k></iterator></k></k></class>
unordered_map.h
template<class class="" fonctionhachage="Hacheur<K" k="" v="">>
class unordered_map
{
struct ExtracteurCleMap
{
const K& operator()(const paire<k v="">& kv)
{
return kv.first;
}
};
public:
typedef typename seau_hachage::TableHachage<k k="" paire="" v="">, ExtracteurCleMap, FonctionHachage>::Iterator iterator;
typedef typename seau_hachage::TableHachage<k k="" paire="" v="">, ExtracteurCleMap, FonctionHachage>::ConstIterator const_iterator;
iterator begin()
{
return _ht.Debut();
}
iterator end()
{
return _ht.Fin();
}
const_iterator begin() const
{
return _ht.Debut();
}
const_iterator end() const
{
return _ht.Fin();
}
V& operator[](const K& cle)
{
paire<iterator bool=""> resultat = inserer({ cle, V() });
return resultat.premier->second;
}
paire<iterator bool=""> inserer(const paire<k v="">& kv)
{
return _ht.Inserer(kv);
}
iterator Trouver(const K& cle)
{
return _ht.Trouver(cle);
}
bool Supprimer(const K& cle)
{
return _ht.Supprimer(cle);
}
private:
seau_hachage::TableHachage<k k="" paire="" v="">, ExtracteurCleMap, FonctionHachage> _ht;
};</k></k></iterator></iterator></k></k></k></class>