map和set的使用

map和set的使用比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应该单词,在词典中就可以找到与其对应的中文含义

一、容器分类

  • 序列式容器:vector list
  • 关联式容器:map set

二、键值对

用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。
比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应该单词,在词典中就可以找到与其对应的中文含义。

SGI-STL中关于键值对的定义:

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

三、set

set的insert

single element (1)	pair<iterator,bool> insert (const value_type& val);
with hint 	   (2)	iterator insert (iterator position, const value_type& val);
range 		   (3) 	template </class InputIterator>
					void insert (InputIterator first, InputIterator last);
void testset1()
{ 
   
	set<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);
	s.insert(5);
	s.insert(5);

	// 搜索树默认遍历是中序
	// 排序+去重
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{ 
   
		cout << *it << " ";
		++it;
	}
	cout << endl;
	for (auto e : s)
	{ 
   
		cout << e << " ";
	}
 }

set的erase

void erase (iterator position);  
size_type erase (const value_type& val); 
void erase (iterator first, iterator last);
void testset2()
{ 
   
	set<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);

	set<int>::iterator it = s.begin();
	while (it != s.end())
	{ 
   
		cout << *it << " ";
		++it;
	}
	cout << endl;
	set<int>::iterator pos = s.find(5);
	if (pos != s.end())
	{ 
   
		s.erase(pos);
	}
	for (auto e : s)
	{ 
   
		cout << e << " ";
	}
}

四、multiset

multiset允许键值重复,其余操作与set几乎相同

multiset的insert

