从零开始手写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相同