从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)（上）：https://developer.aliyun.com/article/1521891
2. 反向迭代器
（此篇文章加上代码两万多字，可以在这分两部分看了）
前面讲 list 我们没实现反向迭代器，计划放在这里讲，反向迭代器怎么实现呢，
反向迭代器和正向迭代器加加的方向不一样（唯一区别）。
（即正向迭代器 ++ 是向后走，反向迭代器 ++ 是向前走）
正常思维是把正向迭代器复制粘贴一份，把 ++ 改成 -- 啥的，
前面讲了容器适配器，大佬就实现了一个迭代器适配器：
库里的反向迭代器其实就是对正向迭代器的一种封装 —— 适配器模式（配接器模式）
用传过来的正向迭代器实现反向迭代器，直接建一个reverse_iterator.h。
2.1 反向迭代器的普通实现
如果知道反向迭代器其实就是对正向迭代器的一种封装 ，因为以前认为rbegin（）指向的是最后一个数据，rend（）指向的是第一个数据的前一个（哨兵位头结点）（库里面不是的）
所以现在普通思路实现出来是这样的：（虽然库里面不是的，但也可以实现出来）
reverse_iterator.h（不对称版）
#pragma once namespace rtx { template<class Iterator, class Ref, class Ptr>// 为了适配const迭代器，再加两个参数 struct __reverse_iterator //普通迭代器传的就是 T& 和 T* const 迭代器传的就是 const T& 和 const T* { Iterator _cur; typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator; __reverse_iterator(Iterator it) :_cur(it) {} RIterator operator++() { --_cur; // 正向迭代器 ++ 就是反向迭代器 -- return *this; } RIterator operator--() { ++_cur; return *this; } Ref operator*() { return *_cur; } Ptr operator->() { //return _cur.operator->(); //return &(*_cur); // 如果这样写，对称的时候就要改了 return &(operator*()); } bool operator!=(const RIterator& it) { return _cur != it._cur; } }; }
如果 vector 需要反向迭代器，那就把 vector 的正向迭代器传给 Iterator，
它就可以通过正向迭代器转换出 vector 的反向迭代器。
也就是说，我们实现的反向迭代器并包装的这个类，不是针对某个容器而是针对所有容器的。
任何一个容器只要你实现了正向迭代器，就可以通过其适配出反向迭代器。
先拿list.h 试一下，包一下头文件"reverse_iterator.h"，在以前实现的 list类 加上了下面的代码
typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; // 传正向迭代器封装出反向迭代器 typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; reverse_iterator rbegin()//按照以前的理解，rbegin指向最后一个数据 { //return reverse_iterator(_head->_prev); return reverse_iterator(--end()); } reverse_iterator rend()//按照以前的理解，rend指向第一个数据前一个（哨兵位） { //return reverse_iterator(_head); return reverse_iterator(end()); } const_reverse_iterator rbegin() const { //return const_reverse_iterator(_head->_prev); return const_reverse_iterator(--end()); } const_reverse_iterator rend() const { //return const_reverse_iterator(_head); return const_reverse_iterator(end()); }
现在的 list.h 就是这样的：
#pragma once #include<iostream> #include<assert.h> #include "reverse_iterator.h" using namespace std; namespace rtx { template<class T> struct list_node // 定义结点 { T _data; list_node* _prev; list_node* _next; list_node(const T& x = T()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; template<class T, class Ref, class Ptr> struct __list_iterator // 定义迭代器 { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> iterator; // 在list类里面： // typedef __list_iterator<T, T&, T*> iterator; // typedef __list_iterator<T, const T&, const T*> const_iterator; Node* _node; __list_iterator(Node* node) :_node(node) {} bool operator!=(const iterator& it) { return _node != it._node; } //T& operator*() Ref operator*() { return _node->_data; // 返回结点的数据 } //T* operator->() Ptr operator->() { return &(operator*()); //即 return &(_node->_data); } iterator& operator++() { _node = _node->_next; return *this; // 返回加加后的值 } iterator operator++(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->_next; return tmp; // 返回加加前的值 } iterator& operator--() { _node = _node->_prev; return *this; // 返回减减后的值 } iterator operator--(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->prev; return tmp; // 返回减减前的值 } }; template<class T> class list // 定义list类 { typedef list_node<T> Node; public: typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; // 传正向迭代器封装出反向迭代器 typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } iterator begin()// begin是实际数据的第一个，_head 是哨兵位头结点 { return iterator(_head->_next); } iterator end()// end是实际数据的下一个 { return iterator(_head); } reverse_iterator rbegin()//按照以前的理解，rbegin指向最后一个数据 { //return reverse_iterator(_head->_prev); return reverse_iterator(--end()); } reverse_iterator rend()//按照以前的理解，rend指向第一个数据前一个（哨兵位） { //return reverse_iterator(_head); return reverse_iterator(end()); } const_reverse_iterator rbegin() const { //return const_reverse_iterator(_head->_prev); return const_reverse_iterator(--end()); } const_reverse_iterator rend() const { //return const_reverse_iterator(_head); return const_reverse_iterator(end()); } void empty_init()// 创建并初始化哨兵位头结点（即构造函数） { _head = new Node; _head->_next = _head; _head->_prev = _head; } template <class InputIterator> list(InputIterator first, InputIterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } } list() { empty_init(); } void swap(list<T>& x)//提一嘴：void swap(list& x)也行（类里面可以省略<T>，类外不行> { std::swap(_head, x._head); // 换哨兵位头结点就行 } list(const list<T>& lt)//lt2(lt1) { empty_init(); list<T> tmp(lt.begin(), lt.end()); // 迭代器区间构造一个(lt1) swap(tmp); // 直接和lt2换哨兵位头结点 } list<T>& operator=(list<T> lt)//lt3 = lt1 这里lt1直接深拷贝给lt，lt是局部对象，出来作用域直接调析构 { swap(lt);// 把深拷贝出来的lt和lt3交换 return *this; // 把lt3返回 } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); // 返回删除位置的下一个结点 } } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* NewNode = new Node(x); prev->_next = NewNode; NewNode->_prev = prev; NewNode->_next = cur; cur->_prev = NewNode; return iterator(NewNode); } void push_back(const T& x) { //Node* tail = _head->_prev; //Node* NewNode = new Node(x); 思路图：head tail NewNode //tail->_next = NewNode; //NewNode->_prev = tail; //_head->_prev = NewNode; //NewNode->_next = _head; insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; // 删cur Node* prev = cur->_prev; prev->_next = cur->_next; // cur前一个指向cur后一个 cur->_next->_prev = prev; // cur后一个指回cur前一个 delete cur; return iterator(prev->_next); // 返回删除位置下一个 } void pop_back() { erase(begin()); } void pop_front() { erase(--end()); } private: Node* _head; // 哨兵位头结点 }; }
测试一下：
#define _CRT_SECURE_NO_WARNINGS 1 #include "list.h" namespace rtx { void Test_reverse_iterator() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; list<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; ++rit; } cout << endl; } } int main() { rtx::Test_reverse_iterator(); return 0; }
测试一下：
#define _CRT_SECURE_NO_WARNINGS 1 #include "list.h" namespace rtx { void Test_reverse_iterator() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; list<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; ++rit; } cout << endl; } } int main() { rtx::Test_reverse_iterator(); return 0; }
这样实现也行，但是rbegin（）和rend（）就没那么美观，
所以巨佬就设计了下面的艺术行为：（也只是为了对称，没别的）
2.2 反向迭代器的对称实现
前面说到，我们认为应该是这样的：
但是库里面是这样实现的：
rbegin 和 rend 是和 end 和 begin 是相对称的形式设计的，
你的 end 就是我的 rbegin，你的 begin 就是我的 rend。
如果这样实现的话，对rbegin解引用就不对了，
我们先看看库里反向迭代器的解引用：
这样取的就是前一个位置了，rbegin() 位置的前一个位置正是想要取的地方。
来改一下，解引用应该是这样的：
reverse_iterator rbegin()// 对称实现 { //return reverse_iterator(_head->_prev); //return reverse_iterator(--end()); return reverse_iterator(end()); } reverse_iterator rend() { //return reverse_iterator(_head); //return reverse_iterator(end()); return reverse_iterator(begin()); } const_reverse_iterator rbegin() const { //return const_reverse_iterator(_head->_prev); return const_reverse_iterator(end()); } const_reverse_iterator rend() const { //return const_reverse_iterator(_head); return const_reverse_iterator(begin()); }
reverse_iterator.h
#pragma once namespace rtx { template<class Iterator, class Ref, class Ptr>// 为了适配const迭代器，再加两个参数 struct __reverse_iterator //普通迭代器传的就是 T& 和 T* const 迭代器传的就是 const T& 和 const T* { Iterator _cur; typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator; __reverse_iterator(Iterator it) :_cur(it) {} RIterator operator++() { --_cur; // 正向迭代器 ++ 就是反向迭代器 -- return *this; } RIterator operator--() { ++_cur; return *this; } Ref operator*() { //return *_cur; auto tmp = _cur; --tmp; return *tmp; } Ptr operator->() { //return _cur.operator->(); //return &(*_cur); // 如果这样写，对称的时候就要改了 return &(operator*()); } bool operator!=(const RIterator& it) { return _cur != it._cur; } }; }
list.h ：
#pragma once #include<iostream> #include<assert.h> #include "reverse_iterator.h" using namespace std; namespace rtx { template<class T> struct list_node // 定义结点 { T _data; list_node* _prev; list_node* _next; list_node(const T& x = T()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; template<class T, class Ref, class Ptr> struct __list_iterator // 定义迭代器 { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> iterator; // 在list类里面： // typedef __list_iterator<T, T&, T*> iterator; // typedef __list_iterator<T, const T&, const T*> const_iterator; Node* _node; __list_iterator(Node* node) :_node(node) {} bool operator!=(const iterator& it) { return _node != it._node; } //T& operator*() Ref operator*() { return _node->_data; // 返回结点的数据 } //T* operator->() Ptr operator->() { return &(operator*()); //即 return &(_node->_data); } iterator& operator++() { _node = _node->_next; return *this; // 返回加加后的值 } iterator operator++(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->_next; return tmp; // 返回加加前的值 } iterator& operator--() { _node = _node->_prev; return *this; // 返回减减后的值 } iterator operator--(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->prev; return tmp; // 返回减减前的值 } }; template<class T> class list // 定义list类 { typedef list_node<T> Node; public: typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; // 传正向迭代器封装出反向迭代器 typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } iterator begin()// begin是实际数据的第一个，_head 是哨兵位头结点 { return iterator(_head->_next); } iterator end()// end是实际数据的下一个 { return iterator(_head); } //reverse_iterator rbegin()//按照以前的理解，rbegin指向最后一个数据 //{ // //return reverse_iterator(_head->_prev); // return reverse_iterator(--end()); //} //reverse_iterator rend()//按照以前的理解，rend指向第一个数据前一个（哨兵位） //{ // //return reverse_iterator(_head); // return reverse_iterator(end()); //} //const_reverse_iterator rbegin() const //{ // //return const_reverse_iterator(_head->_prev); // return const_reverse_iterator(--end()); //} //const_reverse_iterator rend() const //{ // //return const_reverse_iterator(_head); // return const_reverse_iterator(end()); //} reverse_iterator rbegin()// 对称实现 { //return reverse_iterator(_head->_prev); //return reverse_iterator(--end()); return reverse_iterator(end()); } reverse_iterator rend() { //return reverse_iterator(_head); //return reverse_iterator(end()); return reverse_iterator(begin()); } const_reverse_iterator rbegin() const { //return const_reverse_iterator(_head->_prev); return const_reverse_iterator(end()); } const_reverse_iterator rend() const { //return const_reverse_iterator(_head); return const_reverse_iterator(begin()); } void empty_init()// 创建并初始化哨兵位头结点（即构造函数） { _head = new Node; _head->_next = _head; _head->_prev = _head; } template <class InputIterator> list(InputIterator first, InputIterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } } list() { empty_init(); } void swap(list<T>& x)//提一嘴：void swap(list& x)也行（类里面可以省略<T>，类外不行> { std::swap(_head, x._head); // 换哨兵位头结点就行 } list(const list<T>& lt)//lt2(lt1) { empty_init(); list<T> tmp(lt.begin(), lt.end()); // 迭代器区间构造一个(lt1) swap(tmp); // 直接和lt2换哨兵位头结点 } list<T>& operator=(list<T> lt)//lt3 = lt1 这里lt1直接深拷贝给lt，lt是局部对象，出来作用域直接调析构 { swap(lt);// 把深拷贝出来的lt和lt3交换 return *this; // 把lt3返回 } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); // 返回删除位置的下一个结点 } } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* NewNode = new Node(x); prev->_next = NewNode; NewNode->_prev = prev; NewNode->_next = cur; cur->_prev = NewNode; return iterator(NewNode); } void push_back(const T& x) { //Node* tail = _head->_prev; //Node* NewNode = new Node(x); 思路图：head tail NewNode //tail->_next = NewNode; //NewNode->_prev = tail; //_head->_prev = NewNode; //NewNode->_next = _head; insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; // 删cur Node* prev = cur->_prev; prev->_next = cur->_next; // cur前一个指向cur后一个 cur->_next->_prev = prev; // cur后一个指回cur前一个 delete cur; return iterator(prev->_next); // 返回删除位置下一个 } void pop_back() { erase(begin()); } void pop_front() { erase(--end()); } private: Node* _head; // 哨兵位头结点 }; }
Test.cpp：（写到这忽然发现以前的Test.cpp都习惯写成Test.c 了，懂就刑）
#define _CRT_SECURE_NO_WARNINGS 1 #include "list.h" namespace rtx { void Test_reverse_iterator() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; list<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; ++rit; } cout << endl; } } int main() { rtx::Test_reverse_iterator(); return 0; }
以后为了和库里面的类似，所以还是艺术地实现对称的反向迭代器好。
写到这可能还不知道我们实现的反向迭代器有多强（只要提供一个正向迭代器就行）
我们试试把 vector 的弄出来，在vector.h里 #include "reverse_iterator.h"
和上面一样只需在vector类里面加上下面的代码：
一模一样，你甚至可以一步复制粘贴，位置也不改了：
typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; // 传正向迭代器封装出反向迭代器 typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; reverse_iterator rbegin()// 对称实现 { //return reverse_iterator(_head->_prev); //return reverse_iterator(--end()); return reverse_iterator(end()); } reverse_iterator rend() { //return reverse_iterator(_head); //return reverse_iterator(end()); return reverse_iterator(begin()); } const_reverse_iterator rbegin() const { //return const_reverse_iterator(_head->_prev); return const_reverse_iterator(end()); } const_reverse_iterator rend() const { //return const_reverse_iterator(_head); return const_reverse_iterator(begin()); }
所以vector.h就是这样的：
vector.h
#pragma once #include<iostream> #include<assert.h> #include<string> #include "reverse_iterator.h" using namespace std; namespace rtx { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; // 传正向迭代器封装出反向迭代器 typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; reverse_iterator rbegin()// 对称实现 { //return reverse_iterator(_head->_prev); //return reverse_iterator(--end()); return reverse_iterator(end()); } reverse_iterator rend() { //return reverse_iterator(_head); //return reverse_iterator(end()); return reverse_iterator(begin()); } const_reverse_iterator rbegin() const { //return const_reverse_iterator(_head->_prev); return const_reverse_iterator(end()); } const_reverse_iterator rend() const { //return const_reverse_iterator(_head); return const_reverse_iterator(begin()); } vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} ~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } void push_back(const T& x) { //if (_finish == _end_of_storage) //{ // reserve(capacity() == 0 ? 4 : capacity() * 2); //} //*_finish = x; //++_finish; insert(end(), x); } void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * sz); //浅拷贝，不行 for (size_t i = 0; i < sz; i++)// 如果T是int，一个一个拷贝没问题 { tmp[i] = _start[i];// 如果T是string等自定义问题，一个一个拷贝调用的是T的深拷贝，也不会出问题。 } delete[] _start; } _start = tmp; _finish = tmp + sz; _end_of_storage = tmp + n; } } T& operator[](size_t pos) { assert(pos < size()); return *(_start + pos); } const T& operator[](size_t pos) const { assert(pos < size()); return *(_start + pos); } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } template<class InputInterator> vector(InputInterator first, InputInterator last) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (first != last) { push_back(*first); ++first; } } void resize(size_t n, const T& val = T()) { if (n > capacity()) { reserve(n); } if (n > size()) { while (_finish != _start + n) { *_finish = val; ++_finish; } } else { _finish = _start + n; } } void pop_back() { assert(_finish > _start); --_finish; } iterator insert(iterator pos, const T& val) { assert(pos >= _start);// ①检查pos是否越界 assert(pos <= _finish); if (_finish == _end_of_storage)// ②检查是否需要扩容 { size_t len = pos - _start;// 记录一下pos到_start的距离 reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len;// 迭代器失效问题，扩容后pos还是指向原来的空间，更新一下pos， //而且形参不会影响实参，传引用的话begin等就传不了，所以用返回解决 } iterator right = _finish - 1;// ③移动数据 while (right >= pos) { *(right + 1) = *right; --right; } *pos = val;// ④插入数据 ++_finish; return pos; } iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish);// 不能<= 因为_finish指向的是最后一个数据的下一个 iterator left = pos + 1; while (left < _finish) { *(left - 1) = *left; ++left; } --_finish; return pos;//此时pos就是删除位置下一个位置迭代器 } //vector(const vector<T>& v)// 传统写法 //{ // reserve(v.capacity()); // // memcpy(_start, v._start, v.size() * sizeof(T)); // 会翻车 // for (const auto& e : v) // { // push_back(e); // } //} void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } vector(const vector<T>& v)// 现代写法 :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { vector<T> tmp(v.begin(), v.end()); swap(tmp); } vector<T>& operator=(vector<T> v)// 现代写法 { swap(v); return *this; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }
Test.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include "list.h" #include "vector.h" namespace rtx { void Test_reverse_iterator() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; list<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; ++rit; } cout << endl; } void Test_reverse_iterator2() { vector<int> lt;//为了方便lt的名字都不改成常用的v了 lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); lt.push_back(50); vector<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; vector<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; ++rit; } cout << endl; } } int main() { //rtx::Test_reverse_iterator(); rtx::Test_reverse_iterator2(); return 0; }
刑，反向迭代器就讲到这里了，讲了这么多属实有点麻烦，但了解原理后就很方便了。
所有正向迭代器++和--的容器都能用这个反向迭代器了。
3. 迭代器的功能分类
迭代器从功能可以分为这三类：单向迭代器，双向迭代器，随机迭代器，（文档有说明）
其中只有单向迭代器不支持上面实现的反向迭代器，
对应的是没讲的，forward_list单链表和蓝线的下面两个哈希表
下面的迭代器可以看作是上面的迭代器的特殊形式，所以算法库里的传参就有这样的命名：
本篇完。
到这里我们已经讲了容器适配器和迭代器适配器，体会了适配器封装和复用的特点。
软件开发提倡的就是能复用就复用，尽量不要自己写。
到这里我们基本已经把C++（简单的学了），后面继续融合地讲，先讲讲模板没讲的东西。
再讲C++的三大特性里的继承和多态。还有数据结构关于树的内容，map和set容器。
