C++跳表的简单实现

#include
#include
#include
#include
#include
#include
using namespace std;
template<typename T>
class skiplist
{
private:
	static inline constexpr int max_level = 16;//最大级数
	static inline constexpr double p = 0.6;//层级递减概率

	//随机生成模块
	std::random_device rd;
	std::mt19937 gen;
	std::uniform_real_distribution<> dis;
	struct node
	{
		T data{};
		std::array<shared_ptr<node>, max_level> vLevelNext ;
		node(T x = T()) :data(x)
		{
			for_each(vLevelNext.begin(), vLevelNext.end(), [](auto& elment) {elment.reset();});
		}
	};

	shared_ptr<node> head;
public:
	skiplist() :gen(rd())
	{
		head= std::make_shared<node>();//保证头节点非空，否则出现未定义行为
		dis = std::uniform_real_distribution<>(0, 1);
	}

	//好像可以效率优化
	bool find(T x) const
	{
		shared_ptr<node> pNow(head);
		//从最高层级开始查找
		for (int i = max_level - 1; i >= 0; --i)
		{
			while (pNow->vLevelNext[i] != nullptr && pNow->vLevelNext[i]->data < x)//同一层级中查找
				pNow = pNow->vLevelNext[i];
		}

		//若未找到
		if (pNow->vLevelNext[0] == nullptr) return false;
		if (pNow->vLevelNext[0]->data != x) return false;
	}

	//随机层级分配
	int randomLevel()
	{
		int ret = 0;
		while (ret < max_level - 1 && dis(gen) < p)
			++ret;
		return ret;
	}

	void insert(T x)
	{
		//构建插入节点
		shared_ptr<node> tmp = std::make_shared<node>(x);

		shared_ptr<node> pre[max_level];//前驱
		shared_ptr<node> pNow(head);

		for (int i = max_level - 1; i >= 0; --i)
		{
			//确定每个层级列表的前驱位置
			while (pNow->vLevelNext[i] != nullptr && pNow->vLevelNext[i]->data < x)
				pNow = pNow->vLevelNext[i];
			pre[i] = pNow;
		}
		// 根据随机分配的层级，依次把等于，低于这个层级的层级列表分别进行插入动作
		int level = randomLevel();
		for (int i = level; i >= 0; --i)
		{
			tmp->vLevelNext[i] = pre[i]->vLevelNext[i];
			pre[i]->vLevelNext[i] = tmp;
		}
	}
	//好像可以效率优化
	bool remove(T x)//删除成功返回true，未找到元素返回false
	{
		shared_ptr<node> pre[max_level];
		shared_ptr<node> now(head);

		//从上到下找到这个值对应的每层级列表的前驱位置
		for (int i = max_level - 1; i >= 0; i--)
		{
			while (now->vLevelNext[i] != nullptr && now->vLevelNext[i]->data < x)
				now = now->vLevelNext[i];
			pre[i] = now;
		}

		if (now->vLevelNext[0] == nullptr) return false;//说明没找到，跳表中没有这个值
		if (now->vLevelNext[0]->data != x) return false;//说明没找到，跳表中没有这个值

		 //遍历前驱列表，后面指向的是删除节点的都需要删除
		shared_ptr<node> del = now->vLevelNext[0];
		for (int i = max_level - 1; i >= 0; i--)
		{
			if (pre[i]->vLevelNext[i] != nullptr && pre[i]->vLevelNext[i] == del)
				pre[i]->vLevelNext[i] = pre[i]->vLevelNext[i]->vLevelNext[i];
		}

		return true;
	}
};

int main()
{
	for (int i = 1; i <= 10; i++)
	{
		std::set<int> S;
		skiplist<int> L;//基于目前的实现，跳表的析构特别耗费程序堆栈
		double clk1 = clock();
		for (int i = 1000; i >= 1; i--)
			L.insert(i);
		double clk2 = clock();
		for (int i = 1000; i >= 1; i--)
			S.insert(i);
		double clk3 = clock();
		printf("skiplist:%lf,set:%lf\n", clk2 - clk1, clk3 - clk2);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130