C++0x unordered_map/unordered_set - Faith and Brave

C++0x では、 unordered_map と unordered_set という連想コンテナが追加されます。
(unordered_multimap, unordered_multiset もあります)

map と set は二分木を使用した連想コンテナですが
unordered_map と unordered_set はハッシュ表を使用した連想コンテナです。

namespace std {
    // <unordered_map>
    template <class Key,
              class T,
              class Hash = hash<Key>,
              class Pred = std::equal_to<Key>,
              class Alloc = std::allocator<std::pair<const Key, T> > >
    class unordered_map;

    // <unordered_set>
    template <class Value,
              class Hash = hash<Value>,
              class Pred = std::equal_to<Value>,
              class Alloc = std::allocator<Value> >
    class unordered_set;
}

使い方は、 map/set とほとんど同じ

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main()
{
    unordered_map<string, int> m;

    m["Akira"]  = 23;
    m["Johnny"] = 38;
    m["Millia"] = 16;

    cout << m["Akira"] << endl; // 23
}

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int main()
{
    unordered_set<string> s;

    s.insert("Akira");
    s.insert("Johnny");
    s.insert("Millia");

    cout << s.size() << endl; // 3
}

ハッシュ表の名前はいろいろ候補があったみたいです。
hash_set, hased_set, hash::set, hash_table::set, bag_set, unsorted_set ...

N1836 Draft Technical Report on C++ Library Extensions

N1456 A Proposal to Add Hash Tables to the Standard Library (revision 4)

C++0x言語拡張まとめ