// 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; }