Remove exhashmap<T> class.
authorRichard Kreckel <kreckel@ginac.de>
Sun, 22 Sep 2019 11:19:00 +0000 (13:19 +0200)
committerRichard Kreckel <kreckel@ginac.de>
Sun, 22 Sep 2019 11:19:00 +0000 (13:19 +0200)
Class exhashmap<T> was a workaround for missing std::hash_map<Key, T>
in the original C++98 standard. It was put in GiNaC because map<Key, T>
was deemed too slow. Since C++11 there is std::unorderd_map<Key, T>,
which is hash-based. To be able to use it, add specializations of
std::hash<ex> and std:equal_to<ex>.

check/CMakeLists.txt
check/Makefile.am
check/exam_hashmap.cpp [deleted file]
check/time_hashmap.cpp [deleted file]
doc/tutorial/ginac.texi
ginac/ex.h
ginac/hash_map.h

index 58f9736..c229a81 100644 (file)
@@ -29,7 +29,6 @@ set(ginac_tests
        exam_clifford
        exam_archive
        exam_structure
-       exam_hashmap
        exam_misc
        exam_mod_gcd
        exam_cra
@@ -44,7 +43,6 @@ set(ginac_timings
        time_gammaseries
        time_vandermonde
        time_toeplitz
-       time_hashmap
        time_lw_A
        time_lw_B
        time_lw_C
index 0f7e035..e8adab0 100644 (file)
@@ -26,7 +26,6 @@ EXAMS = exam_paranoia \
        exam_clifford  \
        exam_archive  \
        exam_structure  \
-       exam_hashmap  \
        exam_misc \
        exam_mod_gcd \
        check_mul_info \
@@ -41,7 +40,6 @@ TIMES = time_dennyfliegner \
        time_gammaseries \
        time_vandermonde \
        time_toeplitz \
-       time_hashmap \
        time_lw_A \
        time_lw_B \
        time_lw_C \
@@ -146,9 +144,6 @@ exam_archive_LDADD = ../ginac/libginac.la
 exam_structure_SOURCES = exam_structure.cpp
 exam_structure_LDADD = ../ginac/libginac.la
 
-exam_hashmap_SOURCES = exam_hashmap.cpp
-exam_hashmap_LDADD = ../ginac/libginac.la
-
 exam_misc_SOURCES = exam_misc.cpp
 exam_misc_LDADD = ../ginac/libginac.la
 
@@ -176,9 +171,6 @@ time_vandermonde_LDADD = ../ginac/libginac.la
 time_toeplitz_SOURCES = time_toeplitz.cpp \
                        randomize_serials.cpp timer.cpp timer.h
 time_toeplitz_LDADD = ../ginac/libginac.la
-time_hashmap_SOURCES = time_hashmap.cpp \
-                      randomize_serials.cpp timer.cpp timer.h
-time_hashmap_LDADD = ../ginac/libginac.la
 
 time_lw_A_SOURCES = time_lw_A.cpp \
                    randomize_serials.cpp timer.cpp timer.h
diff --git a/check/exam_hashmap.cpp b/check/exam_hashmap.cpp
deleted file mode 100644 (file)
index ad8c1b2..0000000
+++ /dev/null
@@ -1,293 +0,0 @@
-/** @file exam_hashmap.cpp
- *
- *  Regression tests for the exhashmap<> container. */
-
-/*
- *  GiNaC Copyright (C) 1999-2019 Johannes Gutenberg University Mainz, Germany
- *
- *  This program is free software; you can redistribute it and/or modify
- *  it under the terms of the GNU General Public License as published by
- *  the Free Software Foundation; either version 2 of the License, or
- *  (at your option) any later version.
- *
- *  This program is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *  GNU General Public License for more details.
- *
- *  You should have received a copy of the GNU General Public License
- *  along with this program; if not, write to the Free Software
- *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
- */
-
-#include "ginac.h"
-using namespace GiNaC;
-
-#include <iostream>
-using namespace std;
-
-unsigned exam_hashmap()
-{
-       unsigned result = 0;
-       unsigned N = 100;
-
-       cout << "examining hash maps" << flush;
-
-       // Create empty container
-       exhashmap<unsigned> M1;
-       if (M1.size() != 0) {
-               clog << "Newly constructed container has size() != 0" << endl;
-               ++result;
-       }
-       if (!M1.empty()) {
-               clog << "Newly constructed container is not empty" << endl;
-               ++result;
-       }
-
-       cout << '.' << flush;
-
-       // Insert elements
-       for (unsigned i = 0; i < N; ++i)
-               M1.insert(make_pair(i, i));
-
-       if (M1.size() != N) {
-               clog << "After " << N << " insertions, size() returns " << M1.size() << " instead of " << N << endl;
-               ++result;
-       }
-
-       for (unsigned i = 0; i < N; ++i) {
-               if (M1[i] != i) {
-                       clog << "Lookup of key " << i << " in M1 didn't return correct value" << endl;
-                       ++result;
-                       break;
-               }
-       }
-
-       if (M1.size() != N) {
-               clog << "After " << N << " lookups, size() returns " << M1.size() << " instead of " << N << endl;
-               ++result;
-       }
-
-       cout << '.' << flush;
-
-       // Test constructor from two iterators and operator==
-       exhashmap<unsigned> M2(M1.begin(), M1.end());
-       if (M2.size() != M1.size()) {
-               clog << "Constructor from two iterators: size of destination container (" << M2.size() << ") not equal to size of source (" << M1.size() << ")" << endl;
-               ++result;
-       }
-
-       for (unsigned i = 0; i < N; ++i) {
-               if (M2[i] != i) {
-                       clog << "Lookup of key " << i << " in M2 didn't return correct value" << endl;
-                       ++result;
-                       break;
-               }
-       }
-
-       if (M2 != M1) {
-               clog << "Copied container not equal to source" << endl;
-               ++result;
-       }
-
-       cout << '.' << flush;
-
-       // Test assignment operator
-       exhashmap<unsigned> M3;
-       M3 = M1;
-       if (M3.size() != N) {
-               clog << "Assignment operator: size of assigned container not equal to size of original" << endl;
-               ++result;
-       }
-
-       for (unsigned i = 0; i < N; ++i) {
-               if (M3[i] != i) {
-                       clog << "Lookup of key " << i << " in M3 didn't return correct value" << endl;
-                       ++result;
-                       break;
-               }
-       }
-
-       cout << '.' << flush;
-
-       // Test insert(it, it)
-       exhashmap<unsigned> M4;
-       M4.insert(M1.begin(), M1.end());
-
-       if (M4.size() != M1.size()) {
-               clog << "insert(it, it): size of destination container not equal to size of source" << endl;
-               ++result;
-       }
-
-       for (unsigned i = 0; i < N; ++i) {
-               if (M4[i] != i) {
-                       clog << "Lookup of key " << i << " in M4 didn't return correct value" << endl;
-                       ++result;
-                       break;
-               }
-       }
-
-       cout << '.' << flush;
-
-       // Test insert()/find()
-       symbol x("x"), y("y");
-       exhashmap<unsigned> M5;
-       M5.insert(make_pair(x-2, 1));
-       M5.insert(make_pair(sin(x+y), 2));
-       M5.insert(make_pair(Pi, 3));
-       M5.insert(make_pair(0, 4));
-       M5.insert(make_pair(4*pow(x, y), 5));
-       if (M5.size() != 5) {
-               clog << "After 5 insertions, size() returns " << M5.size() << " instead of 5" << endl;
-               ++result;
-       }
-
-       exhashmap<unsigned>::const_iterator cit = M5.find(sin(x+y));
-       if (cit == M5.end()) {
-               clog << "Lookup of sin(x+y) didn't find anything" << endl;
-               ++result;
-       }
-       if (!cit->first.is_equal(sin(x+y))) {
-               clog << "Lookup of sin(x+y) returned an incorrect iterator" << endl;
-               ++result;
-       }
-       if (cit->second != 2) {
-               clog << "Lookup of sin(x+y) returned wrong value" << endl;
-               ++result;
-       }
-
-       cout << '.' << flush;
-
-       // Test re-inserting insert()
-       pair<exhashmap<unsigned>::iterator, bool> pit = M5.insert(make_pair(sin(x+y), 42));
-       if (pit.second) {
-               clog << "Reinsertion of sin(x+y) inserted a new value" << endl;
-               ++result;
-       }
-       if (!pit.first->first.is_equal(sin(x+y))) {
-               clog << "Reinsertion of sin(x+y) returned an incorrect iterator" << endl;
-               ++result;
-       }
-       if (pit.first->second != 2) {
-               clog << "Reinsertion of sin(x+y) changed the value" << endl;
-               ++result;
-       }
-
-       cout << '.' << flush;
-
-       // Test operator[]
-       unsigned v = M5[sin(x+y)];
-       if (M5.size() != 5) {
-               clog << "operator[] with an existing key changed the container size" << endl;
-               ++result;
-       }
-       if (v != 2) {
-               clog << "operator[] with an existing key returned the wrong value" << endl;
-               ++result;
-       }
-
-       v = M5[y+1];
-       if (M5.size() != 6) {
-               clog << "operator[] with a new key didn't insert a new value" << endl;
-               ++result;
-       }
-       if (v != 0) {
-               clog << "operator[] with a new key returned the wrong value" << endl;
-               ++result;
-       }
-
-       cout << '.' << flush;
-
-       // Test erase()
-       exhashmap<unsigned>::iterator it = M5.find(y+1);
-       if (it == M5.end()) {
-               clog << "Key y+1 wasn't found" << endl;
-               ++result;
-       }
-       if (!it->first.is_equal(y+1)) {
-               clog << "find() returned an incorrect iterator" << endl;
-               ++result;
-       }
-       if (it->second != 0) {
-               clog << "find() returned an incorrect value" << endl;
-               ++result;
-       }
-
-       M5.erase(it);
-       if (M5.size() != 5) {
-               clog << "erase(it) didn't reduce the size of the container" << endl;
-               ++result;
-       }
-
-       it = M5.find(y+1);
-       if (it != M5.end()) {
-               clog << "Key was still found after erase()" << endl;
-               ++result;
-       }
-
-       exhashmap<unsigned>::size_type n = M5.erase(Pi);
-       if (n != 1) {
-               clog << "erase(Pi) returned " << n << " instead of 1" << endl;
-               ++result;
-       }
-       if (M5.size() != 4) {
-               clog << "erase(Pi) didn't reduce the size of the container" << endl;
-               ++result;
-       }
-
-       n = M5.erase(42);
-       if (n != 0) {
-               clog << "erase(42) returned " << n << " instead of 0" << endl;
-               ++result;
-       }
-       if (M5.size() != 4) {
-               clog << "erase(42) reduced the size of the container" << endl;
-               ++result;
-       }
-
-       cout << '.' << flush;
-
-       // Test swap()
-       exhashmap<unsigned> M6;
-       M6.swap(M1);
-       if (M6.size() != N) {
-               clog << "After swap, size() returns " << M6.size() << " instead of " << N << endl;
-               ++result;
-       }
-       if (M1.size() != 0) {
-               clog << "After swap with empty container, size() returns " << M1.size() << " instead of 0" << endl;
-               ++result;
-       }
-
-       cout << '.' << flush;
-
-       // Test clear()
-       M2.clear();
-       if (M2.size() != 0) {
-               clog << "Size of cleared container is " << M5.size() << " instead of 0" << endl;
-               ++result;
-       }
-
-       cout << '.' << flush;
-
-       // Test count()
-       n = M5.count(Pi);
-       if (n != 0) {
-               clog << "count(Pi) returns " << n << " instead of 0" << endl;
-               ++result;
-       }
-
-       n = M5.count(4*pow(x, y));
-       if (n != 1) {
-               clog << "count(4*x^y) returns " << n << " instead of 1" << endl;
-               ++result;
-       }
-       cout << '.' << flush;
-
-       return result;
-}
-
-int main(int argc, char** argv)
-{
-       return exam_hashmap();
-}
diff --git a/check/time_hashmap.cpp b/check/time_hashmap.cpp
deleted file mode 100644 (file)
index 7657a47..0000000
+++ /dev/null
@@ -1,117 +0,0 @@
-/** @file time_hashmap.cpp
- *
- *  Timings for exhashmap<> operations. */
-
-/*
- *  GiNaC Copyright (C) 1999-2019 Johannes Gutenberg University Mainz, Germany
- *
- *  This program is free software; you can redistribute it and/or modify
- *  it under the terms of the GNU General Public License as published by
- *  the Free Software Foundation; either version 2 of the License, or
- *  (at your option) any later version.
- *
- *  This program is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *  GNU General Public License for more details.
- *
- *  You should have received a copy of the GNU General Public License
- *  along with this program; if not, write to the Free Software
- *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
- */
-
-#include "ginac.h"
-#include "timer.h"
-using namespace GiNaC;
-
-#include <iostream>
-#include <vector>
-using namespace std;
-
-template <class T>
-static void run_timing(unsigned size, double &time_insert, double &time_find, double &time_erase)
-{
-       vector<symbol> S;
-       T M;
-       timer t;
-
-       S.reserve(size);
-       for (unsigned i=0; i<size; ++i)
-               S.push_back(symbol());
-
-       t.start();
-       for (unsigned i=0; i<size; ++i)
-               M[S[i]] = S[(i+1)%size];
-       time_insert = t.read();
-
-       t.start();
-       for (unsigned i=0; i<size; ++i) {
-               if (!M[S[i]].is_equal(S[(i+1)%size])) {
-                       clog << "map lookup failed" << endl;
-                       return;
-               }
-       }
-       time_find = t.read();
-
-       t.start();
-       for (unsigned i=0; i<size; ++i) {
-               if (M.erase(S[i]) != 1) {
-                       clog << "erasing element " << S[i] << " failed" << endl;
-                       return;
-               }
-       }
-       if (!M.empty()) {
-               clog << "map not empty (size = " << M.size() << ") after erasing all elements" << endl;
-               return;
-       }
-       time_erase = t.read();
-}
-
-
-unsigned time_hashmap()
-{
-       unsigned result = 0;
-
-       cout << "timing hash map operations" << flush;
-
-       unsigned s[] = {10000, 50000, 100000, 500000};
-       vector<unsigned> sizes(s, s+sizeof(s)/sizeof(*s));
-
-       vector<double> times_insert, times_find, times_erase;
-
-       for (vector<unsigned>::const_iterator i = sizes.begin(); i != sizes.end(); ++i) {
-               double time_insert, time_find, time_erase;
-
-               run_timing<exhashmap<ex>>(*i, time_insert, time_find, time_erase);
-
-// If you like, you can compare it with this:
-//             run_timing<std::map<ex, ex, ex_is_less>>(*i, time_insert, time_find, time_erase);
-
-               times_insert.push_back(time_insert);
-               times_find.push_back(time_find);
-               times_erase.push_back(time_erase);
-               cout << '.' << flush;
-       }
-
-       // print the report:
-       cout << endl << "          size:\t";
-       copy(sizes.begin(), sizes.end(), ostream_iterator<unsigned>(cout, "\t"));
-       cout << endl << "      insert/s:\t";
-       copy(times_insert.begin(), times_insert.end(), ostream_iterator<double>(cout, "\t"));
-       cout << endl << "        find/s:\t";
-       copy(times_find.begin(), times_find.end(), ostream_iterator<double>(cout, "\t"));
-       cout << endl << "       erase/s:\t";
-       copy(times_erase.begin(), times_erase.end(), ostream_iterator<double>(cout, "\t"));
-       cout << endl;
-
-       return result;
-}
-
-extern void randomify_symbol_serials();
-
-int main(int argc, char** argv)
-{
-       randomify_symbol_serials();
-       cout << setprecision(2) << showpoint;
-       return time_hashmap();
-}
index a345958..b348b89 100644 (file)
@@ -717,7 +717,6 @@ meta-class for storing all mathematical objects.
 * Matrices::                     Matrices.
 * Indexed objects::              Handling indexed quantities.
 * Non-commutative objects::      Algebras with non-commutative products.
-* Hash maps::                    A faster alternative to std::map<>.
 @end menu
 
 
@@ -2987,7 +2986,7 @@ one form for @samp{F} and explicitly multiply it with a matrix representation
 of the metric tensor.
 
 
-@node Non-commutative objects, Hash maps, Indexed objects, Basic concepts
+@node Non-commutative objects, Methods and functions, Indexed objects, Basic concepts
 @c    node-name, next, previous, up
 @section Non-commutative objects
 
@@ -3771,43 +3770,7 @@ example:
 @end example
 
 
-@node Hash maps, Methods and functions, Non-commutative objects, Basic concepts
-@c    node-name, next, previous, up
-@section Hash Maps
-@cindex hash maps
-@cindex @code{exhashmap} (class)
-
-For your convenience, GiNaC offers the container template @code{exhashmap<T>}
-that can be used as a drop-in replacement for the STL
-@code{std::map<ex, T, ex_is_less>}, using hash tables to provide faster,
-typically constant-time, element look-up than @code{map<>}.
-
-@code{exhashmap<>} supports all @code{map<>} members and operations, with the
-following differences:
-
-@itemize @bullet
-@item
-no @code{lower_bound()} and @code{upper_bound()} methods
-@item
-no reverse iterators, no @code{rbegin()}/@code{rend()}
-@item 
-no @code{operator<(exhashmap, exhashmap)}
-@item
-the comparison function object @code{key_compare} is hardcoded to
-@code{ex_is_less}
-@item
-the constructor @code{exhashmap(size_t n)} allows specifying the minimum
-initial hash table size (the actual table size after construction may be
-larger than the specified value)
-@item
-the method @code{size_t bucket_count()} returns the current size of the hash
-table
-@item 
-@code{insert()} and @code{erase()} operations invalidate all iterators
-@end itemize
-
-
-@node Methods and functions, Information about expressions, Hash maps, Top
+@node Methods and functions, Information about expressions, Non-commutative objects, Top
 @c    node-name, next, previous, up
 @chapter Methods and functions
 @cindex polynomial
index 606cd9d..dd3cfe0 100644 (file)
@@ -962,6 +962,26 @@ inline void swap(GiNaC::ex &a, GiNaC::ex &b)
        a.swap(b);
 }
 
+/** Specialization of std::hash() for ex objects. */
+template<>
+struct hash<GiNaC::ex>
+{
+       std::size_t operator()(const GiNaC::ex & e) const noexcept
+       {
+               return e.gethash();
+       }
+};
+
+/** Specialization of std::equal_to() for ex objects. */
+template<>
+struct equal_to<GiNaC::ex>
+{
+       bool operator()(const GiNaC::ex &e1, const GiNaC::ex &e2) const noexcept
+       {
+               return e1.is_equal(e2);
+       }
+};
+
 } // namespace std
 
 #endif // ndef GINAC_EX_H
