从零开始手写STL库：multimap

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

Gihub链接：miniSTL

一、multimap是什么？

如图multiset之于set，multimap相当于允许map重复储存键值

所以这里也是增加一个count来计数吗？这里是不可以的

multiset用count是因为key和value相同，而map的key和value是不同的

如果也用count来计数，那么考虑<1,2>和<1,5>的插入，由于key相同，所以后插入的会丢失，这显然不对

所以这里的想法是把红黑树的节点做成list，把所有key相同的值放在一个list中

二、multimap要包含什么函数

明确了设计思路，实际上就是红黑树的一层封装了

如下：

template <typename Key, typename Value> class MultiMap
{
public:
    using ValueType = std::list<Value>; 

    MultiMap() : rbTree(), size(0) {}

    void insert(const Key &key, const Value &value) 
    {
        ValueType *existingValues = rbTree.at(key);
        if (existingValues) existingValues->push_back(value);
        else 
        {
            ValueType values;
            values.push_back(value);
            rbTree.insert(key, values);
        }
        size++;
    }

    void remove(const Key &key) 
    {
        ValueType *existingValues = rbTree.at(key);
        if (existingValues) 
        {
            size -= existingValues->size();
            rbTree.remove(key);
        }
    }

    void remove(const Key &key, const Value &value) 
    {
        ValueType *existingValues = rbTree.at(key);
        if (existingValues) 
        {
            existingValues->remove(value);
            size--;
            if (existingValues->empty()) rbTree.remove(key);
        }
    }

    ValueType *at(const Key &key) { return rbTree.at(key); }

    int getSize() { return size; }

    bool empty() { return size == 0; }

private:
    myRedBlackTree<Key, ValueType> rbTree; 
    size_t size;
};

总结

了解list作为节点代替红黑树常用节点即可，这是multimap实现的基本原理，其他考察点与map相同