Online Book Reader

Home Category

Professional C__ - Marc Gregoire [304]

By Root 1375 0
method first increments the list iterator, then checks if it has reached the end of its bucket. If so, it finds the next non-empty bucket in the hashmap and sets the list iterator equal to the start element in that bucket. Note that it can’t simply move to the next bucket, because there might not be any elements in it. If there are no more empty buckets, mIt is set, by the convention chosen for this example, to the end iterator of the last bucket in the hashmap, which is the special “end” position of the HashIterator. Iterators are not required to be any safer than dumb pointers, so error-checking for things like incrementing an iterator already at the end is not required:

// Behavior is undefined if mIt already refers to the past-the-end

// element in the table, or is otherwise invalid.

template

void HashIterator::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();

}

}

Code snippet from Hashmap\FinalHashmap\hashmap.cpp

Decrement is the inverse of increment: It makes the iterator refer to the “previous” element in the container. However, there is an asymmetry because of the asymmetry between the way the start and end positions are represented: Start is the first element, but end is “one past” the last element. The algorithm for decrement checks first if the underlying list iterator is at the start of its current bucket. If not, it can just be decremented. Otherwise, the code needs to check for the first nonempty bucket before the current one. If one is found, the list iterator must be set to refer to the last element in the bucket, which is the end iterator decremented by one. If no non-empty buckets are found, the decrement is invalid, so the code can do anything it wants (behavior is undefined):

// Behavior is undefined if mIt already refers to the first element

// in the table, or is otherwise invalid.

template

void HashIterator::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 (size_t 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;

}

}

Code snippet from Hashmap\FinalHashmap\hashmap.cpp

Note that both increment() and decrement() access protected members of the hashmap class. Thus, the hashmap class must declare HashIterator to be a friend class.

After increment() and decrement(), operator== and operator!= are positively simple. They just compare each of the three data members of the objects:

template

bool HashIterator::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

®Online Book Reader