本文主要是介绍从零开始手写STL库:multiset,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
从零开始手写STL库–multiset的实现
Gihub链接:miniSTL
文章目录
- 从零开始手写STL库–multiset的实现
- 一、multiset是什么
- 二、multiset要包含什么函数
- 总结
一、multiset是什么
multiset 是一个有序容器,允许存储多个相同的元素,并按照元素的值进行排序,以红黑树为基础构建。
与set的区别在于,它允许储存重复的元素,而set的元素都是独一无二的。
但是红黑树里面是不允许重复元素的,那要怎么实现这个multiset呢?
实际上multiset并不会真的插入好几个一样的元素,没必要,而且会影响搜索
multiset的红黑树节点会额外的包含一个元素:count
用count的加减来表示元素是否重复,如果插入重复元素,那只需要对conut++即可
二、multiset要包含什么函数
依然是插入删除查找三个函数,不过插入和删除需要注意重复元素的判断
void insert(const Key &key) {auto count = rbTree.at(key);if (count != nullptr) {(*count)++;sz++;return;}rbTree.insert(key, 1);sz++;}void erase(const Key &key) {auto count = rbTree.at(key);if (count == nullptr) {return;}(*count)--;sz--;if (*count == 0) {rbTree.remove(key);}}
只有当节点不存在时才插入,只有当节点数只有一时才删除
其他功能就是正常的输出
template<typename Key>
class myMultiSet
{
private:myRedBlackTree<Key, size_t> rbtree;size_t sz;public:myMultiSet() : sz(0) {}~myMultiSet() {}void insert(const Key &key) {auto count = rbTree.at(key);if (count != nullptr) {(*count)++;sz++;return;}rbTree.insert(key, 1);sz++;}void erase(const Key &key) {auto count = rbTree.at(key);if (count == nullptr) {return;}(*count)--;sz--;if (*count == 0) {rbTree.remove(key);}}size_t size() const { return sz; }bool empty() const { return sz == 0; }size_t count(const Key &key) {auto num = rbTree.at(key);if (num != nullptr) {return *num;}return 0;}void clear() {sz = 0;rbTree.clear();}
};
总结
只需要注意重复元素的处理方式即可,也就是用另外的count去记录,而不是真的插入多个相同元素
这篇关于从零开始手写STL库:multiset的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!