摘要訊息 : 使用 C++ 來實作跳躍列表.

目錄隱藏

0. 前言

我們在《【資料結構】跳躍列表》中講述了跳躍列表的基本結構, 根據 C++ 標準樣板程式庫中容器的大致樣子, 我們今天要實作一個和這些容器差不多的跳躍列表.

更新紀錄 :

2022 年 6 月 6 日進行第一次更新和修正.

1. 實作

要實作這樣一個容器, 首先就要實作它的疊代器. 跳躍列表是一個前向連結串列, 因此它的疊代器應該是前向疊代器. 不過在此之前, 我們需要跳躍列表每個節點的具體結構 :

template <typename T>
struct skip_list_node {
public:
    T value;
    skip_list_node **next;
    size_t max_level;
};

其中, 成員變數 max_level 既表示了該節點的最高的級, 同時也表示了成員變數 next 的動態陣列大小. 對於跳躍列表的疊代器, 我們將其宣告如下 :

template <typename T, bool IsConst>
class skip_list_iterator;

第二個樣板參數 IsConst 代表這個疊代器是否為不可更改內容的疊代器. 根據 C++ 標準樣板程式庫的規範, 每個疊代器都有一個名為 iterator_category 的別名, 表示疊代器的類型. 那麼在跳躍列表中, 這個別名應該是 using iterator_category = std::forward_iterator_tag;. 這個疊代器應該有兩個成員 :

template <typename T, bool IsConst>
class skip_list_iterator {
    // ...
private:
    skip_list_node<T> *node;
    size_t level;
}

其中, node 表示疊代器現在所處的位置, level 表示目前所處的節點. 那麼其多載的 operator== 比較的應該是它們是否處在同一個位置, 同時也比較是否處在同一級. 除了建構子和解構子之外, 它應該具備多載的 : operator*, operator-> 和 operator++. 其中, skip_list_iterator<T, false> 還應該具備向 skip_list_iterator<T, true> 發生隱含型別轉化的能力. 不過光具備上述操作可能無法滿足我們的要求, 因為我們還需要調整疊代器的級. 此處, 我為其增加了兩個多載運算子 :

skip_list_iterator<T, IsConst> &skip_list_iterator<T, IsConst>::operator+() & noexcept {
    ++this->level;
    return *this;
}
skip_list_iterator<T, IsConst> &skip_list_iterator<T, IsConst>::operator-() & noexcept {
    --this->level;
    return *this;
}

這個是所有 C++ 標準樣板程式庫中容器的疊代器都不具備的, 這也說明了跳躍列表的特殊性. 除了這些需要額外說明的之外, 剩下的都是非常簡單的, 大家可以自行嘗試實作.

跳躍列表除了需要明確型別之外, C++ 標準樣板程式庫還要求每一個容器都可以接受一個空間配置器以自訂記憶體配置操作. 此處, 我們暫時不考慮記憶體配置自訂, 你可以統一使用 std::operator new (std::malloc) 和 std::operator delete (std::free) 來替代. 由於跳躍列表的特殊性, 它本身是一個有序的容器, 因此它還需要進行比較. 跳躍列表需要產生一個級, 這裡使用到了亂數生成. 將這個生成的機率亂數和標準機率進行比較, 於是我們還需要一個機率的產生器. 總結這些, 我們得到了跳躍列表的宣告 :

template <typename T, /* typename Allocator = std::allocator<T> */, typename Compare = std::less<T>, typename Random = skip_list_random_number_generator, typename Probability = skip_list_probability_generator>
class skip_list;

我們看到, 上面有三個預設的樣板引數, 我們預設指定 std::less<> 進行比較. 也就是說, 跳躍列表預設是從小到大有序的. 我們還指定了 skip_list_random_number_generator 和 skip_list_probability_generator 用於產生亂數了產生機率, 他們的實作如下 :

#include <random>

