Thread: list with homebrew iterators...and hopefully not leaky.

It is not totally complete and a bit late (because of Deus Ex:HR).. but posting to see if I'm on the right track:
1.Are iterators supposed to be implemented the way I've done in this?

2.Is the design better compared to my earlier list ? Any more leaks?
< Doubly linked list... nitpick and test if possible >

3. The remove function works okay when in the middle, but at the extreme positions, it leaves a 0. I know this is because I'm not reseting the first and last pointers; but whenever I do so, the loop(for(auto x = foo.begin();x!=foo.end();x++)) runs forever.

Code:

namespace mm
{
    template<typename T> class list
    {
        template <typename X> class node
        {
        public:
            X val;
            node<X>* next;
            node<X>* prev;
            node<X>(const T& t,node<T>* n,node<T>* p )
            {
                val =t;next = n;prev =p;
                n->prev=this;
                p->next=this;
            };
            node<X>(){prev = next = nullptr;};
            ~node<X>(){next->prev = prev;prev->next = next;}
            
        };
        node<T>* first;
        node<T>* last;
        
        node<T>* end_it;
        node<T>* rend_it;
        
        int size_val;
    public:
        class iterator
        {
            
        public:
            node<T>* n;
            iterator(node <T>* arg){n=arg;};
            T& operator*(){return n->val;}
            iterator operator++(int){n=n->next;return *this;};
            iterator operator--(int){n=n->prev;return *this;};
            bool operator!=(iterator it){return n!=it.n;};
            bool operator==(iterator it){return n==it.n;};            
        };
        iterator begin(){return iterator(first);};
        iterator end(){return iterator(end_it);};
        iterator rbegin(){return iterator(last);};
        iterator rend(){return iterator(rend_it);};


        list()
        {
            first= last = nullptr;size_val=0;
            end_it = new node<T>();rend_it=new node<T>();
            end_it->next = rend_it;
            rend_it->prev = end_it;
        }
        void push_back(const T& t)
        {
            if(size_val==0)
            {
                auto new_node = new node<T>(t,end_it,rend_it);
                first = last = new_node;
            }
            else
            {
                auto new_node = new node<T>(t,end_it,last);
                last = new_node;
            }
            size_val++;
        }
        
        iterator insert(iterator& pos,const T& t)//Insert t before pos
        {
            auto new_node = new node<T>(t,pos.n,pos.n->prev);
            if(pos.n==first)first= new_node;
            else if(pos.n==end_it)last = new_node;
            //else if (pos.n==rend_it) throw "<<something>>";
            size_val++;
            return iterator(new_node);
        };
        void remove(iterator pos){delete pos.n;}
    };
}

Your iterator implementation obviously has some problems, if it's causing infinite loops. The end() iterator is supposed to be one past the end of the sequence, ie end_it + 1. If you remove the end node and then set the end() pointer this way, the loop ends like you would expect because it points to the place of the node you just removed.

Also I think reverse iterators are a little more complicated than the way you implemented. For example, if you have a reverse iterator i, i++ should do the right thing and get the previous node. i-- actually goes forward.

Also I think reverse iterators are a little more complicated than the way you implemented. For example, if you have a reverse iterator i, i++ should do the right thing and get the previous node. i-- actually goes forward.

Ops.. forgot that. That'd need a new class, or too many boolean flags.

The end() iterator is supposed to be one past the end of the sequence

pointer end_it is already 1 forward of the end.

pointer end_it is already 1 forward of the end.

It doesn't look like it to me.

Code:

list()
{
   first = last = new node<T>;
   end_it = last->next;
   begin_it = first;
   rbegin_it = last;
   rend_it = first->prev;
}

I suppose I would do it like this.

list() creates an empty list, where first and last are nullptrs and rend_it and end_it act as the sentinel nodes.

You didn't do that right then. Sentinel nodes have to be part of the list in order to be sentinels.

What is wrong with nodes one past the end on both ends acting the delimiter?

Originally Posted by manasij7479

What is wrong with nodes one past the end on both ends acting the delimiter?

Read my post again. If the sentinel nodes aren't part of the list, then they aren't sentinels. Start with begin() and try to get to end(); or rbegin() and try to get to rend(); you never will if they aren't connected to the list, because operator++ depends on the links to traverse the list.

In my case, they are connected in the sense that ++ing from last gets to end_it and --ing from first gets to rend_it.

Do you agree that iterating over an empty list should not result in a segfault...?

Originally Posted by whiteflags

Do you agree that iterating over an empty list should not result in a segfault...?

Ah.. missed that.
It tries to access a member of a empty pointer.

Changed the constructor a little, instead of making first a nullptr for a blank list, I'm now assigning it the same value as end_it.
Problem Solved.. Thanks for the 'prod' .