简易STL实现 | Multimap 的实现

1、特性

键的多重性：与 std::map 不同，std::multimap 允许两个或多个元素 拥有相同的键。这使得 multimap 非常适合于 那些需要根据键 将多个值分组的场景

元素的有序性：std::multimap 中的元素 根据键 自动排序。默认情况下，它使用 std::less 来比较键，这意味着元素会按照键的升序排列。也可以 自定义比较函数，实现不同的排序逻辑

基于红黑树的实现：大多数 STL 实现 使用平衡二叉搜索树（如红黑树）来实现 multimap，这确保了 即使在最坏的情况下，大部分操作（如插入、查找和删除）的时间复杂度 也是对数的

不支持 直接修改键：由于 multimap 中的元素是 根据键排序的，直接修改键 可能会破坏容器的内部顺序。如果 需要修改键，通常的做法是 删除旧元素 并插入一个新元素

2、性能

由于 允许键重复，即使 插入具有相同键的元素，性能也不会受到影响

如果 有多个元素具有相同的键，STL提供了 equal_range 函数

如果 需要删除 所有具有特定键的元素，时间复杂度 仍然保持在对数级别，但实际的操作次数 将增加

3、标准库中的基本用法

#include <map> // For std::multimap// 创建一个 multimap，键和值的类型都是 intstd::multimap<int, std::string> mm;// 插入元素，multimap 允许键重复mm.insert(std::make_pair(1, "Apple"));mm.insert(std::make_pair(1, "Avocado"));// 遍历 multimap 中的所有元素// 运行结果// 1 => Apple// 1 => Avocadostd::cout << "Multimap elements:" << std::endl;for (const auto& element : mm) {std::cout << element.first << " => " << element.second << std::endl;}// 查找键为 1 的所有元素auto range = mm.equal_range(1); // 获取一个范围，包含所有键为 1 的元素for (auto it = range.first; it != range.second; ++it) {std::cout << it->first << " => " << it->second << std::endl;}// 删除键为 2 的所有元素（所有）mm.erase(2);

4、实现

之前实现的红黑树 不支持重复的键值对， 因此 红黑树模板参数中的 Value 使用 Vector 来存储多个 Value

