//  unordered associative containers


//  it was proposed in 1995, but there was no enough time 
//  finishing the standard

//  unordered_map
//  unordered_multimap
//  unordered_set
//  unordered_multiset

//  not to use "hash" to avoid name-collition


//  example: hashig by "hand"

#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
using std::tr1::array;
using std::copy;
using std::find;
using std::ostream_iterator;
using std::list;
using std::cout;
using std::setw;
using std::numeric_limits;


typedef list<int> bucket;
typedef array<bucket, 5> table;


size_t hash(int i)
{ // return hash value for i
  return i;
}

void show(const table& tbl)
{ // show contents of buckets in table
  for (int i = 0; i < tbl.size(); ++i)
  { // show contents of bucket i
    cout << "bucket " << setw(2) << i << ": ";
    copy(tbl[i].begin(), tbl[i].end(),
      ostream_iterator<int>(cout, " "));
    cout << '\n';
  }
}

void insert(table& tbl, int val)
{ // insert val into table
  size_t hash_val = hash(val) % tbl.size();
  tbl[hash_val].push_back(val);
}

bool contains(const table& tbl, int val)
{ // return true if tbl contains val
  int hash_val = hash(val) % tbl.size();
  bucket::const_iterator first = tbl[hash_val].begin();
  bucket::const_iterator last = tbl[hash_val].end();
  return find(first, last, val) != last;
}

void report(const table& tbl, int val)
{ // report whether tbl contains val
  cout << "table "
    << (contains(tbl, val) ? "contains "
       : "does not contain ")
    << val << '\n';
}

int main()
{ // demonstrate simple hash table
  table tbl;
  insert(tbl, 3);
  insert(tbl, 195);
  insert(tbl, 5);
  insert(tbl, 6);
  insert(tbl, 55);
  insert(tbl, 1);
  insert(tbl, 33);
  insert(tbl, 40);
  show(tbl);
  report(tbl, 3);
  report(tbl, 4);
  return 0;
}


//  unordered containers, not reversible, no rbegin(), rend()

template <class Key, class T,
            class Hash = hash<Key>,
            class Pred = equal_to<Key>,
            class Alloc = allocator< pair<const Key,T> >
         >
class unordered_map     // unordered_multimap ...
{
    typedef key_type    Key;
    typedef key_equal   Pred;
    typedef hasher      Hash;

    typedef local_iterator  ...;        // iterate in the bucket
    typedef const_local_iterator ...;   // ...

};



    X(n, hf, eq);   // min n bucket, hf hasher, eq key_equal
    X x(n, hf, eq); // no objects, time = O(n)

    X(n, hf);       // min n bucket, hf hasher, eq = key_equal() 
    X x(n, hf);     // no objects, time = O(n)

    X(n);           // hf = hasher(), eq = key_equal()
    X a(n);         // no objects, time = O(n)

    X();            // unspecified number of buckets
    X a;            // no objects, time = O(1)

    X a(first, last, n,  hf, eq);   // O(n), worst_case = O(n*n)
    ...
    X b(a);         // O(b.size()) worst_case = O(b.size()*b.size())
    a = b;          // O(b.size()) worst_case = O(b.size()*b.size())


    a.insert(t);        // returns: pair<X::iterator,bool>
    a.insert(iter, t);
    a.insert(it1, it2);


    a.erase(k)          // returns size_type
    a.erase(q);
    a.erase(it1,it2);   // not necessarry in the same bucket
    a.clear();


    b.find(k);          // const and non-const versions...
    b.count(k);
    b.equal_range(k);   // no lower_bound() and upper_bound()


    b.hash_function();
    b.key_eq();

    b.bucket_count();   // returns size_type: the # of bucket in b
    b.max_bucket_count();

    b.bucket(k);        // index of the bucket to hold k
    b.bucket_size(n);   // size of the n-th bucket

    b.begin(n);         // returns local_iterator
    b.end(n);

    b.load_factor();     // float: average # of objects per bucket
    b.max_load_factor(); // target load factor

    b.max_load_factor(n); // sets target load factor
    b.rehash(n);          // resizes the container to min n bucket
                          // and at most max load factor


//  exception safety:

clear();    // no exception
erase();    // no exception unless hasher and equal_to
insert();   // atomic unless hasher
swap();     // no exception unless copy !!!!
rehash();   // atomic unless hasher or equal_to



#include <functional>
#include <iostream>
#include <string>
#include <iterator>
#include <vector>
using std::tr1::hash;
using std::cout; using std::string;
using std::vector; using std::iterator_traits;

template <class InIt>
void show_hashes(InIt first, InIt last)
{ // demonstrate use of hash<Ty>
  typedef typename
    iterator_traits<InIt>::value_type type;
  hash<type> hasher;
  while (first != last)
    cout << hasher(*first++) << ' ';
  cout << '\n';
}

struct coord
{ // two-dimensional integer coordinates
  int x, y;
};

namespace std {
namespace tr1 { // put specialization in std::tr1
template <>
struct hash<coord>
{ // template specialization for struct coord
  std::size_t operator()(const coord& val) const
  { // return hash value for val
    hash<int> make_hash;
    return make_hash(val.x) + make_hash(val.y);
  }
};
} }

#define SIZE(arr) (sizeof(arr) / sizeof(*arr))

