当前位置： 首页 > backend >正文

map和set的应用与模拟实现

backend 2025/7/23 12:23:12

map 和 set 是 C++ 标准库中常用的关联式容器，均基于红黑树（自平衡二叉搜索树）实现

set（集合）

  • 存储内容：仅存储单一键值（key），且键值唯一（不允许重复元素）。
  • 核心特性：元素会按照默认的升序（或自定义比较器指定的规则）自动排序；插入重复元素时会被忽略。
  • 主要用途：用于存储不重复的元素集合，适合需要快速查找、去重或有序遍历的场景（如统计唯一元素、检查元素是否存在等）。
  • 常用操作：insert()（插入）、erase()（删除）、find()（查找）、size()（元素数量）等。

map（映射）

  • 存储内容：存储键值对（key-value），其中 key 唯一（不能重复），value 为对应的数据。
  • 核心特性：按键（key）的默认升序（或自定义规则）排序；通过 key 可以快速访问对应的 value。
  • 主要用途：用于建立键与值的映射关系（如字典、索引表），适合需要通过唯一标识（key）查找关联数据（value）的场景（如存储学生 ID 与成绩的对应关系）。
  • 特殊操作：支持[]运算符（如map[key] = value），可直接通过 key 访问或插入 value；find()返回指向键值对的迭代器，通过->first获取 key，->second获取 value。

 红黑树的模拟实现

