从零开始编写网络游戏--基础篇 源码

#ifndef __Tree_H__ #define __Tree_H__ #include <memory> #include <iterator> #include <cassert> namespace Blaze { template <class T, class Alloc = std::allocator<T>> class tree { public: typedef tree<T, Alloc> TreeT; typedef TreeT value_type; typedef TreeT* pointer; typedef const TreeT* const_pointer; typedef TreeT& reference; typedef const TreeT& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; // provide special handling for non-standard VC6 allocators #if _MSC_VER < 1300 typedef Alloc allocator_type; #else typedef typename Alloc::template rebind<TreeT>::other allocator_type; #endif class iterator; class const_iterator; class child_iterator; class const_child_iterator; tree() { init(); } tree(const T& t) : value(t) { init(); } tree(const TreeT& copy) : value(copy.value) { init(); copy_children(copy); } ~tree() { clear(); } const tree& operator=(const TreeT& rhs) { TreeT temp(rhs); swap(temp); return *this; } class iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void> { public: TreeT* _ptr; TreeT* _root; iterator(TreeT* ptr, TreeT* root) : _ptr(ptr), _root(root) {} friend class tree<T, Alloc>; friend class const_iterator; friend class child_iterator; friend class const_child_iterator; public: iterator() : _ptr(0), _root(0) {} TreeT& operator*() const {return *_ptr;} TreeT* operator->() const {return _ptr;} bool operator==(const iterator& rhs) const {return _ptr == rhs._ptr;} bool operator!=(const iterator& rhs) const {return _ptr != rhs._ptr;} iterator& operator++() {_ptr = _ptr->_next; return *this;} iterator& operator--() {_ptr = (_ptr ? _ptr->prev() : _root->_last_descendant); return *this;} iterator operator++(int i) { iterator temp = *this; ++*this; return temp; } iterator operator--(int i) { iterator temp = *this; --*this; return temp; } friend void skip(iterator& it) { it._ptr = it._ptr->next_sibling(); } }; class const_iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void> { protected: const TreeT* _ptr; const TreeT* _root; const_iterator(const TreeT* ptr, const TreeT* root) : _ptr(ptr), _root(root) {} friend class tree<T, Alloc>; friend class const_child_iterator; public: const_iterator() : _ptr(0), _root(0) {} const const_iterator& operator=(const const_iterator& it) {_ptr = it._ptr;_root = it._root; return *this;} const const_iterator& operator=(const iterator& it) {_ptr = it._ptr;_root = it._root; return *this;} const const_iterator& operator=(iterator& it) {_ptr = it._ptr;_root = it._root; return *this;} const TreeT& operator*() const {return *_ptr;} const TreeT* operator->() const {return _ptr;} bool operator==(const const_iterator& rhs) const {return _ptr == rhs._ptr;} bool operator!=(const const_iterator& rhs) const {return _ptr != rhs._ptr;} const_iterator& operator++() {_ptr = _ptr->_next; return *this;} const_iterator& operator--() {_ptr = (_ptr ? _ptr->prev() : _root->_last_descendant); return *this;} const_iterator operator++(int i) { const_iterator temp = *this; ++*this; return temp; } const_iterator operator--(int i) { const_iterator temp = *this; --*this; return temp; } }; class child_iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void> { public: TreeT* _ptr; TreeT* _root; child_iterator(TreeT* ptr, TreeT* root) : _ptr(ptr), _root(root) {} friend class tree<T, Alloc>; friend class const_child_iterator; public: child_iterator() : _ptr(0), _root(0) {} const child_iterator& operator=(const iterator& it){_ptr = it._ptr;_root = it._root;return *this;} operator iterator() const { return iterator(_ptr, _root); } TreeT& operator*() const {return *_ptr;} TreeT* operator->() const {return _ptr;} bool operator==(const child_iterator& rhs) const {return _ptr == rhs._ptr;} bool operator!=(const child_iterator& rhs) const {return _ptr != rhs._ptr;} child_iterator& operator++() {_ptr = _ptr->next_sibling(); return *this;} child_iterator& operator--() {_ptr = (_ptr ? _ptr->prev_sibling() : _root->last_child()); return *this;} child_iterator operator++(int i) { child_iterator temp = *this; ++*this; return temp; } child_iterator operator--(int i) { child_iterator temp = *this; --*this; return temp; } }; class const_child_iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void> { protected: const TreeT* _ptr; const TreeT* _root; const_child_iterator(const TreeT* ptr, const TreeT* root) : _ptr(ptr), _root(root) {} friend class tree<T, Alloc>; public: const_child_iterator() : _ptr(0), _root(0) {} const_child_iterator(const child_iterator& it) : _ptr(it._ptr), _root(it._root) {} const_child_iterator(const iterator& it) : _ptr(it._ptr), _root(it._root) {} const_child_iterator(const const_iterator& it) : _ptr(it._ptr), _root(it._root) {} operator const_iterator() const { return iterator(_ptr, _root); } const TreeT& operator*() const {return *_ptr;} const TreeT* operator->() const {return _ptr;} bool operator==(const const_child_iterator& rhs) const {return _ptr == rhs._ptr;} bool operator!=(const const_child_iterator& rhs) const {return _ptr != rhs._ptr;} const_child_iterator& operator++() {_ptr = _ptr->next_sibling(); return *this;} const_child_iterator& operator--() {_ptr = (_ptr ? _ptr->prev_sibling() : _root->last_child()); return *this;} const_child_iterator operator++(int i) { const_child_iterator temp = *this; ++*this; return temp; } const_child_iterator operator--(int i) { const_child_iterator temp = *this; --*this; return temp; } }; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef std::reverse_iterator<child_iterator> reverse_child_iterator; typedef std::reverse_iterator<const_child_iterator> const_reverse_child_iterator; const_iterator begin() const {return const_iterator(this, this);} const_iterator end() const {return const_iterator(0, this);} iterator begin() {return iterator(this, this);} iterator end() {return iterator(0, this);} const_reverse_iterator rbegin() const {return const_reverse_iterator(end());} const_reverse_iterator rend() const {return const_reverse_iterator(begin());} reverse_iterator rbegin() {return reverse_iterator(end());} reverse_iterator rend() {return reverse_iterator(begin());} const_child_iterator begin_child() const {return const_child_iterator(first_child(), this);} const_child_iterator end_child() const {return const_child_iterator(0, this);} child_iterator begin_child() {return child_iterator(first_child(), this);} child_iterator end_child() {return child_iterator(0, this);} const_reverse_child_iterator rbegin_child() const {return const_reverse_child_iterator(end_child());} const_reverse_child_iterator rend_child() const {return const_reverse_child_iterator(begin_child());} reverse_child_iterator rbegin_child() {return reverse_child_iterator(end_child());} reverse_child_iterator rend_child() {return reverse_child_iterator(begin_child());} void push_back(const TreeT& subtree) { TreeT* child = create_subtree(subtree); insert_subtree(*child, 0); } void push_front(const TreeT& subtree) { TreeT* child = create_subtree(subtree); TreeT* next = first_child(); insert_subtree(*child, next); } void pop_back() { TreeT* last = last_child(); assert(last); erase(iterator(last, this)); } void pop_front() { TreeT* first = first_child(); assert(first); erase