• _cpp利用红黑树封装实现map和set

    文章目录

    0. 前言

    链接：_cpp 红黑树快速了解底层结构
    上面那篇文章，我们了解了红黑树的底层结构并模拟实现红黑树数据插入；最后我们又验证我们红黑树的准确性。

    这篇文章我们利用红黑树封装实现map和set。

    1. 改造红黑树

    1.1 红黑树节点的定义

    • 因为我们要利用一颗树封装实现map和set，所以我们不能写死。

    • 怎么作那看下面代码。

    enum Colour
{
	RED,
	BLACK
};

template<class T>	//k or pair
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//pair _kv;
	T _date;	//   数据
	Colour _col;

	RBTreeNode(const T& date)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _date(date)
	{}
};


    • 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

    • 我们把模板template改为template; 而T代表k or pair。这样就实现了泛型。

    • 看到这里uu们就很疑惑，那怎么区别那？我们就要借助仿函数（KeyOfT ）-> 支持取出T对象中key的值。

    1.2 红黑树中的迭代器

    • 迭代器大致框架跟list模拟实现不变，变的是++和- -怎么操作。我们知道红黑树的中序遍历可以得到一个有序序列；而我们的加加和减减就是查找中序遍历中某一个节点前后的节点是那个。

    1.2.1 模拟实现前置加加的方法

    在这里插入图片描述

    • 通过上图和根据中序遍历的规则，我们很快就发现两条规律。

      1. 右子树不为空，++就是找右子树中序第一个(最左节点)；

        • 例如：11的下一个节点就是12，根据中序遍历的规则。

      2. 右子树为空，++找孩子不是父亲右的那个祖先。

        • 例如：12的下一个节点就是13，根据中序遍历的规则；而7的下一个节点是8，不是6。

    在这里插入图片描述

    1.2.2 模拟实现前置减减的方法

    在这里插入图片描述

    • 通过上图和根据中序遍历的规则，我们很快就发现两条规律。

      1. 左子树不为空，–就是找右子树中序最后一个(最右节点)；

        • 例如：8的上一个节点就是7，根据中序遍历的规则。

      2. 左子树为空，–找孩子不是父亲左的那个祖先。

        • 例如：15的上一个节点就是13，根据中序遍历的规则；而12的上一个节点是11，而不是13。

    到了这里我们发现–和++恰好相反；后置++与- -我们复用一下前置的就可以实现了。

    1.2.3 红黑树迭代器代码

    template<class T, class Ref, class Ptr>		//T T& T*
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef  __RBTreeIterator<T, Ref, Ptr> Self;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_date;
	}

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


	Self& operator++()
	{
		//思路：左子树的父亲，右子树的父亲的父亲直到找到另一个子树的左节点（模拟中序遍历）

		if (_node->_right)//右子树不为空，下个就是右子树最左节点
		{
			// 下一个就是右子树的最左节点
			Node* left = _node->_right;
			while (left && left->_left)
			{
				left = left->_left;
			}

			_node = left;
		}
		else         // 找祖先里面孩子不是祖先的右的那个
		{
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_right)
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			
			_node = parent;
		}

		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		++(*this);

		return tmp;
	}

	Self& operator--()
	{
		if (_node->_left)
		{
			Node* right = _node->_right;
			while (right && right->_right)
			{
				right = right->_right;
			}

			_node = right;
		}
		else
		{
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_left)
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}

			_node = parent;
		}

		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		--(*this);

		return tmp;
	}

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

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

private:
	Node* _node;

};

    • 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

    1.3 仿函数

    • 因为map是pair; kv型原来的直接比较并插入就失效了，我们就需要借助仿函数来提取map中pair的first值；来进行比较。
    
	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    	template<class k>
	class set
	{
		struct SetKeyOfT
		{
			const k& operator()(const k& key) 
			{
				return key;
			}
		};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    实现过程就在上图代码里了。

    1.4 红黑树整体改造完成后的代码

    #pragma once
#include
#include

using namespace std;
enum Colour
{
	RED,
	BLACK
};

template<class T>	//k or pair
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//pair _kv;
	T _date;	//   数据
	Colour _col;

	RBTreeNode(const T& date)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _date(date)
	{}
};

template<class T, class Ref, class Ptr>		//T T& T*
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef  __RBTreeIterator<T, Ref, Ptr> Self;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_date;
	}

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


	Self& operator++()
	{
		//思路：左子树的父亲，右子树的父亲的父亲直到找到另一个子树的左节点（模拟中序遍历）

		if (_node->_right)//右子树不为空，下个就是右子树最左节点
		{
			// 下一个就是右子树的最左节点
			Node* left = _node->_right;
			while (left && left->_left)
			{
				left = left->_left;
			}

			_node = left;
		}
		else         // 找祖先里面孩子不是祖先的右的那个
		{
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_right)
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			
			_node = parent;
		}

		return *this;
	}
	Self operator++(int)
	{
		Self tmp(*this);
		++(*this);

		return tmp;
	}

	Self& operator--()
	{
		if (_node->_left)
		{
			Node* right = _node->_right;
			while (right && right->_right)
			{
				right = right->_right;
			}

			_node = right;
		}
		else
		{
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_left)
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}

			_node = parent;
		}

		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		--(*this);

		return tmp;
	}

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

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

private:
	Node* _node;

};

