map的使用

pair类型介绍

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));
}

可以理解为，现在的key和value不再单独出现，而是整合在一个pair的结构体里面，pair里有两个成员变量，一个代表key，另一个代表value。 

使用样例：

int main()
{
	map<string, string> dict;
	//1.插入有名的pair对象
	pair<string, string> kv1("first", "第一个");
	dict.insert(kv1);
	//2.插入匿名的pair对象
	dict.insert(pair<string, string>("second", "第二个"));
	//3.调用make_pair：本质是一个函数模板（不用自己实例化模板参数），返回一个pair对象（常用）
	//与2.等价
	dict.insert(make_pair("sort", "排序"));
    //补充注意点：因为map不允许数据冗余，当再执行插入一个key同为sort的代码，并不会修改原有数据，因为map底层红黑树比较的基准永远都是key，与value无关
    dict.insert(make_pair("sort", "排序mmmmm"));
	//C++11之后允许多参数的隐式类型转换--->
	//4.使用{}，隐式类型转换成pair（最爱用）
	dict.insert({ "auto","自动的" });
    //initializer_list构造
    //内层走隐式类型转换，外层走initializer
    map<string, string> dict = { {"left", "左边"}, {"right", "右边"}, {"insert", "插⼊"},{ "string", "字符串" } };
	return 0;
}

C++不支持同时返回两个值，如果要同时返回两个值，就需要用一个结构来封装（将key和value放在一个pair结构里面），而且pair不支持流插入和流提取 

因为对于一个节点数据来说，节点包含了对应的key和value数据，因此，访问数据应该使用下列两种方式操作：

1. *it是一个pair，可以用"  . 对象  "的方式进行访问
2. 迭代器除了重载 operator* ，还重载了 operator-> ，如果迭代器指向的对象是一个结构的时候就使用 -> 

	//打印数据
	auto it = dict.begin();
	while (it != dict.end())
	{
		//C++不支持同时返回两个值
		//cout << *it << endl;
		//*it是一个pair，可以用"  . 对象  "的方式进行访问
		cout << (*it).first << ' : ' << (*it).second << endl;

		//迭代器除了重载 operator* ，还重载了 operator-> ，如果迭代器指向的对象是一个结构的时候就使用 -> 
		cout << it->first << ' : ' << it->second << endl;
		//本源是：
		//it.operator->()->first;
		//it.operator->()：返回数据的指针：也就是pair*
		//pair*->first
		
		it++;
	}
	cout << endl;
	return 0;
}

map的使用

map其实跟set相似，只是map多了一个value值（second）

具体参考（点击进入）

• map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持⼩于⽐较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数；（注意是以Key为比较基准）
• map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数；
• map底层是⽤红⿊树实现，增删查改(对于修改操作，仅仅支持对value进行修改)效率是 O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的；
• map的insert操作跟key和value有关，erase/find/count/lower_bound/upper_bound等操作只跟key有关，与value无关；
• equal_range是找到指定数据的左闭右开区间，返回的是一个pair，多用于multi版本的set/map，来查找相同数据的所在的左闭右开区间。

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;

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的增删查关注以下⼏个接⼝即可：

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);

// 返回⼤于等k位置的迭代器
iterator lower_bound(const key_type& k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound(const key_type& k) const;

map的数据修改 

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

利⽤find和iterator修改功能，统计⽔果出现的次数：

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;
}

但是在C++中，并不常以这种方式进行统计次数，而是使用operator [ ] 来实现次数的统计：

对于map重载的operator [ ] ，不再是单纯的实现像数组一样的通过下标去访问元素，这里是说：你给我map里的key，我返回对应的value

mapped_type& operator[] (const key_type& k);
//这里的mapped_type就是我们所指的value
//而他文档写的value_type是我们所指的pair

map重载的operator [ ] 不仅有查找及其修改的功能，它还兼具插入的功能：

• 当你使用 operator[] 访问 map 中的元素时，如果该元素存在，它会返回一个引用，允许你修改该元素的值。
• 如果该元素不存在，operator[] 会插入一个新的元素，并将该元素的值初始化为该键类型的默认值。（对于其他语言来说，或者会抛异常）

功能样例：

int main()
{
	map<string, string> dict;
	dict.insert({ "sort","排序" });

	//key不存在->插入{"insert",string()};
	dict["insert"];//这时候【】的作用就是进行插入操作

	//key不存在->插入+修改
	dict["tea"] = "茶";

	//key存在->修改
	dict["insert"] = "插入";

	//查找：一定要确保所查找的数据存在，不然就是变成了key不存在的插入行为了
	//应当谨慎使用其查找功能
	cout << dict["tea"] << endl;

	for (auto d : dict)
	{
		cout << d.first << ":" << d.second << endl;
	}
	cout << endl;
	return 0;
}

其插入操作，等价于底层调用：

//A call to this function is equivalent to:
(*((this->insert(make_pair(k,mapped_type()))).first)).second

到这里，我们需要好好理解map中的insert操作的返回值：