struct skip_list_probability_generator {
    constexpr double operator()() const noexcept {
        return 0.5;
    }
};
struct skip_list_random_number_generator {
    double operator()() const noexcept {
        static std::random_device d {};
        static std::default_random_engine e(d());
        static std::uniform_real_distribution<double> u(0.0, 1.0);
        return u(e);
    }
};

將標準機率設為 0.5, 是各位前輩經過大量實驗得到的結果, 這樣的跳躍列表可以維持比較高的效能.

每一次在用到 std::less<T>, skip_list_probability_generator 和 skip_list_probability_generator 的時候, 如果都要去建構對應的物件將會耗費不少時間, 因此我們直接將其作為跳躍列表的成員變數. 但是, 如果直接將它們作為跳躍列表的成員變數, 必定會導致 skip_list 的靜態大小, 即 sizeof 值變得很大. 我們希望盡力壓縮它的靜態大小, 而預設的 std::less<T>, skip_list_probability_generator 和 skip_list_probability_generator 它們都不存在成員, 因此可以通過繼承的方式來壓縮. 這就是 C++ 中的空基礎類別壓縮技術 :

template <typename Compare, typename Random, typename Probability, bool, bool, bool>
struct skip_list_compress_auxiliary {
public:
    Compare c;
    Random r;
    Probability p;
public:
    constexpr skip_list_compress_auxiliary() = default;
    explicit skip_list_compress_auxiliary(Compare c) : c {std::move(c)}, r {}, p {} {}
    explicit skip_list_compress_auxiliary(Random r) : c {}, r {std::move(r)}, p {} {}
    explicit skip_list_compress_auxiliary(Probability p) : c {}, r {}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Compare c, Random r) : c {std::move(c)}, r {std::move(r)}, p {} {}
    skip_list_compress_auxiliary(Compare c, Probability p) : c {std::move(c)}, r {}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Random r, Probability p) : c {}, r {std::move(r)}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Compare c, Random r, Probability p) :
            c {std::move(c)}, r {std::move(r)}, p {std::move(p)} {}
public:
    Compare &compare() noexcept {
        return this->c;
    }
    const Compare &compare() const noexcept {
        return this->c;
    }
    Random &random() noexcept {
        return this->r;
    }
    const Random &random() const noexcept {
        return this->r;
    }
    Probability &probability() noexcept {
        return this->p;
    }
    const Probability &probability() const noexcept {
        return this->p;
    }
};

如果給定的三個類別都不是無狀態的 (也就是它們存在成員變數或者存在虛擬成員函式等情況), 那麼它們是無法. 後面三個 bool 型別的樣板參數用於偏特製化, 它們分別表示對應的類別是否不存在成員變數以及是否不可繼承. 上述程式碼是三個類別都需要作為成員的情況, 一旦某一個類別可以通過繼承來壓縮靜態大小, 那麼我們可以寫為 :

template <typename Compare, typename Random, typename Probability>
struct skip_list_compress_auxiliary<Compare, Random, Probability, true, false, false> : public Compare {
public:
    Random r;
    Probability p;
public:
    constexpr skip_list_compress_auxiliary() = default;
    explicit skip_list_compress_auxiliary(Compare) : Compare(), r {}, p {} {}
    explicit skip_list_compress_auxiliary(Random r) : Compare(), r {std::move(r)}, p {} {}
    explicit skip_list_compress_auxiliary(Probability p) : Compare(), r {}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Compare, Random r) : Compare(), r {std::move(r)}, p {} {}
    skip_list_compress_auxiliary(Compare, Probability p) : Compare(), r {}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Random r, Probability p) : Compare(), r {std::move(r)}, p {std::move(p)} {}
    skip_list_compress_auxiliary(Compare, Random r, Probability p) :
            Compare(), r {std::move(r)}, p {std::move(p)} {}
public:
    Compare &compare() noexcept {
        return static_cast<Compare &>(*this);
    }
    const Compare &compare() const noexcept {
        return static_cast<const Compare &>(*this);
    }
    Random &random() noexcept {
        return this->r;
    }
    const Random &random() const noexcept {
        return this->r;
    }
    Probability &probability() noexcept {
        return this->p;
    }
    const Probability &probability() const noexcept {
        return this->p;
    }
};

