提供了键值对的存储机制,处理 具有唯一键的关联数据
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,内容在此基础上整理补充