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

This is a discussion on list with homebrew iterators...and hopefully not leaky. within the C++ Programming forums, part of the General Programming Boards category; It is not totally complete and a bit late (because of Deus Ex:HR).. but posting to see if I'm on ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490

    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;}
        };
    }
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,524
    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.

  3. #3
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,524
    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.

  5. #5
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    list() creates an empty list, where first and last are nullptrs and rend_it and end_it act as the sentinel nodes.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,524
    You didn't do that right then. Sentinel nodes have to be part of the list in order to be sentinels.

  7. #7
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    What is wrong with nodes one past the end on both ends acting the delimiter?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,524
    Quote Originally Posted by manasij7479 View Post
    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.

  9. #9
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  10. #10
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,524
    Code:
     mm::list<char> mylist; for ( mm::list<char>::iterator i = mylist.begin(); i != mylist.end(); i++ ) ;
    Forget about what the loop could do, just prove to me that you can get from first (which is a nullptr) to a sentinel node. I don't see it.
    Last edited by whiteflags; 10-17-2011 at 06:25 AM.

  11. #11
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    Quote Originally Posted by whiteflags
    just prove to me that you can get from first (which is a nullptr) to a sentinel node. I don't see it.
    Simple, compile it.
    Code:
    int main()
    {
        mm::list<int> li;
        li.push_back(9);
        li.push_back(474);
        li.push_back(3);
        
        auto it = li.begin();
        li.insert(it,10);
    
    
        for(auto x = li.begin();x!=li.end();x++)
            std::cout<<*x<<std::endl;
        return 0;
    }
    This results in:
    Quote Originally Posted by a.out
    10
    9
    474
    3

    Which won't be possible unless ....<>.

    and.. first is a nullptr only in a blank list..
    Last edited by manasij7479; 10-17-2011 at 06:18 AM.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  12. #12
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,524
    Do you agree that iterating over an empty list should not result in a segfault...?

  13. #13
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    Quote Originally Posted by whiteflags View Post
    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' .
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



Popular pages Recent additions subscribe to a feed

Similar Threads

  1. List Iterators, erase() -- help
    By Syndacate in forum C++ Programming
    Replies: 16
    Last Post: 02-11-2011, 09:04 PM
  2. incrementing list iterators
    By Lima in forum C++ Programming
    Replies: 7
    Last Post: 04-25-2007, 12:53 PM
  3. <list> iterators with nested templates
    By dwylie in forum C++ Programming
    Replies: 4
    Last Post: 07-19-2005, 12:13 PM
  4. Kosher or leaky?
    By CodeMonkey in forum C++ Programming
    Replies: 2
    Last Post: 06-02-2005, 04:10 PM
  5. std::list and iterators
    By Magos in forum C++ Programming
    Replies: 2
    Last Post: 04-04-2005, 09:03 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21