STL11——手写一个简单版本的multimap（包含multimap的特点及基本用法）、set家族与map家族的对比（思维导图）

1.特点

• 存储键值对

• 键的多重性：与std::map不同，std::multimap允许两个或多个元素拥有相同的键

• 有序性：元素根据键自动升序排列。注意，multimap只对key排序了，但value还是插入的顺序

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

• 基于红黑树

2.基本用法

• 使用场景：将多个值分组到一个键中

• 头文件和定义

  #include <map> multimap<int, string> mm;

• 插入元素

  mm.insert( make_pair( 1，“apple” ））

  mm.insert(make_pair(1, "Apple"));mm.insert(make_pair(1, "Avocado"));mm.insert(make_pair(2, "Banana"));

• 查找元素

  equal_range(键)：一种二分查找算法，返回两个迭代器first和second，分别指向第一个和最后一个元素

  auto range = mm.equal_range(1); // 获取一个范围，包含所有键为 1 的元素for (auto it = range.first; it != range.second; ++it) {cout << it->first << " => " << it->second << sendl;}

另外，-> 前是指针，而 . 前是结构体变量，且 a->b等同于**(a) . b*。所以上面的range并不是指针，而range.first这个整体，显然是指针。指针++，就可以直接移到下一个位置

• 删除元素

 mm.erase(2);

• 遍历

  cout << "\nMultimap after erasing key 2:" << endl;for (const auto& element : mm) {cout << element.first << " => " << element.second << std::endl;}

element是其中的一个元素，而不是指针，所以用 . 号

手写一个简单版本的multimap

【STL 专题之 multimap】multimap 的实现
题目描述

本题需要设计一个 multimap 类，实现如下功能

1、基础功能

• 构造函数：初始化 multimap 实例
• 析构函数：清理资源，确保无内存泄露

2、核心功能

• 在 multimap 中插入一个元素
• 在 multimap 中删除指定的键值
• 在 multimap 中删除所有的值
• 判断 multimap 是否为空
• 获取 multimap 的大小
• 遍历打印 multimap 中的key 对应的 values
• 获取 multimap 中 key 对应的 values

输入描述

题目的包含多行输入，第一行为正整数 N, 代表后续有 N 行命令序列。

接下来 N 行，每行包含一个命令，命令格式为 [operation] [parameters] ，具体命令如下：

insert 命令：

• 格式：insert [key] [value]
• 功能：在 map 中添加 key-value 键值对，如果对应的 key 已经存在，则不进行任何操作

remove 命令：

• 格式：remove [key] [value]
• 功能：在 map 中删除 key 对应的 value

remove_all 命令：

• 格式：remove_all [key]
• 功能：在 map 中删除 key 对应的所有 value

at 命令：

• 格式：at [key]
• 功能：在 map 中获取 key 对应的 value

empty 命令：

• 格式：empty
• 功能：判断 multimap 是否为空

size 命令：

• 格式：size
• 功能：获取 multimap 的大小

#include "RedBlackTree.h"
#include <cstddef>
#include <iostream>
#include <list>template<typename Key,typename Value>
class MultiMap
{
private:RedBlackTree < Key, Value> rbTree;size_t size;
public:using ValueType = list<Value>;MultiMap() :rbTree(), size(0) {}~MultiMap(){}void insert(const Key& key, const Value& value){ValueType* existValues = rbTree.at(key);if (existValues)existValues->push_back(value);else{ValueType values;values.push_back(Value);rbTree.insert(key, values);}size++;}void remove(const Key& key){ValueType* existValues = rbTree.at(key);if (existValues){size -= existValues->size();rbTree.remove(key);}}void remove(const Key& key, const Value& value){ValueType* existValues = rbTree.at(key);if (existValues){existValues->remove(value);size--;if (existValues->empty())rbTree.remove(key);}}ValueType* at(const Key& key){return rbTree.at(key);}int getSize() { return size; }bool empty() { return size == 0; }
};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 exsit" << std::endl;}}}return 0;
}

set家族与map家族的对比（思维导图）