Welcome to Mihooke's blog
这里是我的个人学习小天地，记录了我的成长历程-
binary search tree AVL tree 和set map
二叉搜索树（binary search tree）是这样一棵树，对于每一个节点，其左孩子比它小，右孩子比它大，由于树高为logN，因此我们总可以在logN时间内找到最小值或最大值。
实现树的各种操作利用递归思想很简单，也十分适合递归思想，由于树高平均为logN，所以不用担心栈空间被用尽，递归算法尽管很简明，但是其效率肯定没有非递归实现效率高。
下面二叉搜索树的实现是利用了递归，需要强调一下插入删除操作，在此我们不考虑重复元素。针对删除，存在三种情况：
- 所删除的节点是叶子
这种情况直接删除就行了。
- 删除的节点有一个孩子
这种情况直接让此孩子节点上移就行了。
- 所删除的节点有两个孩子
这种情况稍微复杂点，需要在所删除节点的右子树种找到最小节点，使其上移到删除位置。
最后，需要知道二叉搜索树之所以效率高，是由树高来保证的，那树高怎么保证logN呢？就是尽量保证根元素是中值，这就需要生成树时，元素的输入是随机的，否则很有可能会形成一颗左子树或右子树很大的树，导致树高远大于logN。
template <typename T> class BinarySearchTree { public: BinarySearchTree() : _root(nullptr) {} BinarySearchTree(const BinarySearchTree &other) { _root = clone(other._root); } BinarySearchTree(BinarySearchTree &&other) { _root = clone(move(other._root)); } ~BinarySearchTree() { makeEmpty(_root); } bool isEmpty() const {return _root == nullptr;} bool contains(const T &value) const { return contains(value, _root); } bool findMin(T &value) const { if (TreeNode *tn = findMin(_root)) { value = tn->data; return true; } return false; } bool findMax(T &value) const { if (TreeNode *tn = findMax(_root)) { value = tn->data; return true; } return false; } void insert(const T &value) { insert(value, _root); } void remove(const T &value) { remove(value, _root); } BinarySearchTree &operator=(const BinarySearchTree &other) { if (this != &other) { _root = clone(other._root); } return *this; } BinarySearchTree &operator=(BinarySearchTree &&other) { _root = clone(move(other._root)); return *this; } private: void makeEmpty(TreeNode * &t) { if (t != nullptr) { makeEmpty(t->left); makeEmpty(t->right); delete t; t = nullptr; } } TreeNode *clone(TreeNode *other) const { if (other == nullptr) return nullptr; return TreeNode{other->data, clone(other->left), clone(other->right)}; } bool contains(const T &value, TreeNode *t) const { if (t == nullptr) return false; if (t->data > value) return contains(value, t->left); else if (t->data < value) return contains(value, t->right); return true; } TreeNode *findMin(TreeNode *t) const { if (t == nullptr) return nullptr; if (t->left == nullptr) return t; return findMin(t->left); } TreeNode *findMax(TreeNode *t) const { if (t == nullptr) return nullptr; if (t->right == nullptr) return t; return findMax(t->right); } void insert(const T &value, TreeNode * &t) { if (t == nullptr) t = new TreeNode(value, nullptr, nullptr); if (t->data > value) insert(value, t->left); else if (t->data < value) insert(value, t->right); } void insert(T &&value, TreeNode * &t) { if (t == nullptr) t = new TreeNode(move(value), nullptr, nullptr); if (t->data > value) insert(value, t->left); else if (t->data < value) insert(value, t->right); } void remove(const T &value, TreeNode * &t) { if (t == nullptr) return; if (t->data > value) remove(value, t->left); else if (t->data < value) remove(value, t->right); // 删除的节点有2个子节点 if (t->left != nullptr && t->right != nullptr) { t->data = findMin(t->right)->data; remove(t->data, t->right); } else // 删除的节点有1个子节点 { TreeNode *old = t; t = (t->left != nullptr) ? t->left : t->right; delete old; } } private: class TreeNode { public: T data; TreeNode *left; TreeNode *right; TreeNode(const T &value, TreeNode *l, TreeNode *r) : data(value), left(l), right(r) {} }; TreeNode *_root; };
-
heap和priority_queue
heap形象来说它是一个完全二叉树，即树是满树，因此其父子节点的对应关系是固定的，其特性是按从上往下从左往右的顺序遍历，某个节点i，其两个子节点就是2i和2i+1，因此，heap底层保存数据可利用array。
heap可分为大根堆（big-heap）和小根堆（small-heap），其根节点是最大的和最小的，这里以大根堆为例来实现代码
template <typename T> class Maxheap { public: Maxheap(size_t size) : _data(_size+1), _size(size) {} Maxheap(const vector<T> &v) : _data(v.size()+1), _size(v.size()) { copy(v.cbegin(), v.cend(), _data.begin()+1); buildHeap(); } void insert(const T &value) { if (_size == _data.size()) _data.resize(2 * _size); _data[++_size] = value; int hole = _size; while (_data[hole / 2] < _data[hole / 2]) { swap(_data[hole], _data[hole / 2]); hole /= 2; } } void insert(T &&value) { if (_size == _data.size()) _data.resize(2 * _size); _data[++_size] = move(value); int hole = _size; while (_data[hole / 2] < _data[hole / 2]) { swap(_data[hole], _data[hole / 2]); hole /= 2; } } void pop(T &to) { if (_size == 0) return; to = move(_data[1]); _data[1] = move(_data[_size--]); percolateDown(1); } private: void buildHeap() { for (int hole = _size / 2; hole > 0; --hole) percolateDown(hole); } void percolateDown(int hole) { int child; for (; hole * 2 <= _size; hole = child) { child = 2 * hole; if (child != _size && _data[child+1] > _data[child]) ++child; if (_data[child] < _data[hole]) break; swap(_data[child], _data[hole]); } } vector<T> _data; size_t _size; };C++标准库里priority_queue就是利用heap来实现的，带权值的queue，即queue中元素是按照权值来放置的。堆排序也是利用了堆的特性。
-
hashtable和unordered_set unordered_map hash_set hash_map
2019-03-30hashtable叫散列表，又叫哈希表，这种数据结构主要提供了常数平均时间的查找插入删除操作。
这里和二叉搜索树（binary search tree）做个对比，二叉搜索树是对数平均时间，但有一个假设：数据的输入必须有足够的随机性，否则的话，二叉树就不平衡了，会导致平方时间。
hashtable的关键有两个因素：表大小是一个素数；一个好的散列函数（hash function）。素数可以保证插入元素时的覆盖率（主要针对平方探测法）；散列函数提供了无限输入到有限单元的映射，从这个角度上看，hashtable可看作是一个字典（map），因为hashtable大小固定，因此在插入元素时会发生碰撞（即两个不同元素落在同一位置），常用的解决办法是：线性探测法、平方探测法、分离链表法。
在介绍这几个办法之前，先认识一个术语：填装因子（loading factor），它是指表中元素个数与表大小的比，即散列表中装的元素比例。
-
线性探测：当发生碰撞时，往后挨个遍历表，直到找到空闲位置。
-
平方探测：当发生碰撞时，按照1，3，5……2n-1 规则，直到找到空闲位置。
这两种方法要想取得好的效果，都要求填装因子<0.5，即表中元素数量少于一半，否则大量时间会花在遍历元素探测上。
- 分离链表：它是一个链表数组，当发生碰撞时，附加到链表后面，这种做法填装因子为1，主要是链表分配元素消耗时间。
线性探测/平方探测和分离链表各有优劣，可根据实际来选择使用，当内存紧张时，可选用分离链表；当考虑运行速度，可选用平方探测。在使用平方探测时，若填装因子>0.5时，其效率会降低，这时候需要进行再散列，具体做法是：分配更大的空间，将元素重新散列进去。
C++11之前不同平台可能有hash_set/hash_map，其底层是hashtable，C++11标准模板库里引入了unordered_set，unordered_map，他们便是用hashtable来实现的，替代了hash_set/hash_map，当然，hash_set/hash_map目前在很多平台也还是提供了。
以下是平方探测法和分离链表法的实现。
bool isPrime(size_t value) { for (int i = 2; i <= sqrt(value); ++i) { if (value % i == 0) return false; } return true; } size_t nextPrime(size_t value) { while (!isPrime(++value)) ; return value; } template<> class hash<string> { public: size_t operator() (const string &value) const { size_t v = 0; for (auto ch : value) v = 37 * v + ch; return v; } }; // 平方探测法 template<typename T> class Hashtable { public: enum HashType {Empty, Active, Deleted}; class HashEntry { public: T data; HashType info; HashEntry(const T &value=T{}, HashType t=Empty) : data(value), info(t) {} }; Hashtable(size_t size) : _array(nextPrime(size)) { makeEmpty(); } bool isActive(int pos) const { return _array[pos].info == Active; } bool contains(const T &value) const { return isActive(findPos(value)); } int findPos(const T &value) const { int currentPos = hashFunction(value); int offset = 1; while (_array[currentPos].info != Empty && _array[currentPos].data != value) { currentPos += offset; offset += 2; if (currentPos >= _array.size()) currentPos -= _array.size(); } return currentPos; } bool insert(const T &value) { int currentPos = findPos(value); if (isActive(currentPos)) return false; _array[currentPos] = {value, Active}; if (++_size > _array.size()) rehash(); return true; } bool insert(T &&value) { int currentPos = findPos(value); if (isActive(currentPos)) return false; _array[currentPos] = {move(value), Active}; if (++_size > _array.size() / 2) rehash(); return true; } bool remove(const T &value) { int currentPos = findPos(value); if (!isActive(currentPos)) return false; _array[currentPos].info = Deleted; --_size; return true; } void rehash() { const vector<HashEntry> old = _array; _array.resize(nextPrime(old.size() * 2)); makeEmpty(); for(const HashEntry &entry : old) { if (entry.info == Active) insert(move(entry.data)); } } private: void makeEmpty() { for (auto &entry : _array) entry.info = Empty; _size = 0; } size_t hashFunction(const T &value) { static hash<T> hf; return hf(value) % _array.size(); } vector<HashEntry> _array; size_t _size; };// 分离链表法 class Hashtable { public: Hashtable(size_t size) : _array(nextPrime(size)) { makeEmpty(); } bool contains(const T &value) const { int pos = hashFunction(value); list<T> &curList = _array[pos]; return find(curList.cbegin(), curList.cend(), value) == curList.cend(); } bool insert(const T &value) { if (contains(value)) return false; int pos = hashFunction(value); _array[pos].push_back(value); if (++_size > _array.size()) rehash(); return true; } bool insert(T &&value) { if (contains(value)) return false; int pos = hashFunction(value); _array[pos].push_back(move(value)); if (++_size > _array.size()) rehash(); return true; } bool remove(const T &value) { if (contains(value)) return false; int pos = hashFunction(value); list<T> &curList = _array[pos]; auto itr = find(curList.cbegin(), curList.cend(), value); curList.erase(itr); --_size; return true; } void rehash() { const vector<list<T>> old = _array; _array.resize(nextPrime(old.size() * 2)); makeEmpty(); for (auto &l : old) { for (auto &v : l) insert(move(v)); } } private: void makeEmpty() { for (list<T> &l : _array) l.clear(); } size_t hashFunction(const T &value) { static hash<T> hf; return hf(value) % _array.size(); } vector<list<T>> _array; size_t _size; };
-
-
list和slist
我们已经了解了vector的弊端：虽然访问元素速度很快，但插入删除操作是O(n)时间复杂度，因为插入删除还需要移动后续元素。 如果你选用了vector作为数据的容器，但插入删除操作很频繁，那建议使用list，可以说vector和list是优缺点互补的；list是一个一个的node通过指针相连的，要访问某个位置的元素，必须从头或从尾挨个遍历，时间复杂度是O(n)，但插入删除就很快了，背后是指针之间的交换。 标准库提供了list容器，它是双向链表，也就是说每个node都保存了指向它的前驱和后继指针；slist是单链表，只有后继指针，因为找不到当前node的上一个node，slist不支持插入删除操作，只支持在链表头进行操作。
下面简单实现了list，其中iterator是简化版，我们只需知道每个容器内部都实现了对应的迭代器，方便容器的遍历，list的iterator其实保存了当前node，提供++操作。
list的结构模型是有一个head node和tail node，它们不保存数据，只是起到区分list头和尾的作用，数据的保存是在head和tail之间。这两个node的好处在于简化了代码的实现，比如对于list中第一个元素和最后一个元素的插入和删除操作，否则的话必须特殊对待。
template <typename T> class List { public: struct Node { T data; Node *pre; Node *next; Node(const T &value=T{}, Node *p = nullptr, Node *n = nullptr) : data(value), pre(p), next(n) {} }; class const_iterator { protected: Node *current; }; class iterator : public const_iterator {}; public: List() : _head(new Node), _tail(new Node), _size(0) {} List(const List &other) : _head(new Node), _tail(new Node), _size(0) { for (auto & v : other) push_back(v); } List(List &&other) : _head(other._head), _tail(other._tail), _size(other._size) { other._head = nullptr; other._tail = nullptr; other._size = 0; } List& operator=(const List &other) { if (this != &other) { for (auto &v : other) push_back(v); } return *this; } List& operator=(List &&other) { std::swap(_head, other._head); std::swap(_tail, other._tail); std::swap(_size, other._size); return *this; } iterator begin() { return _head->next; } // Node隐式转换为iterator const_iterator begin() const { return _head->next; } iterator end() { return _tail; } const_iterator end() const { return _tail; } void push_front(const T &value) { insert(begin(), value); } void push_front(T &&value) { insert(begin(), std::move(value)); } void push_back(const T &value) { insert(end(), value); } void push_back(T &&value) { insert(end(), std::move(value)); } void pop_front() { erase(begin()); } void pop_back() { erase(--end()); } iterator insert(iterator pos, const T &value) { Node *currentNode = pos.current; Node *newNode = new Node(value, currentNode->pre, currentNode); // 先操作插入结点的前驱和后继 newNode->pre = currentNode->pre; newNode->next = currentNode; // 再操作前驱的后继，后继的前驱 currentNode->pre->next = newNode; currentNode->pre = newNode; ++_size; return newNode; } iterator insert(iterator pos, T &&value) { Node *currentNode = pos.current; Node *newNode = new Node(std::move(value), currentNode->pre, currentNode); newNode->pre = currentNode->pre; newNode->next = currentNode; currentNode->pre->next = newNode; currentNode->pre = newNode; ++_size; return newNode; } iterator erase(iterator pos) { Node *delNode = pos.current; iterator ret = delNode->next; delNode->pre->next = delNode->next; delNode->next->pre = delNode->pre; delete delNode; return ret; } iterator erase(iterator from, iterator to) { iterator itr = from; while (itr != to) itr = erase(itr); return itr; } private: Node *_head; Node *_tail; size_t _size; };
-
deque和queue stack
deque是双向开头的连续线性容器，即容器的头和尾都可以进行插入删除。当然vector和list也是这样的容器，不过
vector是
头部操作很耗费时间
list是
不是连续内存，元素访问耗费时间
deque结合了vector和list的优点：是连续内存，头部操作线性时间
deque的实现也借鉴了vector的预分配机制，内部使用一个二维数组来存储数据，如图所示结构
map数组存储了一系列指针，每个指针指向一块连续内存，使用的内存从start开始标记，直到finish结束，也就意味着deque是从中间开始使用，这样就很方便在头尾进行操作了，如果头或尾内存用尽了，便会像vector那样重新分配所有内存。
以下是deque的数据结构，deque的核心部分是在start或finish所指的空间用完之后，如何跳到下一部分，为此，我们在iterator中保存了3个指针：first end current，来判断当前部分内存是否用完了，还保存了指向总内存的地址，以此来跳到下一部分。
template <typename T, size_t BufSize=512> class Deque { public: struct iterator { T **map = nullptr; T *first = nullptr; T *end = nullptr; T *current = nullptr; void setNode(T **node) { map = node; first = *node; end = first + BufSize; current = first; } }; Deque(size_t n, const T &value) : _start{}, _finish{}, _size(0) { size_t usedSize = n / BufSize; _size = 2 * usedSize; for (int i = 0; i < _size; ++i) _map[i] = new T[BufSize]; T **nStart = _map + usedSize / 2; T **nFinish = nStart + usedSize - 1; int j = 0; for (iterator cur = nStart; cur != nFinish; ++cur) { for (int i = 0; i < BufSize; ++i) if (j < n) cur[i] = value; j += BufSize; } _start.setNode(nStart); _finish.setNode(nFinish); } private: T **_map = nullptr; iterator _start; iterator _finish; size_t _size; };vector，list，deque是三个基本的数据结构，有了它们，我们可以方便地实现stack和queue，利用某个容器来存储数据，只暴露相应接口。
-
array和vector
array 就是原始数组，之所以使用vector封装array操作，是因为原始数组是静态的，一旦分配了，不能修改大小，这就导致了在实际使用数组时，如果不确定大小，不能很好地分配内存，这便是设计vector的初衷，以下Vector类实现了setter类函数，通常getter类函数只是返回对应成员值，故不再实现，另外，以下实现也未考虑一些异常情况，只是描述了某个功能的实现。
template <typename T> class Vector { public: typedef T* iterator; typedef const T* const_iterator; static const int INIT_CAPACITY = 128; Vector() : _size(0), _capacity(INIT_CAPACITY), _data(new T[_capacity]) {} Vector() : _size(0), _capacity(INIT_CAPACITY), _data(new T[_capacity]) {} Vector(size_t size) : _size(size), _capacity(size+INIT_CAPACITY), _data(new T[_capacity]) {} Vector(size_t size, const T &value) : _size(size), _capacity(size+INIT_CAPACITY), _data(new T[_capacity]) { for (int i=0; i<_size; ++i) { _data[i] = value; } } Vector(const Vector &other) { _data = new T[other._capacity]; for (int i=0; i<other._size; ++i) { _data[i] = other._data[i]; } _size = other._size; _capacity = other._capacity; } Vector(Vector &&other) { _data = other._data; _size = _size; _capacity = other._capacity; } Vector& operator=(const Vector &other) { if (this == &other) return *this; T *data = new T[other._capacity]; for (int i=0; i<other._size; ++i) { data[i] = other._data[i]; } std::swap(data, _data); _size = other._size; _capacity = other._capacity; delete []data; return *this; } ~Vector() {delete []_data;} void resize(size_t size) { if (size > _capacity) { Vector copy = *this; for (int i=0; i<_size; ++i) { _data[i] = copy._data[i]; } } _size = size; _capacity = size + _capacity; } void reserve(size_t capacity) { if (capacity < _size) return; T *data = new T[capacity]; for (int i=0; i<_size; ++i) { data[i] = _data[i]; } std::swap(data, _data); _capacity = capacity; delete []data; } void push_back(const T &value) { if (_size == _capacity) { reserve(2*_capacity); } _data[_size++] = value; } void push_back(T &&value) { if (_size == _capacity) { reserve(2*_capacity); } _data[_size++] = std::move(value); } template <typename... Args> void emplace_back(Args&&... value) { if (_size == _capacity) { reserve(2*_capacity); } _data[_size++] = std::move(T(std::forward(value...))); } void pop_back() {_size--;} size_t size() const {return _size;} size_t capacity() const {return _capacity;} const T &operator[](size_t index) const {return _data[index];} T &operator[](size_t index) {return _data[index];} iterator erase(iterator pos) { iterator end = _data + _size; if (pos+1 != end) { std::copy(pos+1, end, pos); } _size--; return pos; } iterator erase(iterator begin, iterator end) { iterator tail = _data + _size; std::copy(end, tail, begin); _size = _size - (end - begin); return begin; } private: size_t _size; size_t _capacity; T *_data = nullptr; };
Recent Posts
Categories
Tags