// T决定红黑树存什么数据
// set  RBTree
// map  RBTree>
// KeyOfT -> 支持取出T对象中key的仿函数
template<class K, class T, class keyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __RBTreeIterator<T, T&, T*> iterator;
	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		//找到最左，也就是最小值

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


	RBTree()
	{}

	pair<iterator, bool> Insert(const T& date)
	{

		keyOfT kot;
		if (_root == nullptr)
		{
			_root = new Node(date);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}

		//找find
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_date) < kot(date))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_date) > kot(date))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//重复的
				return make_pair(iterator(cur), false);
			}
		}


		//插入
		cur = new Node(date);
		Node* newNode = cur;	//记录一下，最后返回的时候要用。
		cur->_col = RED;

		if (kot(parent->_date) < kot(date))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//调整颜色
		while (parent && parent->_col == RED)	//父母为红，违法规则；才调整
		{
			Node* grandfather = parent->_parent;
			assert(grandfather);
			assert(grandfather->_col == BLACK);
			//关键看叔叔
			//     g
			//   p or p
			// 
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况一: uncle存在且为红，变色＋继续往上调整
				//     g
				//   p   u
				//   c
				if (uncle && uncle->_col==RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else  //uncle || uncle->_col == BLACK
				{
					//情况二、三: uncle存在且为黑或者不存在，变色＋旋转
					if (cur == parent->_left)
					{
						//     g				p
						//   p   u			  c	  g
						//  c						u
						//(g)右单旋＋变色
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//     g             g				c
						//   p   u		   c   u		  p	   g
						//		c		 p	                     u
						//(p)左单旋＋(g)右单旋+ 变色
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else    //parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;

				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else  //uncle || uncle->_col == BLACK
				{
					//情况二、三: uncle存在且为黑或者不存在，变色＋旋转
					if (cur == parent->_right)
					{
						//(g)左单旋＋变色
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//(p)右单旋＋(g)左单旋+ 变色
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;
		return make_pair(iterator(newNode), true);
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col == RED)
		{
			return false;
		}

		//黑色节点数量的基准
		int benchmark = 0;

		return PrecCheck(_root, 0, benchmark);
	}
private:
	bool PrecCheck(Node* root, int blackNum, int& benchmark)
	{
		if (root == nullptr)
		{
			if (benchmark == 0)
			{
				benchmark = blackNum;
				return true;
			}

			if (benchmark != blackNum)
			{
				cout << "某条黑色结点数量不对" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红节点" << endl;
			return false;
		}

		return  PrecCheck(root->_left, blackNum, benchmark)
			&& PrecCheck(root->_right, blackNum, benchmark);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << kot(root->_date) << " ";
		_InOrder(root->_right);
	}

	void RotateR(Node* parent)	//右旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}

		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}

	}

	void RotateL(Node* parent)	//左旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else  //ppNode->_right == parent
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}

	}

	Node* _root = nullptr;
};


    • 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
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
    • 402
    • 403
    • 404
    • 405
    • 406
    • 407
    • 408
    • 409
    • 410
    • 411
    • 412
    • 413
    • 414
    • 415
    • 416
    • 417
    • 418
    • 419
    • 420
    • 421
    • 422
    • 423
    • 424
    • 425
    • 426
    • 427
    • 428
    • 429
    • 430
    • 431
    • 432
    • 433
    • 434
    • 435
    • 436
    • 437
    • 438
    • 439
    • 440
    • 441
    • 442
    • 443
    • 444
    • 445
    • 446
    • 447
    • 448
    • 449
    • 450
    • 451
    • 452
    • 453
    • 454
    • 455
    • 456

    2. 封装实现map

    • 注意：typename的使用–我们要取取类里面的类型而不是变量（例如：类的静态变量）需要说明。
    #pragma once
#include "BR_TREE.h"

namespace Ding
{
	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;

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

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

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));

			return ret.first->second;
		}

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


    • 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

    3. 封装实现set

    • 注意：typename的使用–我们要取取类里面的类型而不是变量（例如：类的静态变量）需要说明。
    #pragma once
#include "BR_TREE.h"

namespace Ding
{
	template<class k>
	class set
	{
		struct SetKeyOfT
		{
			const k& operator()(const k& key) 
			{
				return key;
			}
		};

	public:
		typedef typename RBTree<k, k, SetKeyOfT>::iterator iterator;	//typedef--告诉编译器我们这里取得是类里面的类型而不是变量

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

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

	private:
		RBTree<k, k, SetKeyOfT> _t;
	};
}

    • 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

    4. 测试案例

    /map.h///

    	void test_set()
	{
		set<int> s;

		set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		s.insert(3);
		s.insert(2);
		s.insert(1);
		s.insert(5);
		s.insert(3);
		s.insert(6);
		s.insert(4);
		s.insert(9);
		s.insert(7);


		it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

    • 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

    /set.h///

    	void test_map()
	{
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

		map<string, int> countMap;
		for (auto& str : arr)
		{
			// 1、str不在countMap中，插入pair(str, int()),然后在对返回次数++
			// 2、str在countMap中，返回value(次数)的引用，次数++;
			countMap[str]++;
		}

		map<string, int>::iterator it = countMap.begin();
		while (it != countMap.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}

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

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

    5. 测试结果

    在这里插入图片描述

  • 相关阅读:
    Redis解决超卖问题（一种多线程安全问题） 乐观锁、悲观锁
    第三章：最新版零基础学习 PYTHON 教程（第九节 - Python 运算符—Python 中的除法运算符）
    服装企业ERP系统的基本功能模块
    电脑重装系统Win10关闭网速限制的方法
    手写ngIf，使用视图容器引用ViewContainerRef和模板引用TemplateRef
    网络安全（黑客）自学
    laravel 安装后台管理系统, filament.
    【Python机器学习】零基础掌握VotingClassifier集成学习
    3.3.OpenCV技能树--二值图像处理--图像形态学操作
    数字藏品和NFT的区别
  • 原文地址：https://blog.csdn.net/Dingyuan0/article/details/127718509