#include <iostream>
#include <sstream>
#include <string>
#include <cstddef>
#include <list>enum class Color { RED, BLACK };template <typename Key, typename Value> class RedBlackTree {class Node {public:Key key;Value value;Color color;Node* left;Node* right;Node* parent;// 构造函数Node(const Key& k, const Value& v, Color c, Node* p = nullptr): key(k), value(v), color(c), left(nullptr), right(nullptr), parent(p) {}Node(): color(Color::BLACK), left(nullptr), right(nullptr), parent(nullptr) {}};private:Node* root;size_t size;Node* Nil;// 查询某节点Node* lookUp(Key key) {Node* cmpNode = root;while (cmpNode) {if (key < cmpNode->key) {cmpNode = cmpNode->left;}else if (key > cmpNode->key) {cmpNode = cmpNode->right;}else {return cmpNode;}}return cmpNode;}// 右旋函数void rightRotate(Node* node) {Node* l_son = node->left; // 获取当前节点的左子节点// 当前节点的左子树变成左子节点的右子树node->left = l_son->right;// 如果左子节点的右子树非空，更新其父指针if (l_son->right) {l_son->right->parent = node;}// 左子节点升为当前节点位置，并处理父节点关系l_son->parent = node->parent;// 如果当前节点是根节点，更新根节点为左子节点if (!node->parent) {root = l_son;// 如果当前节点是其父节点的左子节点，更新父节点的左子节点为左子节点}else if (node == node->parent->left) {node->parent->left = l_son;// 如果当前节点是其父节点的右子节点，更新父节点的右子节点为左子节点}else {node->parent->right = l_son;}// 完成右旋转，将当前节点成为左子节点的右子节点l_son->right = node;// 更新当前节点的父节点为左子节点node->parent = l_son;}// 左旋// 是右旋的对称情况, 逻辑和右旋是一样的void leftRotate(Node* node) {Node* r_son = node->right;node->right = r_son->left;if (r_son->left) {r_son->left->parent = node;}r_son->parent = node->parent;if (!node->parent) {root = r_son;}else if (node == node->parent->left) {node->parent->left = r_son;}else {node->parent->right = r_son;}r_son->left = node;node->parent = r_son;}// 插入修复函数void insertFixup(Node* target) {// 当目标节点的父节点存在且父节点的颜色是红色时，需要修复while (target->parent && target->parent->color == Color::RED) {// 当目标节点的父节点是祖父节点的左子节点时if (target->parent == target->parent->parent->left) {Node* uncle = target->parent->parent->right; // 叔叔节点// 如果叔叔节点存在且为红色，进行颜色调整if (uncle && uncle->color == Color::RED) {target->parent->color = Color::BLACK; // 父节点设为黑色uncle->color = Color::BLACK;          // 叔叔节点设为黑色target->parent->parent->color = Color::RED; // 祖父节点设为红色target = target->parent->parent; // 将祖父节点设为下一个目标节点}else {// 如果目标节点是父节点的右子节点，进行左旋转if (target == target->parent->right) {target = target->parent; // 更新目标节点为父节点leftRotate(target);      // 对目标节点进行左旋}// 调整父节点和祖父节点的颜色，并进行右旋转target->parent->color = Color::BLACK;target->parent->parent->color = Color::RED;rightRotate(target->parent->parent);}}else {// 当目标节点的父节点是祖父节点的右子节点时，与上面对称Node* uncle = target->parent->parent->left; // 叔叔节点if (uncle && uncle->color == Color::RED) {target->parent->color = Color::BLACK;uncle->color = Color::BLACK;target->parent->parent->color = Color::RED;target = target->parent->parent;}else {if (target == target->parent->left) {target = target->parent; // 更新目标节点为父节点rightRotate(target);     // 对目标节点进行右旋}// 调整父节点和祖父节点的颜色，并进行左旋转target->parent->color = Color::BLACK;target->parent->parent->color = Color::RED;leftRotate(target->parent->parent);}}}// 确保根节点始终为黑色root->color = Color::BLACK;}// 插入节点函数void insertNode(const Key& key, const Value& value) {// 创建一个新节点，节点的颜色初始化为红色Node* newNode = new Node(key, value, Color::RED);Node* parent = nullptr; // 新节点的父节点指针Node* cmpNode = root;   // 用于比较的节点，初始为根节点// 遍历树，找到新节点的正确位置while (cmpNode) {parent = cmpNode; // 保留当前节点作为新节点的潜在父节点// 如果新节点的键小于当前比较节点的键，则向左子树移动if (newNode->key < cmpNode->key) {cmpNode = cmpNode->left;// 如果新节点的键大于当前比较节点的键，则向右子树移动}else if (newNode->key > cmpNode->key) {cmpNode = cmpNode->right;// 如果键相等，则说明树中已有相同键的节点，删除新节点并返回}else {delete newNode;return;}}// 树的大小增加size++;// 将新节点的父节点设置为找到的父节点位置newNode->parent = parent;// 如果父节点为空，说明树是空的，新节点成为根节点if (!parent) {root = newNode;// 如果新节点的键小于父节点的键，将新节点插入父节点的左子树}else if (newNode->key < parent->key) {parent->left = newNode;// 否则，将新节点插入父节点的右子树}else {parent->right = newNode;}// 插入新节点后，调用insertFixup函数来修复可能破坏的红黑树性质insertFixup(newNode);}// 中序遍历void inorderTraversal(Node* node) const {if (node) {inorderTraversal(node->left);std::cout << node->key << " ";std::cout << node->value << " ";inorderTraversal(node->right);}}// 辅助函数，用新节点替换旧节点void replaceNode(Node* targetNode, Node* newNode) {if (!targetNode->parent) {root = newNode;}else if (targetNode == targetNode->parent->left) {targetNode->parent->left = newNode;}else {targetNode->parent->right = newNode;}if (newNode) {newNode->parent = targetNode->parent;}}// 寻找以某个节点为根节点的子树中的最小节点Node* findMinimumNode(Node* node) {while (node->left) {node = node->left;}return node;}// removeFixup函数用于在删除节点后恢复红黑树的性质void removeFixup(Node* node) {// 如果节点为Nil并且没有父节点，说明它是唯一的节点，直接返回if (node == Nil && node->parent == nullptr) {return;}// 当我们没有到达根节点时继续循环while (node != root) {// 如果节点是其父节点的左子节点if (node == node->parent->left) {// 兄弟节点是节点父亲的右子节点Node* sibling = node->parent->right;// 情况1：节点的兄弟节点是红色if (getColor(sibling) == Color::RED) {// 重新着色兄弟节点和父节点，并进行左旋setColor(sibling, Color::BLACK);setColor(node->parent, Color::RED);leftRotate(node->parent);// 旋转后更新兄弟节点sibling = node->parent->right;}// 情况2：兄弟节点的两个子节点都是黑色if (getColor(sibling->left) == Color::BLACK &&getColor(sibling->right) == Color::BLACK) {// 重新着色兄弟节点并向上移动setColor(sibling, Color::RED);node = node->parent;// 如果父节点是红色，将其改为黑色并结束if (node->color == Color::RED) {node->color = Color::BLACK;node = root;}}else {// 情况3：兄弟节点的右子节点是黑色（左子节点是红色）if (getColor(sibling->right) == Color::BLACK) {// 重新着色兄弟节点和兄弟节点的左子节点，并进行右旋setColor(sibling->left, Color::BLACK);setColor(sibling, Color::RED);rightRotate(sibling);// 旋转后更新兄弟节点sibling = node->parent->right;}// 情况4：兄弟节点的右子节点是红色setColor(sibling, getColor(node->parent));setColor(node->parent, Color::BLACK);setColor(sibling->right, Color::BLACK);leftRotate(node->parent);// 移动到根节点结束node = root;}}else {// 当节点是其父节点的右子节点时，对称的情况Node* sibling = node->parent->left;if (getColor(sibling) == Color::RED) {setColor(sibling, Color::BLACK);setColor(node->parent, Color::RED);rightRotate(node->parent);sibling = node->parent->left;}if (getColor(sibling->right) == Color::BLACK &&getColor(sibling->left) == Color::BLACK) {setColor(sibling, Color::RED);node = node->parent;if (node->color == Color::RED) {node->color = Color::BLACK;node = root;}}else {if (getColor(sibling->left) == Color::BLACK) {setColor(sibling->right, Color::BLACK);setColor(sibling, Color::RED);leftRotate(sibling);sibling = node->parent->left;}setColor(sibling, getColor(node->parent));setColor(node->parent, Color::BLACK);setColor(sibling->left, Color::BLACK);rightRotate(node->parent);node = root;}}}// 确保当前节点是黑色的，以维持红黑树性质setColor(node, Color::BLACK);}// 获取颜色, 空指针为黑色Color getColor(Node* node) {if (node == nullptr) {return Color::BLACK;}return node->color;}void setColor(Node* node, Color color) {if (node == nullptr) {return;}node->color = color;}// 取消Nil哨兵的连接void dieConnectNil() {if (Nil == nullptr) {return;}if (Nil->parent != nullptr) {if (Nil == Nil->parent->left) {Nil->parent->left = nullptr;}else {Nil->parent->right = nullptr;}}}// 删除节点void deleteNode(Node* del) {Node* rep = del; // rep（替代节点）初始指向要删除的节点Node* child = nullptr;      // 要删除节点的孩子节点Node* parentRP;             // 替代节点的父节点Color origCol = rep->color; // 保存要删除节点的原始颜色// 如果删除节点没有左孩子if (!del->left) {rep = del->right;        // 替代节点指向删除节点的右孩子parentRP = del->parent;  // 更新替代节点的父节点origCol = getColor(rep); // 获取替代节点的颜色replaceNode(del, rep);   // 用替代节点替换删除节点}// 如果删除节点没有右孩子else if (!del->right) {rep = del->left;         // 替代节点指向删除节点的左孩子parentRP = del->parent;  // 更新替代节点的父节点origCol = getColor(rep); // 获取替代节点的颜色replaceNode(del, rep);   // 用替代节点替换删除节点}// 如果删除节点有两个孩子else {rep = findMinimumNode(del->right); // 找到删除节点右子树中的最小节点作为替代节点origCol = rep->color; // 保存替代节点的原始颜色// 如果替代节点不是删除节点的直接右孩子if (rep != del->right) {parentRP = rep->parent; // 更新替代节点的父节点child = rep->right; // 替代节点的右孩子变成要处理的孩子节点parentRP->left =child; // 替代节点的父节点的左孩子指向替代节点的孩子（因为替代节点是最小节点，所以不可能有左孩子）if (child != nullptr) {child->parent = parentRP; // 如果替代节点的孩子存在，则更新其父节点}// 将替代节点放到删除节点的位置del->left->parent = rep;del->right->parent = rep;rep->left = del->left;rep->right = del->right;// 如果删除节点有父节点，更新父节点的孩子指向if (del->parent != nullptr) {if (del == del->parent->left) {del->parent->left = rep;rep->parent = del->parent;}else {del->parent->right = rep;rep->parent = del->parent;}}// 如果删除节点没有父节点，说明它是根节点else {root = rep;root->parent = nullptr;}}// 如果替代节点是删除节点的直接右孩子else {child = rep->right; // 孩子节点指向替代节点的右孩子rep->left = del->left; // 替代节点的左孩子指向删除节点的左孩子del->left->parent = rep; // 更新左孩子的父节点// 更新删除节点父节点的孩子指向if (del->parent != nullptr) {if (del == del->parent->left) {del->parent->left = rep;rep->parent = del->parent;}else {del->parent->right = rep;rep->parent = del->parent;}}// 如果删除节点是根节点else {root = rep;root->parent = nullptr;}parentRP = rep; // 更新替代节点的父节点}}// 如果替代节点存在，更新其颜色为删除节点的颜色if (rep != nullptr) {rep->color = del->color;}// 如果替代节点不存在，将删除节点的颜色赋给origCol变量else {origCol = del->color;}// 如果原始颜色是黑色，需要进行额外的修复操作，因为黑色节点的删除可能会破坏红黑树的性质if (origCol == Color::BLACK) {// 如果存在孩子节点，进行修复操作if (child != nullptr) {removeFixup(child);}// 如果不存在孩子节点，将Nil节点（代表空节点）的父节点设置为替代节点的父节点else {Nil->parent = parentRP;// 如果替代节点的父节点存在，设置其对应的孩子指针为Nil节点if (parentRP != nullptr) {if (parentRP->left == nullptr) {parentRP->left = Nil;}else {parentRP->right = Nil;}}// 进行修复操作removeFixup(Nil);// 断开Nil节点与树的连接，因为在红黑树中Nil节点通常是单独存在的dieConnectNil();}}// 删除节点delete del;}public:// 构造函数RedBlackTree() : root(nullptr), size(0), Nil(new Node()) {Nil->color = Color::BLACK;}// 插入void insert(const Key& key, const Value& value) { insertNode(key, value); }// 删除void remove(const Key& key) {Node* nodeToBeRemoved = lookUp(key);if (nodeToBeRemoved != nullptr) {deleteNode(nodeToBeRemoved);size--;}}Value* at(const Key& key) {auto ans = lookUp(key);if (ans != nullptr) {return &ans->value;}return nullptr;}int getSize() { return size; }bool empty() { return size == 0; }// 中序遍历打印void print() {inorderTraversal(root);std::cout << std::endl;}void clear() {deleteNode(root);size = 0;}// 析构函数~RedBlackTree() {// 释放节点内存deleteTree(root);}private:// 递归释放节点内存void deleteTree(Node* node) {if (node) {deleteTree(node->left);deleteTree(node->right);delete node;}}
};

