无序容器的使用

STL

STL中无序容器主要有unordered_set和unordered_map，其主要的功能和set与map差不太多，最大的特点就是其中的关键值是无序的，但是基本上所有的操作都是常数复杂度的。其内部主要是由哈希表实现，所以构造和析构的速度比有序容器稍慢。

以unordered_map为例

1. begin 返回指向容器第一个元素的迭代器，但并不是最小的哈。注意map和unordered_map的迭代器都是指向一个pair的
2. end 返回指向容器尾端的迭代器，这两个迭代器的返回，主要是用于遍历整个unordered_map
3. empty 检查容器是否为空
4. size 返回容纳的元素数
5. clear 删除全部内容
6. insert 插入元素。注意map和unordered_map的插入，都是插入一个pair
7. emplace 就地构造元素，和insert功能相似，但是是直接给构造函数传参数。emplace在C++11 STL中基本上都能使用
8. erase 删除元素，可以删除关键值，也可以删除迭代器
9. []操作符，和map的[]操作符相同，返回的为引用值，可以被修改。注意使用[]的时候，如果[]的关键值在容器中不存在，则会插入该关键值，对应的映射值为默认值。如果随意的使用[]，回造成大量的插入操作，减慢运行速度，甚至会造成MLE
10. count 返回匹配特定键的元素数量, 返回值一定是0或者1，在不知道关键值是否存在的情况下，可以先count一下，再使用[]
11. find 寻找带有特定键的元素的迭代器

由于unordered_map内部使用hash表，所以对于关键值，必须要存在hash函数和判等运算符。好在系统已经内置了所有基础数据类型和string的hash函数和判等运算符。可以直接把他们作为关键值。对于其他类型，暂不予讨论。

unordered_map是C++11新加入的标准容器，所以需要编译器有-std=gnu++11选项。除了#include无需包含其他的头文件。
以PowerOJ2436为例。
C++11代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        int cnt = 0;
        unordered_map<string, int> m;
        while (n--)
        {
            char s[12];
            scanf("%s", s);
            auto it = m.find(s);\\这里隐式调用了string的构造函数
            int ans;
            if (it == m.end())
                m[s] = ans = ++cnt;\\这里也隐式调用了string的构造函数
            else
                ans = it->second;   \\迭代器指向的是pair<string,int>
            printf("%d\n", ans);
        }
    }
    return 0;
}

但是并不是没有C++11就没法用这个容器了，需要包含tr1中的头文件和使用命名空间。
C++98代码：

#include<bits/stdc++.h>
#include<tr1/unordered_map> \\在tr1库中有这个容器
using namespace std;
using namespace std::tr1;   \\需要使用这个命名空间
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        int cnt = 0;
        unordered_map<string, int> m;   \\其他操作和C++11的无区别，只是没有了emplace
        while (n--)
        {
            char s[12];
            scanf("%s", s);
            unordered_map<string, int>::iterator it = m.find(s);
            int ans;
            if (it == m.end())
                m[s] = ans = ++cnt;
            else
                ans = it->second;
            printf("%d\n", ans);
        }
    }
    return 0;
}