从零开始手写STL库：multiset

从零开始手写STL库–multiset的实现

Gihub链接：miniSTL

---

---

一、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去记录，而不是真的插入多个相同元素