Exemple d'implémentation d'une Skip List

Ce qui suit présente un exemple d'implémentation d'une Skip List en C++, donc adapté au moins en partie aux idiomes de ce langage. Il est préférable d'être familière ou familier avec std::optional avant d'aborder ce qui suit.

Notre implémentation d'une Skip List sera pleinement portable à tout compilateur C++ 17.

 
#ifndef SKIP_LIST_H
#define SKIP_LIST_H
#include <optional>
#include <random>
#include <vector>
#include <memory>
#include <ostream>
#include <fstream>
#include <iterator>
#include <utility>

Nous implémenterons une Skip List par le type skip_list<K,V>, où K sera le type des clés et V sera le type des valeurs.

 
template <class K, class V>
   class skip_list {

À l'interne, une skip_list<K,V> définit un outil de génération de hauteurs pseudoaléatoires avec une hauteur maximale fixée a priori.

L'algorithme de génération de niveaux (qui n'est pas de moi) lance une « pièce de monnaie » en l'air plusieurs fois et s'arrête lorsque la probabilité donnée à la construction est atteinte. L'idée ici est d'avoir une Skip List organisée un peu comme un histogramme, où les barres « hautes » sont plus rares que les barres « basses ».

 
      class RandomHeight {
         mutable std::mt19937 prng{ random_device{}() };
         mutable std::uniform_real_distribution<> cenne{ 0.0, 1.0 };
         int max_level;
         float probability;
      public:
         RandomHeight(int max_level, float probability)
            : max_level{ max_level }, probability{ probability } {
         }
         int new_level() const {
            int level = 1;
            while (cenne(prng) < probability && level < max_level)
              ++level;
            return level;
         }
      };

Nous exposerons nos abstractions sous la forme de types internes et publics, comme il se doit.

 
   public:
      using key_type = K;
      using value_type = V;
      using reference = value_type&;
      using const_reference = const value_type&;
      using pointer = value_type*;
      using const_pointer = const value_type*;
      using size_type = std::size_t;

Une skip_list<K,V> conservera une liste chaînée de noeuds (type skip_list<K,V>::node).

Chaque noeud contiendra une valeur (de type std::optional<V> ici, pour éviter toute allocation dynamique de mémoire), une clé (de type K) et une liste de suivants à divers niveaux.

 
   private:
      class node {
         K key_{};
         std::optional<V> value_{};
      public:
         node(K key, const V &value, int height)
            : key_{ key }, value_{ value }, fwd_nodes(height) {
         }
         node(K key, std::nullopt_t, int height)
            : key_{ key }, fwd_nodes(height) {
         }
         node(int height) : fwd_nodes(height) {
         }
         K key() const {
            return key_;
         }
         std::optional<V>& value() {
            return value_;
         }
         std::optional<V> value() const {
            return value_;
         }
         auto height() const {
            return fwd_nodes.size();
         }
         std::vector<node*> fwd_nodes;
      };

Une skip_list<K,V> sera un objet relativement lourd (voir la liste des attributs, à droite). Notez cependant que l'attribut nelems est redondant si aucun calcul ne dépend du nombre d'éléments dans une une Skip List, ce qui permettrait de l'omettre pour certains projets.

 
      size_type nelems{ };
      node *head;
      node *tail;
      int max_height;
      int cur_height{ 1 };
      RandomHeight randGen;

Le constructeur paramétrique d'une Skip List permet d'en spécifier les paramètres clés de fonctionnement, soit :

  • Sa hauteur maximale
  • Sa hauteur courante
  • La probabilité autour de laquelle les choix de hauteur de noeuds seront établis. et
  • Une clé qui servira de sentinelle, étant estimée « plus haute » que toutes celles qui viendront ultérieurement

La tête et la queue seront dès le départ de hauteur maximale.

 
   public:
      skip_list(float probability, int max_height, const K &key)
         : max_height{ max_height }, randGen{max_height, probability} {
         head = new node{ max_height };
         try {
            tail = new node{key, nullopt, max_height};
            for (auto & p : head->fwd_nodes)
               p = tail;
         } catch (...) {
            delete head;
            throw;
         }
      }

Pour simplifier le portrait, j'ai bloqué la copie, mais une Skip List n'est pas fondamentalement incopiable. Si vous en avez envie, implémentez ces services et votre Skip List n'en sera que plus utile.

 
      skip_list(const skip_list&) = delete;
      skip_list& operator=(const skip_list&) = delete;

