C++常用的无序的关联容器

常用的无序关联容器

在实际问题场景中，除了常见的线性表结构，字符串，排序操作之外，散列表和红黑树也是非常常见的，有很多应用场景都会用到它们。

• 散列表虽然比较占空间，但是它的增删查的都很快，趋近于O(1)；
• 红黑树也是一颗二叉排序树，所以入红黑树的数据都是经过排序的，它的增删查时间复杂度都是O() ，对数时间，比哈希表慢

但是如果问题场景对数据的有序性有所要求，而且增删查的操作都比较多，那么就适合用红黑树结构，哈希表里面的数据是无序的。

以链式哈希表作为底层数据结构的无序关联容器有：
unordered_set、unordered_multiset、unordered_map、unordered_multimap，对比如下：

set只存储key，底层是哈希表，经常用来大数据查重复值或者去重复值；

map存储key,value对，经常用来做哈希统计，统计大数据中数据的重复次数，当然它们的应用很广，不仅仅用在海量数据处理问题场景中。

下列代码以unordered_set和unordered_map做一些代码演示

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int main(){
	// 不允许key重复 改成unordered_multiset自行测试
	unordered_set<int> set1; 
	for (int i = 0; i < 100; ++i){
		set1.insert(rand()%100+1);
	}
	cout << set1.size() << endl;

	// 寻找是否存在20并删除
	auto it1 = set1.find(20);
	if (it1 != set1.end()){
		set1.erase(it1);
	}

	// count返回set中有几个50=》最多是1个
	cout << set1.count(50) << endl;
	return 0;
}

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main(){
	// 定义一个无序映射表
	unordered_map<int, string> map;
	// 无序映射表三种添加[key,value]的方式
	map.insert({ 1000, "aaa" });
	map.insert(make_pair(1001, "bbb"));
	map[1002] = "ccc";

	// 遍历map表1
	auto it = map.begin();
	for (; it != map.end(); ++it){
		cout << "key:" << it->first << " value:" << it->second << endl;
	}
  
	// 遍历map表2
	for (pair<int, string> &pair : map){
		cout << "key:" << pair.first << " value:" << pair.second << endl;
	}

	// 查找key为1000的键值对，并且删除
	auto it1 = map.find(1000);
	if (it1 != map.end()){
		map.erase(it1);
	}

	return 0;
}

#include <iostream>
#include <string>
#include <unordered_map>
int main(){
	std::unordered_map<std::string, std::string> mymap =
    {
		{ "house", "maison" },
		{ "apple", "pomme" },
		{ "tree", "arbre" },
		{ "book", "livre" },
		{ "door", "porte" },
		{ "grapefruit", "pamplemousse" }
	};
    
	unsigned n = mymap.bucket_count(); //获取哈希桶的个数
	std::cout << "mymap has " << n << " buckets.\n";
    
	for (unsigned i = 0; i < n; ++i) {
    // 逐个遍历哈希桶中的链表
		std::cout << "bucket #" << i << " contains: ";
		for (auto it = mymap.begin(i); it != mymap.end(i); ++it)
			std::cout << "[" << it->first << ":" << it->second << "] ";
		std::cout << "\n";
	}

	return 0;
}