// MultiMap 实现
template<typename Key, typename Value> class MultiMap {
public:using ValueType = std::list<Value>; // 必须在使用前声明
private:RedBlackTree<Key, ValueType> rbTree;size_t size;
public:MultiMap() : rbTree(), size(0) {} // 所有变量都要初始化，包括 size~MultiMap() {}void insert(const Key& key, const Value& value) {ValueType* pos = rbTree.at(key);if (pos == nullptr) {ValueType ValueList;ValueList.push_back(value);rbTree.insert(key, ValueList);}else {pos->push_back(value);}size++;}// 注意两个remove不同，一个是删除键值，一个是删除一个结点void remove(const Key& key, const Value& value) {ValueType* pos = rbTree.at(key);if (pos != nullptr) {pos->remove(value); // 只能删除 valueif (pos->size() == 0)rbTree.remove(key);size--;}}void remove(const Key& key) {ValueType* pos = rbTree.at(key);if (pos != nullptr) {size -= pos->size();rbTree.remove(key);}}ValueType* at(const Key& key) {return rbTree.at(key);}int getSize() {return size; // 因为跟哈希表中的数目不同了，所以 要重新整一个值记录大小}bool empty() {return rbTree.empty();}
};int main() {MultiMap<int, int> myMultiMap;int N;std::cin >> N;getchar();std::string line;for (int i = 0; i < N; i++) {std::getline(std::cin, line);std::istringstream iss(line);std::string command;iss >> command;int key;int value;if (command == "insert") {iss >> key >> value;myMultiMap.insert(key, value);}if (command == "remove") {iss >> key >> value;myMultiMap.remove(key, value);}if (command == "remove_all") {iss >> key;myMultiMap.remove(key);}if (command == "size") {std::cout << myMultiMap.getSize() << std::endl;}if (command == "empty") {std::cout << (myMultiMap.empty() ? "true" : "false") << std::endl;}if (command == "at") {iss >> key;auto valueList = myMultiMap.at(key);if (valueList) {for (auto value : *valueList) {std::cout << value << " ";}std::cout << std::endl;}else {std::cout << "not exist" << std::endl;}}}return 0;
}