上述程式碼就壓縮了至少一個 Compare 大小 (通常為 1, 但是需要記憶體對位的情況, 可能為 4 甚至 8). 如果 sizeof(skip_list_compress_auxiliary<Compare, Random, Probability, false, false, false>) 的值為 3, 那麼sizeof(skip_list_compress_auxiliary<Compare, Random, Probability, true, false, false>) 的值為 2. 剩餘情況大家可以自行實作.

然後需要用到

#include <type_traits>

template <typename Compare, typename Random, typename Probability>
using skip_list_compress = skip_list_compress_auxiliary<Compare, Random, Probability,
        std::is_empty_v<Compare> and not std::is_final_v<Compare>,
        std::is_empty_v<Random> and not std::is_final_v<Random>,
        std::is_empty_v<Probability> and not std::is_final_v<Probability>>;

避免我們手動地給出三個 bool 型別的樣板引數. 最後考慮到跳躍列表至少要保存頭部節點, 因此我們繼續進行壓縮 :

template <typename NodeType, typename Compare, typename Random, typename Probability>
struct skip_list_compress_with_node_type : skip_list_compress<Compare, Random, Probability> {
public:
    NodeType n;
public:
    constexpr skip_list_compress_with_node_type() = default;
    explicit skip_list_compress_with_node_type(NodeType n) :
            skip_list_compress<Compare, Random, Probability>(), n {n} {}
    skip_list_compress_with_node_type(NodeType n, Compare c) :
            skip_list_compress<Compare, Random, Probability>(std::move(c)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Random r) :
            skip_list_compress<Compare, Random, Probability>(std::move(r)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Probability p) :
            skip_list_compress<Compare, Random, Probability>(std::move(p)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Compare c, Random r) :
            skip_list_compress<Compare, Random, Probability>(std::move(c), std::move(r)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Compare c, Probability p) :
            skip_list_compress<Compare, Random, Probability>(std::move(c), std::move(p)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Random r, Probability p) :
            skip_list_compress<Compare, Random, Probability>(std::move(r), std::move(p)), n {std::move(n)} {}
    skip_list_compress_with_node_type(NodeType n, Compare c, Random r, Probability p) :
            skip_list_compress<Compare, Random, Probability>(std::move(c), std::move(r), std::move(p)),
            n {std::move(n)} {}
public:
    NodeType &node() noexcept {
        return this->n;
    }
    const NodeType &node() const noexcept {
        return this->n;
    }
};

這樣, 預設情況下, sizeof(skip_list<T>) 的值將會是 8. 如果不進行壓縮, 那麼 sizeof(skip_list<T>) 的值將會是 24, 如果增加一個空間配置器, 那麼這個值將會是 32. 這樣的空基礎類別優化的技術, 在 C++ 標準樣板程式庫中相當常見.

每一個 C++ 標準樣板程式庫中的容器都會有一些型別別名, 以方便特性萃取, 我們也為我們的跳躍列表增加型別別名 :

template <typename T, typename Compare = less<T>, typename Random = skip_list_random_number_generator, typename Probability = skip_list_probability_generator>
class skip_list {
public:
    using value_compare = Compare;
    using random_number_generator = Random;
    using probability_generator = Probability;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using reference = T &;
    using const_reference = const T &;
    using rvalue_reference = T &&;
    using pointer = T *;;
    using const_pointer = const T *;
    using iterator = skip_list_iterator<T, false>;
    using const_iterator = skip_list_iterator<T, true>;
    // ...
};

如果跳躍列表的記憶體配置允許自訂, 那麼還需要增加一個型別別名 : using allocator_type = Allocator;.

跳躍列表僅有一個成員 :

template <typename T, typename Compare = less<>, typename Random = skip_list_random_number_generator, typename Probability = skip_list_probability_generator>
class skip_list {
    // ...
private:
    skip_list_compress_with_node_type<skip_list_node<T> *, value_compare, random_number_generator, probability_generator> head;
};