void testmultiset1()
{ 
   
	// 最大区别就是允许插入同样的值
	multiset<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);

	multiset<int>::iterator it = s.begin();
	while (it != s.end())
	{ 
   
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

multiset的find

void testmultiset2()
{ 
   
	multiset<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	for (auto e : s)
	{ 
   
		cout << e << " ";
	}
	cout << endl;
	multiset<int>::iterator pos = s.find(5);
	// 这里找到是中序的第一个5
	/*if (pos != s.end()) { s.erase(pos); }*/
	while (pos != s.end())
	{ 
   
		cout << *pos << " ";
		++pos;
	}
}

multiset的erase

void testmultiset3()
{ 
   
	multiset<int> s;
	s.insert(10);
	s.insert(0);
	s.insert(3);
	s.insert(7);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	for (auto e : s)
	{ 
   
		cout << e << " ";
	}
	cout << endl;
	multiset<int>::iterator pos = s.find(5);
	// 这里找到是中序的第一个5
	 
	
	// 第一种就是删除所有的5迭代器
	//while (pos != s.end()&&*pos==5)
	//{ 
   
	// // 如果直接删除,就会导致迭代器失效
	// auto next = pos;
	// next++;
	// s.erase(pos);
	// pos = next;
	//}

	// 第二种就是直接删除值
	cout << s.erase(5) <<endl;

	for (auto e : s)
	{ 
   
		cout << e << " ";
	}
}

五、map

map的insert

single element (1)	pair<iterator,bool> insert (const value_type& val);
with hint 	   (2)	iterator insert (iterator position, const value_type& val);
range 		   (3)	template <class InputIterator>
  					void insert (InputIterator first, InputIterator last);

数据类型:

key_type | The first template parameter (Key)
mapped_type | The second template parameter (T)
value_type | pair<const key_type,mapped_type>

pair的构造函数:

default 		(1)	pair();
copy 			(2)	template<class U, class V> pair (const pair<U,V>& pr);
initialization  (3)	pair (const first_type& a, const second_type& b);

make_pair较于pair的优势就是它是一个函数模板,可以自动推导参数的类型

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{ 
   
  return ( pair<T1,T2>(x,y) );
}
void testmap1()
{ 
   
	// 字典
	map<string, string> dict;
	// 1、直接构造对象
	pair<string, string> kv1("sort", "排序");
	dict.insert(kv1);

	// 2、匿名对象进行构造
	dict.insert(pair<string, string>("study", "学习"));

	// 3、make_pair是一个函数模板,本质也是\ 返回一个pair的匿名对象,可以自动推导类型
	dict.insert(make_pair("test", "测试"));

	auto it = dict.begin();
	while (it != dict.end())
	{ 
   
		cout << it->first << ": " << it->second << endl;
		//cout << (*it).first << ": " << (*it).second << endl;
		++it;
	}
}

重点operator[ ]

统计水果出现的次数

// 第一种:通过查找的方式统计
void testmap2()
{ 
   
	string fruits[] = { 
    "香蕉","香蕉",
	"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	//key是水果名称,value是该水果出现的次数
	map<string, int> countMap;
	for (auto& str : fruits)
	{ 
   
		auto ret = countMap.find(str);
		if (ret == countMap.end())
		{ 
   
			// 没找到,说明要插入
			countMap.insert(make_pair(str, 1));
		}
		else
		{ 
   
			ret->second++;
		}
	}
	//范围for相当于 kv=*it 这个操作
	for (auto& kv : countMap)
	{ 
   
		cout << kv.first <<" : " << kv.second << endl;
	}
	cout << endl;
}

这种方法的统计有缺陷,就是第一次会查找该值在不在map中,如果在直接value++,如果不在会进行插入操作,插入时又会进行一次查找操作,不免效率会低一点

改进
利用如下insert函数

pair<iterator,bool> insert (const value_type& val);

利用这个insert,它会返回一个pair对象,其成员pair::first设置为一个迭代器,指向新插入的元素或映射中具有等效键的元素。如果插入了新元素,则对键值对中的pair::second元素设置为true ,如果已存在等效键,则设置为false 。

如果不存在,则返回新插入位置的迭代器,second设置为true
如果已存在,则返回已经存在位置的迭代器,second设置为false

// 第二种:改进第一种
void testmap3()
{ 
   
	string fruits[] = { 
    "香蕉","香蕉",\
	"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	//key是水果名称,value是该水果出现的次数
	map<string, int> countMap;
	for (auto& str : fruits)
	{ 
   
		//pair<iterator, bool> insert(const value_type & val);
		auto pair = countMap.insert(make_pair(str,1));
		if (pair.second == false)
		{ 
   
			pair.first->second++;
		}
	}

	//范围for相当于 kv=*it 这个操作
	for (auto& kv : countMap)
	{ 
   
		cout << kv.first << " : " << kv.second << endl;
	}
	cout << endl;
}

使用operator[ ]

mapped_type& operator[] (const key_type& k);
// 第三种:operator[]
void testmap4()
{ 
   
	string fruits[] = { 
    "香蕉","香蕉",\
	"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	map<string, int> countMap;

	for (auto& str : fruits) 
	{ 
   
		countMap[str]++;//一句代码即可统计
	}

	for (auto& kv : countMap) 
	{ 
   
		cout << kv.first << " : " << kv.second << endl;
	}
	cout << endl;
}

以前的[ ]都是数组行为,这里的[ ]的传入的是key,返回的是value的引用,进一步看看[ ]的调用等价于:

mapped_type& operator[] (const key_type& k)
{ 
   
	return (*((this->insert(make_pair(k,mapped_type()))).first)).second;
}

//简化一下
mapped_type& operator[] (const key_type& k)
{ 
   
	pair<iterator,bool> ret =insert(make_pair(k,mapped_type()));
	return ret.first->second;
}

在这里插入图片描述
这里统计次数second给的模板参数是int( ),为0,++过后变为1了,所以虽然刚开始新插入的int为0,返回值是value的引用,所以可以统计次数了。
1、水果第一次出现,插入+修改
2、水果不是第一次出现,查找+修改

总结一下[ ]的作用

  • 插入
  • 查找
  • 修改
void testmap5()
{ 
   
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("test", "测试"));
	dict.insert(make_pair("left", "左边"));

	dict["left"] = "剩余";// 修改left
	dict["hello"];// 没有此key,充当插入的作用 
	cout << dict["sort"] << endl;// 有这个key,充当查找
	dict["C++"] = "C加加";// 充当插入+修改
}

六、multimap

与map使用几乎相同,它允许key冗余,但是没有operator[ ]

multimap的insert

void testmultimap()
{ 
   
	// 允许key冗余
	multimap<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("test", "测试"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("left", "留下"));
	for (auto& kv : dict)
	{ 
   
		cout << kv.first << " : " << kv.second << endl;
	}
	cout << endl;

	// 计数
	cout << dict.count("left") << endl;
}

七、OJ题

  1. 本公司现在要给公司员工发波福利,在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多,但是却又不知道哪种水果比较受欢迎,然后公司就让每个员工报告了自己最爱吃的k种水果,并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数,并且求出大家最喜欢吃的前k种水果

第一种:

//OJ题
//统计最相爱的前k个水果
struct CountVal
{ 
   
	bool operator()(const pair<string,int>& l, const pair<string, int>& r)
	{ 
   
		return l.second > r.second;
	}
};
void GetFavoriteFruit1(const vector<string>& fruits,size_t k) 
{ 
   
	map<string, int> countMap;

	// 统计次数
	for (auto& str : fruits)
	{ 
   
		countMap[str]++;
	}
	
	// 找前k个——topk问题
	//1、数据量不大,我们可以排序
	// 首先我们想要使用sort,必须传入随机迭代器的容器\ 所以我们把数据插入到vector<pair<string, int>>中
	vector<pair<string, int>> sortV;
	for (auto& kv : countMap)
	{ 
   
		sortV.push_back(kv);
	}
	sort(sortV. begin(), sortV.end(),CountVal());

	for (int i = 0; i < k; i++)
	{ 
   
		cout << sortV[i].first << ":" << sortV[i].second << endl;
	}
}
void test1()
{ 
   
	vector<string> fruits = { 
    "香蕉","香蕉","梨",\
	"香蕉","香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit1(fruits,3);
}

第一种改进的版本:

struct CountIterator
{ 
   
	bool operator()(const map<string, int>::iterator& l, map<string, int>::iterator& r)
	{ 
   
		return l->second > r->second;
	}
};
void GetFavoriteFruit1(const vector<string>& fruits,size_t k) 
{ 
   
	map<string, int> countMap;

	// 统计次数
	for (auto& str : fruits)
	{ 
   
		countMap[str]++;
	}
	
	// 找前k个——topk问题
	// 改进:在vector中存map的迭代器,迭代器比pair小,更加节省空间
	vector <map<string, int>::iterator> sortV;
	auto it = countMap.begin();
	while (it != countMap.end())
	{ 
   
		sortV.push_back(it);
		it++;
	}
	sort(sortV.begin(), sortV.end(), CountIterator());
	for (int i = 0; i < k; i++)
	{ 
   
		cout << sortV[i]->first << ":" << sortV[i]->second << endl;
	}
}
void test1()
{ 
   
	vector<string> fruits = { 
    "香蕉","香蕉","梨","香蕉",
		"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit1(fruits,3);
}

第二种:

//2、可以使用multimap
void GetFavoriteFruit2(const vector<string>& fruits, size_t k)
{ 
   
	map<string, int> countMap;
	// 统计次数
	for (auto& str : fruits)
	{ 
   
		countMap[str]++;
	}
	
	multimap<int, string,greater<int>> sortMap;
	for (auto& kv : countMap)
	{ 
   
		sortMap.insert(make_pair(kv.second, kv.first));
	}

	auto it = sortMap.begin();
	while (it != sortMap.end())
	{ 
   
		cout << it->second << " : " << it->first << endl;
		it++;
	}
}
void test1()
{ 
   
	vector<string> fruits = { 
    "香蕉","香蕉","梨","香蕉",
		"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit2(fruits,3);
}

第三种:

struct CountVal
{ 
   
	bool operator()(const pair<string,int>& l, const pair<string, int>& r)
	{ 
   
		return l.second < r.second;
	}
};
void GetFavoriteFruit3(const vector<string>& fruits, size_t k)
{ 
   
	map<string, int> countMap;
	// 统计次数
	for (auto& str : fruits)
	{ 
   
		countMap[str]++;
	}
	//3、可以使用priority_queue
	priority_queue<pair<string, int>, vector<pair<string, int>>, CountVal> qp;
	for (auto& kv : countMap)
	{ 
   
		qp.push(kv);
	}
	while (k--)
	{ 
   
		cout << qp.top().first << ":" << qp.top().second << endl;
		qp.pop();
	}
}
void test1()
{ 
   
	vector<string> fruits = { 
    "香蕉","香蕉","梨","香蕉",
		"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit3(fruits,3);
}

第三种改进版本:

struct CountIterator
{ 
   
	bool operator()(const map<string, int>::iterator& l, map<string, int>::iterator& r)
	{ 
   
		//return l->second > r->second;
		return l->second < r->second;
	}
};
void GetFavoriteFruit3(const vector<string>& fruits, size_t k)
{ 
   
	map<string, int> countMap;

	// 统计次数
	for (auto& str : fruits)
	{ 
   
		countMap[str]++;
	}
	
	priority_queue<map<string, int>::iterator, vector<map<string, int>::iterator>, CountIterator> pq;
	auto it = countMap.begin();
	while (it != countMap.end())
	{ 
   
		pq.push(it);
		++it;
	}

	while (k--)
	{ 
   
		cout << pq.top()->first << ":" << pq.top()->second << endl;
		pq.pop();
	}
}
void test1()
{ 
   
	vector<string> fruits = { 
    "香蕉","香蕉","梨","香蕉",
		"香蕉","苹果","苹果","苹果","香蕉","西瓜","梨" };
	GetFavoriteFruit3(fruits,3);
}
  1. 前K个高频单词
    给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。
    返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字典顺序排序。

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

sort的底层是快速排序,它是不稳定的一个排序,可能OJ过不了。
我们可以选择一个稳定的排序:std::stable_sort,下面所使用的的是multimap来进行排序操作的,也可以完成。

class Solution { 
   
public:
    vector<string> topKFrequent(vector<string>& words, int k) { 
   
        map<string,int> countMap;
        // 统计次数
        for(auto &str: words)
        { 
   
            countMap[str]++;
        }

        // 排序操作
        // 按照value来排序,排降序传入greater
        multimap<int,string,greater<int>> sortMap;
        for(auto & kv: countMap)
        { 
   
            sortMap.insert(make_pair(kv.second,kv.first));
        }

        // 拿到前k个
        vector<string> v;
        auto it=sortMap.begin();
        while(k--)
        { 
   
            v.push_back(it->second);
            ++it;
        }
        return v;
    }
};

今天的文章map和set的使用分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/67614.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注