c++ - 模拟实现set、map

---

前言

在C++标准库中，std::set 和 std::map都是非常常用的容器，它们提供了基于键值对的存储和快速查找能力。然而，关于它们的底层实现，C++标准并没有强制规定具体的数据结构，只是规定了它们的行为特性（如唯一性、有序性等）。不过，大多数C++标准库实现（如GCC的libstdc++和Clang的libc++）都采用了红黑树（Red-Black> Tree）作为std::set和std::map的底层数据结构。

下面都是基于红黑树实现的set和map。

---

一、set模拟实现

当前的红黑树需要这三个类型参数（键值、数据，通过数据求key的仿函数），这是为了map也能够复用，但是set只传入一个数据，所以采用这样的方式：<K， const K，Setfunc< K >>，因为set中的数据是不能被修改的所以在第二个类型中加上const

1、基本框架

//获取红黑树key的函数
template <class K>
struct Setfunc
{K operator()(const K& val){return val;}
};template <class K, class KeyOfValue = Setfunc<K>>
class set
{
public://红黑树typedef RBTree<K, const  K, KeyOfValue> RB;private://红黑树RB _rbset;};

2、迭代器
这里的迭代器直接复用红黑树的迭代器。

/*
第一 K类型是作为键值给删除，查找等需要键值的接口使用的
第二 const K是作为数据，给插入等接口使用
第三 KeyOfValue是仿函数，是给红黑树将数据类型转化为key使用，如插入时使用
*/
//迭代器
typedef typename RBTree<K,const K, KeyOfValue>::Iterator  iterator;
typedef typename RBTree<K, const K, KeyOfValue>::ConstIterator  cosnt_iterator;//迭代器
iterator begin()
{return _rbset.Begin();
}iterator end()
{return _rbset.End();
}cosnt_iterator begin() const
{return _rbset.Begin();
}cosnt_iterator end() const
{return _rbset.End();
}

3、插入、删除、查找、清空
以上接口均复用红黑树接口

//插入
pair<bool, iterator> insert(const K & val)
{return 	_rbset.Insert(val);
}//删除
bool erase(const K& key)
{return _rbset.Erase(key);
}//查找
iterator find(const K& key)
{return _rbset.Find(key);
}//清空
bool clear()
{_rbset.Clear();
}

4、拷贝构造和赋值重载
（1）拷贝构造：
遍历需要拷贝的对象，再插入到新的对象里。

set(const set<K, KeyOfValue> & p) 
{//遍历set,重新插入set<K, KeyOfValue>::cosnt_iterator it = p.begin();while (it != p.end()){insert(*it);++it;}
};

（2）赋值重载：
比拷贝构造多一步，就是在插入前需要清空。

set<K, KeyOfValue>& operator=(const set<K, KeyOfValue>& p)
{//清空当前setclear();//遍历set,重新插入set<K, KeyOfValue>::cosnt_iterator it = p.begin();while (it != p.end()){insert(*it);++it;}
}

5、测试

void test_set()
{set<int> _s;//插入for (int i = 0; i < 10; i++){_s.insert(i);}cout << "s1： ";set<int> s1 = _s;	//拷贝构造//迭代器遍历set<int>::iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";++it1;}cout << endl;cout << "s2： ";set<int> s2;s2 = s1;	//赋值//删除s2.erase(1);s2.erase(5);s2.erase(4);s2.erase(8);//迭代器遍历set<int>::iterator it2 = s2.begin();while (it2 != s2.end()){cout << *it2 << " ";++it2;}cout << endl;
}

6、总代码

//获取红黑树key的函数
template <class K>
struct Setfunc
{K operator()(const K& val){return val;}
};template <class K, class KeyOfValue = Setfunc<K>>
class set
{
public://红黑树typedef RBTree<K, const  K, KeyOfValue> RB;/*第一 K类型是作为键值给删除，查找等需要键值的接口使用的第二 const K是作为数据，给插入等接口使用第三 KeyOfValue是仿函数，是给红黑树将数据类型转化为key使用，如插入时使用*///迭代器typedef typename RBTree<K,const K, KeyOfValue>::Iterator  iterator;typedef typename RBTree<K, const K, KeyOfValue>::ConstIterator  cosnt_iterator;//构造set() {};set(const set<K, KeyOfValue> & p) {//遍历set,重新插入set<K, KeyOfValue>::cosnt_iterator it = p.begin();while (it != p.end()){insert(*it);++it;}};set<K, KeyOfValue>& operator=(const set<K, KeyOfValue>& p){//清空当前setclear();//遍历set,重新插入set<K, KeyOfValue>::cosnt_iterator it = p.begin();while (it != p.end()){insert(*it);++it;}return *this;}//析构~set() {};//迭代器iterator begin(){return _rbset.Begin();}iterator end(){return _rbset.End();}cosnt_iterator begin() const{return _rbset.Begin();}cosnt_iterator end() const{return _rbset.End();}//插入pair<bool, iterator> insert(const K & val){return 	_rbset.Insert(val);}//删除bool erase(const K& key){return _rbset.Erase(key);}//查找iterator find(const K& key){return _rbset.Find(key);}//清空void  clear(){_rbset.Clear();}private://红黑树RB _rbset;
};

二、map模拟实现

map给红黑树传的类型为：<K, pair<const K, V, KeyOfValue> ,K类型用于删除、查找等，pair<const K, V,>作为数据插入，KeyOfValue取pair<const K, V,>中的K类型，又因为键值不能修改所以pair<const K, V,>中的K加上const修饰。

1、基础框架

//获取 pair<K,V>中的key
template <class K,class V>
struct Mapfunc
{K operator()(const pair<K,V>& val){return val.first;}
};template <class K, class V, class KeyOfValue = Mapfunc<K,V>>
class map
{
public://重命名typedef RBTree<K, pair<const K, V>, KeyOfValue> RB;
private://红黑树RB _rbmap;
};

2、迭代器
依旧是复用红黑树迭代器即可。

typedef typename RB::Iterator  iterator;
typedef typename RB::ConstIterator  const_iterator;iterator begin()
{return _rbmap.Begin();
}iterator end()
{return _rbmap.End();
}const_iterator begin() const 
{return _rbmap.Begin();
}const_iterator end()const 
{return _rbmap.End();
}

3、插入、删除、查找、清空
依旧是复用红黑树接口即可。

//插入
pair<bool,iterator> insert(const pair<K, V>& val)
{return _rbmap.Insert(val);
}//删除
bool erase(const K& key)
{return _rbmap.Erase(key);
}//查找
iterator find(const K& key)
{return _rbmap.Find(key);
}//清空
void  clear()
{_rbmap.Clear();
}

4、重载[ ]
当key不存在时，重载[ ]就会用key进行插入操作并返回插入后key对应数据的引用（此时key对应数据是用其默认构造进行初始化的），当key存在时，返回key对应数据的引用。

//重载[]
V& operator[](const K& key)
{pair<bool, iterator> ret = insert(make_pair(key, V()));return ret.second->second;
}

5、拷贝构造和赋值构造
（1）遍历需要拷贝的对象并将其数据插入当前对象即可。

map(const map<K,V, KeyOfValue> & p) 
{map<K, V, KeyOfValue>::const_iterator it = p.begin();while (it != p.end()){insert(*it);++it;}
};

（2）先清空再遍历插入当前对象即可。

map<K, V, KeyOfValue>& operator=(const map<K, V, KeyOfValue>& p)
{clear();map<K, V, KeyOfValue>::const_iterator it = p.begin();while (it != p.end()){insert(*it);++it;}return *this;
}

6、测试