#ifndef RBTREE_H
#define RBTREE_H#include <iostream>
#include <cassert>// 红黑树节点颜色
enum Color { RED, BLACK };// 红黑树节点模板类
template <typename T>
struct RBTreeNode {T data;RBTreeNode* left;RBTreeNode* right;RBTreeNode* parent;Color color;// 构造函数RBTreeNode(const T& val) : data(val), left(nullptr), right(nullptr), parent(nullptr), color(RED) {}
};// 红黑树模板类
template <typename T, typename Compare = std::less<T>>
class RBTree {
protected:using Node = RBTreeNode<T>;Node* root;Compare comp;Node* nil;  // 哨兵节点，简化边界条件处理// 左旋操作void leftRotate(Node* x) {Node* y = x->right;x->right = y->left;if (y->left != nil) {y->left->parent = x;}y->parent = x->parent;if (x->parent == nil) {root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}y->left = x;x->parent = y;}// 右旋操作void rightRotate(Node* y) {Node* x = y->left;y->left = x->right;if (x->right != nil) {x->right->parent = y;}x->parent = y->parent;if (y->parent == nil) {root = x;} else if (y == y->parent->right) {y->parent->right = x;} else {y->parent->left = x;}x->right = y;y->parent = x;}// 插入后修复红黑树性质void insertFixup(Node* z) {while (z->parent->color == RED) {if (z->parent == z->parent->parent->left) {Node* y = z->parent->parent->right;  // 叔叔节点if (y->color == RED) {// 情况1：叔叔是红色z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else {if (z == z->parent->right) {// 情况2：叔叔是黑色，且z是右孩子z = z->parent;leftRotate(z);}// 情况3：叔叔是黑色，且z是左孩子z->parent->color = BLACK;z->parent->parent->color = RED;rightRotate(z->parent->parent);}} else {// 镜像情况：父节点是右孩子Node* y = z->parent->parent->left;  // 叔叔节点if (y->color == RED) {// 情况1：叔叔是红色z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else {if (z == z->parent->left) {// 情况2：叔叔是黑色，且z是左孩子z = z->parent;rightRotate(z);}// 情况3：叔叔是黑色，且z是右孩子z->parent->color = BLACK;z->parent->parent->color = RED;leftRotate(z->parent->parent);}}}root->color = BLACK;  // 根节点始终为黑色}// 查找最小值节点Node* minimum(Node* node) const {while (node->left != nil) {node = node->left;}return node;}// 查找最大值节点Node* maximum(Node* node) const {while (node->right != nil) {node = node->right;}return node;}// 查找后继节点Node* successor(Node* x) const {if (x->right != nil) {return minimum(x->right);}Node* y = x->parent;while (y != nil && x == y->right) {x = y;y = y->parent;}return y;}// 删除后修复红黑树性质void deleteFixup(Node* x) {while (x != root && x->color == BLACK) {if (x == x->parent->left) {Node* w = x->parent->right;  // 兄弟节点if (w->color == RED) {// 情况1：兄弟是红色w->color = BLACK;x->parent->color = RED;leftRotate(x->parent);w = x->parent->right;}if (w->left->color == BLACK && w->right->color == BLACK) {// 情况2：兄弟是黑色，且两个孩子都是黑色w->color = RED;x = x->parent;} else {if (w->right->color == BLACK) {// 情况3：兄弟是黑色，左孩子红色，右孩子黑色w->left->color = BLACK;w->color = RED;rightRotate(w);w = x->parent->right;}// 情况4：兄弟是黑色，右孩子红色w->color = x->parent->color;x->parent->color = BLACK;w->right->color = BLACK;leftRotate(x->parent);x = root;  // 退出循环}} else {// 镜像情况：x是右孩子Node* w = x->parent->left;  // 兄弟节点if (w->color == RED) {// 情况1：兄弟是红色w->color = BLACK;x->parent->color = RED;rightRotate(x->parent);w = x->parent->left;}if (w->right->color == BLACK && w->left->color == BLACK) {// 情况2：兄弟是黑色，且两个孩子都是黑色w->color = RED;x = x->parent;} else {if (w->left->color == BLACK) {// 情况3：兄弟是黑色，右孩子红色，左孩子黑色w->right->color = BLACK;w->color = RED;leftRotate(w);w = x->parent->left;}// 情况4：兄弟是黑色，左孩子红色w->color = x->parent->color;x->parent->color = BLACK;w->left->color = BLACK;rightRotate(x->parent);x = root;  // 退出循环}}}x->color = BLACK;}// 从节点z开始删除void transplant(Node* u, Node* v) {if (u->parent == nil) {root = v;} else if (u == u->parent->left) {u->parent->left = v;} else {u->parent->right = v;}v->parent = u->parent;}// 递归销毁树void destroy(Node* node) {if (node != nil) {destroy(node->left);destroy(node->right);delete node;}}// 复制树Node* copyTree(Node* node, Node* parentNode) {if (node == nil) return nil;Node* newNode = new Node(node->data);newNode->color = node->color;newNode->parent = parentNode;newNode->left = copyTree(node->left, newNode);newNode->right = copyTree(node->right, newNode);return newNode;}public:// 迭代器类class iterator {protected:Node* current;const RBTree* tree;friend class RBTree;public:using value_type = T;using reference = T&;using pointer = T*;using difference_type = std::ptrdiff_t;using iterator_category = std::bidirectional_iterator_tag;iterator(Node* node, const RBTree* t) : current(node), tree(t) {}reference operator*() const { return current->data; }pointer operator->() const { return &(current->data); }iterator& operator++() {current = tree->successor(current);return *this;}iterator operator++(int) {iterator temp = *this;++(*this);return temp;}bool operator==(const iterator& other) const {return current == other.current;}bool operator!=(const iterator& other) const {return !(*this == other);}};// 构造函数RBTree() {nil = new Node(T());nil->color = BLACK;nil->left = nil->right = nil->parent = nil;root = nil;}// 拷贝构造函数RBTree(const RBTree& other) {nil = new Node(T());nil->color = BLACK;nil->left = nil->right = nil->parent = nil;root = copyTree(other.root, nil);comp = other.comp;}// 赋值运算符RBTree& operator=(const RBTree& other) {if (this != &other) {destroy(root);root = copyTree(other.root, nil);comp = other.comp;}return *this;}// 析构函数~RBTree() {destroy(root);delete nil;}// 插入元素std::pair<iterator, bool> insert(const T& val) {Node* z = new Node(val);Node* y = nil;Node* x = root;// 查找插入位置while (x != nil) {y = x;if (comp(z->data, x->data)) {x = x->left;} else if (comp(x->data, z->data)) {x = x->right;} else {// 元素已存在，返回已存在的迭代器和falsedelete z;return {iterator(x, this), false};}}z->parent = y;if (y == nil) {root = z;  // 树为空，z成为根节点} else if (comp(z->data, y->data)) {y->left = z;} else {y->right = z;}z->left = nil;z->right = nil;z->color = RED;insertFixup(z);  // 修复红黑树性质return {iterator(z, this), true};}// 删除元素bool erase(const T& val) {Node* z = nil;Node* x = root;// 查找要删除的节点while (x != nil) {if (comp(val, x->data)) {x = x->left;} else if (comp(x->data, val)) {x = x->right;} else {z = x;break;}}if (z == nil) {return false;  // 元素不存在}Node* y = z;Node* x = nil;Color yOriginalColor = y->color;if (z->left == nil) {x = z->right;transplant(z, z->right);} else if (z->right == nil) {x = z->left;transplant(z, z->left);} else {y = minimum(z->right);yOriginalColor = y->color;x = y->right;if (y->parent == z) {x->parent = y;} else {transplant(y, y->right);y->right = z->right;y->right->parent = y;}transplant(z, y);y->left = z->left;y->left->parent = y;y->color = z->color;}delete z;if (yOriginalColor == BLACK) {deleteFixup(x);  // 修复红黑树性质}return true;}// 查找元素iterator find(const T& val) const {Node* x = root;while (x != nil) {if (comp(val, x->data)) {x = x->left;} else if (comp(x->data, val)) {x = x->right;} else {return iterator(x, this);  // 找到元素}}return end();  // 未找到元素}// 清空树void clear() {destroy(root);root = nil;}// 判断树是否为空bool empty() const {return root == nil;}// 迭代器起始位置iterator begin() const {if (empty()) return end();return iterator(minimum(root), this);}// 迭代器结束位置iterator end() const {return iterator(nil, this);}
};#endif // RBTREE_H

 set的模拟实现