1）using ValueType = std::list<Value>; 必须在使用前声明
类型别名（如 typedef 或 using）必须在使用前进行声明，以便编译器知道它们的含义
如果在使用 ValueType 之前没有声明它，编译器在解析 RedBlackTree<Key, ValueType> rbTree; 时就无法识别 ValueType，从而导致编译错误

作用域：using 定义的类型别名 在其声明的作用域内有效。在类中，修饰符 决定了 外部代码能否访问该 using 声明的类型或别名。因此，必须在使用之前声明
public：using 声明的别名或类型在 public 作用域时，对外部代码可见，外部可以直接使用它
private：using 声明的别名或类型在 private 作用域时，对外部代码不可见，只有类内部和友元可以访问它
protected：using 声明的别名或类型在 protected 作用域时，对派生类可见，但对外部代码不可见

2）默认初始化：在 C++ 中，类的成员变量 如果不在构造函数的初始化列表中 显式初始化，或者 不在声明时 初始化，那么：
对于内置类型（如 int、size_t 等），它们的值将是未定义的（未初始化的）
对于类类型（如 std::string、自定义类等），它们将调用默认构造函数进行初始化

初始化列表的优先级：在 C++ 中，构造函数的初始化列表 比构造函数体内的初始化 具有更高的效率和优先级（如果构造函数的初始化列表中 对某个成员变量进行了赋值，它会覆盖声明时的初始化值）。对于内置类型，初始化列表 和 在构造函数体内赋值 没有本质区别，但对于

