当前位置：网站首页>map和set的实现

#pragma once
#include "RBTree.hpp" //这里的这个头文件就是红黑树博客里面的所有代码组成的头文件

namespace cdd {
	template<class K, class V>
	class map {
		typedef pair<K, V> ValueType;
		struct KeyOfValue {
			const K& operator()(const ValueType& value) {
				return value.first;
			}
		};
		typedef RBTree<ValueType, KeyOfValue> tree;
	public:
		typedef typename tree::iterator iterator;
	public:
		map()
			:_t()
		{}

		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}

		size_t size()const
		{
			return _t.Size();
		}
		bool empty()const
		{
			return _t.Empty();
		}

		V& operator[](const K& key)
		{
			return (*(_t.Insert(make_pair(key, V())).first)).second;
		}
		pair<iterator, bool> insert(const ValueType& value)
		{
			return _t.Insert(value);
		}
		void swap(map<K, V>& m)
		{
			_t.Swap(m._t);
		}
		void clear()
		{
			_t.Clear();
		}
		iterator find(const K& key)
		{
			return _t.Find(make_pair(key, V()));
		}
	private:
		tree _t;
	};
}

标准库map相关知识点

标准库为 map 容器配备的是双向迭代器（bidirectional iterator）。这意味着，map 容器迭代器只能进行 ++p、p++、–p、p–、*p 操作，并且迭代器之间只能使用 == 或者 != 运算符进行比较。

值得一提的是，相比序列式容器，map 容器提供了更多的成员方法（如表 1 所示），通过调用它们，我们可以轻松获取具有指定含义的迭代器。

map容器默认排序规则为:按照key值进行从小到大的排序,当然,我么可以利用仿函数进行排序

set

set就更没有什么难的了,它没有[]重载,也不是键值对,所以实在没有什么有问题的地方

代码

#pragma once
#include "RBTree.hpp"
namespace zds {
	template<class K>
	class set {
		struct KeyOfValue {
			const K& operator()(const K& value) {
				return value;
			}
		};
		typedef RBTree<K, KeyOfValue> tree;
	public:
		typedef typename tree::iterator iterator;
	public:
		set()
			:_t()
		{}

		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
		size_t size()const
		{
			return _t.Size();
		}
		bool empty()const
		{
			return _t.Empty();
		}
		pair<iterator, bool> insert(const K& value)
		{
			return _t.Insert(value);
		}

		void swap(set<K>& s)
		{
			_t.Swap(s._t);
		}

		void clear()
		{
			_t.Clear();
		}
		iterator find(const K& key)
		{
			return _t.Find(key);
		}
	private:
		tree _t;
	};
}