C++之STLmap和set的模拟实现

转x33g5p2x  于2022-03-21 转载在 其他  
字(12.6k)|赞(0)|评价(0)|浏览(232)

模拟实现map和set

我们首先来看一下源码当中的set和map的结构：

  1. template <class Key,class Compare = less<Key>, class Alloc = alloc>
  2. class set {
  3. public:
  4.     typedef Key key_type;
  5.     typedef Key value_type;
  6.     typedef rb_tree<key_type,value_type,identity<value_type>,key_compare,Alloc> rep_type;
  7.     rep_type t; //red-black tree representing set
  8. };
  1. template <class Key,class T, class Compare = less<Key>, class Alloc = alloc>
  2. class map {
  3. public:
  4.     typedef Key key_type;
  5.     typedef pair<const Key,T> value_type;
  6.     typedef rb_tree<key_type,value_type,
  7.                     select1st<value_type>,key_compare,Alloc> rep_type;
  8. 	rep_type t; //red-black tree representing mapI
  9. };
  1. typedef Key value_type;
  2. typedef rb_tree<key_type,value_type,identity<value_type>,key_compare,Alloc> rep_type
  3. //set的红黑树模板参数
  4.     
  5. typedef pair<const Key,T> value_type;
  6. typedef rb_tree<key_type,value_type,select1st<value_type>,key_compare,Alloc> rep_type;
  7. //map的红黑树模板参数

可以看到set当中的红黑树key_type,value_type这两个模板参数，key_type是Key，而且value_type也被typedef成Key，两个Key是什么意思呢？而map当中的红黑树key_type,value_type这两个模板参数，key_type是Key，而且value_type被typedef成pair<const Key,T>

源码中红黑树的结构

  1. template <class Key,class Value, class KeyOfValue,class Compare,class Alloc = allpc>
  2. class rb_tree 
  3. {
  4. protected:
  5. 	typedef _rb_tree_node<Value> rb_tree_node;
  6. 	typedef rb_tree_node* link_type;
  7. protected:
  8. 	link_type header;
  9. };
  10. template <class Value>
  11. struct _rb_tree_node : public _rb_tree_node_base
  12. {
  13. 	typedef _rb_tree_node<Value>* link_type;
  14. 	Value value_field;
  15. };

可以看到红黑树的模板参数中的第二个参数是Value，通过这个参数就可以实现上层set给红黑树传Key，Value就是Key，上层map给红黑树pair<const K,V>，Value就是pair<const K,V>，红黑树中的数据值Value value_field就能够灵活变换。

  1. template<class K>
  2. class set
  3. {
  4. public:
  5.     //...
  6. private:
  7.     RBTree<K,K> _t;
  8. };
  1. template<class K,class V>
  2. class map
  3. {
  4. public:
  5.     //...
  6. private:
  7.     RBTree<K,pair<K,V>> _t;
  8. };

我们发现set底层的红黑树模板参数第一个和第二个一样，那么能不能不要第一个模板参数呢？

不能，对于set省略掉没有问题，因为set传入红黑树的参数一和二是相同的，但是map就不行，因为map如果只传入第二个参数pair，map提供的接口是有些需要Key值的，比如find和erase。

我们将底层红黑树的模板参数写成：

  1. template<class K,class T>
  2. class RBTree{};

T来接受map和set传进来了第二个参数，他可能是key也可能是pair

相应的红黑树节点的数据类型我们也需要改成T：

  1. enum Colour
  2. {
  3.     BLACK,
  4.     RED
  5. };
  6. template<classT>
  7. struct RBTreeNode
  8. {
  9.     RBTreeNode<T>* _left;
  10.     RBTreeNode<T>* _right;
  11.     RBTreeNode<T>* _parent;
  12.     
  13.     Colour _col;//颜色
  14.     
  15.     T _data;//键值对
  16.     
  17.     //构造函数
  18.     RBTreeNode(const T& data)
  19.         :_left(nullptr),
  20.         :_right(nullptr),
  21.         :_parent(nullptr),
  22.         :col(RED),
  23.         :_data(data)
  24. 	{}
  25. };

T传key是key，传pair是pair

模板参数中的仿函数