int main()
{ // demonstrate use and specialization of hash<Ty>
  int data[] = { 1, 2, 3, 4, 5 };
  show_hashes(data, data + SIZE(data));

  char *text[] = { "1", "2", "3", "4", "5" };
  vector<string> strings(text, text + SIZE(text));
  show_hashes(strings.begin(), strings.end());

  coord points[] = { { 0, 0 }, { 0, 1 }, { 1, 0 },
    { 1, 1 }, { 2, 2 } };
  show_hashes(points, points + SIZE(points));
  return 0;
}


#include <unordered_map>
#include <iostream>
#include <ostream>
#include <iomanip>
#include <string>
#include <utility>
#include <algorithm>
#include <iterator>
#include <functional>
using std::tr1::unordered_multimap;
using std::string; using std::make_pair; using std::pair;
using std::setw; using std::setfill;
using std::copy; using std::cout;
using std::basic_ostream; using std::ostream_iterator;
using std::ios_base; using std::ios;
using std::unary_function;

typedef unordered_multimap<string, string> dictionary;
typedef dictionary::value_type element;

static const char *pairs[] =
  { // English/German word pairs
  "day",      "Tag",
  "strange",  "fremd",
  "car",      "Auto",
  "smart",    "elegant",
  "trait",    "Merkmal",
  "strange",  "seltsam",
  "smart",    "raffiniert",
  "smart",    "klug",
  "clever",   "raffiniert",
  0,            0
  };

namespace std { // add inserter to namespace std
template <class Elem, class Traits>
basic_ostream<Elem, Traits>& operator<<(
  basic_ostream<Elem, Traits>& str, const element& elt)
  { // insert element into stream and restore flags
  ios_base::fmtflags flags = str.flags();
  str.setf(ios::left, ios::adjustfield);
  str << ' ' << setw(10) << elt.first << elt.second;
  str.flags(flags);
  return str;
  }
}

template <class InIt, class OutIt, class Pred>
OutIt copy_if(InIt first, InIt last, OutIt dest, Pred pr)
{ // copy elements for which pr(*first) is true
  for ( ; first != last; ++first, ++dest)
    if (pr(*first))
      *dest = *first;
  return dest;
}

struct equals
  : unary_function<element, bool>
{ // callable type that matches second object in pair to string
  equals(const string& s) : str(s) {}
  bool operator()(const element& elt) const
  { // return true for match
    return elt.second == str;
  }
private:
  string str;
};

int main()
{ // demonstrate use of unordered_multimap
  dictionary dict;

    // initialize:
  const char **cur = pairs;
  while (cur[0])
  { // add initial entries
    dict.insert(make_pair(cur[0], cur[1]));
    cur += 2;
  }

    // print out all elements
  ostream_iterator<element> output(cout, "\n");
  cout << make_pair("English", "German") << '\n';
  cout << setfill('-') << setw(20) << ""
    << setfill(' ') << '\n';
  copy(dict.begin(), dict.end(), output);

    // print out all values for key "smart"
  string key("smart");
  cout << '\n' << key << ": \n";
  copy(dict.lower_bound(key), dict.upper_bound(key),
    output);

    // print out all keys for value "raffiniert"
  string value("raffiniert");
  cout << '\n' << value << ": \n";
  copy_if(dict.begin(), dict.end(),
    output, equals(value));
  return 0;
}


#include <unordered_set>
#include <iostream>
using std::tr1::unordered_set;
using std::cout;

typedef unordered_set<int> iset;

static void show_details(const iset& set)
{ // show container properties
  cout << "load factor: " << set.load_factor()
    << " target load factor: " << set.max_load_factor()
    << " buckets: " << set.bucket_count() << '\n';
}

int main()
{ // show growth pattern
  iset set;
  show_details(set);
  int i;
  for (i = 0; i < 20; ++i)
    set.insert(i);
  show_details(set);
  for ( ; i < 40; ++i)
    set.insert(i);
  show_details(set);
  for ( ; i < 60; ++i)
    set.insert(i);
  show_details(set);
  set.max_load_factor(2.0);
  show_details(set);
  set.rehash(10);
  show_details(set);
  set.rehash(30);
  show_details(set);
  return 0;
}



//  tuning

#include <unordered_set>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
using std::cout; using std::setw;
using std::copy; using std::ostream_iterator;

typedef std::tr1::unordered_set<int> iset;
typedef iset::value_type elt;

static void show_buckets(const iset& set)
{ // show details of buckets in set
  cout << setw(3) << set.size() << " elements, "
    << setw(3) << set.bucket_count() << " buckets, "
    << " load factor " << set.load_factor() << ".\n";
  for (int i = 0; i < set.bucket_count(); ++i)
    cout << i << ':' << set.bucket_size(i) << " ";
  cout << '\n';
  ostream_iterator<elt> output(cout, " ");
  for (int i = 0; i < set.bucket_count(); ++i)
  { // show contents of bucket i
    cout << setw(3) << i << ": ";
    copy(set.begin(i), set.end(i), output);
    cout << '\n';
  }
}

int main()
{ // demonstrate use of bucket functions
  iset set;
  for (int i = 0; i < 100; ++i)
    set.insert(i);
  show_buckets(set);
  return 0;
}