set和map简单使用

写在前面

我们现在可以看一下map和set的相关知识了.这里我们先来看看他们的用法,最关键的是如何把他它给模拟实现出来,不过这个应该是下一个博客,那个是红黑树.比这个更难.map和set的底层是一个红黑树,后面我们就会实现.

set 使用

前面我们谈过数据模型,其中set就是K模型.这里先不探究底层,否则的话今天我们都会疯的.先来看一下标准库是如何描述set的.这里我先和大家说明一下,使用set就是排序加上去重,至于原因,后面和大家分析.

这里的模板参数大家应该都不陌生,这里就不加解释了.先来定义一个set类型的数据结构,至于方法都是后面的事了/

#include 

using namespace std;

int main()
{
	set<int> s;
	return 0;
}
1
2
3
4
5
6
7
8
9

构造函数

我们首先要看一下按构造函数,set的构造函数提供了三种.我们前面已经用了一种了,第二种是迭代器区间构造,而且第二个参数还是一个仿函数对象,这是我们插入数据排序的时候用的.

迭代器

这里我们先来看用法,底层不追究,这个的实现有一定的难度.不过用法和我们之前的一样.这里直接看一下.这是个双向迭代器,也就是支持++或者–.这里只做普通的演示.

int main()
{
	set<int> s;
	s.insert(1);
	s.insert(3);
	s.insert(2);
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我来解释一下set的特性,这个对我们很重要.我们插入的元素是不能被修改.想一想我们前面的搜索二插树,如果允许我们修改值了,那么请问还构成搜索二叉树吗,反正我是不能确定.

int main()
{
	set<int> s;
	s.insert(1);
	s.insert(3);
	s.insert(2);
	auto it = s.begin();
	while (it != s.end())
	{
		*it = 10;
		cout << *it << " ";
		++it;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

也就是我们看似存在了两个迭代器,实际上就是一个const修饰的.

insert()

我们先来看数据的插入.一般不是线性表的数据结构,插入数据的方法一般就是insert,set也是如此.前面我们已经用了一种,这里我们重点关注一下第二个的使用方法.

我们这个函数的使用倒是没有太大的问题,主要是返回值的问题.这里第一个insert的放回置好象是一个我们没有见过的类型,这个主要是为了后面的map使用.这里我们先简单的了解一下.pair是一个标准库自定的类型,其中有两个模板参数,而且这里还给实例化出来了.

我们先来简单的使用一下,分别看一下这两个模板参数的作用.这里我们先来解释第一个,第一个就是我们插入插入元素对应的迭代器,后面的bool类型等着后面再考虑.后面的map就需要专门和大家细细分析一下.

int main()
{
	set<int> s;
	auto it = s.insert(1);
	s.insert(1);
	return 0;
}
1
2
3
4
5
6
7

erase()

删除元素也是挺简单的,这里注意参数就可以了,而且也不用太考虑迭代器失效的问题,主要是我们一般用第二个函数

int main()
{
	set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(2);
	s.insert(3);
	for (const int& val : s)
	{
		cout << val << " ";
	}
	cout << endl;
	s.erase(2);
	for (const int& val : s) // 为何 是 const引用 实现的时候再说
	{
		cout << val << " ";
	}
	cout << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

count()

这个函数比较有趣,就是记录set中存在某一个元素的个数,在set中一般是很少用到的,但是后面的一个目录set就不错,等下和大家提一下.

int main()
{
	set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(2);
	s.insert(3);
	cout << s.count(1) << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10

multiset 认识

这个也是一个set类型的数据结构,只不过支持重复插相同的元素,一些方法和我们set是一样的.这个我们就谈谈count就可以了.

int main()
{
	multiset<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(2);
	s.insert(3);
	cout << s.count(2) << endl;
	for (const int& val : s)
	{
		cout << val << " ";
	}
	cout << endl;


	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

map使用

我们前面是认识过KV模型的，这里我们要谈到的map就是一个典型代表.我们要谈的主要有两个,一个就是insert,另外一个就是运算符重载,其余的我们都不看,用法都差不多.

map也是我们比较常用的数据结构,一般而言,我们通过key来进行插入时的比较,V用来存放数据,这里的V可变,但是K是不能变的.

pair

在谈之前,我们先来看一下pair这个类型,这是标准库里面定义的一种类型,是一个类模板,结构就是类似下面的样子.我们先不关心,等到用到时候就会知道了.

template<class T1,class T2>
struct pair
{
	T1 fiest;
	T2 second;
};
1
2
3
4
5
6

准确来说,是下面这样定义的.

insert()

下面就是map的插入,我们县来看看用法.

int main()
{
	map<int, int> m;
	m.insert(std::pair<int, int>(1, 1));  //两种用法,哪一个都行
	m.insert(make_pair(2,2));

	return 0;
}
1
2
3
4
5
6
7
8

operator[]

这个运算符可是我们set当中没有的,这个作用可就大了去了,首先我们要明白一点,在map中,我们是修改不了K的,但是V可以修改,下面就是我们要谈的.

int main()
{
	map<string, string> m;
	m.insert(pair<string, string>("peach", "桃子"));
	m.insert(pair<string, string>("left", "左边"));
	map<string, string>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << (*it).first <<" " << it->second << endl;
		it++;
	}
	cout << "=======================" << endl;
	auto find = m.find("left");
	if (find != m.end())
	{
		find->second = "剩余";
	}

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

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

那么这里就有疑惑了,我们可以修改V值.但是关这个运算符什么事?你不觉得这样写优点麻烦吗.看一下下面的.

int main()
{
	map<string, string> m;
	m.insert(pair<string, string>("peach", "桃子"));
	m.insert(pair<string, string>("left", "左边"));
	map<string, string>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << (*it).first <<" " << it->second << endl;
		it++;
	}
	cout << "=======================" << endl;

	m["left"] = "剩余";

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

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这里我们就可以看一下这个运算符的原理了,看一下截图你就会明白了,后面我们逐步剖析.

我们知道insert是会返回一个pair的这个pair就是我们的重点,里面的first就就是我们插入元素的迭代器,我们可以通过迭代器来找到对应的V值.也就是下面的原理.

mapped_type& operator[](const key_type& k)
{
	pair<iterator,bool> ret = insert(make_pair(k,mapped_type()));
	return ret.fiest->second;
}
1
2
3
4
5

这里先我们解释一下前面的迭代器里面的布尔类型,这里面就有点学问了.如果我们元素插入成功了,那么bool值就是true,否则就是false.而我们平常遇到插入不成功情况一般就是里面存在相同的key值了.

int main()
{
	map<string, string> m;
	auto ret1 = m.insert(pair<string, string>("left", "左边"));
	auto ret2 = m.insert(pair<string, string>("left", "剩余"));

	return 0;
}
1
2
3
4
5
6
7
8

那么这里就存在点意思了,我们需要更好的理解一下这个重载的运算符了.

mapped_type& operator[](const key_type& k)
{
	pair<iterator,bool> ret = insert(make_pair(k,mapped_type()));
	return ret.fiest->second;
}
1
2
3
4
5

先来解释数据类型,看一下下面的截图就会明白了.这里我们先暂时把T看作V,后面实现的时候在专门分享.

也就是说在insert中第二个参数就是我们前面的V,这里会自动生成一个匿名对象,对于int,那么就是0,其他的类型自动调用自己的默认构造函数.

这里再讨论两个情况,假设我们插入的key值不存在,那么这里就是直接插入,我们返回的V可以在外面直接赋值,要是我们插入的key值存在,这里就会出现简单的搜索问题,而且返回值就是V,我们可以修改,这就是重载这个运算符的好处.