【STL】模拟實作STL中set容器

文章目錄

• 1. 模拟實作set需要了解的概念
• 2. 模拟實作set代碼

1. 模拟實作set需要了解的概念

• 在 STL 中的 set 容器，其底層資料結構是

  紅黑樹

• set 中存儲的資料是以 key - value 的形式存儲的
• 使用者存儲的資料是放在 key 中的， value 使用者是無法通路的

2. 模拟實作set代碼

改代碼可以運作的前提是需要紅黑樹的模拟實作中的紅黑樹代碼

map.hpp

#pragma once
#include "RBTree.hpp"	// 紅黑樹的模拟實作

// set 中防止的是
template<class K>
class set
{

	typedef K ValueType;
	struct KOFP
	{
		const K& operator()(const ValueType& data)
		{
			return data;
		}
	};
	typedef RBTree<ValueType, KOFP> RBT;
	typedef typename RBT::iterator iterator;
public:
	set() :_t(){}

	// iterator
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}

	// capacity
	size_t size()
	{
		return _t.size();
	}
	bool empty()
	{
		return _t.empty();
	}

	// modify
	pair<iterator, bool> insert(const ValueType& data)
	{
		return _t.insert(data);
	}
	void swap(set<K>& s)
	{
		_t.swap(s._t);
	}
	void clear()const
	{
		_t.clear();
	}
	iterator find(const K& key)
	{
		return _t.find(key);
	}

private:
	RBT _t;
};