【C++】map与set

序列式容器与关联式容器

1. string、vector、stack、queue、deque等为序列式容器，逻辑结构为线性序列，两个位置的储存值之间没有紧密的关联关系。 2. 序列式容器保存和访问储存值时，一般依靠储存值在容器中储存的位置。 3. map、set系列和unordered_map、unordered_set系列为关联式容器，逻辑结构为非线性结构，两个位置的储存值之间存在紧密的关联关系。 4. 关联式容器保存和访问储存值时，一般依靠容器中的关键字。

set类

set类的介绍

1. 在使用set类时，必须包含 #include <set> 这一行。 2. set类的底层其实是一个红黑树结构，使用时需要显示实例化。 3. 下面是set类的官方文本介绍，里面有详细的用法讲解。 - C++ Reference

/

set类对象的常见构造

1. set<int> s1，什么也不需要传入，构造一个空的set类对象。 2. set<int> s2(s1.begin(),s1.end())，使用另一个set类对象进行迭代器构造。 3. set<int> s3(const set<int>& s2)，使用另一个set类对象进行拷贝构造。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s1;
	set<int> s2(s1.begin(), s1.end());
	set<int> s3(const set<int>&s2);
	return 0;
}

set类对象的容量操作

1. set.size()，返回set类对象中有效元素个数。 2. set.empty()，检测set类对象的有效节点个数是否为空，为空返回true，不为空返回flase。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s1;
	s1.insert(1);
	s1.insert(4);
	s1.insert(3);
	s1.insert(2);
	s1.insert(5);
	s1.insert(6);
	cout << s1.size() << endl;
	cout << s1.empty() << endl;
	return 0;
}

set容器的修改操作

1. set.insert(int num)，向set类对象中插入整数num，如果插入set类对象已有的元素，则插入失败。 2. set.erase(int num)，向set类对象中删除整数num，如果删除set类对象没有的元素，则删除失败。 3. set.erase(iterator pos)，向set类对象中删除迭代器为pos的值。 4. set.find(int num)，检查set类对象中是否存在某个特定的元素num，效率为log(N)，返回一个迭代器。 5. set.count(int num)，检查set类对象中是否存在某个特定的元素num，返回1或者0。 6. set.lower_bound(int num)，返回一个迭代器，指向set类对象中第一个大于等于num的元素。 7. set.upper_bound(int num)，返回一个迭代器，指向set类对象中第一个大于num的元素。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s1;
	s1.insert(1);
	s1.insert(4);
	s1.insert(3);
	s1.insert(2);
	s1.insert(5);
	s1.insert(6);
	s1.insert(6);//如果插入set对象中已有元素，则插入失败
	for (auto it : s1)
	{
		cout << it << " ";
	}
	cout << endl;
	s1.erase(6);
	s1.erase(7);//如果删除set对象中未有元素，则删除失败
	for (auto it : s1)
	{
		cout << it << " ";
	}
	cout << endl;
	s1.erase(s1.begin());
	for (auto it : s1)
	{
		cout << it << " ";
	}
	cout << endl;
	auto it = s1.find(4);
	cout << *it << endl;
	if (s1.count(3))
	{
		cout << "存在3";
	}
	return 0;
}

set类对象的遍历操作

1. set类支持迭代器操作，迭代器遍历走二叉搜索树的中序遍历，因此默认为升序。 2. set.begin()、set.end()，set.begin()获取第一个元素的迭代器，set.end()获取最后一个元素的下一个位置的迭代器。 3. set.rbegin()、set.rend()，set.rbegin()获取最后一个元素的迭代器，set.rend()获取第一个元素的上一个位置的迭代器。

//insert()
#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s1;
	s1.insert(1);
	s1.insert(4);
	s1.insert(3);
	s1.insert(2);
	s1.insert(5);
	s1.insert(6);
	s1.insert(6);//如果插入set对象中已有元素，则插入失败
	for (auto it : s1)
	{
		cout << it << " ";
	}
	return 0;
}
//1 2 3 4 5 6

multiset类

1. multiset 和 set 的使用 基本类似 ，主要区别点在于 multiset支持值冗余 ，那么 insert 、 find 、 count 、 erase 都围绕着 支持冗余 有所差异。 2. insert 插入 multiset类对象 已有元素时，不会插入失败，而会正常插入。 3. find 查找 multiset类对象 已有元素时， 若存在多个 ， 则返回第一个元素的迭代器 。 4. erase 删除 multiset类对象 已有元素时， 若存在多个 ， 删除全部的该元素 。 5. count 查找 multiset类对象 已有元素时， 若存在多个 ， 则会返回该元素的个数 。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
using namespace std;

int main()
{
	multiset<int> m1;
	m1.insert(1);
	m1.insert(1);
	m1.insert(2);
	m1.insert(3);
	m1.insert(3);
	m1.insert(4);
	m1.insert(5);
	m1.insert(6);
	m1.insert(2);
	m1.insert(4);
	for (auto e : m1)
	{
		cout << e << " ";
	}
	cout << endl;
	auto it = m1.find(3);
	cout << *it << endl;
	cout << m1.count(1) << endl;
	m1.erase(2);
	for (auto e : m1)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

map类

map类的介绍

1. 在使用map类时，必须包含 #include <map> 这一行。 2. map类的底层其实是一个红黑树结构，使用时需要显示实例化。 3. 下面是map类的官方文本介绍，里面有详细的用法讲解。 - C++ Reference

/

pair类型的介绍

1. map底层使用红黑树来存储数据，每个节点存储一个键值对，数据类型为 pair<Key,T>。

template <class T1,class T2>
struct pair
{
	typedef pair<T1, T2> pair;
	T1 _first;
	T2 _second;
	pair()
		:_first(T1())
		, _second(T2())
	{}
};

map类对象的常见构造

1. map<string,string> s1，什么也不需要传入，构造一个空的map类对象。 2. map<string,string> s2(s1.begin(),s1.end())，使用另一个map类对象进行迭代器构造。 3. map<string,string> s3(const map<string,string>& s2)，使用另一个map类对象进行拷贝构造。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
using namespace std;

int main()
{
	map<string, string> m1;
	map<string, string> m2(m1.begin(),m1.end());
	map<string, string> m3(m2);
	return 0;
}

map类对象的遍历操作

1. map类支持迭代器操作，迭代器遍历走二叉搜索树的中序遍历，因此默认为升序。 2. map.begin()、map.end()，map.begin()获取第一个元素的迭代器，map.end()获取最后一个元素的下一个位置的迭代器。 3. map.rbegin()、map.rend()，map.rbegin()获取最后一个元素的迭代器，map.rend()获取第一个元素的上一个位置的迭代器。