我们前面可以看到红黑树源码当中还有一个模板参数仿函数，这个参数是用来比较键值用的，因为第二个参数是T，set传入的是key，map传入的是pair，在比较键值的时候，是set还可以直接比较，当时map时，pair是不支持比较的，所以上层容器需要给底层红黑树提供一个仿函数，用来重载()获取key值：

  1. template<class K, class V>
  2. class map
  3. {
  4. 	//仿函数
  5. 	struct MapKeyOfT
  6. 	{
  7. 		const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key
  8. 		{
  9. 			return kv.first;
  10. 		}
  11. 	};
  12. public:
  13. private:
  14. 	RBTree<K, pair<K, V>, MapKeyOfT> _t;
  15. };

set也需要写仿函数，传进去，因为底层红黑树没办法知道传进去的是set还是map，所以当需要键值进行比较大小时，红黑树都会根据仿函数来进行比较

set的仿函数：

  1. template<class K>
  2. class set
  3. {
  4. 	//仿函数
  5. 	struct SetKeyOfT
  6. 	{
  7. 		const K& operator()(const K& key) //返回键值Key
  8. 		{
  9. 			return key;
  10. 		}
  11. 	};
  12. public:
  13. private:
  14. 	RBTree<K, pair<K, V>, SetKeyOfT> _t;
  15. };

增加了一个参数仿函数后，红黑树的参数也发生了变化：

  1. template<class K,class T,class KeyOfT>
  2. class RBTree{};

相应的之前实现的红黑树的一些有比较键值的地方就需要改变，比如查找函数和插入函数

红黑树的迭代器的模拟实现

红黑树的迭代器的实现其实就是对节点的指针进行了封装

迭代器的基本结构

  1. template<class T,class Ref,class Ptr>
  2. struct RBTreeIterator
  3. {
  4. 	typedef RBTreeNode<T> Node;
  5.     typedef RBTreeIterator<T,Ref,Ptr> Self;//自身类型的typedef
  6.     Node* _node;
  7.     //构造函数
  8.     RBTreeIterator(Node* node = nullptr)
  9.         :_node(node)
  10.     {}
  11. };

红黑树的迭代器如何实现*呢？因为我们对节点的指针进行了封装，只需要返回节点的数据的引用即可

  1. Ref operator*()
  2. {
  3.     return _node->_data;
  4. }

红黑树的迭代器如何实现->呢？因为我们对节点的指针进行了封装，只需要返回节点的数据的指针即可

  1. Ptr operator->()
  2. {
  3.     return &_node->_data;
  4. }

相应的!=和==也可以写出来，直接判断两个迭代器所封装的节点是不是同一个即可：

  1. bool operator!=(const Self& s) const
  2. {
  3.     return _node!=s._node;//指向节点的指针不相同
  4. }
  5. bool operator==(const Self& s) const
  6. {
  7.     return _node==s._node;指向节点的指针相同
  8. }

那么红黑树的迭代器如何实现++呢？

一个节点进行++时，应该根据红黑树中序遍历序列找到当前节点的下一个节点，因为中序遍历是先访问左子树再访问根节点，最后访问右子树。

思路如下：

1、如果it指向节点的右子树不为空，下一个就++到右子树中序第一个节点，也就是右子树的最左节点。

2、如果it指向节点右子树为空，下一个++要访问的节点是，沿着it指向节点到根节点的路径中，遍历寻找孩子是父亲左的那个父亲节点

  1. Self& operator++()
  2.     { 
  3.         if(_node->_right)
  4.         {
  5.             //右子树中序第一个节点，也就是右子树的最左节点
  6.             Node* subLeft = _node->_right;
  7.             while(subLeft->_left)
  8.             {
  9.                 subLeft = subLeft->_left;
  10.             }
  11.             _node = subLeft;
  12.         }
  13.         else
  14.         {
  15.             //右为空,当前子树已经访问完了，要去找祖先访问，沿着到根节点的路径往上走，
  16.             //找孩子是父亲左的那个父亲节点
  17.             Node* cur = _node;
  18.             Node* parent = cur->_parent;
  19.             while(parent && parent->_right == cur)
  20.             {
  21.                 cur = parent;
  22.                 parent = parent->_parent;
  23.             }
  24.             _node = parent;
  25.         }
  26.         return *this;
  27.     }

那么红黑树的迭代器如何实现–呢？和++的思路反一下就好了：

1、如果当前节点的左子树不为空，则–操作后要找到其左子树当中的最右节点

