C++之旅-set和map掌握篇

目录

前言

1.set的使用

1.1set类的介绍

1.2 set的构造和迭代器

1.3 set的增删查

1.4 代码练习

1.4.1 set的构造，插入与删除

1.4.2 set 的find的使用样例，与erase结合

1.4.3 set获取区间值函数的应用

1.5 multiset和set的差异

1.6 set强化练习（上链接！！！）

 2.map的使用

2.1 map类的介绍

 2.2 pair类型

2.3 map的构造

 2.4 map的增删查

2.5 map 的数据修改

2.6 代码练习

2.6.1 构造遍历及增删查使用样例 

2.6.2 map的迭代器和[]功能

2.6 multimap和map的差异

2.7 map强化练习

结束语

前言

序列式容器和关联式容器

前面已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为 序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间意一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

#include <set>
#include <map>

template < class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type
> class set;

底层代码展示

// empty (1) ⽆参默认构造
explicit set (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>
set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
// copy (3) 拷贝构造
set (const set& x);
// initializer list (5) initializer 列表构造
set (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();

1.3 set的增删查

相关函数原参数展示

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

1.4 代码练习
 

1.4.1 set的构造，插入与删除

#include <iostream>
#include <vector>
#include <set>
using namespace std;
//int main() {
//	//默认从小到大排列
//	set<int> s1{ 1,23,4 };
//	for (auto s : s1) {
//		cout << s << endl;
//	}
//	int arr[] = { 1,2,4,3,7,5,9 };
//	//修改比较器
//	set<int,greater<int>>s2(arr, arr + sizeof(arr) / sizeof(int));
//	set<int> ::iterator it = s2.begin();
//	//auto it = s2.begin();
//	while (it != s2.end()) {
//		cout << *it << " ";
//		it++;
//	}
//	set<int>s3(s2.begin(), s2.end());
//	set<int>s4 = s1;
//	return 0;
//}
int main() {
	set<int> s;
	s.insert(19);
	s.insert(5);
	s.insert(10);
	int arr[] = { 2,6,4,8 ,5};
	//去重插入
	s.insert(arr, arr + 4);
	for (auto e : s)
		cout << e << " ";
	cout << endl; 
		set<string> str({ "hello", "world", "love" });
		// 遍历string比较ascll码大小遍历
		for (auto& e : str)
		{
			cout << e << " ";
		}
		cout << endl;
		int n;
		cin >> n;
		int num = s.erase(n);
		if (num == 0)
			cout << n << "不存在" << endl;
		else
			cout << "删除成功" << endl;
		for (auto e : s)
			cout << e << " ";

	return 0;
}

不能给常量赋值 

set<int> ::iterator it = s2.begin();
//auto it = s2.begin();
while (it != s2.end()) {
	cout << *it << " ";
	*it = 1;//错误写法
	it++;
}

1.4.2 set 的find的使用样例，与erase结合

int main() {
	set<int> s = { 4,2,7,2,8,5,9 };
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	auto pos = s.find(7);
	if (pos != s.end()) {
		s.erase(pos);
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	int x;
	cout << "删除的数" << endl;
	cin >> x;
	auto pos1 = find(s.begin(), s.end(), x);//O(N)查找
	while (pos1 != s.end()) {
		cout << x << "存在，并删除成功！" << endl;
        break;
	}
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	// 利⽤count间接实现快速查找
	int y;
	cin >>y;
	if (s.count(y))
	{
		cout << y << "在！" << endl;
	}
	else
		
	{
	cout << y << "不存在！" << endl;
	}
	return 0;
}

我们通过了set自带的查找以及算法库的查找，然后也用了set中的count进行了间接查找，通过数据的次数进行判断。

1.4.3 set获取区间值函数的应用

/ 返回大于等val位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回大于val位置的迭代器
iterator upper_bound (const value_type& val) const;

两个函数的区间是左闭右开的

int main() {
	set<int>s;
	for (int i = 1; i <= 9; i++) {
		s.insert(i * 10);
	}
	auto it = s.begin();
	while (it != s.end()) {
		cout << *it << " ";
		it++;
	}
	cout << endl;
	auto itlow = s.lower_bound(30);
	//set<int>:: iterator itup = s.upper_bound(70);
	auto itup = s.upper_bound(70);
	s.erase(itlow, itup);
	for (auto e : s) {
		cout << e << " ";
	}
	//lower_bound（30） 返回一个迭代器 30，而 upper_bound（70） 返回一个迭代器 80。
	return 0;
}

1.5 multiset和set的差异

int main() {
	// 相⽐set不同的是，multiset是排序，但是不去重
	multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个
	int x;
	cin >> x;
	auto pos = s.find(x);
	while (pos != s.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;
	// 相⽐set不同的是，count会返回x的实际个数
	cout << s.count(x) << endl;
	// 相⽐set不同的是，erase给值时会删除所有的x
	s.erase(x);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

1.6 set强化练习（上链接！！！）

 环形链表

142. 环形链表 II - 力扣（LeetCode）

在数据结构链表篇，我们采用了双指针的算法，先定义快慢指针判断链表是否带环，如果相遇，则链表有环存在，然后定义一个meet指针在相遇的位置，头结点和meet 同时往前移动，相遇的时候就是环的位置。

在学习了set之后，我们可以将节点存放到set中，当set中节点个数重复的时候说明有环的存在，就可以返回该节点位置。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*>s;
        ListNode*cur=head;
        while(cur){
            if(s.count(cur))
            return cur;
            else
            s.insert(cur);
            cur=cur->next;
        }
        return NULL;

    }
};

 2.map的使用

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

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

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

 2.4 map的增删查

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;

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

2.6 代码练习

2.6.1 构造遍历及增删查使用样例 

int main() {
	map<string, string>dict{ { "left","左边"},{"right", "右边"}, {"insert", "插入"}};
	pair<string, string>kv( "first","第一个" );
	dict.insert(kv);
	dict.insert(pair<string, string>{"second", "第二个"});
	dict.insert(make_pair("third", "第三个"));
	dict.insert({ "string","字符串" });
	// 插入时只看key，value不相等不会更新
	dict.insert({ "left", "自动的xxxx" });
	map<string, string>::iterator it = dict.begin();
	while (it != dict.end()) {
		//cout << (*it).first << "->" << (*it).second << endl;
		//it->first+='x'; key不能修改
		//it->second += 'x';//值可以修改
		cout << it->first << ":" << it->second << endl;
		// << it.operator->()->first << ":"<<it.operator->()->second << endl;

		it++;
	}
	dict.insert({ "string","字符串串" });//string存在,插入失败
	cout << "输入查询的单词" << endl;
	string s;
	while (cin >> s)
	{
		auto ret = dict.find(s);
		if (ret != dict.end())
		{
			cout << "->" << ret->second << endl;
			break;
		}
		else
		{
			cout << "没有该单词，请重新输入！" << endl;
		}
	}
	dict.erase("second");
	auto it1 = dict.find("first");
	dict.erase(it1);
	for (auto s : dict) {
		cout << s.first << "->" << s.second << endl;
	}
	
	return 0;
}

2.6.2 map的迭代器和[]功能

前提引入

如果我们要统计一个物件的数目，我们就可以采map结构，例如下面代码：

int main() {
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
	map<string, int>countMap;
	for (auto&s : arr) {
		auto pos = countMap.find(s);
		if (pos == countMap.end()) {
			countMap.insert({ s,1 });
		}
		else
			pos->second++;
	}
	for (auto s : countMap) {
		cout << s.first << "->" << s.second << endl;
	}
	return 0; 
}

先查找水果在不在map中

1、不在，说明水果第一次出现，则插入{水果, 1}

2、在，则查找到的节点中水果对应的次数++

这里使用常见的insert来进行数数，通过对[ ]的认识，我们可以利用它的特点同样的来实现计数的功能。

int main() {
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
		"苹果", "香蕉", "苹果", "香蕉" };
	map<string, int>cm;
	for (const auto& str : arr) {
		cm[str]++;
	}
	for (auto& s : cm) {
		cout << s.first << "->" << s.second << endl;
	}
	return 0;
}

[ ]拆分讲解

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;
	for (auto s : dict) {
	cout << s.first << "->" << s.second << endl;
	}
	return 0;
}

2.6 multimap和map的差异

2.7 map强化练习

前k个高频单词

692. 前K个高频单词 - 力扣（LeetCode）

代码1：

class Solution {
public:
    static bool compare(const pair<string,int>&s1,const pair<string,int>&s2){
           return s1.second>s2.second;
     }
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> m;
        for(auto &s:words){
            m[s]++;
        }
        vector<pair<string,int>> v(m.begin(),m.end());
        stable_sort(v.begin(),v.end(),compare);
         
        vector<string>v1;
        for(int i=0;i<k;i++){
            v1.push_back(v[i].first);
        }
        return v1;       
    }
};