Le mouvement est trivial à implémenter. J'ai choisi de copier le générateur pseudoaélatoire, faute d'une meilleure idée.

 
      skip_list(skip_list &&other)
         : head{ std::exchange(other.head, nullptr) },
           tail{ std::exchange(other.tail, nullptr) },
           max_height{ std::exchange(other.max_height, 0) },
           cur_height{ std::exchange(other.cur_height, 0) },
           nelems{ std::exchange(other.nelems, 0) },
           randGen{ other.randGen } { // copie volontaire
      }
      skip_list& operator=(skip_list &&other) {
         skip_list{ std::move(other) }.swap(*this);
         return *this;
      }

Le destructeur est relativement simple. Il parcourt les noeuds de par leur niveau zéro pour s'assurer d'un netoyage complet.

 
      ~skip_list() {
         for (auto p = head; p;) {
            auto q = p->fwd_nodes.front();
            delete p;
            p = q;
         }
      }

Les méthodes empty() et size() vcnt de soi.

 
      bool empty() const noexcept {
         return begin() == end();
      }
      size_type size() const noexcept {
         return nelems;
      }

La méthode find_node(..., k) est l'outil clé de la plupart des services d'une skip_list<K,V>. Elle trouve (et retourne) le noeud situé logiquement juste avant la clé k

 
   private:
      node* find_node(std::vector<node*> &update, const K &key) const {
         auto p = head;
         for (auto h = cur_height - 1; h >= 0; --h) {
            for (auto cmpKey = p->fwd_nodes[h]->key();
                 cmpKey < key;
                 cmpKey = p->fwd_nodes[h]->key())
               p = p->fwd_nodes[h];
            update[h] = p;
         }
         return p;
      }

La méthode insert(k,v) se comporte comme suit :

  • Parcourir les éléments de la Skip List jusqu'au point où la clé du prochain noeud n'est pas plus grande que k
  • Si la clé du prochain noeud est k, alors l'insertion mènerait à un duplicat et la méthode ne procède pas
  • Sinon, un noeud de taille pseudoaléatoire est généré et inséré à l'endroit opportun
 
   public:
      bool insert(const K &key, const V &value) {
         std::vector<node*> update( max_height );
         if (auto p = find_node(update, key);
             p->fwd_nodes.front()->key() == key)
            return false;
         auto lvl = randGen.new_level();
         if (lvl > cur_height) {
            fill(std::begin(update)+cur_height, std::begin(update)+lvl, head);
            cur_height = lvl;
         }
         auto p = new node{ key, value, lvl };
         for (int i = 0; i < lvl; ++i) {
            p->fwd_nodes[i] = update[i]->fwd_nodes[i];
            update[i]->fwd_nodes[i] = p;
         }
         ++nelems;
         return true;
      }

La méthode remove(k) se comporte comme suit :

  • Parcourir les éléments de la Skip List jusqu'au point où la clé du prochain noeud n'est pas plus grande que k
  • Si la clé du prochain noeud diffère de k, on ne peut rien faire
  • Sinon, on élimine le prochain noeud tout en reconstruisant suffisamment de liens pour garder la Skip List opérationnelle
 
      bool remove(const K &key) {
         std::vector<node*> update(max_height);
         auto p = find_node(update, key);
         p = p->fwd_nodes.front();
         if (p->key() != key)
            return false;
         for (int i = 0; i < cur_height && update[i]->fwd_nodes[i] == p; ++i)
            update[i]->fwd_nodes[i] = p->fwd_nodes[i];
         delete p;
         for (--cur_height;
              cur_height >= 0 && head->fwd_nodes[cur_height]->key() == tail->key(); )
            --cur_height;
         --nelems;
         return true;
      }

La méthode retrieve(k) est simple :

  • Parcourir les éléments de la Skip List jusqu'au point où la clé du prochain noeud n'est pas plus grande que k
  • Si la clé du prochain noeud est k, retourner sa valeur
  • Sinon, retourner un std::optional<V> vide
 
      std::optional<V> retrieve(const K &key) const {
         std::vector<node*> update(max_height);
         auto p = find_node(update, key);
         p = p->fwd_nodes.front();
         if(p->key() == key)
            return p->value();
         return {};
      }

Un skip_list<K,V>::iterator permet de parcourir les éléments (les V) d'une Skip List dans l'ordre de classement des clés (les K).

 
      class iterator {
      public:
         using value_type = V;
         using pointer = V *;
         using reference = V &;
         using difference_type = std::ptrdiff_t;
         using iterator_category = std::forward_iterator_tag;
      private:
         node *cur;
         friend class skip_list;
         iterator(node *cur) : cur{ cur } {
         }
      public:
         iterator& operator++() {
            cur = cur->fwd_nodes.front();
            return *this;
         }
         iterator operator++(int) {
            auto temp = *this;
            operator++();
            return temp;
         }
         auto operator*() {
            return cur->value();
         }
         auto operator*() const {
            return cur->value();
         }
         auto operator->() {
            return cur->value();
         }
         auto operator->() const {
            return cur->value();
         }
         bool operator==(const iterator &other) const noexcept {
            return cur == other.cur;
         }
         bool operator!=(const iterator &other) const noexcept {
            return !(*this == other);
         }
      };

