【C/C++】C++11 无序关联容器的诞生背景

背景

C++11 引入了无序关联容器（unordered_map、unordered_set、unordered_multimap 和 unordered_multiset）是为了提供一种高效的元素存储和查找方式。相比于有序关联容器（map、set、multimap 和 multiset），无序关联容器的元素是无序存储的，但是插入、查找和删除操作的平均时间复杂度为 O(1)，比有序关联容器更加高效。

无序关联容器的实现方式是基于哈希表的，它们使用哈希函数将元素的键映射到哈希表中的位置，因此可以快速地进行元素的查找、插入和删除操作。而有序关联容器则是基于红黑树实现的，它们的元素是按照键值有序存储的，因此可以进行范围查找和排序等操作。

因此，无序关联容器适用于需要高效地进行元素的查找、插入和删除操作的场景，而有序关联容器则适用于需要有序存储元素的场景。C++11 引入无序关联容器，是为了提供更加灵活和高效的元素存储和查找方式，以满足不同场景下的需求。

无序关联容器适用场景

无序关联容器（unordered_map、unordered_set、unordered_multimap 和 unordered_multiset）适用于需要高效地进行元素的查找、插入和删除操作的场景。由于无序关联容器的实现方式是基于哈希表的，它们使用哈希函数将元素的键映射到哈希表中的位置，因此可以快速地进行元素的查找、插入和删除操作，平均时间复杂度为 O(1)。

无序关联容器适用于以下场景：

1. 需要高效地进行元素的查找、插入和删除操作，而不需要保证元素的顺序。

2. 元素的键值可以使用哈希函数进行计算，且哈希函数的冲突率较低。

3. 元素的数量较大，但是内存空间有限，需要使用哈希表来进行空间优化。

4. 需要对元素进行快速的去重操作。

总之，无序关联容器适用于需要高效地进行元素的查找、插入和删除操作，并且不需要保证元素的顺序的场景。但是，由于哈希表的实现方式，无序关联容器的元素并不是按照它们被插入的顺序存储的，因此在需要有序存储元素的场景下，应该使用有序关联容器。

有序关联容器适用场景

有序关联容器（map、set、multimap 和 multiset）适用于需要有序存储元素的场景。由于有序关联容器的实现方式是基于红黑树的，它们的元素是按照键值有序存储的，因此可以进行范围查找和排序等操作。

有序关联容器适用于以下场景：

1. 需要对元素进行排序或者按照键值进行范围查找的场景。

2. 元素的数量较小，但是需要进行频繁的查找和插入操作。

3. 元素的键值不能使用哈希函数进行计算，或者哈希函数的冲突率较高。

4. 需要保证元素的顺序。

总之，有序关联容器适用于需要有序存储元素的场景，并且需要进行排序或者按照键值进行范围查找的场景。但是，由于红黑树的实现方式，有序关联容器的插入、查找和删除操作的平均时间复杂度为 O(log n)，比无序关联容器更加低效。因此，在需要高效地进行元素的查找、插入和删除操作的场景下，应该使用无序关联容器。