creating an iterator to search a vector of list<T>

[yellowMonkeyxx]

I have a template class defined as the following:

template <class T, class HF>
class HashTable
{
   private:

   vector<list<T> > bucket;

  public:

  //public methods
  bool find(const T&) const;
  
};

What I'm trying to do is create an iterator to traverse the contents of bucket.

I've tried a few variations of defining a list iterator, such as

list<T>::const_iterator it;

but haven't found anything that is correct? Any ideas?

[Lindley]

That's the correct type. What are you trying to do with it?

[monarch_dodra]

I have a template class defined as the following:

template <class T, class HF>
class HashTable
{
   private:

   vector<list<T> > bucket;

  public:

  //public methods
  bool find(const T&) const;
  
};

What I'm trying to do is create an iterator to traverse the contents of bucket.

I've tried a few variations of defining a list iterator, such as

list<T>::const_iterator it;

but haven't found anything that is correct? Any ideas?

Bucket is a vector, so your iterator has to be a vector iterator:

vector<list<T> >::const_iterator it

Each iterator will point to a list. If you want to iterate on the items in that list, create a list iterator:

vector<list<T> >::const_iterator itVect = bucket.begin();
vector<list<T> >::const_iterator itVectEnd = bucket.end();
for ( ; itVect != itVectEnd ; ++itVect)
{
     list<T>const_iterator itList = itVect->begin();
     list<T>const_iterator itListEnd = itVect->end();
     for ( ; itList != itListEnd ; ++itList )
    {
        //Do things with itListEnd
    }

}

If what you wanted was an actual new iterator type that traverses both, with HashTable::begin() defined as bucket.begin()->begin(), and HashTable::end() defined as (bucket.end()-1)->end(), well I'm afraid you'll have to write your entire own iterator class. I know there are some things in boost that can speed up the process (for example, if you write operator+=, there is a boost class which will automatically generate operator+), I wouldn't their names, and I don't know if they are worth the trouble.

Does that answer your question?

[yellowMonkeyxx]

Bucket is a vector, so your iterator has to be a vector iterator:

vector<list<T> >::const_iterator it

Each iterator will point to a list. If you want to iterate on the items in that list, create a list iterator:

vector<list<T> >::const_iterator itVect = bucket.begin();
vector<list<T> >::const_iterator itVectEnd = bucket.end();
for ( ; itVect != itVectEnd ; ++itVect)
{
     list<T>const_iterator itList = itVect->begin();
     list<T>const_iterator itListEnd = itVect->end();
     for ( ; itList != itListEnd ; ++itList )
    {
        //Do things with itListEnd
    }

}

If what you wanted was an actual new iterator type that traverses both, with HashTable::begin() defined as bucket.begin()->begin(), and HashTable::end() defined as (bucket.end()-1)->end(), well I'm afraid you'll have to write your entire own iterator class. I know there are some things in boost that can speed up the process (for example, if you write operator+=, there is a boost class which will automatically generate operator+), I wouldn't their names, and I don't know if they are worth the trouble.

Does that answer your question?

I changed my iterators to what you have and I get this error:
"is parsed as a non-type, but instantiation yields
a type"

What I want my iterator(s) to do is traverse bucket so I can check if an item is in the list

[Lindley]

Yeah, you're going to have to show some actual code if you want help interpreting that error. We have no idea what you wrote to produce it.

One clarification---when you say you want to traverse "bucket", I'm not entirely sure if you mean you want to search every list in the vector called "bucket", or just the list in one particular bucket (eg, one index of the vector). It's unclear whether you're using the word "bucket" as a variable name or a concept, in other words. Normally the conceptual interpretation would be described as traversing "a bucket", but we get some folks in here without great English, so it can be hard to tell.

[yellowMonkeyxx]

Buckets is defined as

vector<list<T> > buckets;

template<class T, class HF>
bool HashTable<T, HF>::find(const T &item) const
{
  int HashValue = convertKEY(item);

  HashValue &#37; bucketsUsedCount;

  vector<list<T> >::const_iterator itVect    = bucket.begin();
  vector<list<T> >::const_iterator itVectEnd = bucket.end();

  for(; itVect != itVecEnd; ++itVect)
   {
      list<T>const_iterator itList    = itVect->begin();
      list<T>const_iterator itListEnd = itVect->end();

      for(; itList != itListEnd; ++itList)
       {
         if(*itList == item)
          return true;
       }
  }
  return false;
}

The item passed into the find function is of type string. The purpose of this function is to search the vector buckets for the string "item" and return a boolean value if it was found or not.

In otherwords, I'm suppose to perform a "linear search"of the linked list associated with that bucket. If the item to be inserted is already present in the linked list, return false. Otherwise, insert the item into the list for that bucket, increment the size of the hash table, and return true.

[Lindley]

Oh, you just repeated a typo that monarch_dodra made. Should be obvious enough---the error will be pointing right at it.

[yellowMonkeyxx]

If you're talking about "->" I already fixed that unless you are referring to something else?

[Paul McKenzie]

I've tried a few variations of defining a list iterator, such as

list<T>::const_iterator it;

but haven't found anything that is correct? Any ideas?

Why not post the actual error message, so that it is obvious to us what the error is?

If that code is within a template, then it is invalid. This is the correction:

typename std::list<T>::const_iterator it;

Regards,

Paul McKenzie

[monarch_dodra]

Oh, you just repeated a typo that monarch_dodra made. Should be obvious enough---the error will be pointing right at it.

Whoops, sorry about that. I saw the question as more theoretical than code, so I did not double check the code. Here is, in red, the corrections:

typename vector<list<T> >::const_iterator itVect = bucket.begin();
typename vector<list<T> >::const_iterator itVectEnd = bucket.end();
for ( ; itVect != itVectEnd ; ++itVect)
{
     typename list<T>::const_iterator itList = itVect->begin();
     typename list<T>::const_iterator itListEnd = itVect->end();
     for ( ; itList != itListEnd ; ++itList )
    {
        //Do things with itListEnd
    }

}

I had forgotten the "scope operator" (:, as well as the typename keyword, if you are using this inside a template.

On a side note, I see you are using both "bucket" and "buckets". Are they the same thing? Is it just a typo? Naming your variables correctly, as stupid as it sounds, is very important. It usually means means the difference between immediately understanding something at first glance, and having to sit down and analyze every line of code to understand.

You should double check, because it is the kind of thing that make someone tell you how to iterate on the list inside your vector, and someone else how to iterate on the vector.