企业官网建设流程全解析

所谓1-2-3跳跃表是指跳跃表每一个链接层中两个相邻链接指针，之间的下一层节点数只能是1，2或3.它是一种特殊的跳跃表，其操作的时间复杂度可以达到

实现C++代码如下，分为两个版本，第一版本中每个节点的所有链接指针用vector容器组织,第二个版本中每个节点的链接指针用list容器组织

第一个版本：

#include <iostream> #include <vector> #include <deque> #include <set> #include <random> #include <ctime> using namespace std; template <typename T> struct HeadTailNode; template <typename T> struct NodeInfo { int gap_capacity; HeadTailNode<T>* ptr_to_same_level; NodeInfo(const NodeInfo<T>& copy) :gap_capacity(copy.gap_capacity), ptr_to_same_level(copy.ptr_to_same_level) {} NodeInfo() :gap_capacity(0), ptr_to_same_level(nullptr) {} }; template <typename T> struct HeadTailNode { vector<NodeInfo<T>> post_ptr; virtual ~HeadTailNode() { } HeadTailNode() :post_ptr() {} HeadTailNode(const HeadTailNode<T>& copy) :post_ptr(copy.post_ptr) {} }; template <typename T> struct _123SkipListNode : public HeadTailNode<T> { T data; _123SkipListNode(const T& data) :data(data), HeadTailNode<T>() {} ~_123SkipListNode() {} _123SkipListNode(const _123SkipListNode& copy) :data(copy.data), HeadTailNode<T>(copy) {} }; template <typename T> _123SkipListNode<T>* typeCast(HeadTailNode<T>* convert) { return dynamic_cast<_123SkipListNode<T>*>(convert); } template <typename T> class _123SkipList { public: _123SkipList(); _123SkipList<T>* copy(); ~_123SkipList(); bool insert(const T& key); bool remove(const T& key); private: HeadTailNode<T>* head; HeadTailNode<T>* tail; }; template <typename T> _123SkipList<T>* _123SkipList<T>::copy() { struct Node_pair { HeadTailNode<T>* copy; HeadTailNode<T>* _new; Node_pair(HeadTailNode<T>* c, HeadTailNode<T>* _n) :copy(c), _new(_n) {} bool operator<(const Node_pair& t) const { return copy < t.copy; } }; _123SkipList<T>* new_123_skip_list = new _123SkipList(); new_123_skip_list->~_123SkipList(); new_123_skip_list->head = new HeadTailNode<T>(*head); set<Node_pair> has_visited; HeadTailNode<T>* cur = new_123_skip_list->head; for (HeadTailNode<T>* run = head; run != tail; run = run->post_ptr[0].ptr_to_same_level) { for (size_t i = 0; i < run->post_ptr.size(); ++i) { typename set<Node_pair>::iterator it = has_visited.find(Node_pair(run->post_ptr[i].ptr_to_same_level, nullptr)); if (it != has_visited.end()) { cur->post_ptr[i].ptr_to_same_level = it->_new; } else { if (run->post_ptr[i].ptr_to_same_level == tail) { cur->post_ptr[i].ptr_to_same_level = new HeadTailNode<T>(*tail); } else { cur->post_ptr[i].ptr_to_same_level = new _123SkipListNode<T>(*typeCast(run->post_ptr[i].ptr_to_same_level)); } has_visited.insert(Node_pair(run->post_ptr[i].ptr_to_same_level, cur->post_ptr[i].ptr_to_same_level)); } } cur = cur->post_ptr[0].ptr_to_same_level; } new_123_skip_list->tail = new_123_skip_list->head->post_ptr.back().ptr_to_same_level; return new_123_skip_list; } template <typename T> _123SkipList<T>::~_123SkipList() { while (head->post_ptr[0].ptr_to_same_level != tail) { HeadTailNode<T>* cur = head->post_ptr[0].ptr_to_same_level; head->post_ptr[0].ptr_to_same_level = cur->post_ptr[0].ptr_to_same_level; delete cur; } delete head; delete tail; } template <typename T> _123SkipList<T>::_123SkipList() :head(new HeadTailNode<T>()), tail(new HeadTailNode<T>()) { head->post_ptr.push_back(NodeInfo<T>()); head->post_ptr[0].ptr_to_same_level = tail; } template <typename T> void borrowFromLeft(vector<pair<HeadTailNode<T>*, HeadTailNode<T>*>>& borrowing_path, HeadTailNode<T>* run, int borrow_point, size_t level) { for (int j = borrowing_path.size() - 1; j >= borrow_point; --j) { borrowing_path[j].second->post_ptr.push_back(borrowing_path[j].first->post_ptr.back()); borrowing_path[j].first->post_ptr.pop_back(); borrowing_path[j].second->post_ptr.back().gap_capacity += 1; if (j == 0) { run->post_ptr[level - 1].ptr_to_same_level = borrowing_path[j].second; run->post_ptr[level - 1].gap_capacity -= 1; } else { borrowing_path[j - 1].first->post_ptr[level - 1].ptr_to_same_level = borrowing_path[j].second; borrowing_path[j - 1].first->post_ptr[level - 1].gap_capacity -= 1; } } } template <typename T> void borrowFromRight(HeadTailNode<T>* cur, HeadTailNode<T>* first_level, size_t level) { HeadTailNode<T>* pre = cur; HeadTailNode<T>* post = cur->post_ptr[level - 1].ptr_to_same_level; do { HeadTailNode<T>* sub = post->post_ptr[level - 2].ptr_to_same_level; sub->post_ptr.push_back(post->post_ptr.back()); post->post_ptr.pop_back(); pre->post_ptr[level - 1].ptr_to_same_level = sub; sub->post_ptr.back().gap_capacity -= 1; pre->post_ptr[level - 1].gap_capacity += 1; pre = sub; post = sub->post_ptr[level - 1].ptr_to_same_level; } while (post != first_level); } template <typename T> HeadTailNode<T>* Find(HeadTailNode<T>* run, size_t level) { while (run->post_ptr[level - 2].ptr_to_same_level->post_ptr.size() != level) { run = run->post_ptr[level - 2].ptr_to_same_level; } return run; } template <typename T> bool _123SkipList<T>::remove(const T& key) { if (head->post_ptr.size() == 1) { return false; } size_t level = head->post_ptr.size(); HeadTailNode<T>* run = head; vector<HeadTailNode<T>*> list(head->post_ptr.size(), nullptr); for (; level >= 1; --level) { while (run->post_ptr[level - 1].ptr_to_same_level != tail && typeCast(run->post_ptr[level - 1].ptr_to_same_level)->data < key) { run = run->post_ptr[level - 1].ptr_to_same_level; } list[level - 1] = run; } HeadTailNode<T>* cur = run->post_ptr[0].ptr_to_same_level; if (cur == tail || typeCast(cur)->data != key) { return false; } if (cur->post_ptr.size() >= 2) { _123SkipListNode<T>* _deleted = typeCast(cur->post_ptr[0].ptr_to_same_level); typeCast(cur)->data = _deleted->data; cur->post_ptr[0].ptr_to_same_level = _deleted->post_ptr[0].ptr_to_same_level; delete _deleted; --(cur->post_ptr[1].gap_capacity); } else { run->post_ptr[0].ptr_to_same_level = cur->post_ptr[0].ptr_to_same_level; delete typeCast(cur); --(list[1]->post_ptr[1].gap_capacity); cur = list[1]; } size_t _size = head->post_ptr.size(); for (level = 2; level <= _size; ++level) { if (cur->post_ptr[level - 1].gap_capacity != 0) { break; } if (cur->post_ptr.size() > level) { HeadTailNode<T>* first_level = cur->post_ptr[level - 1].ptr_to_same_level; while (first_level != cur->post_ptr[level].ptr_to_same_level) { if (first_level->post_ptr[level - 1].gap_capacity >= 2) { break; } first_level = first_level->post_ptr[level - 1].ptr_to_same_level; } if (first_level == cur->post_ptr[level].ptr_to_same_level) { first_level = cur->post_ptr[level - 1].ptr_to_same_level; cur->post_ptr[level - 1].ptr_to_same_level = first_level->post_ptr[level - 1].ptr_to_same_level; first_level->post_ptr.pop_back(); cur->post_ptr[level - 1].gap_capacity += 2; cur->post_ptr[level].gap_capacity -= 1; if (cur->post_ptr[level].gap_capacity != 0) { break; } } else { borrowFromRight(cur, first_level->post_ptr[level - 1].ptr_to_same_level, level); break; } } else { if (level == _size) { head->post_ptr.pop_back(); break; } else { HeadTailNode<T>* post = cur->post_ptr[level - 1].ptr_to_same_level; run = list[level]; vector<pair<HeadTailNode<T>*, HeadTailNode<T>*>> borrowing_path; //(借补过程中高度降一的节点，高度增一节点) if (post == tail || post->post_ptr.size() > level) { while (run != cur) { run = Find(run, level); borrowing_path.push_back({ run->post_ptr[level - 2].ptr_to_same_level , run }); run = run->post_ptr[level - 2].ptr_to_same_level; } run = list[level]; int i = borrowing_path.size() - 1; for (; i >= 0; --i) { if (i == 0) { if (run->post_ptr[level - 1].gap_capacity >= 2) { break; } } else { if (borrowing_path[i - 1].first->post_ptr[level - 1].gap_capacity >= 2) { break; } } } if (i < 0) { cur->post_ptr.pop_back(); if (borrowing_path.size() == 1) { run->post_ptr[level - 1].ptr_to_same_level = post; run->post_ptr[level - 1].gap_capacity += 1; } else { borrowing_path[borrowing_path.size() - 2].first->post_ptr[level - 1].ptr_to_same_level = post; borrowing_path[borrowing_path.size() - 2].first->post_ptr[level - 1].gap_capacity += 1; } run->post_ptr[level].gap_capacity -= 1; if (run->post_ptr[level].gap_capacity != 0) { break; } cur = run; } else { borrowFromLeft(borrowing_path, run, i, level); break; } } else { { int borrow_point; if (run->post_ptr[level - 1].ptr_to_same_level != cur) { HeadTailNode<T>* _first = run->post_ptr[level - 1].ptr_to_same_level; if (_first->post_ptr[level - 1].gap_capacity >= 2) { _first = Find(_first, level); borrowing_path.push_back({ run->post_ptr[level - 1].ptr_to_same_level, nullptr }); borrowing_path.push_back({ cur , _first }); borrow_point = 1; } else if (run->post_ptr[level - 1].gap_capacity >= 2) { HeadTailNode<T>* temp = Find(run, level); borrowing_path.push_back({ _first, temp }); temp = Find(_first, level); borrowing_path.push_back({ cur , temp }); borrow_point = 0; } } else { if (run->post_ptr[level - 1].gap_capacity >= 2) { HeadTailNode<T>* temp = Find(run, level); borrowing_path.push_back({ cur, temp }); borrow_point = 0; } } if (borrowing_path.empty() == false) { borrowFromLeft(borrowing_path, run, borrow_point, level); break; } } { HeadTailNode<T>* borrow_point = nullptr; if (post->post_ptr[level - 1].ptr_to_same_level != run->post_ptr[level].ptr_to_same_level) { if (post->post_ptr[level - 1].gap_capacity >= 2) { borrow_point = post->post_ptr[level - 1].ptr_to_same_level; } else { HeadTailNode<T>* temp = post->post_ptr[level - 1].ptr_to_same_level; if (temp->post_ptr[level - 1].gap_capacity >= 2) { borrow_point = temp->post_ptr[level - 1].ptr_to_same_level; } } } else { if (post->post_ptr[level - 1].gap_capacity >= 2) { borrow_point = run->post_ptr[level].ptr_to_same_level; } } if (borrow_point != nullptr) { borrowFromRight(cur, borrow_point, level); break; } cur->post_ptr.back().ptr_to_same_level = post->post_ptr.back().ptr_to_same_level; post->post_ptr.pop_back(); cur->post_ptr.back().gap_capacity += 2; run->post_ptr[level].gap_capacity -= 1; if (run->post_ptr[level].gap_capacity != 0) { break; } cur = run; } } } } } return true; } template <typename T> bool _123SkipList<T>::insert(const T& key) { if (head->post_ptr.size() == 1) { head->post_ptr.push_back(NodeInfo<T>()); head->post_ptr[1].ptr_to_same_level = tail; head->post_ptr[1].gap_capacity = 1; HeadTailNode<T>* _new = new _123SkipListNode<T>(key); _new->post_ptr.push_back(NodeInfo<T>()); _new->post_ptr[0].ptr_to_same_level = tail; head->post_ptr[0].ptr_to_same_level = _new; return true; } int level = head->post_ptr.size(); int original_level = head->post_ptr.size(); HeadTailNode<T>* run = head; HeadTailNode<T>* pre_level = nullptr; for (; level >= 1; --level) { while (run->post_ptr[level - 1].ptr_to_same_level != tail && typeCast(run->post_ptr[level - 1].ptr_to_same_level)->data < key) { run = run->post_ptr[level - 1].ptr_to_same_level; } if (level != 1) { if (run->post_ptr[level - 1].gap_capacity == 3) { if (level == original_level) { pre_level = head; run->post_ptr.push_back(NodeInfo<T>()); run->post_ptr.back().ptr_to_same_level = tail; } HeadTailNode<T>* mid = run->post_ptr[level - 2].ptr_to_same_level->post_ptr[level - 2].ptr_to_same_level; mid->post_ptr.push_back(NodeInfo<T>()); mid->post_ptr.back().ptr_to_same_level = run->post_ptr[level - 1].ptr_to_same_level; run->post_ptr[level - 1].ptr_to_same_level = mid; mid->post_ptr.back().gap_capacity = 1; run->post_ptr[level - 1].gap_capacity = 1; pre_level->post_ptr[level].gap_capacity += 1; if (key > typeCast(run->post_ptr[level - 1].ptr_to_same_level)->data) { run = run->post_ptr[level - 1].ptr_to_same_level; } } pre_level = run; } else { if (run->post_ptr[0].ptr_to_same_level == tail || typeCast(run->post_ptr[0].ptr_to_same_level)->data != key) { HeadTailNode<T>* _new = new _123SkipListNode<T>(key); _new->post_ptr.push_back(NodeInfo<T>()); _new->post_ptr[0].ptr_to_same_level = run->post_ptr[0].ptr_to_same_level; run->post_ptr[0].ptr_to_same_level = _new; pre_level->post_ptr[1].gap_capacity += 1; } else { return false; } } } return true; } int main() { const int N = 2000; _123SkipList<int> g; //vector<int> input{34, 12, 9, 23, 56, 11, 6, 67}; vector<int> input; for (int i = 1; i <= N; ++i) { input.push_back(i); } shuffle(input.begin(), input.end(), default_random_engine(time(nullptr))); for (const int& run : input) { cout << "插入" << run << endl; if (g.insert(run)) { cout << "插入成功" << endl; } else { cout << "插入失败" << endl; } } _123SkipList<int>* copy = g.copy(); for (const int& run : input) { cout << "删除" << run << endl; if (copy->remove(run)) { cout << "删除成功" << endl; } else { cout << "删除失败" << endl; } } delete copy; return 0; }

