Skiplist实现

Question

这是我跳过列表实现的一个版本。在我的项目中，我存储类似于一对blobs的自定义类。我用int替换了我的自定义类。在skiplist.cc的末尾，我还添加了一些测试用法的main()函数。我想知道是否有一些错误或性能改进我错过了。

#skiplist.h

#ifndef _SKIP_LIST_LIST_H
#define _SKIP_LIST_LIST_H

#include <cstdint>
#include <array>

using size_t = std::size_t;

using V = int;
using K = int;

constexpr int compare(V const a, K const b){
    return a - b;
}

class SkipList {
public:
    using size_type   = size_t;
    using height_type = uint8_t;

public:
    static constexpr height_type MAX_HEIGHT     = 64;
    static constexpr height_type DEFAULT_HEIGHT = 32;

    class Iterator;

public:
    explicit
    SkipList(height_type height = DEFAULT_HEIGHT);
    SkipList(SkipList &&other);
    ~SkipList();

public:
    bool clear();

    const K *operator[](const K &key) const;
    bool erase(const V &key);

    bool insert(V &&data);

    size_type size(bool const = false) const noexcept{
        return dataCount_;
    }

public:
    Iterator lowerBound(const V &key) const;
    Iterator begin() const;
    static constexpr Iterator end();

private:
    struct      Node;

    template<typename T>
    using       HeightArray = std::array<T,  MAX_HEIGHT>;

    height_type height_;
    HeightArray<Node *>
            heads_;

    size_type   dataCount_;

private:
    void zeroing_();

    struct NodeLocator;

    NodeLocator locate_(const K &key, bool shortcut_evaluation);

    const Node *locateNode_(const K &key, bool const exact) const;

    height_type getRandomHeight_();

private:
    class RandomGenerator;

    static RandomGenerator rand_;
};

// ==============================

class SkipList::Iterator{
private:
    friend class SkipList;
    constexpr Iterator(const Node *node) : node_(node){}

public:
    Iterator &operator++();
    const V &operator*() const;

public:
    bool operator==(const Iterator &other) const{
        return node_ == other.node_;
    }

    bool operator!=(const Iterator &other) const{
        return ! operator==(other);
    }

    const V *operator ->() const{
        return & operator*();
    }

private:
    const Node  *node_;
};

// ==============================

inline auto SkipList::lowerBound(const K &key) const -> Iterator{
    return locateNode_(key, false);
}

inline auto SkipList::begin() const -> Iterator{
    return heads_[0];
}

inline constexpr auto SkipList::end() -> Iterator{
    return nullptr;
}

#endif

skiplist.cc

#include "skiplist.h"

#include <stdexcept>
#include <algorithm>    // fill
#include <random>   // mt19937, bernoulli_distribution

#include <cassert>

class SkipList::RandomGenerator{
public:
    bool operator()(){
        return distr_(gen_);
    }

private:
    std::mt19937            gen_{ (uint32_t) time(nullptr) };
    std::bernoulli_distribution distr_{ 0.5 };
};

SkipList::RandomGenerator SkipList::rand_;

// ==============================

/*
We do ***NOT*** store next[] array size,
***NOR*** we store NULL after last next node.

It turn out it does not need, because NULL lanes are already NULL.

Disadvantage is once allocated, no one knows the size,
except probably with malloc_usable_size();

[2]------------------------------->NULL
[1]------>[1]------>[1]----------->NULL
[0]->[0]->[0]->[0]->[0]->[0]->[0]->NULL

*/

struct SkipList::Node{
    V   data;
    Node    *next[1];   // system dependent, dynamic, at least 1

public:
    // no need universal ref
    Node(V &&data) : data(std::move(data)){}

private:
    static size_t calcNewSize__(size_t const size, height_type const height){
        return size + (height - 1) * sizeof(Node *);
    }

public:
    static void *operator new(size_t const size, height_type const height) {
        return ::operator new(calcNewSize__(size, height));
    }

    static void *operator new(size_t const size, height_type const height, std::nothrow_t ) {
        return ::operator new(calcNewSize__(size, height), std::nothrow);
    }
};

// ==============================

struct SkipList::NodeLocator{
    HeightArray<Node **>    prev;
    Node            *node   = nullptr;
};

// ==============================

SkipList::SkipList(height_type const height) :
        height_(height){
    assert( height > 0 && height <= MAX_HEIGHT );

    zeroing_();
}

SkipList::SkipList(SkipList &&other):
        height_     (std::move(other.height_    )),
        heads_      (std::move(other.heads_     )),
        dataCount_  (std::move(other.dataCount_ )){
    other.zeroing_();
}

SkipList::~SkipList(){
    clear();
}

bool SkipList::clear(){
    for(const Node *node = heads_[0]; node; ){
        const Node *copy = node;

        node = node->next[0];

        delete copy;
    }

    zeroing_();

    return true;
}

