unordered_map

Ⅰ.unordered_map

从C++11 开始，标准库又引入了一类容器，即无序关联式容器。无序关联式容器，又称哈希容器（unordered_map 容器），直译过来就是 “无序 map 容器” 的意思。所谓 “无序”，指的是 unordered_map 容器不会像 map 容器那样对存储的数据进行排序。
换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。
具体来讲，unordered_map 容器和 map 容器一样，以键值对，即 pair类型 的形式存储数据，存储的各个键值对的键互不相同且不允许被修改。
但由于 unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。 因为，无序容器是 C++ 11 标准才正式引入到 STL 标准库中的，这意味着如果要使用该类容器，则必须选择支持 C++ 11 标准的编译器。
需要注意的是：map和unordered_map有本质上的不同：关联式容器的底层实现采用的树存储结构，更确切的说是红黑树结构；无序容器的底层实现采用的是哈希表的存储结构。
总的来说，实际场景中如果涉及大量遍历容器的操作，建议首选关联式容器；反之，如果更多的操作是通过键获取对应的值，则应首选无序容器。

特点：基于底层实现采用了不同的数据结构，因此和关联式容器相比，无序容器具有以下 2 个特点：

• 无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键。
• 和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 \(O(1)\)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。

#include<bits/stdc++.h>
using namespace std;

unordered_map<int,int>mp1; 

int main(){
    mp1[43] = 123;
    mp1[1] = 1234;
    for(unordered_map<int,int>::iterator it = mp1.begin();it != mp1.end();it++){
        cout<<it->first<<" "<<it->second<<endl;
    }
    return 0;
}

STL 迭代器有的可以自减，有的不可以；比如 unordered_map 的迭代器是不可以自减的。