這就是為什麼 sizeof(skip_list) 的值僅為 8 的原因.

最後, 我們宣告它的成員函式 :

template <typename T, typename Compare = std::less<>, typename Random =, typename Probability = skip_list_probability_generator>
class skip_list {
public:
    using value_compare = Compare;
    using random_number_generator = Random;
    using probability_generator = Probability;
    using size_type = allocator_traits_t(allocator_type, size_type);
    using difference_type = allocator_traits_t(allocator_type, difference_type);
    using value_type = T;
    using reference = allocator_traits_t(allocator_type, reference);
    using const_reference = allocator_traits_t(allocator_type, const_reference);
    using rvalue_reference = allocator_traits_t(allocator_type, rvalue_reference);
    using pointer = allocator_traits_t(allocator_type, pointer);
    using const_pointer = allocator_traits_t(allocator_type, const_pointer);
    using iterator = skip_list_iterator<T, false>;
    using const_iterator = skip_list_iterator<T, true>;
private:
    skip_list_compress_with_node_type<skip_list_node<T> *, value_compare, random_number_generator, probability_generator> head;
public:
    skip_list();
    explicit skip_list(size_type);
    skip_list(size_type, const_reference);
    explicit skip_list(value_compare);
    explicit skip_list(random_number_generator);
    explicit skip_list(probability_generator);
    skip_list(value_compare, random_number_generator);
    skip_list(value_compare, probability_generator);
    skip_list(random_number_generator, probability_generator);
    skip_list(value_compare, random_number_generator, probability_generator);
    template <typename Iterator>
    skip_list(std::enable_if_t<is_input_iterator_v<Iterator>, Iterator>, Iterator);
    skip_list(std::initializer_list<value_type>);
    skip_list(const skip_list &);
    skip_list(skip_list &&) noexcept;
    ~skip_list() noexcept;
public:
    skip_list &operator=(const skip_list &);
    skip_list &operator=(skip_list &&) noexcept;
    skip_list &operator=(std::initializer_list<value_type>);
    skip_list &operator=(random_number_generator);
    skip_list &operator=(probability_generator);
public:
    void assign(size_type, const_reference);
    template <typename Iterator>
    void assign(std::enable_if_t<is_input_iterator_v<Iterator>, Iterator>, Iterator);
    void assign(std::initializer_list<value_type>);
    reference front() noexcept;
    const_reference front() const noexcept;
    iterator before_begin() noexcept;
    const_iterator before_begin() const noexcept;
    iterator begin() noexcept;
    const_iterator begin() const noexcept;
    iterator end() noexcept;
    const_iterator end() const noexcept;
    const_iterator cbefore_begin() const noexcept;
    const_iterator cbegin() const noexcept;
    const_iterator cend() const noexcept;
    iterator lbefore_begin() noexcept;
    const_iterator lbefore_begin() const noexcept;
    const_iterator clbefore_begin() const noexcept;
    iterator lbegin() noexcept;
    const_iterator lbegin() const noexcept;
    const_iterator clbegin() const noexcept;
    bool empty() const noexcept;
    size_type size() const noexcept;
    size_type max_level() const noexcept;
    constexpr size_type max_size() noexcept;
    void clear() noexcept;
    void swap(skip_list &) noexcept;
    iterator insert(const_reference, size_type);
    iterator insert(rvalue_reference);
    template <typename Iterator>
    iterator insert(std::enable_if_t<is_input_iterator_v<Iterator>, Iterator>, Iterator);
    iterator insert(std::initializer_list<value_type>);
    iterator erase_after(const_iterator, const_iterator) noexcept;
    iterator erase_after(const_iterator) noexcept;
    template <typename ...Args>
    iterator emplace(Args &&...);
    void pop_front() noexcept;
public:
    random_number_generator &get_random_number_generator() noexcept;
    const random_number_generator &get_random_number_generator() const noexcept;
    probability_generator &get_probability_generator() noexcept;
    const probability_generator &get_probability_generator() const noexcept;
    template <typename ...Args>
    void reset_random_number_generator(Args &&...);
    template <typename ...Args>
    void reset_probability_generator(Args &&...);
public:
    template <typename ValueType>
    size_type remove(const ValueType &);
    template <typename UnaryPredicate>
    size_type remove_if(UnaryPredicate);
    template <typename BinaryPredicate>
    void unique(BinaryPredicate);
    template <typename ValueType>
    iterator find(const ValueType &);
    template <typename ValueType>
    const_iterator find(const ValueType &) const;
    template <typename UnaryPredicate>
    iterator find_if(UnaryPredicate);
    template <typename UnaryPredicate>
    const_iterator find_if(UnaryPredicate) const;
    template <typename ValueType>
    bool contains(const ValueType &) const;
    template <typename UnaryPredicate>
    bool contains_if(UnaryPredicate) const;
    template <typename ValueType>
    size_type count(const ValueType &) const;
    template <typename UnaryPredicate>
    size_type count_if(UnaryPredicate) const;
};

