简易STL实现 | Map 的实现

提供了键值对的存储机制，处理 具有唯一键的关联数据

1、特性

键值对存储：std::map 通过键值对的形式 存储数据，其中每个键 都是唯一的，并且 与一个值相关联

自动排序：std::map 内部 使用一种平衡二叉搜索树（通常是红黑树）来存储元素，这使得元素根据键自动排序

元素唯一性：在 std::map 中，键必须是唯一的。如果尝试 插入一个已存在的键，插入操作将失败

直接访问：可以使用键 直接访问 std::map 中的元素，这提供了 高效的查找能力
灵活的元素操作：std::map 提供了 丰富的元素操作，包括 插入、删除、查找等

2、性能

插入操作：插入操作的时间复杂度为 O(log n)，其中 n 是 std::map 中元素的数量。这是因为需要在平衡二叉树中 找到合适的位置来插入新元素
查找操作：查找操作的时间复杂度 也是 O(log n)，由于 std::map 的有序性，可以快速定位到任何键
删除操作：删除操作的时间复杂度同样为 O(log n)，需要找到要删除的元素 并在保持树平衡的同时移除它
遍历操作：遍历 std::map 的时间复杂度为 O(n)，因为 需要访问容器中的每个元素

3、标准库中基本用法

// 创建一个map，键和值都是int类型std::map<int, int> myMap;// 插入元素myMap.insert({1,100});myMap[2] = 200; // 使用下标操作符直接插入或修改// 迭代遍历for (const auto& pair : myMap) {std::cout << pair.first << " => " << pair.second << std::endl;}// 查找元素auto search = myMap.find(2); // 查找键为2的元素if (search != myMap.end()) {std::cout << "Found element with key 2: " << search->second << std::endl;} else {std::cout << "Element with key 2 not found." << std::endl;}myMap.erase(2); // 删除键为2的元素

4、实现

#include <iostream>
#include <sstream>
#include <string>
#include <iostream>
#include <utility> // For std::pairenum 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;}}
};

