C++:map和set

一、set

1.set的介绍

set 是一个Key模型的搜索二叉树 #include<set>

2.insert 

 insert ：排序 + 去重

void test_set1()
{
	set<int> s;
	s.insert(3);
	s.insert(4);
	s.insert(2);
	s.insert(1);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(1);

	// 排序 + 去重 
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		//*it = 10;    迭代器不支持修改
		cout << *it << " ";
		++it;
	}
	cout << endl;

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

 

 3.find

 能找到就返回元素的迭代器，找不到就返回end

set::find 搜索二叉树特性查找，时间复杂度是O(logN)

全局的find 是暴力查找，时间复杂度是O(N)

void test_set2()
{
	set<int> s;
	s.insert(3);
	s.insert(4);
	s.insert(2);
	s.insert(1);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(1);

	set<int>::iterator pos = s.find(2);  // O(logN)
	if (pos != s.end())
	{
		cout << "set.find找到了" << endl;
	}

	pos = find(s.begin(), s.end(), 2); // O(N)
	if (pos != s.end())
	{
		cout << "find找到了" << endl;
	}
}

4.erase

void test_set3()
{
	set<int> s;
	s.insert(3);
	s.insert(4);
	s.insert(2);
	s.insert(1);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	cout << s.erase(3) << endl;    //有就返回1
	cout << s.erase(30) << endl;   //没有就返回0

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

	set<int>::iterator pos = s.find(3);
	if (pos != s.end())
		s.erase(pos);

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

}

 

 5.swap

6.count 

void test_set4()
{
	set<int> s;
	s.insert(3);
	s.insert(4);
	s.insert(2);
	s.insert(1);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(1);

	cout << s.count(2) << endl;
	cout << s.count(5) << endl;

	cout << s.count(20) << endl;
}

 

7.lower_bound 

返回>= val的位置迭代器

用途：删除>=val的所有值

void test_set5()
{
	set<int> s;
	s.insert(3);
	s.insert(4);
	s.insert(2);
	s.insert(1);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 要求删除>=x的所有值
	int x;
	cin >> x;
	set<int>::iterator lowIt = s.lower_bound(x);
	s.erase(lowIt, s.end());

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

 8.upper_bound

 返回>x位置的迭代器

9.multiset

插入重复的数时set会去重，multiset不去重，允许冗余 

multiset 的count和erase 返回查找或删除个数

find(x) 多个x的话，find返回中序第一个x

void test_set6()
{
	multiset<int> s;
	s.insert(3);
	s.insert(4);
	s.insert(2);
	s.insert(1);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	s.insert(8);
	s.insert(9);
	set<int>::iterator it = s.begin();    //迭代器打印
	while (it != s.end())
	{
		//*it = 10;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : s)        //范围for打印
	{
		cout << e << " ";
	}
	cout << endl;

	cout << s.count(1) << endl;    //测试count，打印2，因为1有2个
	cout << s.erase(1) << endl;    //测试erase，打印2，因为1有2个
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	auto pos = s.find(3);         // 多个x的话，find返回中序第一个x
	while (pos != s.end())        //从中序第一个3开始打印完整个
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;

}

二、map 

map是Key_val模型的搜索二叉树，insert和[]用法是重点，其他用法参考set        #include<map>

几个map和set的冷知识：

map:

①map是C++98中已存在的，unordered_map是C++11中才有的
②map中都重载了[]运算符，multimap中没有重载[]运算符，set也没有重载[]。
原因：map中key是唯一的，每个key都有与之对应的value，经常需要通过key获取value，因此 map为了形象简单 就重载了[]运算符, multimap中key是可以重复的，如果重载了[]运算符，给定 一个key时，就没有办法返回     value了，因此，multimap中没有重载[]运算符

③map中key不能修改，因为如果修改了就不能保证红黑树的有序特性了
set:

①set中也可以存储键值对，实例化set时，将set中元素类型设置为pair即可

②set默认是升序，但是其内部默认不是按照大于比较，而是按照 less小于比较

less是把小的放左边，所以是升序；greater是把大的放左边，所以是降序

③map和set查询的时间复杂度都是O(log_2N)

解释：map和set的底层结构都是红黑树，而红黑树是近似的平衡二叉搜索树，故查询时间复杂度为O(log_2N)

④map和set底层都是使用红黑树实现的

pair

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代
表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然
有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应
该单词，在词典中就可以找到与其对应的中文含义。
pair 打包了KV模型的key和val两个类型的值，c++不支持返回两个值，也就不知道返回key和val哪一个了，所以干脆打包key和val，返回一个pair结构

make_pair

make_pair 相当于返回了一个pair的匿名对象