V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
zhengji
V2EX  ›  分享创造

C++ 实现一个支持模板的 SkipList

  •  
  •   zhengji · 2018-08-11 23:32:45 +08:00 · 1844 次点击
    这是一个创建于 1203 天前的主题,其中的信息可能已经有所发展或是发生改变。

    License: MIT

    SkipList

    使用模板实现的跳表:

    • 使用简单,只需要引入头文件 SkipList.h
    • 支撑增删改查
    • 支持各种类型: 包括内建类型, 自定义数据结构

    Quick Start

    #include "SkipList.h"
    #include <iostream>
    using namespace std;
    
    int main() {
        SkipList<int> sl;
        sl.Print();
    
        sl.Insert(3);
        sl.Insert(1);
        sl.Insert(0);
    
        if (sl.Contains(s1))
        {
            cout << "3 in list" << endl;
        }
        sl.Print();
    
        sl.Erase(s1);
        sl.Print();
    
        if (!sl.Contains(s1))
            cout << "3 has been deleted" << endl;
        return 0;
    }
    
    8 条回复    2018-08-15 17:45:14 +08:00
    coordinate
        1
    coordinate   2018-08-12 09:33:37 +08:00
    。。。这也可以开源吗,而且你这代码质量不行啊
    GeruzoniAnsasu
        2
    GeruzoniAnsasu   2018-08-12 10:58:34 +08:00 via Android
    课……课堂作业?
    lychnis
        3
    lychnis   2018-08-12 13:46:47 +08:00
    楼上暴击...
    看了下, 确实需要提高代码水平..
    这年头为啥什么人都想着开源呢....国内这种浮躁的风气真是提现方方面面..
    大概随便看了几眼, 说几个改进点
    1 int 这种类型不要随便乱用
    2 分配内存 new...??? std 标准库没看过? 给个分配器啊大哥
    3 #define MAX_LEVEL 100 ????
    4 很多地方缺少 checker.. 同上 麻烦看下 std 一般实现
    5 变量名 x 这种太随意了.. 如果面试写出这种代码..怕是直接 pass 了
    6 楼下补充
    yulon
        4
    yulon   2018-08-12 18:35:48 +08:00
    演示代码变量名和 int 都没什么关系,分配器这种东西,标准委员会都觉得普通容器加上简直脱裤子放屁,还会增加不必要的代码,所以搞了个 std::pmr,有需求再用,旧的还支持只是为了兼容旧的分配器模型。
    ccpp132
        5
    ccpp132   2018-08-14 13:58:00 +08:00
    感觉 skip list 和 c++内置的 rbtree 比没什么优势啊
    wyx
        6
    wyx   2018-08-14 16:41:30 +08:00
    @ccpp132 skip list 的实现简单
    shilyx
        7
    shilyx   2018-08-14 16:44:28 +08:00   ❤️ 1
    距离“库”的要求还比较远
    1、头文件中出现“ using std ”?
    2、Print 函数直接打印到控制台?

    暂没到做“库”的水平但有做“库”的心,相信是个好的开始,先自己持续使用和迭代吧
    plusice
        8
    plusice   2018-08-15 17:45:14 +08:00   ❤️ 1
    老纪!
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2341 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 09:41 · PVG 17:41 · LAX 01:41 · JFK 04:41
    ♥ Do have faith in what you're doing.