// 此处开始为 map 的实现
template <typename Key, typename Value> class Map {
public:Map() : rbTree() {}// 操作都是针对键值（key）void insert(const Key& key, const Value& value) {rbTree.insert(key, value);}void erase(const Key& key) {rbTree.remove(key);}size_t size() {return rbTree.getSize();}bool empty() {return rbTree.empty();}bool contains(const Key& key) {return rbTree.at(key) != nullptr;}// at没找到抛出错误Value &at(const Key &key) {Value *foundVal = rbTree.at(key);if (foundVal) {return *foundVal;}else {throw std::out_of_range("Key not found");}}// []没找到直接插入，并返回新插入的值的引用（具体值不确定）Value &operator[](const Key& key) {Value *foundVal = rbTree.at(key);if (foundVal) {return *foundVal;}else {Value tmp;rbTree.insert(key, tmp);return tmp;}}
private:RedBlackTree<Key, Value> rbTree;
};int main() {Map<int, int> myMap;int N;std::cin >> N;getchar();while (N--) {std::string line;std::getline(std::cin, line);std::istringstream iss(line);std::string command;iss >> command;int key;int value;if (command == "insert") {iss >> key >> value; // 可以连着写myMap.insert(key, value);}else if (command == "erase") {iss >> key;myMap.erase(key);}else if (command == "empty") {bool b = myMap.empty();if (b == true) {std::cout << "true" << std::endl;}else {std::cout << "false" << std::endl;}}else if (command == "size") {std::cout << myMap.size() << std::endl;}else if (command == "at") {// 对于抛出标准错误的处理iss >> key;try {std::cout << myMap.at(key) << std::endl;} catch(const std::out_of_range& e) {std::cout << "not exist" << std::endl;}}else if (command == "contains") {iss >> key;bool b = myMap.contains(key);if (b == true) {std::cout << "true" << std::endl;}else {std::cout << "false" << std::endl;}}}return 0;
}

1、返回值设为 Value& 是为了避免不必要的值拷贝，同时确保返回的是引用，而不是副本 原因

Value &operator[](const Key& key)

1）避免值拷贝：如果返回类型是 Value 而不是 Value&，那么在返回时 会产生一次值的拷贝，而这可能会 导致性能上的开销，尤其当 Value 类型是一个较大的对象时。通过返回引用，函数可以直接 返回原来的对象，避免了拷贝操作

2）允许对返回的值 进行修改：如果函数返回 Value&，那么调用者可以 对返回的对象进行修改，而不会影响到 其它地方的代码。特别是 如果 希望通过下标操作符修改 rbTree 中的值（比如 obj[key] = newValue），需要返回对值的引用

当 operator[] 返回引用时，任何对返回值的修改都会立即反映在容器中

obj[key] = newValue;
等同于：
Value& ref = obj[key];  // 获取引用
ref = newValue;         // 通过引用修改实际存储的值

如果 operator[] 只返回值的副本，修改不会持久保存，因为只是副本被修改，原始的值保持不变

如果 newKey 在 rbTree 中不存在，operator[] 会 先创建并插入一个默认构造的 Value，然后通过 返回对该 Value 的引用，将其修改为 newValue（完整的修改 是两个步骤）。这种行为 依赖于 引用返回，使得在没有键时 自动插入新元素成为可能，并且 可以立即修改这个新元素

3）保持一致性：既然这个函数是 一个类似于 字典或映射的 operator[]，在标准容器（如 std::map）的 operator[] 也会返回一个引用。因此，使用引用作为返回类型 符合这种操作符的常见行为，并确保 该操作符合预期：访问或修改键所对应的值

2、写 iss >> key >> value; 这样的代码时，操作的顺序如下：
第一步，执行 iss >> key;：从 iss 流中提取数据并存储到 key 中，操作结束后返回 iss 本身的引用
第二步，由于 iss >> key 返回 iss 的引用，因此接着 可以对 iss 再执行 >> value，这时会从流中 提取下一个数据并存储到 value 中

3、和 C++ 标准库中的 std::map 的区别：
1）功能完备性：
上述代码 仅实现了基本的插入、查找和删除功能，并未考虑 std::map 中的所有功能，如迭代器、比较器、异常安全性等。 std::map 还提供了一系列其他功能，例如 lower_bound、upper_bound、equal_range 等

lower_bound 返回的是 一个指向第一个 不小于 给定键的元素的迭代器

upper_bound 返回的是 一个指向第一个 大于 给定键的元素的迭代器

equal_range 返回一个 std::pair，包含两个迭代器，分别表示 lower_bound 和 upper_bound 的结果
equal_range(2) 返回了 std::multimap 中所有键为 2 的元素的范围，遍历这个范围 就能访问所有与键 2 相关的值

#include <iostream>
#include <map>int main() {std::multimap<int, std::string> mmap = {{1, "one"}, {2, "two"}, {2, "deux"}, {3, "three"}};// 查找 key 为 2 的所有元素auto range = mmap.equal_range(2);for (auto it = range.first; it != range.second; ++it) {std::cout << it->first << ": " << it->second << std::endl;}return 0;
}

输出：

2: two
2: deux

2、性能和优化：
如 节点分配 和 管理的内存池、迭代器优化等。

3、异常安全性

4、模板元编程和元编程技巧：
使用了复杂的 模板元编程 技巧，以 支持通用性、泛型编程和性能优化

5、常见面试题

1、std::map和std::unordered_map有什么区别
内部实现：std::map 内部 基于红黑树实现，因此它的元素是 自动排序的。而 std::unordered_map 基于哈希表实现，元素是无序的
性能：对于 std::map，查找、插入和删除操作的时间复杂度 通常是 O(log n)。对于 std::unordered_map，这些操作的平均时间复杂度是 O(1)，但最坏情况下是 O(n)
内存消耗：由于哈希表的开销，std::unordered_map 可能会比 std::map 消耗更多内存
元素排序：std::map 中的元素 按照键自动排序，而 std::unordered_map 中的元素没有特定的顺序

2、std::map 的迭代器失效的情况有哪些
删除当前迭代器指向的元素 会使该迭代器失效，但其他迭代器 仍然有效
插入操作 不会使现有迭代器失效
std::map 的迭代器是 双向迭代器，对树的结构修改（如插入或删除）不会影响其他迭代器，除了 指向被删除元素的迭代器

std::map 的迭代器是 双向迭代器，这意味着它允许：
前向遍历：使用 ++it 可以向前移动迭代器
后向遍历：使用 --it 可以向后移动迭代器
双向迭代器 不像 随机访问迭代器（例如 std::vector 的迭代器那样支持 it + n 等操作），但它能灵活地 在有序数据结构（如 std::map）中来回移动

当 插入或删除元素时，树可能会 做出一定的自我平衡调整（例如旋转、重染色等操作），以保持树的平衡。但尽管 底层树结构可能发生变化，除了 指向被删除元素的迭代器以外，其他迭代器 不会失效

std::map<int, std::string> myMap = {{1, "one"}, {3, "three"}, {4, "four"}};
auto it = myMap.find(3);  // 找到key为3的迭代器
myMap.erase(1);  // 删除key为1的元素// 删除key为1的元素后，原来指向key为3的迭代器仍然有效
std::cout << it->first << ": " << it->second << std::endl;  // 输出 3: threemyMap.erase(3);  // 删除key为3的元素
// 现在，指向key为3的迭代器失效，访问它会导致未定义行为

3、如果 std::map 的键类型是 自定义类型，需要怎么做
如果键类型是 自定义类型，则需要 定义比较函数 或 重载 < 运算符，以便 std::map 能够对键进行排序。可以通过 在自定义类型中 重载 < 运算符 或 提供自定义比较函数 作为 std::map 的第三个模板参数来实现

struct MyKey {int key;bool operator<(const MyKey& other) const {return key < other.key;}
};
std::map<MyKey, int> myMap;

或者：

struct MyCompare {bool operator()(const MyKey& lhs, const MyKey& rhs) const {return lhs.key < rhs.key;}
};
std::map<MyKey, int, MyCompare> myMap;

4、解释 std::map::emplace 和 std::map::insert 的区别
emplace 方法会在 map 中直接构造元素，避免了 额外的复制或移动操作。它接受构造元素所需的参数，并且尝试在容器中构造元素
insert 方法 用于将已经构造好的元素 插入到 map 中。如果提供了键值对，insert 可能会导致 一次或两次额外的复制 或 移动构造，首先是 创建临时键值对对象，然后是 将其复制或移动之后 插入到容器中

emplace更高效，因为它直接在容器内部构造元素，减少了 不必要的复制或移动操作。然而，选择使用 emplace 还是 insert 取决于具体情况，有时 为了代码的清晰可读，使用 insert 可能更合适

使用 emplace 时，容器内部会根据提供的参数，直接在容器中构造对象；insert 方法通常需要一个已经构造好的对象，将其复制或移动到容器中

myMap.insert(std::make_pair(1, "one"));
// 首先创建一个临时的 std::pair<int, std::string> 对象，然后 insert 会将该对象复制后插入到 map 中。这种方式涉及到一次额外的构造和复制（或移动）
myMap.emplace(1, "one");

std::map 和 std::unordered_map 中的 insert 函数 不会替换已经存在的键值对。换句话说，当 试图插入一个键已经存在的元素时，insert 不会插入新的值或替换已有的值，而是保持已有的元素不变，和 emplace 一样

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