生成文件和从文件中读取数据。
需求如下：
你的任务是实现 SkipList 类中的数据持久化成员函数和数据加载成员函数。
持久化数据成员函数签名：void dump_file();
该成员函数负责将存储引擎内的数据持久化到文件中。数据的持久化格式是将每个键值对写入文件的单独一行，采用key:value的格式。这种方式不仅确保了数据格式的一致性，还便于数据的恢复和解析。
读取数据成员函数签名：void load_file();
此成员函数的目的是从文件中读取之前持久化的数据，并将其加载到存储引擎中。读取的数据格式遵循每行一个key:value键值对的规则。在数据加载过程中，成员函数还需确保跳表的索引能够被正确地重建，以保持数据的快速访问和检索性能。
其实看起来蛮简单的，就是把原本数据按照一定格式读入到文件中，和从文件中读取数据再调用insert_element函数就行了。但实现起来还是遇到了几个坑的。
首先是文件读写，这个网上版本很多，随意选择一种就行。
包含如下头文件：
#include <fstream>
#include <iostream>在要编写的dump_file函数里写明绝对路径，然后修改下print拿过来用就行了。代码如下：
void dump_file() {
std::ofstream out("D:\\dev_c++\\destination\\out.txt");
if (out.is_open())
{
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
while (cur) {
out << cur->getKey() << ":" << cur->get_value() << '\n';
cur = cur->forwards[curlevel];
}
curlevel--;
}
out.close();
}
}这个在在线判题系统里似乎修改不了，需要用本地C++编译器。然后还会在time(0)出报错，需要加上如下头文件：
#include <sys/time.h>
实现效果如图，还用的删除跳表那里的输入输出数据
再来看读入数据：
这个首先要判断是否打开了文件，没打开直接报错，在线判题网上里就是直接报错的。所以我们还是要用编译器。之后就是对输入字符串进行处理，循环遍历找到':'下标作为分隔符下标，以此为依据调用substr函数即可。
代码如下：
void load_file() {
std::ifstream in("D:\\dev_c++\\destination\\out.txt");
char buffer[256];
if (!in.is_open()) {
std::cout << "open error";
} else {
while (!in.eof()) {
std::string s;
in >> s;
int index = 0;
if (s.size() == 0) return;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ':') {
index = i;
break;
}
}
// std::cout << s << ' ';
std::string s1 = s.substr(0, index);
std::string s2 = s.substr(index + 1, s.length() - 1 - index); //下标从index+1开始
std::cout << s1 << s2 << std::endl;
// int key = std::stoi(s1);
int value = std::stoi(s2);
insert_element(key, value);
}
}
}这个实现的就只是int类型的读取文件。
运行效果如图：
由于我们采用的是随机层数的机制，所以每次结果层数会不一致，也很正常。这也是跳表好玩的地方之一了。
整体代码如下：
#include<stdlib.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <sys/time.h>
template<typename K, typename V>
class Node {
private:
K key;
V val;
int node_level;
public:
Node** forwards;
public:
Node(K inkey, V value, int level): key(inkey), val(value),
node_level(level),forwards(nullptr)
{
this->forwards = new Node<K, V>*[node_level+1];
memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));
}
~Node(){
delete forwards;
};
K getKey() const {
return key;
}
V get_value() const {
return val;
}
int getLevel() const {
return node_level;
}
void set_value(V value) {
val = value;
}
};
template<typename K, typename V>
class SkipList {
private:
Node<K,V>* HeadNode = nullptr;
int _maxlevel = 0;
int temp_level = 0;
public:
SkipList(int maxlevel = 500) {
_maxlevel = maxlevel;
HeadNode = new Node<K, V>(K(),V(),maxlevel);
}
~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }
int getRandomLevel() {
srand((int)time(0));
int k = 1;
while (rand() % 2) {
k++;
}
k = (k < _maxlevel) ? k : _maxlevel;
return k;
}
int insert_element(const K key, const V value) {
int flag = 0;
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode;
while (cur) {
if (cur->getKey() == key) {
flag = 1;
cur->set_value(value);
}
cur = cur->forwards[curlevel];
}
curlevel--;
}
if (flag == 1) return 1;
Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());
if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();
curlevel = newNode->getLevel();
while (curlevel) {
Node<K,V>* prev = HeadNode;
cur = HeadNode->forwards[curlevel];
while (cur) {
if (cur->getKey() > newNode->getKey()) {
prev->forwards[curlevel] = newNode;
newNode->forwards[curlevel] = cur;
break;
}
cur = cur->forwards[curlevel];
prev = prev->forwards[curlevel];
}
if (!cur)
prev->forwards[curlevel] = newNode;
curlevel--;
}
return 0;
}
bool search_element(K key) {
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
while (cur) {
if (cur->getKey() == key) return true;
cur = cur->forwards[curlevel];
}
curlevel--;
}
return false;
}
void delete_element(K key) {
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
Node<K,V>* prev = HeadNode;
cur = HeadNode->forwards[curlevel];
while (cur) {
if (cur->getKey() == key) {
prev->forwards[curlevel] = cur->forwards[curlevel];
break;
}
cur = cur->forwards[curlevel];
prev = prev->forwards[curlevel];
}
curlevel--;
}
}
void print() {
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
std::cout << "Level " << curlevel-1 << ": ";
while (cur) {
std::cout << cur->getKey() << ":" << cur->get_value() << ';';
cur = cur->forwards[curlevel];
}
std::cout << std::endl;
curlevel--;
}
}
void dump_file() {
std::ofstream out("D:\\dev_c++\\destination\\out.txt");
if (out.is_open())
{
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
while (cur) {
out << cur->getKey() << ":" << cur->get_value() << '\n';
cur = cur->forwards[curlevel];
}
curlevel--;
}
out.close();
}
}
void load_file() {
std::ifstream in("D:\\dev_c++\\destination\\out.txt");
char buffer[256];
if (!in.is_open()) {
std::cout << "open error";
} else {
while (!in.eof()) {
std::string s;
in >> s;
int index = 0;
if (s.size() == 0) return;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ':') {
index = i;
break;
}
}
// std::cout << s << ' ';
std::string s1 = s.substr(0, index);
std::string s2 = s.substr(index + 1, s.length() - 1 - index);
// std::cout << s1 << s2 << std::endl;
int key = std::stoi(s1);
int value = std::stoi(s2);
insert_element(key, value);
}
}
}
};
int main() {
SkipList<int, int> mySkipList;
// 插入删除数据
int n,k,m;
std::cin >> n >> k >> m;
while (n--) {
int key, v, r;
std::cin >> key >> v;
r = mySkipList.insert_element(key,v);
if (r == 0) std::cout << "Insert Success" << std::endl;
else std::cout << "Insert Failed" << std::endl;
}
while (k--) {
int key;
std::cin >> key;
mySkipList.delete_element(key);
}
while (m--) {
int k;
std::cin >> k;
if (mySkipList.search_element(k)) std::cout << "Search Success" << std::endl;
else std::cout << "Search Failed" << std::endl;
}
mySkipList.dump_file();
// 读文件并展示
mySkipList.load_file();
mySkipList.print();
}模块合并
需求如下：
你的任务是创建一个 skiplist.h 的头文件，包含前面所有章节介绍的 Node 类和 SkipList 类，用以在其他程序中进行引用
其实主要也就是引入了锁，加上如下头文件：
#include <mutex> 并且在插入删除数据函数前后分别加锁和解锁就行了，伪代码如下：
// 只有在插入和删除的时候，才会进行加锁
template <typename K, typename V>
int SkipList<K, V>::insert_element(const K key, const V value) {
mtx.lock(); // 在函数第一句加锁
// ... 算法过程（省略）
if (current != NULL && current->get_key() == key) {
std::cout << "key: " << key << ", exists" << std::endl;
// 在算法流程中有一个验证 key 是否存在的过程
// 在此处需要提前 return，所以提前解锁
mtx.unlock();
return 1;
}
// ...
mtx.unlock(); // 函数执行完毕后解锁
return 0;
}
template <typename K, typename V>
void SkipList<K, V>::delete_element(K key) {
mtx.lock(); // 加锁
// ... 算法过程（省略）
mtx.unlock(); // 解锁
return;
}最终代码如下：
#include<stdlib.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <mutex>
#include <sys/time.h>
std::mutex mtx;
template<typename K, typename V>
class Node {
private:
K key;
V val;
int node_level;
public:
Node** forwards;
public:
Node(K inkey, V value, int level): key(inkey), val(value),
node_level(level),forwards(nullptr)
{
this->forwards = new Node<K, V>*[node_level+1];
memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));
}
~Node(){
delete forwards;
};
K getKey() const {
return key;
}
V get_value() const {
return val;
}
int getLevel() const {
return node_level;
}
void set_value(V value) {
val = value;
}
};
template<typename K, typename V>
class SkipList {
private:
Node<K,V>* HeadNode = nullptr;
int _maxlevel = 0;
int temp_level = 0;
public:
SkipList(int maxlevel = 500) {
_maxlevel = maxlevel;
HeadNode = new Node<K, V>(K(),V(),maxlevel);
}
~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }
int getRandomLevel() {
srand((int)time(0));
int k = 1;
while (rand() % 2) {
k++;
}
k = (k < _maxlevel) ? k : _maxlevel;
return k;
}
int insert_element(const K key, const V value) {
mtx.lock();
int flag = 0;
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode;
while (cur) {
if (cur->getKey() == key) {
flag = 1;
cur->set_value(value);
}
cur = cur->forwards[curlevel];
}
curlevel--;
}
if (flag == 1) return 1;
Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());
if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();
curlevel = newNode->getLevel();
while (curlevel) {
Node<K,V>* prev = HeadNode;
cur = HeadNode->forwards[curlevel];
while (cur) {
if (cur->getKey() > newNode->getKey()) {
prev->forwards[curlevel] = newNode;
newNode->forwards[curlevel] = cur;
break;
}
cur = cur->forwards[curlevel];
prev = prev->forwards[curlevel];
}
if (!cur)
prev->forwards[curlevel] = newNode;
curlevel--;
}
mtx.unlock();
return 0;
}
bool search_element(K key) {
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
while (cur) {
if (cur->getKey() == key) return true;
cur = cur->forwards[curlevel];
}
curlevel--;
}
return false;
}
void delete_element(K key) {
mtx.lock();
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
Node<K,V>* prev = HeadNode;
cur = HeadNode->forwards[curlevel];
while (cur) {
if (cur->getKey() == key) {
prev->forwards[curlevel] = cur->forwards[curlevel];
break;
}
cur = cur->forwards[curlevel];
prev = prev->forwards[curlevel];
}
curlevel--;
}
mtx.unlock();
}
void print() {
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
std::cout << "Level " << curlevel-1 << ": ";
while (cur) {
std::cout << cur->getKey() << ":" << cur->get_value() << ';';
cur = cur->forwards[curlevel];
}
std::cout << std::endl;
curlevel--;
}
}
void dump_file() {
std::ofstream out("D:\\dev_c++\\destination\\out.txt");
if (out.is_open())
{
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
while (cur) {
out << cur->getKey() << ":" << cur->get_value() << '\n';
cur = cur->forwards[curlevel];
}
curlevel--;
}
out.close();
}
}
void load_file() {
std::ifstream in("D:\\dev_c++\\destination\\out.txt");
char buffer[256];
if (!in.is_open()) {
std::cout << "open error";
} else {
while (!in.eof()) {
std::string s;
in >> s;
int index = 0;
if (s.size() == 0) return;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ':') {
index = i;
break;
}
}
// std::cout << s << ' ';
std::string s1 = s.substr(0, index);
std::string s2 = s.substr(index + 1, s.length() - 1 - index);
// std::cout << s1 << s2 << std::endl;
int key = std::stoi(s1);
int value = std::stoi(s2);
insert_element(key, value);
}
}
}
};
int main() {
SkipList<int, int> mySkipList;
// 插入删除数据
int n,k,m;
std::cin >> n >> k >> m;
while (n--) {
int key, v, r;
std::cin >> key >> v;
r = mySkipList.insert_element(key,v);
if (r == 0) std::cout << "Insert Success" << std::endl;
else std::cout << "Insert Failed" << std::endl;
}
while (k--) {
int key;
std::cin >> key;
mySkipList.delete_element(key);
}
while (m--) {
int k;
std::cin >> k;
if (mySkipList.search_element(k)) std::cout << "Search Success" << std::endl;
else std::cout << "Search Failed" << std::endl;
}
mySkipList.dump_file();
// 读文件并展示
mySkipList.load_file();
mySkipList.print();
}压力测试
测试结果如图
这一模块是要编写代码对所做项目进行测试，所用代码文件如下：
// 引入必要的头文件
#include <iostream> // 用于输入输出流
#include <chrono> // 用于高精度时间测量
#include <cstdlib> // 包含一些通用的工具函数，如随机数生成
#include <pthread.h> // 用于多线程编程
#include <time.h> // 用于时间处理函数
#include "./skiplist.h" // 引入自定义的跳表实现
// 定义宏常量
#define NUM_THREADS 1 // 线程数量
#define TEST_COUNT 100000// 测试用的数据量大小
SkipList<int, std::string> skipList(18); // 创建一个最大层级为18的跳表实例
// 插入元素的线程函数
void *insertElement(void* threadid) {
long long tid; // 线程ID
tid = (long long)threadid; // 将void*类型的线程ID转换为long型
std::cout << tid << std::endl; // 输出线程ID
int tmp = TEST_COUNT/NUM_THREADS; // 计算每个线程应该插入的元素数量
// 循环插入元素
for (int i=tid*tmp, count=0; count<tmp; i++) {
count++;
skipList.insert_element(rand() % TEST_COUNT, "a"); // 随机生成一个键，并插入带有"a"的元素
}
pthread_exit(NULL); // 退出线程
}
// 检索元素的线程函数
void *getElement(void* threadid) {
long long tid; // 线程ID
tid = (long long)threadid; // 将void*类型的线程ID转换为long型
std::cout << tid << std::endl; // 输出线程ID
int tmp = TEST_COUNT/NUM_THREADS; // 计算每个线程应该检索的元素数量
// 循环检索元素
for (int i=tid*tmp, count=0; count<tmp; i++) {
count++;
skipList.search_element(rand() % TEST_COUNT); // 随机生成一个键，并尝试检索
}
pthread_exit(NULL); // 退出线程
}
int main() {
srand(time(NULL)); // 初始化随机数生成器
{
pthread_t threads[NUM_THREADS]; // 定义线程数组
int rc; // 用于接收pthread_create的返回值
int i; // 循环计数器
auto start = std::chrono::high_resolution_clock::now(); // 开始计时
// 创建插入元素的线程
for( i = 0; i < NUM_THREADS; i++ ) {
std::cout << "main() : creating thread, " << i << std::endl;
rc = pthread_create(&threads[i], NULL, insertElement, (void *)i); // 创建线程
if (rc) {
std::cout << "Error:unable to create thread," << rc << std::endl;
exit(-1); // 如果线程创建失败，退出程序
}
}
void *ret; // 用于接收pthread_join的返回值
// 等待所有插入线程完成
for( i = 0; i < NUM_THREADS; i++ ) {
if (pthread_join(threads[i], &ret) != 0 ) {
perror("pthread_create() error");
exit(3); // 如果线程等待失败，退出程序
}
}
auto finish = std::chrono::high_resolution_clock::now(); // 结束计时
std::chrono::duration<double> elapsed = finish - start; // 计算耗时
std::cout << "insert elapsed:" << elapsed.count() << std::endl; // 输出插入操作耗时
}
// 下面的代码块与上面类似，用于创建并管理检索操作的线程
{
pthread_t threads[NUM_THREADS];
int rc;
int i;
auto start = std::chrono::high_resolution_clock::now();
for( i = 0; i < NUM_THREADS; i++ ) {
std::cout << "main() : creating thread, " << i << std::endl;
rc = pthread_create(&threads[i], NULL, getElement, (void *)i);
if (rc) {
std::cout << "Error:unable to create thread," << rc << std::endl;
exit(-1);
}
}
void *ret;
for( i = 0; i < NUM_THREADS; i++ ) {
if (pthread_join(threads[i], &ret) != 0 ) {
perror("pthread_create() error");
exit(3);
}
}
auto finish = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> elapsed = finish - start;
std::cout << "get elapsed:" << elapsed.count() << std::endl;
}
pthread_exit(NULL); // 主线程退出
return 0;
}我们还需要新建一个项目工程文件，将之前写的代码重命名成skiplist.h，编译运行进行测试，编译链接要按照如下指令来：
g++ --std=c++11 main.cpp -o stress -pthreaddev_c++里面点进这里修改这个即可。
但在测试过程中，我发现即便是很少的数据量比如4，运行黑框仍旧会卡住，一直无法出来。自己检查代码后才发现，是我在插入数据函数加锁时只在return 0的情况下加了锁，因此在return 1 的情况下，系统就陷入了死锁局面！
加上去之后就好了。
修改后代码如下：
//skiplist.h
#include<stdlib.h>
#include <iostream>
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>
#include <mutex>
#include <sys/time.h>
std::mutex mtx;
template<typename K, typename V>
class Node {
private:
K key;
V val;
int node_level;
public:
Node** forwards;
public:
Node(K inkey, V value, int level): key(inkey), val(value),
node_level(level),forwards(nullptr)
{
this->forwards = new Node<K, V>*[node_level+1];
memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));
}
~Node(){
delete forwards;
};
K getKey() const {
return key;
}
V get_value() const {
return val;
}
int getLevel() const {
return node_level;
}
void set_value(V value) {
val = value;
}
};
template<typename K, typename V>
class SkipList {
private:
Node<K,V>* HeadNode = nullptr;
int _maxlevel = 0;
int temp_level = 0;
public:
SkipList(int maxlevel = 500) {
_maxlevel = maxlevel;
HeadNode = new Node<K, V>(K(),V(),maxlevel);
}
~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }
int getRandomLevel() {
srand((int)time(0));
int k = 1;
while (rand() % 2) {
k++;
}
k = (k < _maxlevel) ? k : _maxlevel;
return k;
}
int insert_element(const K key, const V value) {
mtx.lock();
int flag = 0;
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode;
while (cur) {
if (cur->getKey() == key) {
flag = 1;
cur->set_value(value);
}
cur = cur->forwards[curlevel];
}
curlevel--;
}
if (flag == 1) {
mtx.unlock();
return 1;
}
Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());
if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();
curlevel = newNode->getLevel();
while (curlevel) {
Node<K,V>* prev = HeadNode;
cur = HeadNode->forwards[curlevel];
while (cur) {
if (cur->getKey() > newNode->getKey()) {
prev->forwards[curlevel] = newNode;
newNode->forwards[curlevel] = cur;
break;
}
cur = cur->forwards[curlevel];
prev = prev->forwards[curlevel];
}
if (!cur)
prev->forwards[curlevel] = newNode;
curlevel--;
}
mtx.unlock();
return 0;
}
bool search_element(K key) {
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
while (cur) {
if (cur->getKey() == key) return true;
cur = cur->forwards[curlevel];
}
curlevel--;
}
return false;
}
void delete_element(K key) {
mtx.lock();
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
Node<K,V>* prev = HeadNode;
cur = HeadNode->forwards[curlevel];
while (cur) {
if (cur->getKey() == key) {
prev->forwards[curlevel] = cur->forwards[curlevel];
break;
}
cur = cur->forwards[curlevel];
prev = prev->forwards[curlevel];
}
curlevel--;
}
mtx.unlock();
}
void print() {
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
std::cout << "Level " << curlevel-1 << ": ";
while (cur) {
std::cout << cur->getKey() << ":" << cur->get_value() << ';';
cur = cur->forwards[curlevel];
}
std::cout << std::endl;
curlevel--;
}
}
void dump_file() {
std::ofstream out("D:\\dev_c++\\destination\\out.txt");
if (out.is_open())
{
Node<K,V>* cur = HeadNode;
int curlevel = temp_level;
while (curlevel) {
cur = HeadNode->forwards[curlevel];
while (cur) {
out << cur->getKey() << ":" << cur->get_value() << '\n';
cur = cur->forwards[curlevel];
}
curlevel--;
}
out.close();
}
}
void load_file() {
std::ifstream in("D:\\dev_c++\\destination\\out.txt");
char buffer[256];
if (!in.is_open()) {
std::cout << "open error";
} else {
while (!in.eof()) {
std::string s;
in >> s;
int index = 0;
if (s.size() == 0) return;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ':') {
index = i;
break;
}
}
// std::cout << s << ' ';
std::string s1 = s.substr(0, index);
std::string s2 = s.substr(index + 1, s.length() - 1 - index);
// std::cout << s1 << s2 << std::endl;
int key = std::stoi(s1);
int value = std::stoi(s2);
insert_element(key, value);
}
}
}
};跳表项目总结
这次完整做完了一个小项目，花了几天。最后才发现测试时会有一些不测试就发现不了的小bug，所以说测试还是蛮重要的。