2、如果当前节点的左子树为空，则–操作后应该在该节点到根节点的路径中找到孩子在父亲右的祖先

  1. Self operator--()
  2. {
  3. 	if (_node->_left) 
  4. 	{
  5.          //左子树中序第一个节点，也就是左子树的最右节点
  6. 		//寻找该结点左子树当中的最右结点
  7. 		Node* right = _node->_left;
  8. 		while (right->_right)
  9. 		{
  10. 			right = right->_right;
  11. 		}
  12. 		_node = right; 
  13. 	}
  14. 	else //结点的左子树为空
  15. 	{
  16. 		//寻找孩子在父亲右的祖先
  17. 		Node* cur = _node;
  18. 		Node* parent = cur->_parent;
  19. 		while (parent&&cur == parent->_left)
  20. 		{
  21. 			cur = parent;
  22. 			parent = parent->_parent;
  23. 		}
  24. 		_node = parent; 
  25. 	}
  26. 	return *this;
  27. }

最后我们需要在红黑树里面实现begin和end：

  1. typedef RBTreeIterator<T,T&,T*> iterator;
  2. typedef RBTreeIterator<T,const T&,const T*> const_iterator; 
  3. iterator begin()
  4. {
  5.     Node* left = _root;
  6.     while(left && left->_left)
  7.     {
  8.         left = left->_left;
  9.     }
  10.     return iterator(left);//返回最左节点的迭代器
  11. }
  1. iterator end()
  2. {
  3.     return iterator(nullptr);
  4. }

我们实现的迭代器和STL当中的是有差别的，我们对end()–理应返回最后一个节点的迭代器，但是上面的实现无法实现此操作，在STL库当中实现红黑树时，他在根节点增加了头节点，它的左指针指向红黑树的最左节点，右指针指向红黑树当中的最右节点，父亲指针指向红黑树的根节点。通过一些逻辑的控制就可以实现上面的操作