穿插：map中insert的返回值

//single element (1)	
pair<iterator,bool> insert (const value_type& val);

可以看出，这里的insert的返回值是一个pair，其中value_type也是一个pair（用于存键值对），因此，有两个pair；

1. 返回的pair中iterator(迭代器)作用是为了返回新插入元素位置的迭代器，如该map结构已经存在相同元素，则指向原有元素位置的迭代器
2. 返回的pair中bool的作用是判断insert操作是否成功，如果key存在，该布尔值为false，反之，为true

简单来说：

插入成功：
pair<新插入值所在迭代器, true>

插入失败：
pair<已经存在的跟key相等值迭代器, false>

那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现 operator[]

operator[] 的内部实现：

// 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;
}

代码优化：使用operator [ ] 

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;
}

multimap和map的区别

在C++标准库中，map和multimap都是关联容器，它们存储了键值对（key-value pairs），并且提供了基于键的有序访问。它们之间的主要区别在于：

1. 唯一性：

   • map：每个键必须是唯一的。如果尝试插入一个已经存在的键，那么该操作将不会改变容器。
   • multimap：允许有多个元素具有相同的键。这意味着可以存储多个具有相同键的值。

2. 插入操作：

   • map：如果插入的键已经存在，那么插入操作不会成功，容器内容不变。
   • multimap：即使键已经存在，插入操作也会成功，并且会创建一个新的键值对。

3. 迭代器：

   • map：迭代器指向唯一的元素，所以迭代器的 operator* 直接返回一个 pair 对象，其中包含键和值。
   • multimap：迭代器也指向 pair 对象，但由于可能有多个相同的键，所以迭代器的 operator* 返回一个引用到 pair 的对象。

4. 查找操作：

   • map：查找操作返回一个迭代器，指向找到的元素或者在未找到时指向插入点。
   • multimap：查找操作返回一个迭代器范围（一个迭代器对），包含所有具有指定键的元素。

5. 删除操作：

   • map：删除操作会删除键及其关联的值。
   • multimap：删除操作会删除所有具有该键的元素。

6. 成员函数：

   • map：提供了 find, count, equal_range 等成员函数。
   • multimap：提供了 find, count, equal_range 等成员函数，但 count 返回的是具有相同键的元素数量，equal_range 返回一个迭代器对，表示具有相同键的范围。

7. 用途：

   • map：当你需要快速查找、插入和删除唯一键时使用。
   • multimap：当你需要关联多个具有相同键的值时使用。

在C++标准库中，multimap不支持使用 operator[] 的原因是因为 multimap 允许有多个元素具有相同的键。operator[] 通常用于访问元素，并且它返回一个引用，这意味着它应该定位到一个确切的元素。

对于 map，由于每个键是唯一的，使用 operator[] 可以直接访问或创建并访问一个特定的键值对。

然而，对于 multimap，如果使用 operator[] 会遇到以下问题：

1. 歧义性：如果有多个元素具有相同的键，operator[] 应该返回哪一个元素的引用？
2. 效率问题：operator[] 通常需要提供一个快速访问，但 multimap 需要遍历以找到正确的元素，这与 operator[] 设计的初衷不符。

如何在 multimap 中访问元素

虽然 multimap 不支持 operator[]，但可以使用其他方法来访问或修改具有特定键的元素：

1. 使用 find 方法：

   • find 方法返回一个指向找到元素的迭代器，如果元素不存在，则返回 end() 迭代器。

   std::multimap<int, std::string> myMultimap;
   myMultimap.insert(std::make_pair(1, "One"));
   myMultimap.insert(std::make_pair(2, "Two"));
   myMultimap.insert(std::make_pair(2, "Another Two"));
   
   auto it = myMultimap.find(2);
   if (it != myMultimap.end()) {
       std::cout << it->second << std::endl; // 输出 "Two"
   }

2. 使用 equal_range 方法：

   • equal_range 方法返回一个迭代器对，表示具有指定键的所有元素的范围。

   std::pair<std::multimap<int, std::string>::iterator,
             std::multimap<int, std::string>::iterator> range;
   
   range = myMultimap.equal_range(2);
   for (auto it = range.first; it != range.second; ++it) {
       std::cout << it->second << std::endl; // 输出所有键为2的元素
   }

3. 使用 lower_bound 和 upper_bound 方法：

   • 这些方法也可以用来找到具有特定键的元素的范围。

   auto lower = myMultimap.lower_bound(2);
   auto upper = myMultimap.upper_bound(2);
   for (auto it = lower; it != upper; ++it) {
       std::cout << it->second << std::endl; // 输出所有键为2的元素
   }

总结：

multimap 不支持 operator[] 是因为它的设计允许多个具有相同键的元素存在，这会导致访问时的歧义性。相反，可以使用 find、equal_range、lower_bound 和 upper_bound 等方法来访问或修改具有特定键的元素。这些方法提供了更灵活的访问方式，可以处理 multimap 中键的重复性。

习题巩固：

学习本章之后，可以通过下面习题进行巩固知识