bool SkipList::insert(V && newdata){
    const auto &key = newdata;

    const auto nl = locate_(key, true);

    if (nl.node){
        // update in place.

        V & olddata = nl.node->data;

        // copy assignment
        olddata = std::move(newdata);

        return true;
    }

    // create new node

    height_type const height = getRandomHeight_();

    Node *newnode = new(height, std::nothrow) Node(std::move(newdata));

    if (newnode == nullptr){
        // newdata will be magically destroyed.
        return false;
    }

    /* SEE REMARK ABOUT NEXT[] SIZE AT THE TOP */
    // newnode->height = height

    // place new node where it belongs
    for(height_type i = 0; i < height; ++i){
        newnode->next[i] = *nl.prev[i];
        *nl.prev[i] = newnode;
    }

#ifdef DEBUG_PRINT_LANES
    printf("%3u Lanes-> ", height);
    for(height_type i = 0; i < height; ++i)
        printf("%p ", (void *) newnode->next[i]);
    printf("\n");
#endif

    /* SEE REMARK ABOUT NEXT[] SIZE AT THE TOP */
    // newnode->next[i] = NULL;

    ++dataCount_;

    return true;
}

const V *SkipList::operator[](const K &key) const{
    const Node *node = locateNode_(key, true);

    return node ? & node->data : nullptr;
}

bool SkipList::erase(const K &key){
    const auto nl = locate_(key, false);

    if (nl.node == nullptr)
        return true;

    for(height_type h = 0; h < height_; ++h){
        if (*nl.prev[h] == nl.node)
            *nl.prev[h] = nl.node->next[h];
        else
            break;
    }

    const V & data = nl.node->data;

    dataCount_--;

    delete nl.node;

    return true;
}

// ==============================

void SkipList::zeroing_(){
    dataCount_ = 0;

    std::fill(heads_.begin(), heads_.end(), nullptr);
}

auto SkipList::locate_(const K &key, bool const shortcut_evaluation) -> NodeLocator{
    NodeLocator nl;

    Node **jtable = heads_.data();

    for(height_type h = height_; h --> 0;){
        for(Node *node = jtable[h]; node; node = node->next[h]){
            const V & data = node->data;
            int const cmp = compare(data, key);

            if (cmp >= 0){
                if (cmp == 0 && (shortcut_evaluation || h == 0) ){
                    // found
                    nl.node = node;

                    if (shortcut_evaluation){
                        // at this point, we do not really care,
                        // if nl.prev is setup correctly.
                        return nl;
                    }
                }

                break;
            }

            jtable = node->next;
        }

        nl.prev[h] = & jtable[h];
    }

    return nl;
}

auto SkipList::locateNode_(const K &key, bool const exact) const -> const Node *{
    const Node * const *jtable = heads_.data();

    const Node *node = nullptr;

    for(height_type h = height_; h --> 0;){
        for(node = jtable[h]; node; node = node->next[h]){
            const V & data = node->data;
            int const cmp = compare(data, key);

            if (cmp >= 0){
                if (cmp == 0){
                    // found
                    return node;
                }

                break;
            }

            jtable = node->next;
        }
    }

    return exact ? nullptr : node;
}


auto SkipList::getRandomHeight_() -> height_type{
    // This gives slightly better performance,
    // than divide by 3 or multply by 0.33

    // We execute rand() inside the loop,
    // but performance is fast enought.

    height_type h = 1;
    while( h < height_ && rand_() )
        h++;

    return h;
}


// ==============================


SkipList::Iterator &SkipList::Iterator::operator++(){
    node_ = node_->next[0];
    return *this;
}

const V &SkipList::Iterator::operator*() const{
    assert(node_);

    return node_->data;
}

// ==============================
// ==============================
// ==============================

#include <iostream>

inline void print(const char *val){
    std::cout << val << '\n';
}

inline void println(){
    print("-------------------");
}

inline void print(const V val){
    std::cout << val << '\n';
}

inline void print(const V *val){
    if (val)
        print(*val);
    else
        print("_none_");
}

inline void print(const SkipList &list){
    for(auto x : list)
        print(x);

    println();
}

constexpr V samples[] = { 100, 5, 22, 59, 35, 25, 8, 3 };

int main(){
    SkipList list;

    for(auto x : samples)
        list.insert(std::move(x));

    print(list);

    print(list[22]);
    print(list[999]);

    println();

    list.erase(22);

    print(list[22]);

    println();

    print(list);
}

Answer 1

您是否知道，如果您定义了移动构造函数(正如您所做的那样)，移动赋值不是默认生成的，并且复制赋值和复制构造被删除，也就是会给出一个编译器错误？

同样，constexpr也暗示着内联，这样您就可以跳过它了。