creating an iterator to search a vector of list<T>
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

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

  1. #1
    Join Date
    Feb 2010
    Posts
    28

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

    I have a template class defined as the following:

    Code:
    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
    Code:
    list<T>::const_iterator it;
    but haven't found anything that is correct? Any ideas?

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

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

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

  3. #3
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,281

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

    Quote Originally Posted by yellowMonkeyxx View Post
    I have a template class defined as the following:

    Code:
    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
    Code:
    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:

    Code:
    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:

    Code:
    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?
    Last edited by monarch_dodra; April 21st, 2010 at 07:29 PM.

  4. #4
    Join Date
    Feb 2010
    Posts
    28

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

    Quote Originally Posted by monarch_dodra View Post
    Bucket is a vector, so your iterator has to be a vector iterator:

    Code:
    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:

    Code:
    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

  5. #5
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

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

    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.
    Last edited by Lindley; April 21st, 2010 at 07:50 PM.

  6. #6
    Join Date
    Feb 2010
    Posts
    28

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

    Buckets is defined as

    Code:
    vector<list<T> > buckets;
    Code:
    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.
    Last edited by yellowMonkeyxx; April 21st, 2010 at 07:58 PM.

  7. #7
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

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

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

  8. #8
    Join Date
    Feb 2010
    Posts
    28

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

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

  9. #9
    Join Date
    Apr 1999
    Posts
    27,423

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

    Quote Originally Posted by yellowMonkeyxx View Post
    I've tried a few variations of defining a list iterator, such as
    Code:
    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:
    Code:
    typename std::list<T>::const_iterator it;
    Regards,

    Paul McKenzie

  10. #10
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,281

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

    Quote Originally Posted by Lindley View Post
    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:

    Code:
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center