C++实现用户排行榜

在学习C时,一位大佬给我出了个题,如何实现积分排行榜,我通过查资料问AI,写了下面的处理方式\首先,当积分排行榜很明显就是对大量数据进行排序,会对指定结点有大量的删除,修改,增加操作我首先想的是肯定不能用vector这类的数据结构,vector,对于数据的增加,删除和修改vector的添加时间复杂度O(n),删除O(n),修改,O(n),查前top500 O(1)所以时间复杂度太高了,不合适set和map,这两个数据结构底层是红黑树实现的,每次添加时需要保证红黑树规则,进行左旋右旋,修改颜色操作,删除,修改都需要进行大量对结点的操作,时间复杂度可想而知的O(logn),而且构建时很复杂通过查找资料Redis 有序集合 (ZSet) 底层就是跳表是全球互联网公司排行榜的标准方案。那到底是用红黑树写还是要通过跳表来写跳表的结构如下可以看到,当查找数据时,从头结点开始(最上层),想找到9,第3层的头节点开始先找4,右边是NULL,往下跳,跳到第2层的4结点找10,大了,从4结点开始再往下跳,跳到第1层的4结点,往右找到7,小了,小了就把指针放到7这个结点,再往右跳,10大了,在7这个结点往下跳,跳到第0层的7结点,往右跳,找到9了.这过程中4--4--4--7--7--9走了6个结点如果是红黑树呢找9走过了4个结点,这是数据量小的情况,如果数据量超级大100000个用户,这个红黑树和跳表其实是差不多的.再看插入,跳表在插入时,从第3层开始找,和查找一样找到第0层该插入的位置,然后插入,再抛硬币0.5概率,决定是否要往上建索引(在极端情况下,当每次插入时抛硬币,都不往上插,那效率就会降低到O(n)),效率为O(logn)红黑树在插入时,要遵循左根右,根叶红,不红红,黑路同,需要左旋右旋,判断爷,叔,父结点颜色,改变颜色,等等复杂操作,效率为O(logn)修改数据时,跳表修改结点不需要动太多结点而红黑树需要判断红黑树是否满足,再次判断左根右,根叶红,不红红,黑路同获取数据时,跳表的效率是O(m),从第0层从左到右获取你想要的前m个用户积分数据即可红黑树则是O(logn)下面是对整个排行榜的构建过程在构建过程中,我觉得难点在于删除操作,删除时,要记录前驱结点,从上到下删除,改指针,找前驱#includeiostream #includevector using namespace std; struct Node { string username; int score; Node* down; Node* right; Node(string username, int score) :username(username), score(score), down(nullptr), right(nullptr){} }; class SkipList { public: int MAX_LEVEL; vectorNode*head;//存头结点(最左边那列) vectorNode*path;//存走过的结点 SkipList(int maxlevel) { MAX_LEVEL maxlevel; path.resize(maxlevel, nullptr);//对走过的结点初始化 for (int i 0; i maxlevel - 1; i) {//最左边的头结点 head.push_back(new Node(, -65535)); } for (int i maxlevel-1; i 0; --i) { head[i]-down head[i - 1]; } } void insertNode(string name,int score) { //从最顶层开始存放前驱结点 Node* cur head[MAX_LEVEL - 1]; int level MAX_LEVEL-1; while (cur ! nullptr) { if (cur-right nullptr || cur-right-score score) { path[level] cur;//将最左侧的头节点都记录到了path中 cur cur-down; level--; } else { cur cur-right; } } //从最底层开始插入 Node* node new Node(name, score); node-right path[0]-right;//path[0]右边相当于连了个nullptr,先把nullptr给到node-right path[0]-right node;//然后连到一起 int nowlevel 0;//从0层开始插入,50%的概率插入 while (rand() % 2 0 nowlevel MAX_LEVEL - 1) { nowlevel; Node* upNode new Node(name, score); upNode-right path[nowlevel]-right; path[nowlevel]-right upNode; upNode-down node;//连下面 //更新现在node的位置 node upNode; } } Node* SearchUser(int score,string name) { //从头节点开始找 Node* nodeHead head[MAX_LEVEL - 1]; while (nodeHead ! nullptr) { while (nodeHead-right ! nullptr nodeHead-right-score score) {//只要满足右边比左边大,且右边不是空的,就一直往右边走 nodeHead nodeHead-right; } if (nodeHead-right ! nullptr) {//右边不为空,但是分数小于或者等于了要找的分数 if (nodeHead-right-score score nodeHead-right-username name) { return nodeHead; } } else { nodeHead nodeHead-down; } } //找完了都没找到 return nullptr; } void DeleteNode(int score,string name) { //先找,找到之后再从前驱里面找,删结点,然后改指针 Node* headNode head[MAX_LEVEL - 1]; int level MAX_LEVEL-1; while (headNode ! nullptr) { if (headNode-right nullptr || headNode-right-score score) { path[level] headNode; headNode headNode-down; level--; } else if (headNode-right-score score headNode-right-username name) { path[level] headNode;//前驱结点,记录 headNode headNode-down;//准备去删下面的 level--; } else {//右边分数大于查找的分数,继续往右找 headNode headNode-right; } } if (headNode nullptr) { cout Cant Find the User endl; } else { Node* delNode;//要删除的结点 for (int i 0; i MAX_LEVEL; i) {//从最底层开始删 if (path[i] ! nullptr path[i]-right ! nullptr path[i]-right-score score path[i]-right-username name) { delNode path[i]-right;//前驱结点不是空的,前驱结点的右边也不是,当前结点的分数和名字都一样,确定是要删的结点 path[i]-right delNode-right;//前驱结点连接到要删结点的右边,把要删除的结点的链条断掉 delete delNode;//删掉 } path[i] nullptr;//把每一层的前驱删掉,下次再使 } } } void updateNode(int score,string name,int newScore) { //更新就是先查找,先删,改分数,再插入 Node* cur SearchUser(score, name); if (cur ! nullptr) { DeleteNode(score, name); insertNode(name,newScore); } else { cout Cant Find the User endl; } } void printLevel() { for (int i MAX_LEVEL - 1; i 0; i--) { cout 第 i 层; Node* cur head[i]-right; while (cur ! nullptr) { cout cur-username ( cur-score ) ---; cur cur-right; } cout nullptr; cout endl; } } void printTop(int num) { //打印前num名用户 Node*HeadNodehead[0]-right; cout 榜 num 为:endl; for (int i 0; i num; i) { if (HeadNode ! nullptr) { cout HeadNode-username ( HeadNode-score ) endl; HeadNode HeadNode-right; } else { cout 暂无用户 endl; } } } }; int main() { SkipList sl(4);//最大4层,跳表 sl.insertNode(张三, 2314); sl.insertNode(李四, 3215); sl.insertNode(王五, 234612); sl.insertNode(赵六, 1246123); sl.insertNode(刘七, 65431); sl.insertNode(王八, 2152); sl.insertNode(谭九, 1235); sl.insertNode(白小白, 20452); sl.printLevel(); cout endl; sl.printTop(10); return 0; }在工程项目中,一定是多线程对于数据结构进行操作,上面的结构适用于单线程使用,多线程使用必然崩溃,同时有多个线程操作插入查找删除,尤其是更新,还没删除就插入了,还没查找就删除了,很容易混乱全部操作都在共享内存中,可以在跳表结构中加一个互斥锁,mutex,每段增删改查都加上锁,这样的改造成本明显降低但如果想要使用无锁跳表,原子级别操作,我建议还是使用redis中的zset合适,现成的如果有大佬有改进意见欢迎评论,谢谢