一、set

1.set简介和基本用法

set底层的实现就是红黑树

相较于算法中的 find O(N)
set用AVL树实现的find可以达到 O(logN)
用红黑树实现的find可以达到O(2logN)

将数据放入set中后会自动去重排序

2.multiset

相较于set少了去重的部分,可以让数据重复

find,erase等成员删除的都是中序遍历中第一个成员

二、map

1.pair(键值对)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)
	{}
};

2.插入

1
2
3
4
5
map<int, int> m;
m.insert(pair<int, int>(1, 1)); //相当于传入pair临时构造的匿名对象
								//pair构造函数,构造一个匿名对象
m.insert(make_pair(2, 2));      //函数 模板 构造一个pair对象
								//实际上更推荐用make_pair,不用声明模板参数,自动推断

map的插入返回值为

1
2
3
pair<iterator, bool> Insert(const T& data)
//当插入的数在map中没有时,则插入成功,返回插入val的迭代器(引用),和true
//当插入的数在map中已经有了,则插入失败,返回已经和val相同值的迭代器(引用),和false

作为其operator[]的底层

3.operator[]

map用来计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
map<string, int> countmap;
string strs[] = { "iphone","iphone","huawei","honor","huawei","summim" };
for (auto& e : strs)
{
	map<string, int>::iterator ret = countmap.find(e);
	if (ret != countmap.end())
		//(*ret).second++;
		ret->second++;
	else
		countmap.insert(make_pair(e, 1));
}

for (auto& e : countmap)
{
	cout << e.first << ":" << e.second << endl;
}

也可以用operator[]更加便捷

1
2
3
4
5
6
7
8
map<string, int> countmap;
string strs[] = { "iphone","iphone","huawei","honor","huawei","summim" };
for (auto& e : strs)
{
	//如果不在map中,则operator[]会插入pair<str,0> (0 == int() 即默认类型值)  返回映射对象(次数)的引用并且++
	//如果在map中	,则operator[]返回key对应的映射对象(次数)的应用,对其++
	countmap[e]++;
}

operator的底层可以看作为

1
2
3
4
5
6
7
8
9
mapped_type& operator[](const key_type& k)
		{
			return (*((this->insert (make_pair(k, mapped_type()) )).first)).second;
			//this->insert (make_pair(k, mapped_type()) 返回值为 pair<map<string,int>::iterator,bool>
			//.first                                    取 map<string,int>::iterator
			//*											取 pair<key_type,mapped_type>
			//.second									取 mapped_type 并返回其引用
			//返回引用的作用是,方便对其进行以后的操作
		}

所以operator有三种用途
1.插入
2.查找k对应的映射对象
3.修改k对应的映射对象的值

1
2
3
4
5
6
7
8
9
10
map<string, int> countmap;
countmap["vivo"];     //插入
countmap["vivo"] = 1; //修改
cout << countmap["vivo"] << endl; //查找
countmap["oppo"] = 2; //插入+修改

map<string, string> dict;
dict.insert(make_pair("string", "字符串"));
dict["string"] = "字字符串";
dict["sort"] = "排序";

4.multimap

multimap也是去掉了查重的功能,但没有 operator[]
当有多个相同的键值时,不知道返回哪一个对应的val

三、模拟实现set,map

底层都是由红黑树实现的,为了方便了解逻辑,删除了红黑树部分接口

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#pragma once
#include<iostream>
using namespace std;

template <class T, class Ref, class Ptr>
struct __BRTreeIterator
{
	typedef BRTreeNode <T> Node;
	Node* _node;
	typedef __BRTreeIterator<T, Ref, Ptr> Self;
	typedef __BRTreeIterator<T, T&, T*> iterator;
	
	__BRTreeIterator(Node* node)
		:_node(node)
	{}

	//普通迭代器时，是拷贝构造
	//const迭代器，指出迭代器构造const迭代器
	__BRTreeIterator(const iterator& s)
		:_node(s._node)
	{}
	
	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	Self operator++()
	{
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}
			_node = min;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self operator--()
	{
		if (_node->_left)
		{
			Node* max = _node->_left;
			while (max->_right)
			{
				max = max->_right;
			}
			_node = max;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};


template<class K, class T, class KeyOfT>
class BRTree
{
public:
	typedef BRTreeNode<T> Node;
	typedef __BRTreeIterator<T, T&, T*> iterator;
	typedef __BRTreeIterator<T, const T&, const T*> const_iterator;

	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	const_iterator begin() const
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		return const_iterator(left);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}

	pair<iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = Black;
			return make_pair(iterator(_root), true);
		}
		KeyOfT kot;
		//父子节点确定插入的位置
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return make_pair(iterator(cur), false);
		}

		//走到这cur就是要插入的位置
		//cur要连接parent，parent也要连接cur---判断靠kv的大小
		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) > kot(cur->_data))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		while (parent && parent->_col == Red)
		{
			Node* grandparent = parent->_parent;
			//parent分在grandparent左右
			if (grandparent->_left == parent)
			{
				//关键是看uncle节点不存在/红色/黑色的情况
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == Red)
				{
					grandparent->_col = Red;
					parent->_col = uncle->_col = Black;
					.....
					
		return make_pair(iterator(newnode), true);
	}

private:
	Node* _root = nullptr;
};

1.set

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include "RBTree.hpp"

namespace 9TSe
{
	template<class K>
	class Set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};
		typedef typename BRTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename BRTree<K, K, SetKeyOfT>::const_iterator const_iterator;

		pair<iterator, bool> Insert(const K& k)
		{
			return _t.Insert(k);
		}

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		const_iterator begin() const
		{
			return _t.begin();
		}

		const_iterator end() const
		{
			return _t.end();
		}

	private:
		BRTree<K, K, SetKeyOfT> _t;
	};

set内数据本身是不能修改的
否则会破坏树的结构
所以迭代器都是由红黑树的const_iterator构成的

2.map

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include "RBTree.hpp"

namespace 9TSe
{
	template<class K, class V>
	class Map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

		V& operator[](const K& k)
		{
			pair<iterator, bool> ret = Insert(make_pair(k, V()));
			return ret.first->second;
		}

		typedef typename BRTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename BRTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

		pair<iterator, bool> Insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}

		const_iterator begin() const
		{
			return _t.begin();
		}

		const_iterator end() const
		{
			return _t.end();
		}

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

	private:
		BRTree<K, pair<const K, V>, MapKeyOfT> _t;
	};