第二个版本:

#include <iostream> #include <vector> #include <deque> #include <set> #include <random> #include <ctime> #include <list> #include <algorithm> using namespace std; template <typename T> struct HeadTailNode; template <typename T> struct NodeInfo { int gap_capacity; HeadTailNode<T>* ptr_to_same_level; NodeInfo(const NodeInfo<T>& copy) :gap_capacity(copy.gap_capacity), ptr_to_same_level(copy.ptr_to_same_level) {} NodeInfo() :gap_capacity(0), ptr_to_same_level(nullptr) {} }; template <typename T> struct HeadTailNode { list<NodeInfo<T>> post_ptr; virtual ~HeadTailNode() {} HeadTailNode() :post_ptr() {} HeadTailNode(const HeadTailNode<T>& copy) :post_ptr(copy.post_ptr) {} }; template <typename T> struct _123SkipListNode : public HeadTailNode<T> { T data; _123SkipListNode(const T& data) :data(data), HeadTailNode<T>() {} ~_123SkipListNode() {} _123SkipListNode(const _123SkipListNode& copy) :data(copy.data), HeadTailNode<T>(copy) {} }; template <typename T> struct ListNode { typename list<NodeInfo<T>>::iterator cur_level_pos; HeadTailNode<T>* cur_level_ptr = nullptr; ListNode() = default; }; template <typename T> _123SkipListNode<T>* typeCast(HeadTailNode<T>* convert) { return dynamic_cast<_123SkipListNode<T>*>(convert); } template <typename T> class _123SkipList { public: _123SkipList(); _123SkipList<T>* copy(); ~_123SkipList(); bool insert(const T& key); bool remove(const T& key); private: HeadTailNode<T>* head; HeadTailNode<T>* tail; }; template <typename T> _123SkipList<T>* _123SkipList<T>::copy() { struct Node_pair { HeadTailNode<T>* copy; HeadTailNode<T>* _new; Node_pair(HeadTailNode<T>* c, HeadTailNode<T>* _n) :copy(c), _new(_n) {} bool operator<(const Node_pair& t) const { return copy < t.copy; } }; _123SkipList<T>* new_123_skip_list = new _123SkipList(); new_123_skip_list->~_123SkipList(); new_123_skip_list->head = new HeadTailNode<T>(*head); set<Node_pair> has_visited; HeadTailNode<T>* cur = new_123_skip_list->head; for (HeadTailNode<T>* run = head; run != tail; run = run->post_ptr.begin()->ptr_to_same_level) { for (typename list<NodeInfo<T>>::iterator cur_it = cur->post_ptr.begin(), it = run->post_ptr.begin(); it != run->post_ptr.end(); ++it, ++cur_it) { typename set<Node_pair>::iterator temp = has_visited.find(Node_pair(it->ptr_to_same_level, nullptr)); if (temp != has_visited.end()) { cur_it->ptr_to_same_level = temp->_new; } else { if (it->ptr_to_same_level == tail) { cur_it->ptr_to_same_level = new HeadTailNode<T>(*tail); } else { cur_it->ptr_to_same_level = new _123SkipListNode<T>(*typeCast(it->ptr_to_same_level)); } has_visited.insert(Node_pair(it->ptr_to_same_level, cur_it->ptr_to_same_level)); } } cur = cur->post_ptr.begin()->ptr_to_same_level; } new_123_skip_list->tail = new_123_skip_list->head->post_ptr.back().ptr_to_same_level; return new_123_skip_list; } template <typename T> _123SkipList<T>::~_123SkipList() { while (head->post_ptr.front().ptr_to_same_level != tail) { HeadTailNode<T>* cur = head->post_ptr.front().ptr_to_same_level; head->post_ptr.front().ptr_to_same_level = cur->post_ptr.front().ptr_to_same_level; delete cur; } delete head; delete tail; } template <typename T> _123SkipList<T>::_123SkipList() :head(new HeadTailNode<T>()), tail(new HeadTailNode<T>()) { head->post_ptr.push_back(NodeInfo<T>()); head->post_ptr.back().ptr_to_same_level = tail; } template <typename T> typename list<NodeInfo<T>>::iterator next(typename list<NodeInfo<T>>::iterator it) { return ++it; } template <typename T> typename list<NodeInfo<T>>::iterator _pre(typename list<NodeInfo<T>>::iterator it) { return --it; } template <typename T> void borrowFromLeft(vector<pair<HeadTailNode<T>*, HeadTailNode<T>*>>& borrowing_path, typename list<NodeInfo<T>>::iterator it, int borrow_point) { for (int j = borrowing_path.size() - 1; j >= borrow_point; --j) { borrowing_path[j].second->post_ptr.push_back(borrowing_path[j].first->post_ptr.back()); borrowing_path[j].first->post_ptr.pop_back(); borrowing_path[j].second->post_ptr.back().gap_capacity += 1; if (j == 0) { it->ptr_to_same_level = borrowing_path[j].second; it->gap_capacity -= 1; } else { borrowing_path[j - 1].first->post_ptr.back().ptr_to_same_level = borrowing_path[j].second; borrowing_path[j - 1].first->post_ptr.back().gap_capacity -= 1; } } } template <typename T> void borrowFromRight(typename list<NodeInfo<T>>::iterator it, HeadTailNode<T>* first_level) { HeadTailNode<T>* post = it->ptr_to_same_level; do { HeadTailNode<T>* sub = _pre<T>(_pre<T>(post->post_ptr.end()))->ptr_to_same_level; sub->post_ptr.push_back(post->post_ptr.back()); post->post_ptr.pop_back(); it->ptr_to_same_level = sub; sub->post_ptr.back().gap_capacity -= 1; it->gap_capacity += 1; it = _pre<T>(sub->post_ptr.end()); post = it->ptr_to_same_level; } while (post != first_level); } template <typename T> HeadTailNode<T>* Find(typename list<NodeInfo<T>>::iterator it, size_t level) { HeadTailNode<T>* run = nullptr; while (it->ptr_to_same_level->post_ptr.size() != level) { run = it->ptr_to_same_level; it = --run->post_ptr.end(); } return run; } template <typename T> bool _123SkipList<T>::remove(const T& key) { if (head->post_ptr.size() == 1) { return false; } size_t level = head->post_ptr.size(); HeadTailNode<T>* run = head; typename list<NodeInfo<T>>::iterator run_it = --head->post_ptr.end(); vector<ListNode<T>> list(head->post_ptr.size()); for (; level >= 1; --level) { while (run_it->ptr_to_same_level != tail && typeCast(run_it->ptr_to_same_level)->data < key) { run = run_it->ptr_to_same_level; run_it = --run->post_ptr.end(); } list[level - 1].cur_level_ptr = run; list[level - 1].cur_level_pos = run_it; if (level != 1) { --run_it; } } HeadTailNode<T>* cur = run->post_ptr.begin()->ptr_to_same_level; if (cur == tail || typeCast(cur)->data != key) { return false; } if (cur->post_ptr.size() >= 2) { _123SkipListNode<T>* _deleted = typeCast(cur->post_ptr.begin()->ptr_to_same_level); typeCast(cur)->data = _deleted->data; cur->post_ptr.begin()->ptr_to_same_level = _deleted->post_ptr.begin()->ptr_to_same_level; delete _deleted; --((++(cur->post_ptr.begin()))->gap_capacity); } else { run->post_ptr.begin()->ptr_to_same_level = cur->post_ptr.begin()->ptr_to_same_level; delete typeCast(cur); --(list[1].cur_level_pos->gap_capacity); cur = list[1].cur_level_ptr; } run_it = ++cur->post_ptr.begin(); run = cur; size_t _size = head->post_ptr.size(); for (level = 2; level <= _size; ++level) { if (run->post_ptr.end() == run_it) { run_it = list[level - 1].cur_level_pos; } if (run_it->gap_capacity != 0) { break; } if (cur->post_ptr.size() > level) { HeadTailNode<T>* first_level = run_it->ptr_to_same_level; ++run_it; while (first_level != run_it->ptr_to_same_level) { if ((--first_level->post_ptr.end())->gap_capacity >= 2) { break; } first_level = (--first_level->post_ptr.end())->ptr_to_same_level; } if (first_level == run_it->ptr_to_same_level) { --run_it; first_level = run_it->ptr_to_same_level; run_it->ptr_to_same_level = (--first_level->post_ptr.end())->ptr_to_same_level; first_level->post_ptr.pop_back(); run_it->gap_capacity += 2; next(run_it)->gap_capacity -= 1; if (next(run_it)->gap_capacity != 0) { break; } run = cur; } else { --run_it; borrowFromRight(run_it, first_level->post_ptr.back().ptr_to_same_level); break; } } else { if (level == _size) { head->post_ptr.pop_back(); break; } else { HeadTailNode<T>* post = run_it->ptr_to_same_level; run = list[level].cur_level_ptr; vector<pair<HeadTailNode<T>*, HeadTailNode<T>*>> borrowing_path; //(借补过程中高度降一的节点，高度增一节点) typename std::list<NodeInfo<T>>::iterator _it = list[level].cur_level_pos; if (post == tail || post->post_ptr.size() > level) { _it = _pre<T>(_pre<T>(_it)); while (run != cur) { run = Find<T>(_it, level); borrowing_path.push_back({ run->post_ptr.back().ptr_to_same_level , run }); run = run->post_ptr.back().ptr_to_same_level; _it = _pre<T>(_pre<T>(run->post_ptr.end())); } run = list[level].cur_level_ptr; _it = _pre<T>(list[level].cur_level_pos); int i = borrowing_path.size() - 1; for (; i >= 0; --i) { if (i == 0) { if (_it->gap_capacity >= 2) { break; } } else { if (borrowing_path[i - 1].first->post_ptr.back().gap_capacity >= 2) { break; } } } if (i < 0) { --run_it; cur->post_ptr.pop_back(); if (borrowing_path.size() == 1) { _it->ptr_to_same_level = post; _it->gap_capacity += 1; } else { borrowing_path[borrowing_path.size() - 2].first->post_ptr.back().ptr_to_same_level = post; borrowing_path[borrowing_path.size() - 2].first->post_ptr.back().gap_capacity += 1; } ++_it; _it->gap_capacity -= 1; if (_it->gap_capacity != 0) { break; } swap(cur, run); } else { borrowFromLeft(borrowing_path, _it, i); break; } } else { { int borrow_point; --_it; if (_it->ptr_to_same_level != cur) { HeadTailNode<T>* _first = _it->ptr_to_same_level; if (_first->post_ptr.back().gap_capacity >= 2) { _first = Find<T>(_pre<T>(_pre<T>(_first->post_ptr.end())), level); borrowing_path.push_back({ _it->ptr_to_same_level, nullptr }); borrowing_path.push_back({ cur , _first }); borrow_point = 1; } else if (_it->gap_capacity >= 2) { HeadTailNode<T>* temp = Find<T>(_pre<T>(_it), level); borrowing_path.push_back({ _first, temp }); temp = Find<T>(_pre<T>(_pre<T>(_first->post_ptr.end())), level); borrowing_path.push_back({ cur , temp }); borrow_point = 0; } } else { if (_it->gap_capacity >= 2) { HeadTailNode<T>* temp = Find<T>(_pre<T>(_it), level); borrowing_path.push_back({ cur, temp }); borrow_point = 0; } } if (borrowing_path.empty() == false) { borrowFromLeft(borrowing_path, _it, borrow_point); break; } } { ++_it; HeadTailNode<T>* borrow_point = nullptr; if (post->post_ptr.back().ptr_to_same_level != _it->ptr_to_same_level) { if (post->post_ptr.back().gap_capacity >= 2) { borrow_point = post->post_ptr.back().ptr_to_same_level; } else { HeadTailNode<T>* temp = post->post_ptr.back().ptr_to_same_level; if (temp->post_ptr.back().gap_capacity >= 2) { borrow_point = temp->post_ptr.back().ptr_to_same_level; } } } else { if (post->post_ptr.back().gap_capacity >= 2) { borrow_point = _it->ptr_to_same_level; } } if (borrow_point != nullptr) { borrowFromRight(run_it, borrow_point); break; } cur->post_ptr.back().ptr_to_same_level = post->post_ptr.back().ptr_to_same_level; post->post_ptr.pop_back(); cur->post_ptr.back().gap_capacity += 2; _it->gap_capacity -= 1; if (_it->gap_capacity != 0) { break; } swap(cur, run); } } } } ++run_it; } return true; } template <typename T> bool _123SkipList<T>::insert(const T& key) { if (head->post_ptr.size() == 1) { head->post_ptr.push_back(NodeInfo<T>()); head->post_ptr.back().ptr_to_same_level = tail; head->post_ptr.back().gap_capacity = 1; HeadTailNode<T>* _new = new _123SkipListNode<T>(key); _new->post_ptr.push_back(NodeInfo<T>()); _new->post_ptr.begin()->ptr_to_same_level = tail; head->post_ptr.begin()->ptr_to_same_level = _new; return true; } int level = head->post_ptr.size(); int original_level = head->post_ptr.size(); HeadTailNode<T>* run = head; typename list<NodeInfo<T>>::iterator run_it = --head->post_ptr.end(); typename list<NodeInfo<T>>::iterator pre_run_it; for (; level >= 1; --level) { while (run_it->ptr_to_same_level != tail && typeCast(run_it->ptr_to_same_level)->data < key) { run = run_it->ptr_to_same_level; run_it = --run->post_ptr.end(); } if (level != 1) { if (run_it->gap_capacity == 3) { if (level == original_level) { run->post_ptr.push_back(NodeInfo<T>()); run->post_ptr.back().ptr_to_same_level = tail; pre_run_it = --run->post_ptr.end(); } HeadTailNode<T>* mid = _pre<T>(run_it)->ptr_to_same_level; mid = mid->post_ptr.back().ptr_to_same_level; mid->post_ptr.push_back(NodeInfo<T>()); mid->post_ptr.back().ptr_to_same_level = run_it->ptr_to_same_level; run_it->ptr_to_same_level = mid; mid->post_ptr.back().gap_capacity = 1; run_it->gap_capacity = 1; pre_run_it->gap_capacity += 1; if (key > typeCast(mid)->data) { run = mid; run_it = --run->post_ptr.end(); } } pre_run_it = run_it; --run_it; } else { if (run->post_ptr.begin()->ptr_to_same_level == tail || typeCast(run->post_ptr.begin()->ptr_to_same_level)->data != key) { HeadTailNode<T>* _new = new _123SkipListNode<T>(key); _new->post_ptr.push_back(NodeInfo<T>()); _new->post_ptr.back().ptr_to_same_level = run->post_ptr.begin()->ptr_to_same_level; run->post_ptr.begin()->ptr_to_same_level = _new; pre_run_it->gap_capacity += 1; } else { return false; } } } return true; } int main() { const int N = 2000; _123SkipList<int> g; //vector<int> input{34, 12, 9, 23, 56, 11, 6, 67}; vector<int> input; for (int i = 1; i <= N; ++i) { input.push_back(i); } shuffle(input.begin(), input.end(), default_random_engine(time(nullptr))); for (const int& run : input) { cout << "插入" << run << endl; if (g.insert(run)) { cout << "插入成功" << endl; } else { cout << "插入失败" << endl; } } _123SkipList<int>* copy = g.copy(); for (const int& run : input) { cout << "删除" << run << endl; if (copy->remove(run)) { cout << "删除成功" << endl; } else { cout << "删除失败" << endl; } } delete copy; return 0; }