#ifndef SET_H
#define SET_H#include "rbtree.h"// set模板类
template <typename Key, typename Compare = std::less<Key>>
class set {
public:using key_type = Key;using value_type = Key;using reference = value_type&;using const_reference = const value_type&;using size_type = size_t;using difference_type = std::ptrdiff_t;using compare = Compare;private:using Tree = RBTree<value_type, Compare>;Tree tree;public:// 迭代器类型using iterator = typename Tree::iterator;// 构造函数set() : tree() {}// 拷贝构造函数set(const set& other) : tree(other.tree) {}// 赋值运算符set& operator=(const set& other) {if (this != &other) {tree = other.tree;}return *this;}// 插入元素std::pair<iterator, bool> insert(const value_type& val) {return tree.insert(val);}// 删除元素bool erase(const value_type& val) {return tree.erase(val);}// 查找元素iterator find(const value_type& val) {return tree.find(val);}// 清空setvoid clear() {tree.clear();}// 判断set是否为空bool empty() const {return tree.empty();}// 迭代器起始位置iterator begin() {return tree.begin();}// 迭代器结束位置iterator end() {return tree.end();}
};#endif

 map的模拟实现

#ifndef MAP_H
#define MAP_H#include "rbtree.h"
#include <utility>// 用于map的键值对比较器
template <typename Key, typename T, typename Compare>
struct PairCompare {Compare comp;bool operator()(const std::pair<Key, T>& a, const std::pair<Key, T>& b) const {return comp(a.first, b.first);}
};// map模板类
template <typename Key, typename T, typename Compare = std::less<Key>>
class map {
public:using key_type = Key;using mapped_type = T;using value_type = std::pair<key_type, mapped_type>;using reference = value_type&;using const_reference = const value_type&;using size_type = size_t;using difference_type = std::ptrdiff_t;using compare = Compare;private:using Tree = RBTree<value_type, PairCompare<Key, T, Compare>>;Tree tree;public:// 迭代器类型using iterator = typename Tree::iterator;// 构造函数map() : tree() {}// 拷贝构造函数map(const map& other) : tree(other.tree) {}// 赋值运算符map& operator=(const map& other) {if (this != &other) {tree = other.tree;}return *this;}// 插入元素std::pair<iterator, bool> insert(const value_type& val) {return tree.insert(val);}// 删除元素bool erase(const key_type& key) {return tree.erase(value_type(key, mapped_type()));}// 查找元素iterator find(const key_type& key) {return tree.find(value_type(key, mapped_type()));}// 访问或插入元素mapped_type& operator[](const key_type& key) {std::pair<iterator, bool> result = tree.insert(value_type(key, mapped_type()));return result.first->second;}// 清空mapvoid clear() {tree.clear();}// 判断map是否为空bool empty() const {return tree.empty();}// 迭代器起始位置iterator begin() {return tree.begin();}// 迭代器结束位置iterator end() {return tree.end();}
};#endif

 

总的来说，set 专注于元素的唯一性和有序性

ma专注于通过键快速访问对应的值

两者均依赖红黑树实现，因此具备有序性和高效的平衡操作

 

http://www.xdnf.cn/news/16014.html

相关文章：

  • postgresql使用记录 SCRAM authentication requires libpq version 10 or above
  • 得物视觉算法面试30问全景精解
  • C++刷题常用方法
  • iOS组件化详解
  • 架构演进核心路线：从离线仓库到实时湖仓一体
  • 建造者设计模式
  • ArcGIS水文及空间分析与SWMM融合协同在城市排水防涝领域中的应用
  • web复习
  • Element Plus Table 组件扩展：表尾合计功能详解
  • 【后端】HMAC签名
  • 【React 入门系列】React 组件通讯与生命周期详解
  • 替代Oracle？金仓数据库用「敢替力」重新定义国产数据库
  • Node.js：Web模块、Express框架
  • [hot 100]两数之和-Python3-Hash Table
  • 蔚来汽车视觉算法面试30问全景精解
  • MySQL：内置函数
  • 实现分布式锁
  • numpy的详细知识点，简单易懂
  • Redis持久化-AOF
  • Oracle数据恢复—Oracle数据库所在分区被删除后报错的数据恢复案例
  • Spring Boot 使用Jasypt加密
  • 【bug】ubuntu20.04 orin nx Temporary failure resolving ‘ports.ubuntu.com‘
  • Debug 与 Release 版本构建详解
  • Unity里的加力
  • 0722 数据结构顺序表
  • Linux系统权限全面解析：掌握你的数字王国钥匙
  • docker pull 用法
  • PHP获取淘宝拍立淘（以图搜图）API接口操作详解
  • CSS+JavaScript 禁用浏览器复制功能的几种方法
  • 【前端】ikun-pptx编辑器前瞻问题二： pptx的压缩包结构，以及xml正文树及对应元素介绍