Thread: implementing iterator in copy ctor

  1. #1
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127

    implementing iterator in copy ctor

    my current copy ctor looks like this:
    Code:
    template <typename T> List<T>::List<T>(const List& src) : head(new Node(T())), tail(new Node(T()))
    {
        clear();  // This deletes all the Nodes in the list
    
        for( Node* temp = ( src.head )->next; temp != src.tail; temp = temp->next )
        {
            pushb( temp->data ) ;
        }
    }
    I have a public Iterator class declared in the List class:
    Code:
    class List
    {
        public:
           class Iter;
           Iter begin(){ return Iter(head); }
           Iter end(){ return Iter(tail); }
    I've overloaded the operator++(pre & post) , operator--(pre & post) and the operator*.

    How can I implement my Iter's in my copy ctor? What I'm worried about is the src.head & src.tail.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    There is no Iter member, so you shouldn't have to worry about the Iter class in the List copy constructor.

    If you are worried that an Iter returned by begin() or end() will be invalidated by copying, then I would not worry about it. Let the user of the class enforce that. It will never be a problem for the copy constructor anyway, since it is a constructor and the object won't exist before it is called. It might be an issue for the copy assignment operator, but there isn't much you can do short of having complicated pointers from the List to the Iters and back that "clean up" the Iters that have been used.

    BTW, there is probably not any need to clear() the list in a copy constructor. The list should be empty when you first construct an object.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    There's something strange about your immediately allocating a head and a tail node. I don't know your implementation, and it may be necessary (e.g. to implement bidirectional iterators), but those nodes shouldn't hold any data. As it is, you require the value type of the list to provide a default constructor, and you expect it not to have any side effects. Both are assumptions you shouldn't make.
    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

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I don't know your implementation, and it may be necessary (e.g. to implement bidirectional iterators)
    Why? Both end() and rend() would return NULL, and if you set head and tail to NULL for an empty list, so would begin() and rbegin() - being immediately equal to end() and rend(), so no iteration would occur...
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    Here's my .h file:
    Code:
    #ifndef LIST_H
    #define LIST_H
    
    template < typename T > class List
    {       
        public:
    
            List() : head( new Node( T() ) ), tail( new Node( T() ) ) {}
            
            List( const List& src ) : head( new Node( T() ) ), tail( new Node( T() ) )
            {
                clear();
    
                for( Node* temp = ( src.head )->next; temp != src.tail; temp = temp->next )
                {
                    pushb( temp->data ) ;
                }
            }
           
           ~List()
            {
                clear();
                delete head;
                delete tail;
            }
           
            class Iterator;
            Iter begin(){ return Iter(head); }
            Iter end(){ return Iter(tail); }
    
            /*  INTERFACE:
            */
            bool empty();
            unsigned int size();
            int sorted();
            bool prox( const T& );
            void makef( const T& );
            void pushf( const T& );
            void pushb( const T& );
            void popf();
            void popb();
            void insert( const T& );
            void revins( const T& );     
            void ins( const T& ); 
            void remove( const T& );
            void revrem( const T& );
            void rem( const T& );
            void remall( const T& );
            void dis();
            void revdis();
            void sort();
            void revsort();
            void rev();
            bool search( const T& );
            void consearch( const T& );
            void clear();
            
        private:
            
            
            class Node;
            Node *head, *tail;
            
    };
    
    template <typename T> class List<T>::Iterator{
    
       public:
          
          
          Iterator(Node* p) : Node_(p) {}
         ~Iterator() {}
          
          Iterator& operator=(const Iterator& other)
          {
             Node_ = other.Node_;
             return(*this);
          }
    
          Iterator& operator++()
          {
             if (Node_ != NULL)
             {
                Node_ = Node_->next_;
             }
             return(*this);
          }
    
          Iterator& operator++(int)
          {
             Iterator tmp(*this);
             ++(*this);
             return(tmp);
          }
    
          // Node directly.
          T& operator*()
          {
             return(Node_->getVal());
          }
    
       private:
          Node* Node_;
       };
    
    
    
    
    template <typename T> class List<T>::Node{
        
        public:
        
            Node( const T& x, Node* y = 0, Node* z = 0 ) : data( x ), prev( y ), next( z ) {}
            Node( const Node& src ) : data( src.data ), prev( src.prev ), next( src.next ) {}
            
            const T getVal(){ return data; }
        
        private:
                
            T data;
            Node *prev, *next;      
                
    };
    
    #endif

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The list needs the assignment operator.

    I'm pretty sure that iterators need the == and != operator. How else would you write:
    Code:
    for (ListIterator it = my_list.begin(); it != my_list.end(); ++it)
    And I still can't see why you need to insert two unused nodes into an empty list.

    By the way, do you get compiler errors? The compiler tells me that Iterator (not Iter) is an incomplete type (in Iter begin() and Iter end()), suggesting that the nested class should be defined inside the List class. So is Node.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Either define the nested classes inside the nesting class, or define begin() and end() out of line, after defining the nested classes. Either way works.

    There are more peculiarities, e.g. your interface member names. pushf, pushb, etc. Why not use push_front, push_back, and all those names from std::list? What on earth is revins? prox?What's the difference between rem and remove?

    Also, there's too much copying of the value type going on. In particular, Node::getData() returns the object by value. This means that a list node, once added, can never be changed. Is that what you actually intended?
    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

  8. #8
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    Quote Originally Posted by CornedBee
    Also, there's too much copying of the value type going on. In particular, Node::getData() returns the object by value. This means that a list node, once added, can never be changed. Is that what you actually intended?
    No. I've only added that recently to try and get the Iterator working.

    As far as the names, they're just the names that i like. I like the minimum amount of typing while still knowing what they are.

    pushf = push_front

    popb = pop_back

    prox = proximity ( tells me whether the query is closer to the head or tail )

    remove = removes an item from the list, iteration begins from the head

    revrem = removes an item from the list, iteration begins from the tail

    rev = removes an item from the list, iteration direction is decided after prox() has been called



    ....hopefully that clears up some of the naming conventions i've chose.

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I _think_ CornedBee's comment was more to the effect "Why are you NOT using the existing names for existing functionality". The idea is that you should be able to quickly switch from one form of template class to another. If you use non-standard names, it's much harder to replace a standard class with your class. I realize you are probably not planning to use this for commercial use, but still, it's kind of useful to be able to just switch back and forth between similar capability classes.

    You could even write a test-case where you can switch between your class and some similar capability standard class, just to verify that your test-case works - say using a macro to define if you use your class or a standard class.

    Making things "work the way people expect" is a very important part of software engineer. One of those expectations is in the naming convention. You don't want to remember three different variants of "push_back()" for three different classes, do you?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Get an IDE with auto-complete. Most of the time you shouldn't need to type more than 2-3 characters after "." and Enter

    There is still something strange about the list. It seems to me that you are implementing something like a multiset as a list - because a lot of the functionality seems to be based on finding elements.

    There is nothing wrong with it if it is a learning exercise but it seems that there might be much more suitable container types for these tasks.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Yes, all the lookup of values is not really what a list is good for.
    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

  12. #12
    Registered Abuser
    Join Date
    Sep 2007
    Location
    USA/NJ/TRENTON
    Posts
    127
    thankx everyone. I understand linked-lists pretty well i think. typically i would use a much simpler implementation such as:
    Code:
    class List{
        
        public:
           
            /* Interface */
    
       private:
    
            struct Node{...};
            Node *head, *tail;
    };
    The template thing definately obfuscates the whole thing though. To add to my confusion, there's the whole iterator thing, which I was trying to emulate what many STL implementations I've seen do.

    Can anyone write up a simple outline like I've done above, to show me the RIGHT way I should be doing a template linked-list class?

  13. #13
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Make up your mind. Do you want to learn how to make a linked list or how to write a templated container with iterators? If it is the latter you might practice upon a simpler underlying container type - even something as simple as a static array (like boost::array) - unless you have a good non-templated, iteratorless implementation of a linked list around that you can use as your base. It seems that you are trying to implement too much functionality for a learning exercise (considering that a linked list is very bad at many of those things).

    As to templates, you might start out with a non-templated version that works with int's for example. Then, if you get that working, just change the relevant int's to typename T.

    I'm no expert in iterators but what I know I learnt from Bruce Eckel's freely downloadable Thinking in C++, vol. 1, last chapter.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I have no idea if this is particularly {good, useful, bad, ugly} (chose any of the above), but I hacked this up while my wife was whatching TV this evening:
    Code:
    // list.h
    #ifndef LIST_H
    #define LIST_H
    
    template <typename T> 
    class mlist {
    private:
    	class Node {
    	public:
    		T data;
    		Node *next;
    		Node(const T &d) : data(d), next(0) { };
    	};
    	Node *head; 
        Node *tail;
    public:
    	class iterator
    	{ 
    	private: 
    		Node *curr;
    	public:
    		iterator(Node *n = 0):curr(n){};
    		iterator & operator++(int) { curr = curr->next; return *this; };
    		bool operator!=(const iterator &i) {
    			return i.curr != curr;
    		};
    		const T &operator*() const { return curr->data; };
    	};
    	void push_back(const T &a);
    	mlist<T>();
    	iterator begin() const { return iterator(head); };
    	iterator end() const { return iterator(tail->next); };
    };
    
    template <typename T>
    mlist<T>::mlist() : head(0), tail(0)
    {
    }
    
    template <typename T>
    void mlist<T>::push_back(const T &a)
    {
    	if (!head) {
    		tail = head = new Node(a);
    	}
    	else 
    	{
    		tail->next = new Node(a);
    		tail = tail->next;
    	}
    }
    
    #endif
    Code:
    // main.c:
    #include <iostream>
    #include "list.h"
    
    mlist <int> ilist;
    
    int main() 
    {
    	std::ofstream out;
    
    	ilist.push_back(3);
    	ilist.push_back(4);
    	ilist.push_back(5);
    	ilist.push_back(6);
    	ilist.push_back(7);
    
    	for(mlist<int>::iterator i = ilist.begin(); i != ilist.end(); i++) {
    			std::cout << "node = " << *i << std::endl;
    		}
    
    	return 0;
    }
    It's certainly a minimal approach, and there's almost certainly some problems with it that I haven't figured out yet - it is my first "STL-style" template class, so don't be too harsh on it... :-)

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    The larch
    Join Date
    May 2006
    Posts
    3,573
    You should change the end () method, to make it more efficient and not crash with empty lists

    Code:
    iterator end() const { return iterator(0); };
    I also suspect that if you only allow readonly access through the iterator, it should be called const_iterator more properly.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Functions which return a reference
    By Stonehambey in forum C++ Programming
    Replies: 10
    Last Post: 07-05-2008, 01:43 PM
  2. Question about linked-list copy ctor
    By dudeomanodude in forum C++ Programming
    Replies: 8
    Last Post: 03-06-2008, 10:29 AM
  3. calling copy constructor from template
    By Ancient Dragon in forum C++ Programming
    Replies: 3
    Last Post: 09-28-2005, 01:54 PM
  4. dynamic memory alloccation & returning objects
    By haditya in forum C++ Programming
    Replies: 8
    Last Post: 04-21-2005, 11:55 PM
  5. Copy Constructor Help
    By Jubba in forum C++ Programming
    Replies: 2
    Last Post: 11-07-2001, 11:15 AM