红黑树的迭代器的整体代码

  1. template<class T,class Ref,class Ptr>
  2. struct RBTreeIterator
  3. {
  4. 	typedef RBTreeNode<T> Node;
  5.     typedef RBTreeIterator<T,Ref,Ptr> Self;
  6.     Node* _node;
  7.     RBTreeIterator(Node* node = nullptr)
  8.         :_node(node)
  9.     {}
  10.     Ref operator*()
  11.     {
  12.         return _node->data;
  13.     }
  14.     Ptr operator->()
  15.     {
  16.         return &_node->_data;
  17.     }
  18.     bool operator!=(const Self& s) const
  19.     {
  20.         return _node!=s._node;
  21.     }
  22.     bool operator==(const Self& s) const
  23.     {
  24.         return _node==s._node;
  25.     }
  26.     Self& operator++()
  27.     { 
  28.         if(_node->_right)
  29.         {
  30.             //右子树中序第一个节点，也就是右子树的最左节点
  31.             Node* subLeft = _node->_right;
  32.             while(subLeft->_left)
  33.             {
  34.                 subLeft = subLeft->_left;
  35.             }
  36.             _node = subLeft;
  37.         }
  38.         else
  39.         {
  40.             //右为空,当前子树已经访问完了，要去找祖先访问，沿着到根节点的路径往上走，
  41.             //找孩子是父亲左的那个父亲节点
  42.             Node* cur = _node;
  43.             Node* parent = cur->_parent;
  44.             while(parent && parent->_right == cur)
  45.             {
  46.                 cur = parent;
  47.                 parent = parent->_parent;
  48.             }
  49.             _node = parent;
  50.         }
  51.         return *this;
  52.     }
  53.     Self operator--()
  54.     {
  55.         if (_node->_left) 
  56.         {
  57.              //左子树中序第一个节点，也就是左子树的最右节点
  58.             //寻找该结点左子树当中的最右结点
  59.             Node* right = _node->_left;
  60.             while (right->_right)
  61.             {
  62.                 right = right->_right;
  63.             }
  64.             _node = right; 
  65.         }
  66.         else //结点的左子树为空
  67.         {
  68.             //寻找孩子在父亲右的祖先
  69.             Node* cur = _node;
  70.             Node* parent = cur->_parent;
  71.             while (parent&&cur == parent->_left)
  72.             {
  73.                 cur = parent;
  74.                 parent = parent->_parent;
  75.             }
  76.             _node = parent; 
  77.         }
  78.         return *this;
  79.     }
  80. }
  1. #pragma once
  2. enum Colour
  3. {
  4.     BLACK,
  5.     RED
  6. };
  7. template<class T>
  8. struct RBTreeNode
  9. {
  10.     RBTreeNode<T>* _left;
  11.     RBTreeNode<T>* _right;
  12.     RBTreeNode<T>* _parent;
  13.     Colour _col;
  14.     T _data;
  15.     RBTreeNode(const T& data)
  16.         :_left(nullptr),
  17.         :_right(nullptr),
  18. 		:_parent(nullptr),
  19.     	:col(RED),
  20.     	:_data(data)
  21. 	{}
  22. };
  23. template<class T,class Ref,class Ptr>
  24. struct RBTreeIterator
  25. {
  26. 	typedef RBTreeNode<T> Node;
  27.     typedef RBTreeIterator<T,Ref,Ptr> Self;
  28.     Node* _node;
  29.     RBTreeIterator(Node* node = nullptr)
  30.         :_node(node)
  31.         {}
  32.     Ref operator*()
  33.     {
  34.         return _node->data;
  35.     }
  36.     Ptr operator->()
  37.     {
  38.         return &_node->_data;
  39.     }
  40.     bool operator!=(const Self& s) const
  41.     {
  42.         return _node!=s._node;
  43.     }
  44.     bool operator==(const Self& s) const
  45.     {
  46.         return _node==s._node;
  47.     }
  48.     Self& operator++()
  49.     { 
  50.         if(_node->_right)
  51.         {
  52.             //右子树中序第一个节点，也就是右子树的最左节点
  53.             Node* subLeft = _node->_right;
  54.             while(subLeft->_left)
  55.             {
  56.                 subLeft = subLeft->_left;
  57.             }
  58.             _node = subLeft;
  59.         }
  60.         else
  61.         {
  62.             //右为空,当前子树已经访问完了，要去找祖先访问，沿着到根节点的路径往上走，
  63.             //找孩子是父亲左的那个父亲节点
  64.             Node* cur = _node;
  65.             Node* parent = cur->_parent;
  66.             while(parent && parent->_right == cur)
  67.             {
  68.                 cur = parent;
  69.                 parent = parent->_parent;
  70.             }
  71.             _node = parent;
  72.         }
  73.         return *this;
  74.     }
  75.     Self& operator--()
  76.     { 
  77.         //跟++基本是反过来
  78.         return *this;
  79.     }
  80. }    
  81. template<class K,class T,class KeyOfT>
  82. class RBTree
  83. {
  84.     typedef RBTreeNode<T> Node;
  85. public:
  86.     typedef RBTreeIterator<T,T&,T*> iterator;
  87.     typedef RBTreeIterator<T,const T&,const T*> const_iterator;
  88.     
  89.     iterator begin()
  90.     {
  91.         Node* left = _root;
  92.         while(left && left->_left)
  93.         {
  94.             left = left->_left;
  95.         }
  96.         return iterator(left);
  97.     }
  98.     iterator end()
  99.     {
  100.         return iterator(nullptr);
  101.     }
  102.     RBTree()
  103.         :_root(nullptr)
  104.     {}
  105.     
  106.     //查找函数
  107. 	iterator Find(const K& key)
  108. 	{
  109. 		KeyOfT kot;
  110. 		Node* cur = _root;
  111. 		while (cur)
  112. 		{
  113. 			if (key < kot(cur->_data)) //key值小于该结点的值
  114. 			{
  115. 				cur = cur->_left; //在该结点的左子树当中查找
  116. 			}
  117. 			else if (key > kot(cur->_data)) //key值大于该结点的值
  118. 			{
  119. 				cur = cur->_right; //在该结点的右子树当中查找
  120. 			}
  121. 			else //找到了目标结点
  122. 			{
  123. 				return iterator(cur); //返回该结点
  124. 			}
  125. 		}
  126. 		return end(); //查找失败
  127. 	}
  128.     
  129.     //插入
  130.     pair<iterator,bool> Insert(const T& data)//插入需要比较大小找位置，此时引入了第三个模板参数KeyOfT
  131.     {
  132.         if(_root == nullptr)
  133.         {
  134.             _root = new Node(data);
  135.             _root->_col = BLACK;
  136.             return make_pair(iterator(_root),true);
  137.         }
  138.         KeyOfT kot;
  139.         Node* parent = nullptr;
  140.         Node* cur = _root;
  141.         while(cur)
  142.         {
  143.             if(kot(cur->_data) < kot(data))
  144.             {
  145.                 parent = cur;
  146.                 cur = cur->_right;
  147.             }
  148.             else if((kot(cur->_data) > kot(data))
  149.             {
  150.                 parent = cur;
  151.                 cur = cur->_left;
  152.             }
  153.             else
  154.             {
  155.                 //相等了，已经有了
  156.                 return make_pair(iterator(cur),false);
  157.             }
  158.         }
  159.         //插入红色可能破坏规则3，插入黑色一定破坏规则4,破坏规则4比较难处理
  160.         //新增节点就新增一个红色节点
  161.         //1、如果新增节点的父亲是黑色，没有影响
  162.         //2、如果新增节点的父亲是红色，则产生了连续的红色节点，破坏了规则3，需要分情况处理：
  163.         
  164.         cur = new Node(data);
  165.        	Node* newnode = cur;
  166.         cur->_col = RED;
  167.         //插入链接
  168.         if(kot(parent->_data) < kot(data))
  169.         {
  170.             parent->_right = cur;
  171.             cur->_parent = parent;
  172.         }
  173.         else
  174.         {
  175.             parent->_left = cur;
  176.             cur->_parent = parent;
  177.         }
  178.         //控制平衡,控制颜色
  179.         while(parent && parent->_col == RED)
  180.         {
  181.             Node* greandfather = parent->_parent;
  182.             if(parent == greandfather->_right)
  183.             {
  184.                 //找到叔叔
  185.                 Node* uncle = greandfather->_right;
  186.                 //情况一：uncle存在且为红，进行变色处理即可,并且继续往上更新处理
  187.                 if(uncle && uncle->_col == RED)
  188.                 {
  189.                     parent->_col = uncle->_col = BLACK;
  190.                     grandfather->_col = RED;
  191.                     
  192.                     cur = grandfather;
  193.                     parent = cur->_parent;
  194.                 }//情况二+三：uncle不存在，uncle存在且为黑，进行旋转+变色处理
  195.                 else
  196.                 {
  197.                     //情况二：单旋+变色
  198.                     if(cur == parent->_left)
  199.                     {
  200.                         RotateR(greandfather);
  201.                         parent->_col = BLACK;
  202.                         greandfather->_col = RED;
  203.                     }
  204.                     else
  205.                     {
  206.                         //情况三：双旋+变色
  207.                         RotateL(parent);
  208.                         RotateR(greandfather);
  209.                         cur->_col = BLACK;
  210.                         greandfather->_col = RED;
  211.                     }
  212.                     break;
  213.                 }
  214.             }
  215.             else//parent == greandfather->_right
  216.             {
  217.                 Node* uncle = greandfather->_left; 
  218.                 if(uncle && uncle ->col == RED)
  219.                 {
  220.                     parent->_col = uncle->_col = BLACK;
  221.                     grandfather->_col = RED;
  222.                     
  223.                     cur = grandfather;
  224.                     parent = cur->_parent;
  225.                 }
  226.                 else
  227.                 {
  228.                     if(parent->_right == cur)
  229.                     {
  230.                         RotateL(grandfather);
  231.                         parent->_col = BLACK;
  232.                         grandfather->COL = RED;
  233.                     }
  234.                     else//parent->_left == cur
  235.                     {
  236.                         //双旋+变色
  237.                         RotateR(parent);
  238.                         RotateL(grandfather);
  239.                         cur->_col = BLACK;
  240.                         grandfather->_col = RED;
  241.                     }
  242.                     //不用再继续了，不会有连续红色和黑色个数不一样
  243.                     break;
  244.                 }
  245.             }
  246.         }
  247.         _root->_col = BLACK;
  248.         return make_pair(iterator(newnode),true);
  249.     }
  250.     void _InOrder(Node* root)
  251. 	{
  252. 		if (root == nullptr)
  253. 		{
  254. 			return;
  255. 		}
  257. 		_InOrder(root->_left);
  258. 		cout << root->_kv.first << " ";
  259. 		_InOrder(root->_right);
  260. 	}
  262. 	void InOrder()
  263. 	{
  264. 		_InOrder(_root);
  265. 		cout<<endl;
  266. 	}
  267.     void RotateR(Node* parent)
  268. 	{
  269. 		Node* subL = parent->_left;
  270. 		Node* subLR = subL->_right;
  272. 		parent->_left = subLR;
  273. 		if (subLR)
  274. 			subLR->_parent = parent;
  276. 		Node* ppNode = parent->_parent;
  278. 		subL->_right = parent;
  279. 		parent->_parent = subL;
  281. 		if (parent == _root)
  282. 		{
  283. 			_root = subL;
  284. 			subL->_parent = nullptr;
  285. 		}
  286. 		else
  287. 		{
  288. 			if (ppNode->_left == parent)
  289. 				ppNode->_left = subL;
  290. 			else
  291. 				ppNode->_right = subL;
  293. 			subL->_parent = ppNode;
  294. 		}
  295. 	}
  297. 	void RotateL(Node* parent)
  298. 	{
  299. 		Node* subR = parent->_right;
  300. 		Node* subRL = subR->_left;
  302. 		parent->_right = subRL;
  303. 		if (subRL)
  304. 			subRL->_parent = parent;
  306. 		Node* ppNode = parent->_parent;
  308. 		subR->_left = parent;
  309. 		parent->_parent = subR;
  311. 		if (parent == _root)
  312. 		{
  313. 			_root = subR;
  314. 			subR->_parent = nullptr;
  315. 		}
  316. 		else
  317. 		{
  318. 			if (ppNode->_left == parent)
  319. 			{
  320. 				ppNode->_left = subR;
  321. 			}
  322. 			else
  323. 			{
  324. 				ppNode->_right = subR;
  325. 			}
  327. 			subR->_parent = ppNode;
  328. 		}
  329. 	}
  330. private:
  331.     Node* _root;
  332. }

map的模拟实现

map的实现，成员函数底层都是使用红黑树的接口完成的，对于map来说，除了将插入函数和查找函数返回值改为迭代器之外，还要实现[]运算符的重载

  1. #include"RBTree.h"
  2. namespace Z
  3. {
  4.     template<class K,class V>
  5.     class map
  6.     {
  7.         struct MapKeyOfT
  8.         {
  9.             const K& operator()(const pair<const K,V>& kv)
  10.             {
  11.                 return kv.first;
  12.             }
  13.         };
  14.     public:
  15.         typedef typename RBTree<K,K,MapKeyOfT>::iterator iterator;
  16.         iterator begin()
  17.         {
  18.             return _t.begin();
  19.         }
  20.         iterator end()
  21.         {
  22.             return _t.end();
  23.         }
  24.         
  25.         pair<iterator,bool> Insert(const pair<const K,V>& kv)
  26.         {
  27.             return _t.Insert(kv);
  28.         }
  29.         iterator find(const K& key)
  30.         {
  31.             return _t.Find(key);
  32.         }
  33.         V& operator[](const K& key)
  34.         {
  35.             pair<iterator,bool> ret = _t.Insert(make_pair(key,V()));
  36.         	return ret.first->second;
  37.         }
  38.     private:
  39.         RBTree<K,pair<const K,V>,MapKeyOfT> _t;
  40.     };
  41.     void test_map()
  42.     {
  43.         map<string,string> dict;
  44.         dict.insert(make_pair("sort","排序"));
  45.         dict.insert(make_pair("string","字符串"));    
  46.         map<string, string>::iterator it = dict.begin();
  47. 		while (it != dict.end())
  48. 		{
  49. 			cout << it->first << ":" << it->second << endl;
  50. 			++it;
  51. 		}
  52. 		cout << endl;
  53.     }
  54. }

set的模拟实现

成员函数底层都是使用红黑树的接口完成的，将插入函数和查找函数返回值改为迭代器

  1. #include"RBTree.h"
  2. namespace Z
  3. {
  4.     template<class K,class V>
  5.     class set
  6.     {
  7.         struct SetKeyOfT
  8.         {
  9.             K& operator()(const K& key)
  10.             {
  11.                 return key;
  12.             }
  13.         };
  14.     private:
  15.         RBTree<K,K,SetKeyOfT> _t;
  16.     public:
  17.         typedef typename RBTree<K,K,SetKeyOfT>::iterator iterator;//生成实例后再去找
  18.         iterator begin()
  19.         {
  20.             return _t.begin();
  21.         }
  22.         iterator end()
  23.         {
  24.             return _t.end();
  25.         }
  26.         pair<iterator, bool> Insert(const K& key)
  27.         {
  28.             return _t.Insert(key);
  29.         }
  30.         iterator find(const K& key)
  31.         {
  32.             return _t.Find(key);
  33.         }
  34.     };
  35.     void test_set()
  36.     {
  37.         set<int> s;
  38.         s.insert(1);
  39.         s.insert(2);
  40.         s.insert(3);    
  41.         s.insert(4);   
  42.         set<int>::iterator it = s.begin();
  43.         while(it!=s.end())
  44.         {
  45.             cout<<*it<<" ";
  46.             ++it;
  47.         }
  48.         cout<<endl;
  49.     }
  50. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/attemptendeavor/article/details/123646853

内容来源于网络，如有侵权，请联系作者删除！

c++map和set

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com