index fb37d86..032489f 100644 (file)
 #ifndef GINAC_HASH_MAP_H
 #define GINAC_HASH_MAP_H
 
-#include <algorithm>
-#include <functional>
-#include <iterator>
-#include <list>
-#include <utility>
+#include <unordered_map>
 
 namespace GiNaC {
 
-/*
- *  "Hashmap Light" - buckets only contain one value, quadratic probing,
- *  grows automatically
- */
-
-namespace internal {
-
-// List of prime numbers shamelessly stolen from GCC STL
-enum { num_primes = 29 };
-
-static const unsigned long prime_list[num_primes] =
-{
-       31ul,        53ul,         97ul,         193ul,       389ul,
-       769ul,       1543ul,       3079ul,       6151ul,      12289ul,
-       24593ul,     49157ul,      98317ul,      196613ul,    393241ul,
-       786433ul,    1572869ul,    3145739ul,    6291469ul,   12582917ul,
-       25165843ul,  50331653ul,   100663319ul,  201326611ul, 402653189ul,
-       805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
-};
-
-inline unsigned long next_prime(unsigned long n)
-{
-       const unsigned long *first = prime_list;
-       const unsigned long *last = prime_list + num_primes;
-       const unsigned long *pos = std::lower_bound(first, last, n);
-       return pos == last ? *(last - 1) : *pos;
-}
-
-} // namespace internal
-
-
-// Define default arguments
-template <typename T, template <class> class A = std::allocator>
-class exhashmap;
-
-
-/** Pair Associative Container with 'ex' objects as keys, that is implemented
- *  with a hash table and can be used as a replacement for map<> in many cases.
- *
- *  Differences to map<>:
- *   - no lower_bound()/upper_bound()
- *   - no reverse iterators, no rbegin()/rend()
- *   - no operator<()
- *   - comparison functor is hardcoded to ex_is_less
- *   - bucket_count() returns the number of buckets allocated in the hash table
- *   - insert() and erase() invalidate all iterators
- *   - average complexity of find() is constant time, worst case is O(n) */
-template <typename T, template <class> class A>
-class exhashmap {
-public:
-       static const unsigned min_num_buckets = 31; // must be prime
-
-       // Standard types
-       typedef ex key_type;
-       typedef T mapped_type;
-       typedef std::pair<key_type, T> value_type;
-       typedef ex_is_less key_compare;
-       typedef ex_is_equal key_equal;
-       typedef value_type & reference;
-       typedef const value_type & const_reference;
-       typedef value_type * pointer;
-       typedef const value_type * const_pointer;
-
-protected:
-       // Private types
-       enum bucket_state {
-               EMPTY,  ///< bucket empty (never used)
-               USED,   ///< bucket in use
-               ERASED  ///< bucket empty (element deleted), but may be part of a search chain
-       };
-       typedef std::pair<bucket_state, value_type> Bucket;
-
-public:
-       // More standard types
-       typedef A<Bucket> allocator_type;
-
-protected:
-       // More private types
-       typedef std::vector<Bucket, allocator_type> Table;
-
-       typedef typename Table::iterator table_iterator;
-       typedef typename Table::const_iterator table_const_iterator;
-
-public:
-       // Iterators
-       template <typename Pointer, typename Reference, class TableIterator>
-       class exhashmap_iterator : public std::iterator<std::forward_iterator_tag, value_type, typename Table::difference_type, Pointer, Reference> {
-       protected:
-               friend class exhashmap;
-
-       public:
-               exhashmap_iterator() {}
-               exhashmap_iterator(TableIterator t, TableIterator te)
-                : it(t), table_end(te) {}
-
-               // Allow iterator to const_iterator conversion
-               template <typename P, typename R, class TI>
-               exhashmap_iterator(const exhashmap_iterator<P, R, TI> &other)
-                : it(other.get_it_()), table_end(other.get_table_end_()) {}
-
-               typename exhashmap_iterator::reference operator*() const
-               {
-                       return it->second;
-               }
-
-               typename exhashmap_iterator::pointer operator->() const
-               {
-                       return &(it->second);
-               }
-
-               exhashmap_iterator &operator++()
-               {
-                       increment();
-                       return *this;
-               }
-
-               exhashmap_iterator operator++(int)
-               {
-                       exhashmap_iterator tmp = *this;
-                       increment();
-                       return tmp;
-               }
-
-               template <typename P, typename R, class TI>
-               bool operator==(const exhashmap_iterator<P, R, TI> &other) const
-               {
-                       return it == other.get_it_();
-               }
-
-               template <typename P, typename R, class TI>
-               bool operator!=(const exhashmap_iterator<P, R, TI> &other) const
-               {
-                       return it != other.get_it_();
-               }
-
-               // Private access function
-               TableIterator get_it_() const { return it; }
-               TableIterator get_table_end_() const { return table_end; }
-
-       protected:
-               TableIterator it;        ///< Pointer to current bucket
-               TableIterator table_end; ///< Pointer to one-past-last bucket
-
-               void increment()
-               {
-                       if (it != table_end)
-                               ++it;
-
-                       // Skip empty and erased buckets
-                       while (it != table_end && it->first != USED)
-                               ++it;
-               }
-       };
-
-       typedef exhashmap_iterator<value_type*, value_type&, table_iterator> iterator;
-       typedef exhashmap_iterator<const value_type*, const value_type&, table_const_iterator> const_iterator;
-
-       // More standard types
-       typedef typename Table::size_type size_type;
-       typedef typename Table::difference_type difference_type;
-
-       class value_compare : private key_compare {
-               friend class exhashmap;
-       public:
-               bool operator()(const value_type &lhs, const value_type &rhs) const
-               {
-                       return key_compare::operator()(lhs.first, rhs.first);
-               }
-
-               bool operator()(const key_type &lhs, const value_type &rhs) const
-               {
-                       return key_compare::operator()(lhs, rhs.first);
-               }
-
-               bool operator()(const value_type &lhs, const key_type &rhs) const
-               {
-                       return key_compare::operator()(lhs.first, rhs);
-               }
-       };
-
-protected:
-       // Private data
-       size_type num_entries; ///< Number of values stored in container (cached for faster operation of size())
-       size_type num_buckets; ///< Number of buckets (= hashtab.size())
-       Table hashtab;         ///< Vector of buckets, each bucket is kept sorted
-
-       /** Return index of key in hash table. */
-       static size_type hash_index(const key_type &x, size_type nbuckets)
-       {
-               return x.gethash() % nbuckets;
-       }
-
-       static table_iterator find_bucket(const key_type &x, table_iterator tab, size_type nbuckets);
-       static table_const_iterator find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets);
-       static table_iterator find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets);
-
-       /** Return pointer to bucket corresponding to key (or first empty bucket). */
-       table_iterator find_bucket(const key_type &x)
-       {
-               return find_bucket(x, hashtab.begin(), num_buckets);
-       }
-
-       /** Return pointer to bucket corresponding to key (or first empty bucket). */
-       table_const_iterator find_bucket(const key_type &x) const
-       {
-               return find_bucket(x, hashtab.begin(), num_buckets);
-       }
-
-       /** Return pointer to bucket corresponding to key (or first empty or erased bucket). */
-       table_iterator find_bucket_for_insertion(const key_type &x)
-       {
-               return find_bucket_for_insertion(x, hashtab.begin(), num_buckets);
-       }
-
-       /** Return number of entries above which the table will grow. */
-       size_type hwm() const
-       {
-               // Try to keep at least 25% of the buckets free
-               return num_buckets - (num_buckets >> 2);
-       }
-
-       void grow();
-
-public:
-       // 23.3.1.1 Construct/copy/destroy
-       exhashmap()
-        : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
-
-       explicit exhashmap(size_type nbuckets)
-        : num_entries(0), num_buckets(internal::next_prime(nbuckets)), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
-
-       template <class InputIterator>
-       exhashmap(InputIterator first, InputIterator last)
-        : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type())))
-       {
-               insert(first, last);
-       }
-
-       exhashmap &operator=(const exhashmap &other)
-       {
-               exhashmap(other).swap(*this);
-               return *this;
-       }
-
-       // Iterators
-       iterator begin()
-       {
-               // Find first used bucket
-               table_iterator bucket = hashtab.begin();
-               while (bucket != hashtab.end() && bucket->first != USED)
-                       ++bucket;
-               return iterator(bucket, hashtab.end());
-       }
-
-       const_iterator begin() const
-       {
-               // Find first used bucket
-               table_const_iterator bucket = hashtab.begin();
-               while (bucket != hashtab.end() && bucket->first != USED)
-                       ++bucket;
-               return const_iterator(bucket, hashtab.end());
-       }
-
-       iterator end()
-       {
-               return iterator(hashtab.end(), hashtab.end());
-       }
-
-       const_iterator end() const
-       {
-               return const_iterator(hashtab.end(), hashtab.end());
-       }
-
-       // Capacity
-       bool empty() const
-       {
-               return num_entries == 0;
-       }
-
-       size_type size() const
-       {
-               return num_entries;
-       }
-
-       size_type max_size() const
-       {
-               return hashtab.max_size();
-       }
-
-       size_type bucket_count() const
-       {
-               return num_buckets;
-       }
-
-       // 23.3.1.2 Element access
-       T &operator[](const key_type &x)
-       {
-               return insert(value_type(x, mapped_type())).first->second;
-       }
-
-       // Modifiers
-       std::pair<iterator, bool> insert(const value_type &x);
-
-       iterator insert(iterator pos, const value_type &x)
-       {
-               return insert(x).first;
-       }
-
-       template <class InputIterator>
-       void insert(InputIterator first, InputIterator last)
-       {
-               for (; first != last; ++first)
-                       insert(*first);
-       }
-
-       void erase(iterator position)
-       {
-               table_iterator bucket = position.get_it_();
-               bucket->first = ERASED;
-               bucket->second.first = 0;
-               --num_entries;
-       }
-
-       size_type erase(const key_type &x);
-
-       void swap(exhashmap &other)
-       {
-               hashtab.swap(other.hashtab);
-               std::swap(num_buckets, other.num_buckets);
-               std::swap(num_entries, other.num_entries);
-       }
-
-       void clear();
-
-       // Observers
-       key_compare key_comp() const
-       {
-               return key_compare();
-       }
-
-       value_compare value_comp() const
-       {
-               return value_compare();
-       }
-
-       // 23.3.1.3 Map operations
-       iterator find(const key_type &x);
-       const_iterator find(const key_type &x) const;
-
-       size_type count(const key_type &x) const
-       {
-               return find(x) == end() ? 0 : 1;
-       }
-
-       std::pair<iterator, iterator> equal_range(const key_type &x)
-       {
-               iterator i = find(x);
-               if (i == end())
-                       return std::make_pair(i, i);
-               else {
-                       iterator j = ++i;
-                       return std::make_pair(i, j);
-               }
-       }
-
-       std::pair<const_iterator, const_iterator> equal_range(const key_type &x) const
-       {
-               const_iterator i = find(x);
-               if (i == end())
-                       return std::make_pair(i, i);
-               else {
-                       const_iterator j = ++i;
-                       return std::make_pair(i, j);
-               }
-       }
-
-       friend bool operator==(const exhashmap &lhs, const exhashmap &rhs)
-       {
-               if (lhs.num_entries != rhs.num_entries || lhs.num_buckets != rhs.num_buckets)
-                       return false;
-
-               // We can't compare the tables directly as the elements may be
-               // in different order due to the collision handling. We therefore
-               // look up each value from the lhs map in the rhs map separately.
-               for (const_iterator itl = lhs.begin(); itl != lhs.end(); ++itl) {
-                       const_iterator itr = rhs.find(itl->first);
-                       if (itr == rhs.end())
-                               return false;
-                       if (itl->second != itr->second)
-                               return false;
-               }
-               return true;
-       }
-
-       friend bool operator!=(const exhashmap &lhs, const exhashmap &rhs)
-       {
-               return !(lhs == rhs);
-       }
-
-#if 0
-       void dump() const
-       {
-               std::clog << "num_entries = " << num_entries << std::endl;
-               std::clog << "num_buckets = " << num_buckets << std::endl;
-               size_type t = 0;
-               for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it, ++t) {
-                       std::clog << " bucket " << t << ": ";
-                       std::clog << (it->first == EMPTY ? "free" : (it->first == USED ? "used" : "erased")) << ", " << it->second.first << " -> " << it->second.second << std::endl;
-               }
-       }
-#endif
-};
-
-/** Return pointer to bucket corresponding to key (or first empty bucket). */
-template <typename T, template <class> class A>
-inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_iterator tab, size_type nbuckets)
-{
-       // Quadratic probing
-       size_type h = hash_index(x, nbuckets);
-       size_type d = 1;
-       table_iterator it = tab + h;
-       while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
-               h = (h + d) % nbuckets;
-               d += 2;
-               it = tab + h;
-       }
-       return it;
-}
-
-/** Return pointer to bucket corresponding to key (or first empty bucket). */
-template <typename T, template <class> class A>
-inline typename exhashmap<T, A>::table_const_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets)
-{
-       // Quadratic probing
-       size_type h = hash_index(x, nbuckets);
-       size_type d = 1;
-       table_const_iterator it = tab + h;
-       while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
-               h = (h + d) % nbuckets;
-               d += 2;
-               it = tab + h;
-       }
-       return it;
-}
-
-/** Return pointer to bucket corresponding to key (or first empty or erased bucket). */
-template <typename T, template <class> class A>
-inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets)
-{
-       // Quadratic probing
-       size_type h = hash_index(x, nbuckets);
-       size_type d = 1;
-       table_iterator it = tab + h;
-       while (it->first != EMPTY && !key_equal()(it->second.first, x)) {
-               h = (h + d) % nbuckets;
-               d += 2;
-               it = tab + h;
-       }
-       return it;
-}
-
-/** Grow hash table */
-template <typename T, template <class> class A>
-void exhashmap<T, A>::grow()
-{
-       // Allocate new empty hash table
-       size_type new_num_buckets = internal::next_prime(num_buckets + 1);
-       Table new_hashtab;
-       new_hashtab.resize(new_num_buckets);
-       for (table_iterator it = new_hashtab.begin(); it != new_hashtab.end(); ++it)
-               it->first = EMPTY;
-
-       // Re-insert all elements into new table
-       for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it) {
-               if (it->first == USED) {
-                       table_iterator bucket = find_bucket(it->second.first, new_hashtab.begin(), new_num_buckets);
-                       *bucket = *it;
-               }
-       }
-
-       // Swap with the old table
-       hashtab.swap(new_hashtab);
-       num_buckets = new_num_buckets;
-}
-
-template <typename T, template <class> class A>
-std::pair<typename exhashmap<T, A>::iterator, bool> exhashmap<T, A>::insert(const value_type &x)
-{
-       table_iterator bucket = find_bucket_for_insertion(x.first);
-       if (bucket->first == USED) {
-               // Value already in map
-               return std::make_pair(iterator(bucket, hashtab.end()), false);
-       } else {
-               // Insert new value
-               bucket->first = USED;
-               bucket->second = x;
-               ++num_entries;
-               if (num_entries >= hwm()) {
-                       grow();
-                       bucket = find_bucket(x.first);
-               }
-               return std::make_pair(iterator(bucket, hashtab.end()), true);
-       }
-}
-
-template <typename T, template <class> class A>
-typename exhashmap<T, A>::size_type exhashmap<T, A>::erase(const key_type &x)
-{
-       iterator i = find(x);
-       if (i != end()) {
-               erase(i);
-               return 1;
-       } else
-               return 0;
-}
-
-template <typename T, template <class> class A>
-typename exhashmap<T, A>::iterator exhashmap<T, A>::find(const key_type &x)
-{
-       table_iterator bucket = find_bucket(x);
-       if (bucket->first == USED)
-               return iterator(bucket, hashtab.end());
-       else
-               return end();
-}
-
-template <typename T, template <class> class A>
-typename exhashmap<T, A>::const_iterator exhashmap<T, A>::find(const key_type &x) const
-{
-       table_const_iterator bucket = find_bucket(x);
-       if (bucket->first == USED)
-               return const_iterator(bucket, hashtab.end());
-       else
-               return end();
-}
-
-template <typename T, template <class> class A>
-void exhashmap<T, A>::clear()
-{
-       for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i) {
-               i->first = EMPTY;
-               i->second.first = 0;
-               i->second.second = mapped_type();
-       }
-       num_entries = 0;
-}
+template <typename T,
+         class Hash = std::hash<ex>,
+         class KeyEqual = std::equal_to<ex>,
+         class Allocator = std::allocator<std::pair<const ex, T>>>
+using exhashmap = std::unordered_map<ex, T, Hash, KeyEqual, Allocator>;
 
 } // namespace GiNaC
 
-
-// Specializations of Standard Library algorithms
-namespace std {
-
-/** Specialization of std::swap() for exhashmap. */
-template <typename T, template <class> class A>
-inline void swap(GiNaC::exhashmap<T, A> &lhs, GiNaC::exhashmap<T, A> &rhs)
-{
-       lhs.swap(rhs);
-}
-
-} // namespace std
-
 #endif // ndef GINAC_HASH_MAP_H