目录

set：

一：什么是set

二：举例

set的find：

set的erase：

set中的count：

 set中的lower_bound

 set中的upper_bound

 multiset：

map：

一：什么是map

二：函数与[]

---

set：

一：什么是set

set 翻译为集合，是一个内部自动有序且不含重复元素的容器，加入 set 之后可以实现自动排序。

简单来说就是去重+排序（默认从小到大）

二：举例

我们插入多个数字1，并且打乱1-5的顺序

int main()
{
	set<int> s;
	s.insert(1);
	s.insert(1);
	s.insert(1);
	s.insert(1);
	s.insert(1);
	s.insert(5);
	s.insert(4);
	s.insert(2);
	s.insert(3);
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	return 0;
}

结果如下：set就实现了去重+排序

 

 三：一些简单的函数用法和简析

set的find：

find函数的用法和set一样，我们就以前面为例，找数字2

auto pos = s.find(2);

但是我们同样知道算法中也有一个find函数

auto pos = find(s.begin(), s.end(), 2);

 那么他们究竟有什么区别？

算法中的find是暴力查找，是遍历整个区间，所以时间复杂度是O（N）；

而set中的find利用了搜索树的特性，时间复杂度是O（longN）；

所以在数据量非常大的时候，set函数就用自己自带的find函数就行了

set的erase：

这里erase和find结合起来使用

以上面为例，假如我要删除

	int x;
	while (cin >> x)//输入要删除的值
	{
		auto pos = s.find(x);//接收
		if (pos != s.end())
		{
			s.erase(pos);//删除
			cout << "删除" << x << "成功" << endl;
		}
}

 有些同学会说，我们不能直接放在外面吗？

s.insert（3）;
s.erase(3);//放在这里不行吗？？？？？？
	int x;
	while (cin >> x)//输入要删除的值
	{
		auto pos = s.find(x);//接收
		if (pos != s.end())
		{
			s.erase(pos);//删除
			cout << "删除" << x << "成功" << endl;
		}
}

 答案是不行的。

如果我们这个数据中如果没有对应的值，假如我们在这里删除3

S.insert（1）;
S.insert（2）;
S.erase（3）；

 那么编译器就会报错

 如果我们判断了，没有这个数再进行删除，那么就不会报错了，所以说判断是很重要的不能省略。

同时如果删除成功，这里返回1，删除失败返回0

s.inser(3);
cout << s.erase(3) << endl;
cout << s.erase(30) << endl;

 

set中的count：

count函数的功能类似于find但是比find更简单

 

s.insert(3);
if(s.count(3))
{
  cout<<"在"<<endl;
}

 如果在，返回1，如果不在返回0

结果如下

 set中的lower_bound

返回大于等于的值

举例：我插入1-5,7,9.然后用lower_bound找3和6,3可以直接找到，但是6没有，所以返回>=6最近的元素7.

set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);
	s.insert(7);
	s.insert(9);
	auto it = s.lower_bound(3);
	cout << *it << endl;
	it = s.lower_bound(6);
	cout << *it << endl;

结果如下：

 

 set中的upper_bound

与lower_bound的大于等于，upper_bound返回大于

相当于lower是闭区间，而upper是开区间

验证如下：还是1-5，然后7,9

set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);
	s.insert(7);
	s.insert(9);
	auto it = s.upper_bound(3);
	cout << *it << endl;
	it = s.upper_bound(6);
	cout << *it << endl;

 结果如下：

此时虽然队列中有3，但是upper是返回比3更大值的最近的一个，所以返回了4 

 multiset：

允许同一个数据的插入

multiset<int> s;
	s.insert(1);
	s.insert(1);
	s.insert(1);
s.insert(2);

结果如下： 

 

map：

一：什么是map

map是STL的一个关联容器，它提供一对一的hash。

map有两个，一个被称为关键字key，另一个被称为关键字的值value

举一个例子：我定义了一个map的对象dict，然后在dict里面插入了一个关键字left

然后左边，是对left给的值

然后输出

map<string, string> dict;
	dict.insert(make_pair("left", "左边"));
	auto it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first <<it->second<< " ";
		it++;
	}
	cout << endl;

• 
   

结果如下：

 

二：函数与[]

map中的insert插入：

对于insert我们有三种插入的写法，但是我们一般使用第三种，因为第三种方便

// 定义一个map对象
map<string, string> dict;
 
// 第一种 用insert函數插入pair
mapStudent.insert(pair<int, string>("left", "左边"));
 
// 第二种 用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type("left", "左边"));
 
// 第三种 用"make_pair"方式插入
dict.insert(make_pair("left", "左边"));

[]：

map的[]与vector和string等不一样，[]的方括号一般用来统计

string arr[] = { "苹果","西瓜","苹果","西瓜" ,"苹果" };
	map<string, int> countMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}
	auto it = countMap.begin();
	while (it != countMap.end())
	{
		cout << it->first << ":" << it->second << " " << endl;
		it++;
	}

结果如下：

 在库中是这样实现的

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