C++STL~~map

文章目录

• • 序列式容器和关联式容器
  • 一、map的概念
  • 二、map的使用
  • 三、map&multimap的差异
  • 四、map的练习
  • 五、总结

序列式容器和关联式容器

序列式容器
前面已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，比如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。本章节讲解的map底层是红黑树map是key/value搜索场景的结构。

一、map的概念

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是O(logN) ，迭代器遍历是走的中序，所以是按key有序顺序遍历的。

template < class Key, // map::key_type
 class T, // map::mapped_type
 class Compare = less<Key>, // map::key_compare
 class Alloc = allocator<pair<const Key,T> > // map::allocator_type
 > class map;

pair的概念
map底层的红黑树节点中的数据，使用pair<Key,T>存储键值对数据

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
	template<class U, class V>
	pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
	{}
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{
	return (pair<T1, T2>(x, y));
}

二、map的使用

map的构造
map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

// empty (1) ⽆参默认构造 
explicit map(const key_compare& comp = key_compare(),
	const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造 
template <class InputIterator>
map(InputIterator first, InputIterator last,
	const key_compare& comp = key_compare(),
	const allocator_type & = allocator_type());
// copy (3) 拷⻉构造 
map(const map& x);
// initializer list (5) initializer 列表构造 
map(initializer_list<value_type> il,
	const key_compare& comp = key_compare(),
	const allocator_type& alloc = allocator_type());

// 迭代器是⼀个双向迭代器 
iterator->a bidirectional iterator to const value_type
// 正向迭代器 
iterator begin();
iterator end();
// 反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

map的增删查
map增接口，插入的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value

Member types
key_type->The first template parameter(Key)
mapped_type->The second template parameter(T)
value_type->pair<const key_type, mapped_type>
// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 
pair<iterator, bool> insert(const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊ 
void insert(initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊ 
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找k，返回k所在的迭代器，没有找到返回end() 
iterator find(const key_type& k);
// 查找k，返回k的个数 
size_type count(const key_type& k) const;
// 删除⼀个迭代器位置的值 
iterator erase(const_iterator position);
// 删除k，k存在返回0，存在返回1 
size_type erase(const key_type& k);
// 删除⼀段迭代器区间的值 
iterator erase(const_iterator first, const_iterator last);
Member types
key_type->The first template parameter(Key)
mapped_type->The second template parameter(T)
value_type->pair<const key_type, mapped_type>
// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 
pair<iterator, bool> insert(const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊ 
void insert(initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊ 
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找k，返回k所在的迭代器，没有找到返回end() 
iterator find(const key_type& k);
// 查找k，返回k的个数 
size_type count(const key_type& k) const;
// 删除⼀个迭代器位置的值 
iterator erase(const_iterator position);
// 删除k，k存在返回0，存在返回1 
size_type erase(const key_type& k);
// 删除⼀段迭代器区间的值 
iterator erase(const_iterator first, const_iterator last);

map的数据修改
前面提到map支持修改mapped_type数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。
map第⼀个支持修改的方式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有⼀个⾮常重要的修改接口operator[]，但是operator[]不仅仅⽀持修改，还⽀持插⼊数据和查找数据，所以他是⼀个多功能复合接口
需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型，typedef为mapped_type。而value_type是红⿊树结点中存储的pair键值对值。日常使用还是习惯将这里的T映射值叫做value。

Member types
key_type->The first template parameter(Key)
mapped_type->The second template parameter(T)
value_type->pair<const key_type, mapped_type>
// 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的
mapped_type值
iterator find(const key_type& k);
// ⽂档中对insert返回值的说明 
// The single element versions (1) return a pair, with its member pair::first 
set to an iterator pointing to either the newly inserted element or to the
element with an equivalent key in the map.The pair::second element in the pair
is set to true if a new element was inserted or false if an equivalent key
already existed.
// insert插⼊⼀个pair<key, T>对象 
// 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象
first是key所在结点的迭代器，second是false
// 2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象
first是新插⼊key所在结点的迭代器，second是true
// 也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭
代器
// 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现
operator[]
// 需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，另⼀个是insert返回值pair<iterator, bool>
pair<iterator, bool> insert(const value_type & val);
mapped_type& operator[] (const key_type& k);
// operator的内部实现 
mapped_type& operator[] (const key_type& k)
{
	// 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储
	mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ + 修改功能
		// 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的
		迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找 + 修改的功能
		pair<iterator, bool> ret = insert({ k, mapped_type() });
	iterator it = ret.first;
	return it->second;
}

构造遍历及增删查使用

#include<iostream>
#include<map>
using namespace std;
int main()
{
	// initializer_list构造及迭代遍历 
	map<string, string> dict = { {"left", "左边"}, {"right", "右边"},
   {"insert", "插⼊"},{ "string", "字符串" } };

	//map<string, string>::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		//cout << (*it).first <<":"<<(*it).second << endl;

		// map的迭代基本都使⽤operator->,这⾥省略了⼀个-> 
		// 第⼀个->是迭代器运算符重载，返回pair*，第⼆个箭头是结构指针解引⽤取pair数据
			//cout << it.operator->()->first << ":" << it.operator->()-> second << endl;
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
	// insert插⼊pair对象的4种⽅式，对⽐之下，最后⼀种最⽅便 
	pair<string, string> kv1("first", "第⼀个");
	dict.insert(kv1);
	dict.insert(pair<string, string>("second", "第⼆个"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert({ "auto", "⾃动的" });
	// "left"已经存在，插⼊失败 
	dict.insert({ "left", "左边，剩余" });
	// 范围for遍历 
	for (const auto& e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;

	string str;
	while (cin >> str)
	{
		auto ret = dict.find(str);
		if (ret != dict.end())
		{
			cout << "->" << ret->second << endl;
		}
		else
		{
			cout << "无此单词，请重新输⼊" << endl;
		}
	}

	// erase等接⼝跟set完全类似，这⾥就不演⽰讲解了 
	return 0;
}

这段代码实现了一个简单的英中字典功能。通过使用std::map来存储英文单词及其对应的中文释义。代码支持初始化字典、插入新的单词释义对、查找特定单词的释义以及通过迭代器遍历字典内容。
map的迭代器和[]功能

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
	// 利⽤find和iterator修改功能，统计⽔果出现的次数 
	string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠",
   "苹果", "⾹蕉", "苹果", "⾹蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		// 先查找⽔果在不在map中 
		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1} 
		// 2、在，则查找到的节点中⽔果对应的次数++ 
		auto ret = countMap.find(str);
		if (ret == countMap.end())
		{
			countMap.insert({ str, 1 });
		}
		else
		{
			ret->second++;
		}
	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	return 0;
}

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
	// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数 
	string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠",
   "苹果", "⾹蕉", "苹果", "⾹蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		// []先查找⽔果在不在map中 
		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引⽤，++⼀下就变成1次了
		// 2、在，则返回⽔果对应的次数++ 
		countMap[str]++;

	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	return 0;
}

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	// key不存在->插⼊ {"insert", string()} 
	dict["insert"];
	// 插⼊+修改 
	dict["left"] = "左边";
	// 修改 
	dict["left"] = "左边、剩余";
	// key存在->查找 
	cout << dict["left"] << endl;
	return 0;
}

三、map&multimap的差异

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全⼀样，比如find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。

• 键的唯一性

1. std::map
   在std::map中，键是唯一的。这意味着如果试图插入一个已经存在键的元素，新的元素将不会被插入（如果使用insert成员函数，插入操作会失败；如果使用下标操作符[]，则会更新与该键关联的值）。例如：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap.insert(std::make_pair(1, "one"));
    myMap.insert(std::make_pair(1, "new one"));
    std::cout << myMap[1] << std::endl;  // 输出 "one"，第二次插入由于键已存在未生效
    return 0;
}

2. std::multimap
   而std::multimap允许键重复。可以插入多个具有相同键但不同值的元素。例如：

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> myMultimap;
    myMultimap.insert(std::make_pair(1, "one"));
    myMultimap.insert(std::make_pair(1, "new one"));
    for (auto it = myMultimap.begin(); it!= myMultimap.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }
    return 0;
}

上述代码会输出两条记录，键都是 1，但值分别为 “one” 和 “new one”。

• 元素访问与查找操作

1. std::map
   由于键的唯一性，std::map提供了更高效的查找操作。可以使用find成员函数通过键快速找到对应的元素。如果找到，find返回指向该元素的迭代器；如果找不到，则返回end()迭代器。例如：

std::map<int, std::string> myMap;
myMap[1] = "one";
auto it = myMap.find(1);
if (it!= myMap.end()) {
    std::cout << "Found: " << it->second << std::endl;
}

2. std::multimap
   std::multimap的查找操作相对复杂一些。find函数在std::multimap中只能找到具有指定键的第一个元素。如果要查找所有具有相同键的元素，需要使用equal_range函数。equal_range返回一个包含两个迭代器的std::pair，分别指向具有指定键的元素范围的开始和结束（不包含结束迭代器指向的元素）。例如：

std::multimap<int, std::string> myMultimap;
myMultimap.insert(std::make_pair(1, "one"));
myMultimap.insert(std::make_pair(1, "new one"));
auto range = myMultimap.equal_range(1);
for (auto it = range.first; it!= range.second; ++it) {
    std::cout << "Value: " << it->second << std::endl;
}

• 迭代器操作的语义差异

1. std::map
   因为std::map中键是唯一的，所以迭代器按照键的顺序（默认是升序）遍历元素时，每个键只会被访问一次。
2. std::multimap
   在std::multimap中，由于键可以重复，当按照顺序遍历容器时，可能会多次遇到相同的键。

四、map的练习

随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
  你的代码 只 接受原链表的头节点 head 作为传入参数。
  
  思路：

1. 要求复制一个链表，其中每个节点都有一个next指针指向下一个节点，还有一个random指针可能指向链表中的任意一个节点或者为空。
2. 需要创建一个深拷贝，即新链表中的节点都是全新的，不能与原链表中的节点有任何关联。
3. 首先遍历原链表，使用map建立原链表节点和新链表节点的映射关系。对于原链表中的每个节点，创建一个新节点，将原节点的值复制到新节点中，并将原节点和新节点存入map中。
4. 再次遍历原链表，对于原链表中的每个节点，通过map找到对应的新节点。如果原节点的next指针不为空，将新节点的next指针指向原节点next指针对应的新节点；如果原节点的random指针不为空，将新节点的random指针指向原节点random指针对应的新节点。
5. 最后返回新链表的头节点，即原链表头节点对应的新节点。
6. 时间复杂度：两次遍历链表，每遍历的时间复杂度为O(n) ，其中n是链表的长度。所以总的时间复杂度为 O(n)
7. 空间复杂度：使用了一个map来存储原链表节点和新链表节点的映射关系，空间复杂度为O(n)，其中n是链表的长度。

#include <iostream>
#include <map>

// 定义链表节点结构
struct Node {
    int val;
    Node* next;
    Node* random;
    Node(int x) : val(x), next(nullptr), random(nullptr) {}
};

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    std::map<Node*, Node*> nodeMap;
    Node* curr = head;
    // 第一次遍历，创建新节点并建立映射关系
    while (curr) {
        nodeMap[curr] = new Node(curr->val);
        curr = curr->next;
    }
    curr = head;
    // 第二次遍历，设置新节点的 next 和 random 指针
    while (curr) {
        nodeMap[curr]->next = nodeMap[curr->next];
        nodeMap[curr]->random = nodeMap[curr->random];
        curr = curr->next;
    }
    return nodeMap[head];
}

前K个高频单词
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

• 示例 1：

输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。

• 示例 2：

输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。
思路

1. 给定一个单词列表，需要统计每个单词的出现次数。
2. 找出出现次数最多的前k个单词，如果出现次数相同，则按字典顺序排序。
3. 使用std::unordered_map来统计每个单词的出现次数。遍历单词列表，对于每个单词，如果在map中不存在，则将其插入map中并初始化为出现次数 1；如果已经存在，则将其出现次数加 1。
4. 将map中的单词和出现次数存储到一个vector<pair<string, int>>中，这样方便后续进行排序操作。
5. 对存储了单词和出现次数的vector进行自定义排序。首先按照出现次数从高到低排序，如果出现次数相同，则按照字典顺序升序排序。
6. 取排序后的vector中的前k个元素，即为出现次数最多的前k个单词。
7. 时间复杂度：遍历单词列表统计出现次数的时间复杂度为O(nlogn) ，其中n是单词列表的长度。
   对存储了单词和出现次数的vector进行排序的时间复杂度通常为O(nlogn) ，其中n是不同单词的个数。
   总的时间复杂度为O(nlogn) 。
8. 空间复杂度：使用了unordered_map和vector来存储单词和出现次数，空间复杂度为O(n) ，其中n是不同单词的个数。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

bool compare(const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) {
    if (a.second!= b.second)
        return a.second > b.second;
    else
        return a.first < b.first;
}

std::vector<std::string> topKFrequent(std::vector<std::string>& words, int k) {
    std::unordered_map<std::string, int> wordCount;
    for (const std::string& word : words) {
        wordCount[word]++;
    }
    std::vector<std::pair<std::string, int>> wordFreq;
    for (const auto& pair : wordCount) {
        wordFreq.push_back(pair);
    }
    std::sort(wordFreq.begin(), wordFreq.end(), compare);
    std::vector<std::string> result;
    for (int i = 0; i < k; i++) {
        result.push_back(wordFreq[i].first);
    }
    return result;
}

五、总结

1.性能特点

• 查找效率高
  • 基于内部的红黑树实现（在大多数标准库实现中），std::map的查找操作具有对数时间复杂度O(logn)，其中是容器中的元素数量。这使得在大规模数据中快速查找键 - 值对成为可能。
• 插入和删除相对高效
  • 插入和删除操作也具有对数时间复杂度O(logn)，因为在插入或删除元素时，红黑树需要进行平衡调整操作。

2.与其他容器的关系和区别

• 与std::vector等顺序容器的区别
  • std::vector是顺序容器，元素在内存中是连续存储的，访问元素可以通过下标直接访问，时间复杂度为O(1)，但查找特定元素需要线性搜索，时间复杂度为O(n)。而std::map以键 - 值对的形式存储元素，主要用于根据键快速查找、插入和删除值，虽然查找、插入和删除的时间复杂度是对数级别的，但不能像std::vector那样直接通过下标随机访问元素。
• 与std::unordered_map的区别
  • std::unordered_map是无序的关联容器，它基于哈希表实现。查找、插入和删除操作的平均时间复杂度为O(1)，但在最坏情况下可能为O(n)。std::map是有序的，在需要元素按照键的顺序存储和遍历的场景下使用，而std::unordered_map在对查找速度要求极高且不关心元素顺序的场景下更有优势。

3.使用场景

• 数据查找与检索
  • 根据键快速查找值
    当需要根据某个特定的键来快速查找对应的值时，std::map是一个很好的选择。例如，在一个学生信息管理系统中，如果以学生的学号作为键，学生的详细信息（如姓名、年龄、成绩等）作为值，使用std::map可以方便地根据学号快速获取学生的所有信息。
• 数据关联与映射
  • 建立一对一的映射关系
    在许多情况下，需要建立两个不同类型数据之间的一对一映射关系。例如，在一个单词计数程序中，可以将单词作为键，单词出现的次数作为值。每次遇到一个单词，就更新其在std::map中的计数。
• 维护有序数据
  • 按照键的顺序存储和访问数据
    如果需要按照某个特定的顺序（默认是键的升序）存储和访问数据，std::map很有用。例如，在一个任务调度系统中，任务按照优先级（假设优先级是一个整数键）进行排序。可以使用std::map来存储任务，按照优先级顺序依次执行任务。
• 实现字典结构
  • 类似字典的键 - 值存储
    在需要实现类似字典的数据结构时，std::map非常合适。例如，在一个多语言翻译程序中，可以将一种语言中的单词作为键，另一种语言中的对应翻译作为值，构建一个简单的翻译字典。
    替代多层嵌套结构
• 简化数据结构
  • 在某些情况下，可以用std::map替代多层嵌套的结构来简化代码逻辑。例如，原本可能使用二维数组来表示一个棋盘游戏的棋盘状态，其中行和列索引作为数组下标。但如果棋盘的行列索引不是连续的整数或者需要关联更多的信息，可以使用std::map，将坐标对（可以用std::pair作为键）与棋盘格的状态信息（如棋子类型、颜色等作为值）关联起来。