 void test_map()
{//默认构造map<int, int> m;//插入for(int i = 1; i < 10; i++)m.insert({ i,i });//迭代器遍历cout << "m1:";//拷贝构造map<int, int> m1 = m;map<int, int>::iterator it1 = m1.begin();while (it1 != m1.end()){cout << it1->second << " ";++it1;}cout << endl;cout << "m2:";//赋值map<int, int> m2;m2 = m;//删除m2.erase(1);m2.erase(2);//使用[]m2[3] = 100;m2[4] = 100;map<int, int>::iterator it2 = m2.begin();while (it2 != m2.end()){cout << it2->second << " ";++it2;}}

7、总代码

template <class K,class V>
struct Mapfunc
{K operator()(const pair<K,V>& val){return val.first;}
};
template <class K, class V, class KeyOfValue = Mapfunc<K,V>>
class map
{
public:typedef RBTree<K, pair<const K, V>, KeyOfValue> RB;typedef typename RB::Iterator  iterator;typedef typename RB::ConstIterator  const_iterator;map() {};~map() {};map(const map<K,V, KeyOfValue> & p) {map<K, V, KeyOfValue>::const_iterator it = p.begin();while (it != p.end()){insert(*it);++it;}};map<K, V, KeyOfValue>& operator=(const map<K, V, KeyOfValue>& p){clear();map<K, V, KeyOfValue>::const_iterator it = p.begin();while (it != p.end()){insert(*it);++it;}return *this;}//迭代器iterator begin(){return _rbmap.Begin();}iterator end(){return _rbmap.End();}const_iterator begin() const {return _rbmap.Begin();}const_iterator end()const {return _rbmap.End();}//插入pair<bool,iterator> insert(const pair<K, V>& val){return _rbmap.Insert(val);}//删除bool erase(const K& key){return _rbmap.Erase(key);}//查找iterator find(const K& key){return _rbmap.Find(key);}//重载[]V& operator[](const K& key){pair<bool, iterator> ret = insert(make_pair(key, V()));return ret.second->second;}//清空void  clear(){_rbmap.Clear();}private:RB _rbmap;
};