hashmap.cpp

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

{
  // hash the key to get the bucket
  bucket = mHash.hash(x);

  // Look for the key in the bucket
  for (typename ListType::iterator it = (*mElems)[bucket].begin();
       it != (*mElems)[bucket].end(); ++it) {
    if (mComp(it->first, x)) {
      return (it);
    }
  }
  return ((*mElems)[bucket].end());
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::iterator
hashmap<Key, T, Compare, Hash>::find(const key_type& x)
{
  int bucket;
  // Use the findElement() helper
  typename ListType::iterator it = findElement(x, bucket);
  if (it == (*mElems)[bucket].end()) {
    // we didn't find the element -- return the end iterator
    return (end());
  }
  // We found the element -- convert the bucket/iterator to a HashIterator
  return (HashIterator<Key, T, Compare, Hash>(bucket, it, this));
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::const_iterator
hashmap<Key, T, Compare, Hash>::find(const key_type& x) const
{
  int bucket;
  // Use the findElement() helper
  typename ListType::iterator it = findElement(x, bucket);
  if (it == (*mElems)[bucket].end()) {
    // we didn't find the element -- return the end iterator
    return (end());
  }
  // We found the element -- convert the bucket/iterator to a HashIterator
  return (HashIterator<Key, T, Compare, Hash>(bucket, it, this));
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::size_type
hashmap<Key, T, Compare, Hash>::count(const key_type& x) const
{
  // There are either 1 or 0 elements matching key x.
  // If we can find a match, return 1, otherwise return 0.
  if (find(x) == end()) {
    return (0);
  } else {
    return (1);
  }
}
template <typename Key, typename T, typename Compare, typename Hash>
T& hashmap<Key, T, Compare, Hash>::operator[] (const key_type& x)
{
  // This definition is the same as that used by map, according to
  // the standard.
  // It's a bit cryptic, but it basically attempts to insert
  // a new key/value pair of x and a new value. Regardless of whether
  // the insert succeeds or fails, insert() returns a pair of an
  // iterator/bool. The iterator refers to a key/value pair, the
  // second element of which is the value we want to return.
  return (((insert(make_pair(x, T()))).first)->second);
}

template <typename Key, typename T, typename Compare, typename Hash>
pair<typename hashmap<Key, T, Compare, Hash>::iterator, bool>
hashmap<Key, T, Compare, Hash>::insert(const value_type& x)
{
  int bucket;
  // Try to find the element
  typename ListType::iterator it = findElement(x.first, bucket);

  if (it != (*mElems)[bucket].end()) {
    // The element already exists
    // Convert the list iterator into a HashIterator, which
    // also requires the bucket and a pointer to the hashmap.
    HashIterator<Key, T, Compare, Hash> newIt(bucket, it, this);

    // Some compilers don't like make_pair here
    pair<HashIterator<Key, T, Compare, Hash>, bool> p(newIt, false);
    return (p);
  } else {
    // We didn't find the element, so insert a new one.
    mSize++;
    typename ListType::iterator endIt =
      (*mElems)[bucket].insert((*mElems)[bucket].end(), x);
    pair<HashIterator<Key, T, Compare, Hash>, bool> p(
      HashIterator<Key, T, Compare, Hash>(bucket, endIt, this), true);
    return (p);
  }
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::iterator
hashmap<Key, T, Compare, Hash>::insert(typename hashmap<Key, T, Compare,
   Hash>::iterator position, const value_type& x)
{
  // completely ignore position
  return (insert(x).first);
}

template <typename Key, typename T, typename Compare, typename Hash>
template <class InputIterator>
void hashmap<Key, T, Compare, Hash>::insert(InputIterator first,
					    InputIterator last)
{
  // Copy each element in the range by using an insert_iterator
  // adapter. Give begin() as a dummy position -- insert ignores it
  // anyway.
  std::insert_iterator<hashmap<Key, T, Compare, Hash> > it(*this, begin());
  copy(first, last, it);
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::size_type
hashmap<Key, T, Compare, Hash>::erase(const key_type& x)
{
  int bucket;

  // First, try to find the element
  typename ListType::iterator it = findElement(x, bucket);

  if (it != (*mElems)[bucket].end()) {
    // The element already exists -- erase it
    (*mElems)[bucket].erase(it);
    mSize--;
    return (1);
  } else {
    return (0);
  }
}

template <typename Key, typename T, typename Compare, typename Hash>
void hashmap<Key, T, Compare, Hash>::erase(
					   hashmap<Key, T, Compare, Hash>::iterator position)
{
  // Erase the element from its bucket
  (*mElems)[position.mBucket].erase(position.mIt);
  mSize--;
} 

template <typename Key, typename T, typename Compare, typename Hash>
void hashmap<Key, T, Compare, Hash>::erase(
					   hashmap<Key, T, Compare, Hash>::iterator first,
					   hashmap<Key, T, Compare, Hash>::iterator last)
{
  typename hashmap<Key, T, Compare, Hash>::iterator cur, next;

  // erase all the elements in the range
  for (next = first; next != last; ) {
    cur = next++;
    erase(cur);
  }
}

template <typename Key, typename T, typename Compare, typename Hash>
void hashmap<Key, T, Compare, Hash>::clear()
{
  // Call clear on each list.
  for_each(mElems->begin(), mElems->end(), mem_fun_ref(&ListType::clear));
  mSize = 0;
}


template <typename Key, typename T, typename Compare, typename Hash>
bool hashmap<Key, T, Compare, Hash>::empty() const
{
  return (mSize == 0);
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::size_type
hashmap<Key, T, Compare, Hash>::size() const
{
  return (mSize);
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::size_type
hashmap<Key, T, Compare, Hash>::max_size() const
{
  // In the worst case, all the elements hash to the
  // same list, so the max_size is the max_size of a single
  // list. This code assumes that all the lists have the same
  // max_size.
  return ((*mElems)[0].max_size());
}

// Just swap the four data members
// Use the generic swap template
template <typename Key, typename T, typename Compare, typename Hash>
void hashmap<Key, T, Compare, Hash>::swap(hashmap<
					  Key, T, Compare, Hash>& hashIn)
{
  // explicitly qualify with std:: so the compiler doesn't think
  // it's a recursive call.
  std::swap(*this, hashIn);
} 

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::iterator
hashmap<Key, T, Compare, Hash>::begin()
{
  if (mSize == 0) {
    // Special case: there are no elements, so return the end iterator
    return (end());
  }

  // We know there is at least one element. Find the first element
  for (size_t i = 0; i < mElems->size(); ++i) {
    if (!((*mElems)[i].empty())) {
      return (HashIterator<Key, T, Compare, Hash>(i,
						  (*mElems)[i].begin(), this));
    }
  }
  // should never reach here, but if we do, return the end iterator
  return (end());
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::iterator
hashmap<Key, T, Compare, Hash>::end()
{
  // The end iterator is just the end iterator of the list in last bucket
  return (HashIterator<Key, T, Compare, Hash>(mElems->size() - 1,
	(*mElems)[mElems->size() - 1].end(), this));
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::iterator
hashmap<Key, T, Compare, Hash>::begin() const
{
  if (mSize == 0) {
    // Special case: there are no elements, so return the end iterator
    return (end());
  }

  // We know there is at least one element. Find the first element
  for (size_t i = 0; i < mElems->size(); ++i) {
    if (!((*mElems)[i].empty())) {
      return (HashIterator<Key, T, Compare, Hash>(i,
						  (*mElems)[i].begin(), this));
    }
  }
  // should never reach here, but if we do, return the end iterator
  return (end());
}

template <typename Key, typename T, typename Compare, typename Hash>
typename hashmap<Key, T, Compare, Hash>::iterator
hashmap<Key, T, Compare, Hash>::end() const
{
  // The end iterator is just the end iterator of the list in last bucket
  return (HashIterator<Key, T, Compare, Hash>(mElems->size() - 1,
	(*mElems)[mElems->size() - 1].end(), this));
}