代码2：

class Solution {
public:
struct Compare
{
bool operator()(const pair<string, int>& x, const pair<string, int>& y)
const
{
return x.second > y.second;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> countMap;
for(auto& e : words)
{
countMap[e]++;
}
vector<pair<string, int>> v(countMap.begin(), countMap.end());
// 仿函数控制降序
stable_sort(v.begin(), v.end(), Compare());
//sort(v.begin(), v.end(), Compare());
// 取前k个
vector<string> strV;
for(int i = 0; i < k; ++i)
{
strV.push_back(v[i].first);

}
return strV;
}
};

 解决思路2

class Solution {
  
public:
    static bool compare(const pair<string,int>&s1,const pair<string,int>&s2){
           return s1.second>s2.second ||(s1.second==s2.second && s1.first<s2.first);
     }
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> m;
        for(auto &s:words){
            m[s]++;
        }
        vector<pair<string,int>> v(m.begin(),m.end());
        sort(v.begin(),v.end(),compare);
         
        vector<string>v1;
        for(int i=0;i<k;i++){
            v1.push_back(v[i].first);
        }
        return v1;       
    }
};

结束语

本节内容就到此结束啦，内容很多，其实是代码有点多，希望通过本节内容的学习大家对set和map有了深刻的理解认识，下节我们将对map和set的底层进行认识，实现自己的map和set。

最后感谢各位友友们的支持！！！谢谢三连！！！