类类型，使用初始化列表 可以直接调用合适的构造函数，避免不必要的默认构造和赋值操作：
如果 不使用初始化列表，成员变量 会先调用默认构造函数进行初始化，然后在 构造函数体内再次赋值，这会导致 多一次的对象构造操作（即先构造后赋值），从而 影响性能

使用初始化列表的情况：

class Person {
private:std::string name;public:// 构造函数使用初始化列表Person(const std::string& name) : name(name) {// 在这里，成员变量 name 是通过初始化列表直接初始化的std::cout << "Person constructed with name: " << this->name << std::endl;}
};

name 只调用一次 std::string 的复制构造函数，避免了 多余的构造和赋值

不使用初始化列表的情况：

class Person {
private:std::string name;public:// 构造函数没有使用初始化列表Person(const std::string& name) {// 先默认构造 name，然后在构造函数体内赋值this->name = name;std::cout << "Person constructed with name: " << this->name << std::endl;}
};

首先，成员变量 name 会在进入构造函数体之前，通过 std::string 的默认构造函数 进行初始化
然后，在构造函数体内，通过赋值运算符 将参数 name 的值复制给成员变量 name，这相当于 调用一次 std::string 的赋值运算符

5、常见面试题

1、在 multimap 中搜索一个特定键对应的所有值
使用 equal_range 方法获得一个迭代器对，它包含 指向给定键的第一个元素 和 超过最后一个元素的迭代器。然后，可以遍历这个范围 来访问所有对应的值

2、如何从 multimap 中删除一个特定的键值对
要从 multimap 中 删除一个特定的键值对，需要遍历 与该键关联的所有元素，并比较值。当找到 匹配的键值对时，使用迭代器指向的元素 调用 erase 方法来删除它

std::multimap<int, std::string> mm;mm.insert({1, "apple"});mm.insert({1, "banana"});mm.insert({1, "cherry"});mm.insert({2, "date"});mm.insert({2, "fig"});mm.insert({3, "grape"});// 要删除的键值对int keyToRemove = 1;std::string valueToRemove = "banana";// 找到与 keyToRemove 相关的所有元素的范围auto range = mm.equal_range(keyToRemove);// 遍历与该键关联的所有元素，查找特定的值for (auto it = range.first; it != range.second; ++it) {if (it->second == valueToRemove) {// 找到匹配的键值对后，使用迭代器调用 erase 删除mm.erase(it);break;  // 因为 multimap 允许重复键，找到并删除一个后可以退出循环}}

https://kamacoder.com/ 手写简单版本STL，内容在此基础上整理补充