在c++中有两个关联容器,一个是map,另一个是unordered_map。下面说一下他们之间内部实现机理。
 
一、map和unordered_map的实现机理:
map:是基于红黑树来实现的(红黑树是非常严格的平衡二叉搜索树),红黑树具有自动排序功能,红黑树的每一个节点都代表着map中的一个元素,因此对于map的查找,删除和插入操作都是对红黑树的操作。
unordered_map:是基于哈希表来实现的,查找的时间复杂度是O(1),在海量数据处理中有着广泛的应用。
 
二、map和unordered_map的优缺点
map的优点:(1)map是有序的(2)基于红黑树实现,查找的时间复杂度是O(n)
map的缺点:空间占用率比较高,因为内部实现了红黑树,虽然提高了运行效率,但是每个节点都要保存父亲节点和孩子节点和红黑树的性质,使得每一个节点都占用大量的空间。
适用的情况:对于要有序的结构,适用map
unordered_map的优点:因为内部是哈希表来实现的,所以查找效率会非常高
unordered_map的缺点:哈希表的建立比较费时
适用的情况:对于查找问题,适用unordered_map会更好一点。

三、map的常用操作

/*map中常用的操作
*begin()	还回指向map头部的迭代器
*clear()	删除所有元素,注意是所有元素
*count()	还回指定元素出现的次序
*empty()	如果map为空则还回true
*end()		还回指向map末尾的迭代器
*erase()	删除一个元素
*find()		查找一个元素
*insert()	插入一个元素
*max_size()	还回可以容纳的最大元素个数
*size()		还回map中元素的个数
*swap()		交换两个map
*/

int main() {
	map<int, char> m;
	//一、数据的插入
	m.insert(pair<int, char>(1, 'a'));
	m.insert(pair<int, char>(3, 'b'));
	m.insert(pair<int, char>(2, 'c'));
	m.insert(pair<int, char>(-1, 'd'));
	map<int, char>::iterator it = m.begin();
	for (; it != m.end(); it++) {
		cout << it->first << ":" << it->second << endl;
	}
	//二、数据的查找
	/*(1)使用find()函数,该函数可以找到key对应的value
	(2)使用count()函数,该函数的还回值只有0和1,1为找到,但是还回要查找的值*/
	it = m.find(1);
	if (it != m.end()) { cout << "find" << it->second << endl; }
	else { cout << "not find" << endl; }

	//三、map的清空
	//m.clear(m.begin(), m.end());

	//四、数据的删除
	//m.erase(it);

	//五、map的反向遍历,使用反向迭代容器
	
	for (map<int, char>::reverse_iterator Rit = m.rbegin(); Rit!=m.rend(); Rit++) {
		cout << Rit->first << ":" << Rit->second;
	}
	return 0;
}

反向代理容器的原理:
在这里插入图片描述
四、按照Value排序
  把map中的元素放到vector中,然后对vector进行排序。

bool Vcmp(pair<int,int> p1,pair<int,int> p2) {
	return p1.second < p2.second;
}
int main() {
	map<int, int> m;
	m[0] = 1;
	m[1] = 1;
	m[2] = 5;
	m[3] = 4;
	map<int, int>::iterator it;
	for (it=m.begin(); it != m.end(); it++) {
		cout << it->first << ":" << it->second;
	}
	cout << endl;
	vector<pair<int, int>> vec(m.begin(), m.end());
	sort(vec.begin(),vec.end(),Vcmp);
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i].second << endl;
	}
	return 0;
}
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