hashmap.cpp

C++高级编程这本书所附的源代码

#include <iterator>

// Throws invalid_argument if numBuckets is non-positive
template <typename T>
DefaultHash<T>::DefaultHash(int numBuckets) throw (invalid_argument)
{
  if (numBuckets <= 0) {
    throw (invalid_argument("numBuckets must be > 0"));
  }
  mNumBuckets = numBuckets;
}

// Uses the division method for hashing.
// Treats the key as a sequence of bytes, sums the ASCII
// values of the bytes, and mods the total by the number
// of buckets.
template <typename T>
int DefaultHash<T>::hash(const T& key) const
{
  int bytes = sizeof(key);
  unsigned long res = 0;
  for (int i = 0; i < bytes; ++i) {
    res += *((char*)&key + i);
  }
  return (res % mNumBuckets);
}

// Throws invalid_argument if numBuckets is non-positive
DefaultHash<string>::DefaultHash(int numBuckets) throw (invalid_argument)
{
  if (numBuckets <= 0) {
    throw (invalid_argument("numBuckets must be > 0"));
  }
  mNumBuckets = numBuckets;
}

// Uses the division method for hashing after summing the
// ASCII values of all the characters in key.
int DefaultHash<string>::hash(const string& key) const
{
  int sum = 0;

  for (size_t i = 0; i < key.size(); i++) {
    sum += key[i];
  }
  return (sum % mNumBuckets);
}

// Dereferencing or incrementing an iterator constructed with the
// default ctor is undefined, so it doesn't matter what values we give
// here.
template<typename Key, typename T, typename Compare, typename Hash>
HashIterator<Key, T, Compare, Hash>::HashIterator()
{
  mBucket = -1;
  mIt = list<pair<const Key, T> >::iterator();
  mHashmap = NULL;
}

template<typename Key, typename T, typename Compare, typename Hash>
HashIterator<Key, T, Compare, Hash>::HashIterator(int bucket,
    typename list<pair<const Key, T> >::iterator listIt,
    const hashmap<Key, T, Compare, Hash>* inHashmap) :
  mBucket(bucket), mIt(listIt), mHashmap(inHashmap)
{
}

// Return the actual element
template<typename Key, typename T, typename Compare, typename Hash>
pair<const Key, T>& HashIterator<Key, T, Compare, Hash>::operator*() const
{
  return (*mIt);
}

// Return the iterator, so the compiler can apply -> to it to access
// the actual desired field.
template<typename Key, typename T, typename Compare, typename Hash>
pair<const Key, T>*
HashIterator<Key, T, Compare, Hash>::operator->() const
{
  return (&(*mIt));
}
// Defer the details to the increment() helper
template<typename Key, typename T, typename Compare, typename Hash>
HashIterator<Key, T, Compare, Hash>&
HashIterator<Key, T, Compare, Hash>::operator++()
{
  increment();
  return (*this);
}

// Defer the details to the increment() helper
template<typename Key, typename T, typename Compare, typename Hash>
const HashIterator<Key, T, Compare, Hash>
HashIterator<Key, T, Compare, Hash>::operator++(int)
{
  HashIterator<Key, T, Compare, Hash> oldIt = *this;
  increment();
  return (oldIt);
}

// Defer the details to the decrement() helper
template<typename Key, typename T, typename Compare, typename Hash>
HashIterator<Key, T, Compare, Hash>&
HashIterator<Key, T, Compare, Hash>::operator--()
{
  decrement();
  return (*this);
}

// Defer the details to the decrement() helper
template<typename Key, typename T, typename Compare, typename Hash>
const HashIterator<Key, T, Compare, Hash>
HashIterator<Key, T, Compare, Hash>::operator--(int)
{
  HashIterator<Key, T, Compare, Hash> newIt = *this;
  decrement();
  return (newIt);
}