除了一些新增加的函式, 基本上大部分都和 C++ 標準樣板程式庫保持了一致. 對於新增加的成員函式, 主要有 :

lbegin, clbegin, lbefore_begin 和 clbefore_begin : 它用於回傳最低層的疊代器. 預設情況下, 我們回傳的疊代器處於節點的最高層. 這樣, 對於尋訪每一個元素帶來了困難;
max_level : 用於回傳當前跳躍列表中的最高級數, 它就直接保存在頭部節點中. 因為不可能存在任何節點, 其級數高於頭部節點.

個人認為比較複雜的操作有 :

複製建構子和複製指派運算子;
emplace 系列成員函式;
搜尋類成員函式;
erase 系列及 remove 系列成員函式.

對此, 我有對應的建議 :

你可以撰寫一個從其它跳躍列表複製到當前跳躍列表的專門函式, 讓複製建構子和複製指派運算子共享這個函式即可. 不過需要注意的是, 複製指派運算子在複製元素之前, 要清理當前存在於跳躍列表的元素;
所有 insert 系列函式都可以委託給成員函式 emplace. 在插入時, 你還需要考慮級的增加, 以及維護整個跳躍列表的級;
搜尋時可以判斷一下元素是否超出了跳躍列表當前所有元素的範圍. 雖然目前實作的是前向的跳躍列表, 不過我們至少可以判斷一下要搜尋的元素是否小於跳躍列表中的最小元素;
從跳躍列表中移除一個節點比較複雜, 除了要移除節點之外, 還需要維護跳躍列表的級;

另外, 如果跳躍列表中, 最高級對應的連結串列有且唯有頭部節點, 那麼我不建議繼續向上增加級. 根據文章, 大家可以自行進行實作.

大家可以參考一下我的程式碼 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/skip_list.hpp.

【資料結構】跳躍列表 (實作篇)

0. 前言

1. 實作

【C++】實作 `<type_traits>` (下)

機器學習筆記

發表評論點擊這裡以取消回覆

Board

文章預告

【資料結構】跳躍列表 (實作篇)

0. 前言

1. 實作

【C++】實作 <type_traits> (下)

機器學習筆記

估你鍾意

距離最近的點

【資料結構】佇列的應用 : 像素分割

貪婪演算法與 NP 問題 (下) – 0/1 背包問題

【C++】細談 constexpr

貪婪演算法與 NP 問題 (上) – 任務排程和箱櫃裝載

【資料結構】堆疊的應用 : 括號匹配和開關盒佈線

【演算法】凸包

C++ 2a 特性導讀 – Concept

新版本下的 Seafile

發表評論 點擊這裡以取消回覆

Board

文章預告

大家都搜尋

關注我們的微信官方帳號

【C++】實作 `<type_traits>` (下)

【C++】細談 `constexpr`

發表評論點擊這裡以取消回覆