C++ STL 中的 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;

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

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

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;

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

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