// Behavior is undefined if mIt already refers to the past-the-end
// element in the table, or is otherwise invalid.
template<typename Key, typename T, typename Compare, typename Hash>
void HashIterator<Key, T, Compare, Hash>::increment()
{
  // mIt is an iterator into a single bucket.
  // Increment it.
  ++mIt;

  // If we're at the end of the current bucket,
  // find the next bucket with elements.
  if (mIt == (*mHashmap->mElems)[mBucket].end()) {
    for (size_t i = mBucket + 1; i < (*mHashmap->mElems).size(); i++) {
      if (!((*mHashmap->mElems)[i].empty())) {
	// We found a non-empty bucket.
	// Make mIt refer to the first element in it.
	mIt = (*mHashmap->mElems)[i].begin();
	mBucket = i;
	return;
      }
    }
    // No more empty buckets. Assign mIt to refer to the end
    // iterator of the last list.
    mBucket = (*mHashmap->mElems).size() - 1;
    mIt = (*mHashmap->mElems)[mBucket].end();
  }
}
// Behavior is undefined if mIt already refers to the first element
// in the table, or is otherwise invalid.
template<typename Key, typename T, typename Compare, typename Hash>
void HashIterator<Key, T, Compare, Hash>::decrement()
{
  // mIt is an iterator into a single bucket.
  // If it's at the beginning of the current bucket, don't decrement it.
  // Instead, try to find a non-empty bucket ahead of the current one.
  if (mIt == (*mHashmap->mElems)[mBucket].begin()) {
    for (int i = mBucket - 1; i >= 0; --i) {
      if (!((*mHashmap->mElems)[i].empty())) {
	mIt = (*mHashmap->mElems)[i].end();
	--mIt;
	mBucket = i;
	return;
      }
    }
    // No more non-empty buckets. This is an invalid decrement.
    // Assign mIt to refer to one before the start element of the first
    // list (an invalid position).
    mIt = (*mHashmap->mElems)[0].begin();
    --mIt;
    mBucket = 0;
  } else {
    // We're not at the beginning of the bucket, so
    // just move down.
    --mIt;
  }
}

template<typename Key, typename T, typename Compare, typename Hash>
bool HashIterator<Key, T, Compare, Hash>::operator==(
						     const HashIterator& rhs) const
{
  // All fields, including the hashmap to which the iterators refer,
  // must be equal.
  return (mHashmap == rhs.mHashmap && mBucket == rhs.mBucket &&
	  mIt == rhs.mIt);
}

template<typename Key, typename T, typename Compare, typename Hash>
bool HashIterator<Key, T, Compare, Hash>::operator!=(
						     const HashIterator& rhs) const
{
  return (!operator==(rhs));
}


// Construct mElems with the number of buckets.
template <typename Key, typename T, typename Compare, typename Hash>
hashmap<Key, T, Compare, Hash>::hashmap(
					const Compare& comp, const Hash& hash) throw(invalid_argument) :
  mSize(0), mComp(comp), mHash(hash)
{
  if (mHash.numBuckets() <= 0) {
    throw (invalid_argument("Number of buckets must be positive"));
  }
  mElems = new vector<list<value_type> >(mHash.numBuckets());
}

// Make a call to insert() to actually insert the elements.
template <typename Key, typename T, typename Compare, typename Hash>
template <class InputIterator>
hashmap<Key, T, Compare, Hash>::hashmap(
InputIterator first, InputIterator last, const Compare& comp,
const Hash& hash) throw(invalid_argument) : mSize(0), mComp(comp), mHash(hash)
{
  if (mHash.numBuckets() <= 0) {
    throw (invalid_argument("Number of buckets must be positive"));
  }
  mElems = new vector<list<value_type> >(mHash.numBuckets());
  insert(first, last);
}


template <typename Key, typename T, typename Compare, typename Hash>
hashmap<Key, T, Compare, Hash>::~hashmap()
{
  delete mElems;
}

template <typename Key, typename T, typename Compare, typename Hash>
hashmap<Key, T, Compare, Hash>::hashmap(const hashmap<
					Key, T, Compare, Hash>& src) :
  mSize(src.mSize), mComp(src.mComp), mHash(src.mHash)
{
  // Don't need to bother checking if numBuckets is positive, because
  // we know src checked.

  // Use the vector copy constructor
  mElems = new vector<list<value_type> >(*(src.mElems));
}

template <typename Key, typename T, typename Compare, typename Hash>
hashmap<Key, T, Compare, Hash>& hashmap<Key, T, Compare, Hash>::operator=(
									  const hashmap<Key, T, Compare, Hash>& rhs)
{
  // check for self-assignment
  if (this != &rhs) {
    delete mElems;
    mSize = rhs.mSize;
    mComp = rhs.mComp;
    mHash = rhs.mHash;
    // Don't need to bother checking if numBuckets is positive, because
    // we know rhs checked

    // Use the vector copy constructor
    mElems = new vector<list<value_type> >(*(rhs.mElems));
  }
  return (*this);
}

template <typename Key, typename T, typename Compare, typename Hash>
typename list<pair<const Key, T> >::iterator
hashmap<Key, T, Compare, Hash>::findElement(const key_type& x, int& bucket) const