Un skip_list<K,V>::const_iterator ressemble beaucoup à un skip_list<K,V>::iterator, mais avec quelques fonctionnalités de moins (celles qui permettraient de muter les éléments de la séquence)

 
      class const_iterator {
      public:
         using value_type = V;
         using pointer = const V *;
         using reference = const V &;
         using difference_type = std::ptrdiff_t;
         using iterator_category = std::forward_iterator_tag;
      private:
         node *cur;
         friend class skip_list;
         const_iterator(node *cur) : cur{ cur } {
         }
      public:
         const_iterator& operator++() {
            cur = cur->fwd_nodes.front();
            return *this;
         }
         const_iterator operator++(int) {
            auto temp = *this;
            operator++();
            return temp;
         }
         auto operator*() const {
            return cur->value();
         }
         auto operator->() const {
            return cur->value();
         }
         bool operator==(const const_iterator &other) const noexcept {
            return cur == other.cur;
         }
         bool operator!=(const const_iterator &other) const noexcept {
            return !(*this == other);
         }
      };

Les méthodes begin() et end(), en version const et non-const, sont triviales. Il en va de même pour cbegin() et cend().

 
      iterator begin() noexcept {
         return head == tail? tail : head->fwd_nodes.front();
      }
      const_iterator begin() const noexcept {
         return head == tail? tail : head->fwd_nodes.front();
      }
      iterator end() noexcept {
         return tail;
      }
      const_iterator end() const noexcept {
         return tail;
      }
      const_iterator cbegin() const {
         return begin();
      }
      const_iterator cend() const {
         return end();
      }

À titre illustratif, nous accompagnerons notre skip_list<K,V> d'un opérateur de projection sur un flux, qui projettera les valeurs (les V) sur le flux en ordre croissant de clé (les K).

 
      friend std::ostream& operator<<(std::ostream &os, const skip_list<K, V> &lst) {
         for (const auto & elem : lst)
            os << *elem << ' ';
         return os;
      }
   };
#endif

Un exemple simple de code client serait ce qui suit.

Notre test ne reposera que sur des outils standards, outre la classe skip_list elle-même bien entendu.

 
#include "skip_list.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <string_view>
#include <memory>
using namespace std;

Le test reposera sur des instances de la classe Orque, visible à droite.

 
struct Orque {
   float puanteur;
   string nom;
   friend ostream& operator<<(ostream &os, const Orque &orque) {
      return os << orque.nom << ' ' << orque.puanteur;
   }
   Orque(string_view nom, float puanteur) : nom{ nom }, puanteur{ puanteur } {
   }
};

Pour les fins du test, nous utiliserons une fonction réalisant une recherche d'une certaine clé dans une Skip List, et affiche la valeur qui lui est associée si cette clé y est trouvée. Remarquez le test fait sur le résultat de retreive(), écrit ainsi parce que la méthode retourne un std::optional<V>.

 
template <class K, class V>
   void trouver_et_afficher(const K &key, const skip_list<K, V> &liste) {
      if (auto p = liste.retrieve(key); p)
         cout << "J'ai trouve " << *p << endl;
      else
         cout << key << " introuvable" << endl;
   }

Le programme de test en soi crée une Skip List composée d'instances de la classe Orque, et utilise à titre de sentinelle une clé « maximale » (plus « haute » que la plus « haute » des clés que nous y utiliserons).

Les clés utilisées sont les noms des orques.

 
int main() {
   skip_list<string, Orque> sList(0.5f, 4, "ZZZZZ"); // clé max arbitraire -- sentinelle
   vector<Orque> v = { { "Urg", 0.2f }, { "Arg", 0.1f }, { "Org", 0.9f } };
   for (auto &orque : v)
      sList.insert(orque.nom, orque);
   auto cle_test = v[0].nom;
   cout << sList << " ... taille " << sList.size() << endl;
   trouver_et_afficher(cle_test, sList);
   sList.remove(cle_test);
   cout << sList << " ... taille " << sList.size() << endl;
   trouver_et_afficher(cle_test, sList);
}

Voilà!

Valid XHTML 1.0 Transitional

CSS Valide !