unordered_map

C++11 STL Boost

---

unordered_map

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

　　std::unordered_map与 std::map的区别就是，std::map是按照operator<比较判断元素是否相同，以及比较元素的大小，然后选择合适的位置插入到树中。所以，如果对map进行遍历（中序遍历）的话，输出的结果是有序的。顺序就是按照operator< 定义的大小排序。而std::unordered_map是计算元素的Hash值，根据Hash值判断元素是否相同。所以，对std::unordered_map进行遍历，结果是无序的。
　　用法的区别就是，std::map 的key需要定义operator< 。 而std::unordered_map需要定义hash_value函数并且重载operator==。对于内置类型，如std::string，这些都不用操心。对于自定义的类型做key，就需要自己重载operator< 或者hash_value()了。
　　最后，说，当不需要结果排好序时，最好用std::unordered_map。

unordered_map::unordered_map

explicit unordered_map ( size_type n = /* see below */,
                         const hasher& hf = hasher(),
                         const key_equal& eql = key_equal(),
                         const allocator_type& alloc = allocator_type() );
explicit unordered_map ( const allocator_type& alloc );
template <class InputIterator>
    unordered_map ( InputIterator first, InputIterator last,
                  size_type n = /* see below */,
                  const hasher& hf = hasher(),
                  const key_equal& eql = key_equal(),
                  const allocator_type& alloc = allocator_type() );
unordered_map ( initializer_list<value_type> il,
                size_type n = /* see below */,
                const hasher& hf = hasher(),
                const key_equal& eql = key_equal(),
                const allocator_type& alloc = allocator_type() );

example

#include <iostream>
#include <string>
#include <unordered_map>
typedef std::unordered_map<std::string,std::string> stringmap;
stringmap merge (stringmap a,stringmap b) {
  stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
}
int main ()
{
  stringmap first;                              // empty
  stringmap second ( {{"apple","red"},{"lemon","yellow"}} );       // init list
  stringmap third ( {{"orange","orange"},{"strawberry","red"}} );  // init list
  stringmap fourth (second);                    // copy
  stringmap fifth (merge(third,fourth));        // move
  stringmap sixth (fifth.begin(),fifth.end());  // range
  std::cout << "sixth contains:";
  for (auto& x: sixth) std::cout << " " << x.first << ":" << x.second;
  std::cout << std::endl;
  return 0;
}

unordered_map::at

mapped_type& at ( const key_type& k );
const mapped_type& at ( const key_type& k ) const;

unordered_map::operator[]

mapped_type& operator[] ( const key_type& k );
mapped_type& operator[] ( key_type&& k );

unordered_map::bucket

size_type bucket ( const key_type& k ) const;
//Locate element's bucket
size_type bucket_count() const noexcept;
//return number of buckets
size_type bucket_size ( size_type n ) const;
//returns the number of elements in bucket n.

unordered_map::count

size_type count ( const key_type& k ) const;
//count elements with a specific key

unordered_map::emplace

template <class... Args>
    pair<iterator, bool> emplace ( Args&&... args );
//就地构造新的元素<k,v>，如果k尚未在unorder_map中出现，即插入<k,v>

example

#include <iostream>
#include <string>
#include <unordered_map>
int main ()
{
  std::unordered_map<std::string,std::string> mymap;
  mymap.emplace ("NCC-1701", "J.T. Kirk");
  mymap.emplace ("NCC-1701-D", "J.L. Picard");
  mymap.emplace ("NCC-74656", "K. Janeway");
  std::cout << "mymap contains:" << std::endl;
  for (auto& x: mymap)
    std::cout << x.first << ": " << x.second << std::endl;
  std::cout << std::endl;
  return 0;
}

unordered_map::emplace_hint

template <class... Args>
iterator emplace_hint ( const_iterator position, Args&&... args );

与emplace的功能基本一致，就地生成新元素，若k尚未出现在unordered_map中即插入，插入新元素时有一个hint提示位置，告诉函数从给定的位置查找的插入位置，这样可以提高速度，但是hint给出的迭代器可能不能使得优化插入速度，函数就不会使用。通常还是使用上述的emplace即可。

unordered_map::insert

pair<iterator,bool> insert ( const value_type& val );
//typedef pair<const Key, T> value_type;
template <class P>
    pair<iterator,bool> insert ( P&& val );
iterator insert ( const_iterator hint, const value_type& val );
template <class P>
    iterator insert ( const_iterator hint, P&& val );
template <class InputIterator>
    void insert ( InputIterator first, InputIterator last );
void insert ( initializer_list<value_type> il );

example

#include <iostream>
#include <string>
#include <unordered_map>
int main ()
{
  std::unordered_map<std::string,double>
              myrecipe,
              mypantry = {{"milk",2.0},{"flour",1.5}};
  std::pair<std::string,double> myshopping ("baking powder",0.3);
  myrecipe.insert (myshopping);                        // copy insertion
  myrecipe.insert (std::make_pair<std::string,double>("eggs",6.0)); // move insertion
  myrecipe.insert (mypantry.begin(), mypantry.end());  // range insertion
  myrecipe.insert ( {{"sugar",0.8},{"salt",0.1}} );    // initializer list insertion
  std::cout << "myrecipe contains:" << std::endl;
  for (auto& x: myrecipe)
    std::cout << x.first << ": " << x.second << std::endl;
  std::cout << std::endl;
  return 0;
}

unordered_map::public member function

      iterator begin() noexcept;
const_iterator begin() const noexcept;

      local_iterator begin ( size_type n );
const_local_iterator begin ( size_type n ) const;

      iterator end() noexcept;
const_iterator end() const noexcept;

      local_iterator end (size_type n);
const_local_iterator end (size_type n) const;

const_iterator cbegin() const noexcept;
const_local_iterator cbegin ( size_type n ) const;

const_iterator cend() const noexcept;
const_local_iterator cend ( size_type n ) const;

iterator erase ( const_iterator position );
size_type erase ( const key_type& k );
iterator erase ( const_iterator first, const_iterator last );

      iterator find ( const key_type& k );
const_iterator find ( const key_type& k ) const;

void rehash( size_type n ); //set number of buckets
void reserve ( size_type n ); //request a capacity change
size_type size() const noexcept; //return container size

bool empty() const noexcept