Thread: inheriting iterators

  1. #1
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391

    inheriting iterators

    I was reading this trying to figure out how to implement the decrement operator (because I'm guessing I need the bidirectional_iterator) for the circular_iterator template class but it's not working.

    The increment operator seems to work fine but when I use decrement it complains.

    Here's what main looks like:
    Code:
    int main(){
    	
    	list<int> *m_list;
    	m_list = new list<int>();
    	
    	for( int i = 0; i < 10; i++ )
    		m_list->push_back( i+1 );
    		
    	circular_list_iterator<int> it = m_list;
    	for(; it != circular_list_end( m_list ); --it) // Complains here (main.cpp line 42)
    		std::cout << *it << endl;
    	
    	return 0;	
    }
    Here's the header for circular_list_iterator:
    Code:
    template<typename T>
    class circular_list_iterator : public std::iterator<std::bidirectional_iterator_tag, T>{
        
        public:
        
            circular_list_iterator( std::list<T>* container )
            : container( container ), iter( container->begin() ) {}
    
        	circular_list_iterator( std::list<T>* container, typename std::list<T>::iterator iter )
            : container( container ), iter( iter ) {}
            
        	circular_list_iterator& operator++(){
            	
                if ( iter != container->end() )
                    ++iter;
                else
            	iter = container->begin();
                return *this;
        	}
        		
        	circular_list_iterator& operator--(){
        			
        	    if ( iter != container->rend() ) // circ_iter.h line 32
        		--iter;
        	    else
        		iter = container->rbegin(); // circ_iter.h line 35
        	    return *this;
        	}
    
        	T& operator*(){ return *iter; }
    
        	bool operator!=( circular_list_iterator rhs ) const { return iter != rhs.iter; }
    
        private:
        
        	std::list<T>* container;
        	typename std::list<T>::iterator iter;
    };
    
    template<typename T>
    circular_list_iterator<T> circular_list_end( std::list<T>* container ){
        
        return circular_list_iterator<T>( container, container->end() );
    }
    Here's what g++ has to say about all this:
    Code:
    circ_iter.h: In member function ‘circular_list_iterator<T>& circular_list_iterator<T>::operator--() [with T = int]’:
    main.cpp:42:   instantiated from here
    circ_iter.h:32: error: no match for ‘operator!=’ in ‘((circular_list_iterator<int>*)this)->circular_list_iterator<int>::iter != std::list<_Tp, _Alloc>::rend() [with _Tp = int, _Alloc = std::allocator<int>]()’
    /usr/include/c++/4.1.3/bits/stl_list.h:173: note: candidates are: bool std::_List_iterator<_Tp>::operator!=(const std::_List_iterator<_Tp>&) const [with _Tp = int]
    main.cpp:42:   instantiated from here
    circ_iter.h:35: error: no match for ‘operator=’ in ‘((circular_list_iterator<int>*)this)->circular_list_iterator<int>::iter = std::list<_Tp, _Alloc>::rbegin() [with _Tp = int, _Alloc = std::allocator<int>]()’
    /usr/include/c++/4.1.3/bits/stl_list.h:112: note: candidates are: std::_List_iterator<int>& std::_List_iterator<int>::operator=(const std::_List_iterator<int>&)
    make: *** [main.o] Error 1
    So is the problem with rend() and rbegin()? Is it with the iterator category I've inherited? Also, with the use of the pointer to the container, is the inheritance even necessary?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    rbegin() and rend() return reverse_iterators, which are a different type than your iter member variable. You can't compare those two different types.

    You should still use end() and begin(), and just check to see if the iterator hits begin() before decrementing instead of checking end() like you did in the increment.

  3. #3
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Ok, so here's the changes I've made...

    this is the new decrement:
    Code:
    circular_list_iterator& operator--(){
        			
        			if ( iter != container->begin() )
        				--iter;
        			else
        				iter = container->end();
        			return *this;
        		}
    here's a circular_list_iterator begin function (entirely for the purpose of figuring this out):
    Code:
    template <typename T>
    circular_list_iterator<T> circular_list_begin( std::list<T>* container ){
    	
    	return circular_list_iterator<T>( container, container->begin() );
    }
    and here's what main looks like now:
    Code:
    int main(){
    	
    	list<int> m_list;
    	
    	for( int i = 0; i < 10; i++ )
    		m_list.push_back( i + 1 );
    	
    	circular_list_iterator<int> it( &m_list, m_list.end() );
    	for(; it != circular_list_begin( &m_list ); --it){
    		std::cout << *it << "\n";
    	}
    	
    	return 0;	
    }
    And unfortunately my output look like this:
    Code:
    10
    10
    9
    8
    7
    6
    5
    4
    3
    2
    close but no cigar.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  4. #4
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    I think the problem with my output is that end() returns one past the actual last element in the list. So, I guess I need to work that out now...
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  5. #5
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Code:
    template <typename T>
    circular_list_iterator<T> circular_list_begin( std::list<T>* container ){
    	
    	return circular_list_iterator<T>( container, container->begin() );
    }
    This is wrong. Because end() returns one past the last element in the list, this is NOT the reverse-equivalent if you will. And changing it to:

    --container->begin()

    just gives me an erroneous address.

    hmmmmm.........

    what to do? what to do.....
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> what to do? what to do.....

    There is a simple solution that is rather analogous to the solution to the similar problem you had with the forward iterator. Think about when your decrement function causes the iterator to point to an invalid location and think about where it should really point to.

  7. #7
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Quote Originally Posted by Daved View Post
    >> what to do? what to do.....

    There is a simple solution that is rather analogous to the solution to the similar problem you had with the forward iterator. Think about when your decrement function causes the iterator to point to an invalid location and think about where it should really point to.
    And I'm STILL having that problem with the forward iterator, now it's just the same thing with the other direction as well. I was too caught up in changing the container to a pointer (which was easy once I figured out that it doesn't follow the same syntax like the iterators I'm used to).

    Ok, I'll figure this out, thank you Daved for all your help on this matter.

    and laserlight for supplying the underlying code!

    I truly appreciate you guys for your patience!
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> And I'm STILL having that problem with the forward iterator
    Sorry, I didn't notice that.

    Just picture or draw a small list of 3 elements. Draw the begin() iterator pointing to the first element and the end() iterator pointing to a fake element one past the third (and last) actual element.

    Now just start with your circular iterator at begin() and figure out where it should go after incrementing (in your picture). Keep doing that until you've gone through the list and are back past the beginning. You should see where the iterator is stopping at an invalid point, and where it should be instead.

    Another hint would be to check the location of the iterator after the increment or decrement and make sure it's valid. This might be more intuitive (even though either way can probably work).

  9. #9
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Here's my quick fix thus far:
    Code:
    circular_list_iterator& operator++(){
            	
            		++iter;
            		if( iter == container->end() )
            			iter = container->begin();
    
            		return *this;
        		}
    though, this renders the circular_list_end() function USELESS, because if used in conjuntion in the for loop, it's an infinite loop.

    Do I really need the circular_list_end() function though? I heard some of the pros and cons for and against it, but I don't think it really suits my purposes (especially since I'm not doing the multithreaded thing involving circular-lists anytime soon).

    What do you think?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  10. #10
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    and this gives me the equivalent behavior for the decrement:
    Code:
    circular_list_iterator& operator--(){
        			
        			--iter;
        			if( iter == --container->begin() )
        				iter = --container->end();
        			return *this;
        		}
    though it looks a bit odd...
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  11. #11
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    The copy ctor also proved straightforward and useful so now I can declare the circular_iterator like this:

    Code:
    circular_list_iterator<int> it = circular_list_begin( &m_list );
    it = circular_list_rbegin( &m_list );
    It doesn't seem necessary to write the assignment operator, though i could be wrong.

    I also found the circular_list_begin, circular_list_end, etc. functions useful at least for initialization and copying purposes.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Your increment operator looks good. Well done.

    Your decrement is overly complicated and actually not legal. You can't do --begin(). Maybe think about avoiding doing a -- on a begin iterator and converting it to end() first.

    It's not necessary to write the copy assignment operator or the copy constructor. Both will work as intended. What you wrote was not a copy constructor. This is how you might use a copy constructor:
    Code:
    circular_list_iterator<int> it1( &m_list ); // regular constructor
    circular_list_iterator<int> it2(it1); // copy constructor
    Also, implementation of rbegin doesn't seem necessary, and if you wanted it you should make a separate class (since standard library rbegin() functions return a different type).

    I'm not sure of the need of circular_list_begin or circular_list_end. I can't think of any reason to have those as part of your class, but I might be wrong.

    Finally, one minor observation is that your regular constructor should take a container reference, not a pointer. You should still store a pointer in the class, but by making the parameter a reference you force the user to pass a real container and not a null pointer.

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Think about decrement as the reverse of the increment operation. In increment, you do this:
    1) Increment the iterator.
    2) If it's now equal to the end, set it to the start.

    What's the exact reverse of this? (You could just go peeking in my circular iterator.)
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #14
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Okay, I fixed the decrement operator:
    Code:
    circular_list_iterator& operator--(){
        			
        if( iter == container->begin() )
            iter = container->end();
        --iter;
        return *this;
    };
    I verified with CornedBee's example, so I think that's right now.

    Here's how I changed my constructors to take a reference while still storing the pointer to the container:
    Code:
    circular_list_iterator( std::list<T>& container )
    : container( &container ), iter( container.begin() ) {};
    
    circular_list_iterator( std::list<T>& container, typename std::list<T>::iterator iter )
    : container( &container ), iter( iter ) {};
    I think those are right now.

    As for the begin, end, rbegin, rend functions, I find them useful for initializing the iterator (and nothing else really).

    This is why I find them useful:

    If I want to iterate the list starting from the end I need to initialize the circular iterator like this:
    Code:
    circular_list_iterator<int> it( m_list, m_list.end() );
    --it;
    
    // iterate the list as normal
    but if I want to actually refer to the last element of the list using my own rbegin function I do so like this:
    Code:
    /* Here's rbegin():
    */
    template <typename T>
    circular_list_iterator<T> circular_list_rbegin( std::list<T>& container ){
    	
    	circular_list_iterator<T> it( container, container.end() );
    	return --it;
    }
    
    /* And here's how it can be used in initialization:
    */
    circular_list_iterator<int> it = circular_list_rbegin(m_list);
    
    // iterate the list as normal
    Is this okay? Any hidden problems with that, that I can't see? Does this diverge somehow from the standard use of rbegin() and rend() (besides of course NOT returning a reverse iterator)

    Thoughts?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  15. #15
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Okay, I fixed the decrement operator
    Looks good.

    >> Here's how I changed my constructors to take a reference while still storing the pointer to the container
    Looks good.

    >> circular_list_iterator<int> it( m_list, m_list.end() );
    My personal opinion is that if the constructor takes an iterator it should check to see if the iterator is end() and change it to begin() if it is. You should always have a valid list iterator in the circular_list_iterator class, and if you just store the end() directly that won't be the case.

    >> Does this diverge somehow from the standard use of rbegin() and rend()
    Yes. In the standard library, if you store the result of rbegin(), you have to use ++ to walk backwards through the list towards rend(). You don't use -- (unless you want to go forward through the list with the reverse_iterator).

    What you want is not rbegin, it is just end. However, you still don't need a special function for that. If you make the fix I mentioned in the constructor, then you can do this before iterating backwards:

    Code:
    circular_list_iterator<int> it(m_list, m_list.end());
    That will work the same way. In fact, you could also do either of these two as well:
    Code:
    circular_list_iterator<int> it(m_list, m_list.begin());
    circular_list_iterator<int> it(m_list);
    They're all the same and would allow you to iterate forwards or backwards through the list with ++ or --.

    The point of the reverse iterator is that there is templated code that takes something that implements the concept of an iterator. For example, the copy algorithm takes first and last iterators and uses ++ on the first iterator until it matches the last. But what if you wanted to copy backwards? You can't use -- because the copy algorithm code is already written to use ++. Instead you use a reverse_iterator. Those follow the concept of an iterator in that you can use ++ to move through the container. The difference is that ++ causes the iterator to move backwards. This allows you to pass iterators to code that expects them and still go in the opposite direction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. algorithms over vector: offsets or iterators for speed?
    By pheres in forum C++ Programming
    Replies: 2
    Last Post: 04-09-2009, 02:23 AM
  2. C++ STL: Why use member iterators
    By Vandrian in forum C++ Programming
    Replies: 4
    Last Post: 04-03-2008, 11:52 AM
  3. vector of strings with iterators.
    By Mario F. in forum C++ Programming
    Replies: 6
    Last Post: 05-31-2006, 12:12 PM
  4. Using reverse iterators in algorithms
    By 0rion in forum C++ Programming
    Replies: 1
    Last Post: 02-27-2006, 03:19 AM
  5. Writing Iterators...
    By Geolingo in forum C++ Programming
    Replies: 6
    Last Post: 05-29-2003, 09:31 PM