C++

Forum

 
Perfecting my linked list

Pages: 12345
Volatile Pulse (1543)
That really makes more sense now that I look at it. So with the range based for loops, there is no way to actually tell which position you're at? Like, you can't compare the iterator, just the values?

A few other things that I was working on the last few days were rend, rbegin, remove, unique, and erase. Remove and unique are quite easy, or at least I think so. But they both rely on erase which I can't seem to get down.

To start with, I started working on rend and rbegin, thinking they'd just be the opposite of their forward counterparts. Then I looked at how the STL library did it. It uses a reverse iterator. Do I need to create a whole new class for the reverse iterator, or can I just inherit from my iterator class and change what I need? Mine works, aside from the fact that you need to decrement the iterator as opposed to incrementing it like the STL library does it.

Back to the erase function though, here was my first attempt at it that failed miserably.
1
2
3
4
5
6
7
8
9
10
11
12
13
 
template<class T>
typename vp::list<T>::iterator vp::list<T>::erase(iterator it) {
   if (it == iterator())
      return it;
   node* prev = it.current->prev;
   node* next = it.current->next;
   delete it.current;
   prev->next = next;
   next->prev = prev;
   it.current = prev;
   mSize --;
   return iterator(prev);
}


I didn't think about it prior, but why can't my list access the iterator's private members? The list is still the parent class, or would I need to change it to protected to have it work like that? A second attempt at this is going to be me looping through the list with a temp node* and check to see if (iterator(temp) == it) I don't see that that's very efficient since it creates a new iterator at each step of the loop and the overhead would be huge.

Also, with the erase functions, the STL doesn't use a reference to the iterators. Won't this cause issues since the node that the iterator points to would be deleted? Or is this not an issue since an iterator would still be modified since it's essentially a pointer? Also, it's supposed to return an iterator. I'm assuming to point at the position before "it" or iterator() if empty.

And finally to unique. Once I figure out how to erase properly, I can just call that when the value passed to unique is equal to whatever dereferenced iterator I'm currently at.

Here's what I have so far for remove:
1
2
3
4
5
 
void vp::list<T>::remove(const T& value) {
   for (iterator it(firstNode); it != end(); it ++)
      if (*it == value)
         it = erase(it);
}


Obviously it doesn't work yet since erase isn't working properly, but the line it = erase(it); doesn't "feel" right. In my mind it should just be erase(it);

I know this is a lot at once, but I've been without internet for the last few days so I've been trying to get a bunch of stuff together before posting again.

Again, thanks for all of the help so far. You have no idea how much I've learned from you and how happy it's making me to finally understand how everything works.
closed account (D80DSL3A)
Can I make a code suggestion for your elusive erase() function?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
template<class T>
typename vp::list<T>::iterator vp::list<T>::erase(iterator it) {
   if (it == iterator())
      return it;
   // tie the links across it.current
    if( it.current->prev ) it.current->prev->next = it.current->next;
    if( it.current->next ) it.current->next->prev = it.current->prev;

    // create an iterator for the return value
    iterator retVal( it.current->prev );

    // now you can delete it
   delete it.current;
   
   mSize --;
   return retVal;
}
Volatile Pulse (1543)
I still run into the issue of not being able to access current. I had wanted to keep it private, or should my list be allowed to access that member? I also need to work on setting up the correct link between elements for when the iterator points at firstNode or lastNode so that they don't break. That was just a rough function to see what could be done and since it violates member access rules, I was looking into other means.

Granted, changing current to a protected member instead of private would make my life a lot easier in the long run, is that the proper way to remedy this situation?
closed account (D80DSL3A)
Not sure about the private/protected issue, but clearly you need to do something there.
You can't make this a member function of the iterator class because the result would be an object deleting itself.

Re:
I also need to work on setting up the correct link between elements for when the iterator points at firstNode or lastNode so that they don't break.


Sorry, I forgot that detail. Whether firstNode or lastNode needs to be updated can be judged from the values of it.current->next and prev, like so:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
template<class T>
typename vp::list<T>::iterator vp::list<T>::erase(iterator it) {
   if (it == iterator())
      return it;

   // tie the links across it.current
    if( it.current->prev ) 
        it.current->prev->next = it.current->next;
    else
        firstNode = it.current->next;

    if( it.current->next ) 
        it.current->next->prev = it.current->prev;
    else
        lastNode = it.current->prev;

    // create an iterator for the return value
    iterator retVal( it.current->prev );

    // now you can delete it
   delete it.current;
   
   mSize --;
   return retVal;
}
cire (8284)
Well, the list class should be a friend of the node class:

1
2
3
4
 
       class iterator {
               // ...
               friend class list<T> ;
         };


We're talking about removing a node from the list and deleting the node. So, why not make one do the other? It requires a small change to the node class - the addition of a destructor.
1
2
3
4
5
6
7
8
9
10
11
 

         struct node {
             // ...
            ~node()
            {
                if ( prev )
                    prev->next = next ;
                if ( next )
                    next->prev = prev ;
            }
         };


And erase suddenly becomes much easier to implement.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template<class T>
typename vp::list<T>::iterator vp::list<T>::erase(iterator it) {
   if (it != end()) 
   {
        if ( firstNode == it.current)
            firstNode = it.current->next ;
        if ( lastNode == it.current)
            lastNode == it.current->prev ;

       --mSize ; 
       delete (it++).current ;
   }
   return it ;
}


Not tested, btw.

[Edit: Note that erase should not return the previous element in the list -- what happens when you erase the first one?]

[Edit 2: Fixed erase to account for firstNode and lastNode pointers. If you used actual nodes for those, there wouldn't be additional handling, but I don't know if keeping around two extra copies of T is a good idea. Maybe a base class node derives from without the data in it - probably more work than it's worth.)]
Last edited on
naraku9333 (2163)
@Volatile Pulse
VS2010's implementation of std::list::iterator has a _Mynode() method 
1
2
3
 
std::list<int> l(10, 5);
	for(std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
		std::cout<<(it._Mynode())->_Myval<<std::endl;
closed account (D80DSL3A)
That is cool!

Note that erase should not return the previous element in the list -- what happens when you erase the first one?

I did that because it looked like that was what you were trying to do above.
What would happen is a NULL (invalid) iterator would be returned.
What should the function return?

I noticed something similar about writing member functions in the node class that are normally handled by functions in the list class. These functions become much simpler and recursive solution methods almost jump out at you!

I found, for instance, that if a node was used to perform a push_back() on a singly linked list (in which no back* is being maintained) that this will do:
1
2
3
4
5
6
7
 
void node::push_back( int X )
{
    if( link )
        link->push_back(X);
    else
        link = new node( X, NULL );
}

This is intriguing, but I'm not sure what to do with it.
Further experimentation may make that clearer.
naraku9333 (2163)
erase should return an iterator that points to the next node, which if the erased node was the last the iterator will point to end().
cire (8284)
What should the function return?


erase should return an iterator to the element that follows the one to be erased.

usage:

1
2
3
4
5
6
7
8
9
 
vp::list<T>::iterator it = myList.begin() ;

while ( it != myList.end() )
{
    if ( filter_func(*it) )
        it = myList.erase(it) ;
    else
        ++it ;
}


which mimics the use of erase on standard containers.
Volatile Pulse (1543)
@naraku9333
Now, something that I'm unsure of is that I understand that it should return an iterator, but what I don't get is why the iterator passed isn't changed. for example: myIterator = myList.erase(myIterator); why do I need to set it equal to erase? Why can't it just modify myIterator? Or does it? that's one of those things that always eludes me.

@cire
That is awesome. But, I thought that since iterator was declared a part of list, it was automatically a friend. I must have been mistaken. And logically, why isn't the iterator passed to erase modified? If the iterator is no longer valid, what's wrong with modifying what the iterator points to?
cire (8284)
And logically, why isn't the iterator passed to erase modified?


It's a design decision that was made based (I would guess) on the premise that myList.erase(myList.begin()) should work. If erase took a non-const reference, the temporary returned by myList.begin() wouldn't bind to it, so going that way would require overloads for erase and inconsistent methodology as far as getting the correct iterator back to the user.
Volatile Pulse (1543)
Alright, so I went back to the program and I completed unique(). I didn't know this, but the STL unique only erases the node prior if they are the same, not every node that matches. This makes sense due to a large list, the overhead could get quite large. Anyways, here is the code. I feel like I'm missing something rather simple since it looks sorta ugly to me compared to the other functions I have.
1
2
3
4
5
6
 
template<class T>
void vp::list<T>::unique() {
   for (iterator it = begin(); it != end(); it ++)
      if ((it != begin()) && (*it == it.current->prev->value))
         erase(it);
}


I also went to start on the swap function, but realized that I never made an assignment operator for my list, so that will have to be made first.

Going back to the erase function, the STL list as has a two parameter version that makes use of a first and last iterator. It points to the first and ends just before the last one, which makes sense so you can do list.erase(list.begin(), list.end());. But is it supposed to check for cases when, let's say, it's list.erase(list.end(), list.begin());?

Edit: I assume not since upon testing it, the function never completes, ie, it hangs. But looking ahead, if you pass a null iterator, what should happen? Shouldn't it crash instead of hanging? I know you can't increment a null iterator, and imho, it should just return if first == end(). Maybe there is something I'm not seeing however.

And the one I think I'm going to have the hardest time with is sort. I believe the best way to do this is to shift the pointers to point to the correct node, sequentially. Would it add overhead to duplicate the list and use it as a reference? Which sort algorithm would work best? I'm only familiar with the bubble sort, however, I know there is much better ones out there.
Last edited on
closed account (D80DSL3A)
If you are trying to model the behavior of STL then I say don't be afraid to experiment so you can find out what the STL containers and functions will actually do.

This erase operation L.erase( L.end(), L.begin() ); will complete.
No compile time error, no exception thrown at runtime.

I then try writing the contents of the list to cout, checking if L is empty 1st of course:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
list<int> L;
    L.push_back(1);
    L.push_back(2);
    L.push_back(3);
    L.push_back(4);

    L.erase( L.end(), L.begin() );

    list<int>::const_iterator it = L.begin();
    if( !L.empty() )
    {
        for( ; it != L.end(); ++it )
            cout << *it << " ";
        cout << endl;
    }
    else
        cout << "L is empty" << endl;

Output? It isn't "L is empty"!

I get 1 2 3 4... forever.
So, in keeping with general C++ philosophy, this function does permit foot shooting.

EDIT:
And this results in 4 3 2 1...CRASH!!
1
2
3
4
5
6
7
8
9
10
11
 
L.erase( L.end(), L.begin() );

    list<int>::const_reverse_iterator it = L.rbegin();// try iterating thru backwards
    if( !L.empty() )
    {
        for( ; it != L.rend(); ++it )
            cout << *it << " ";
        cout << endl;
    }
    else
        cout << "L is empty" << endl;
Last edited on
closed account (D80DSL3A)
I now have a working selection_sort() for my own double list.
The initial version was quite long and I would not post it here.

Then I began experimenting with creating member functions for the
node class (dNode in mine) to "support" operations being performed during the sort. Since nodes must be removed from one spot in a list then inserted back in another spot I wrote a function, similar to erase, except that the node isn't destroyed:
1
2
3
4
5
6
7
8
9
10
 
void dNode::extract(void)
{
    if( prev )
        prev->next = next;

    if( next )
        next->prev = prev;

    prev = next = NULL;// isolating this dNode
}

This would always be followed by an insertion operation so the insert_after() starts off by calling extract (on itself!)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
// extract self from list then insert self after pNode
void dNode::insert_after( dNode* pNode )
{
    if( pNode )
    {
        if( pNode == this )
            return;// no inserting after self!!

        extract();// extract self from list.
        prev = pNode;
        next = pNode->next;
        if( pNode->next ) pNode->next->prev = this;
        pNode->next = this;
    }
}

Finally, there will be a need to find the node with the highest value (int x in mine) in the range of this to another given node in the list:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
// returns high node in range this to pLast (inclusive)
dNode* dNode::find_hiNode( dNode* pLast )
{
    dNode* curr = this;
    dNode* hiNode = this;
    int hiVal = x;
    // locate the hiNode
    while( curr != pLast )
    {
        curr = curr->next;
        if( curr->x > hiVal )
        {
            hiVal = curr->x;
            hiNode = curr;
        }
    }
    return hiNode;
}

Obviously, these functions can't help with maintaining firstNode, lastNode (front, back my list), nor should they, I would argue.

It is on the calling code to check the values of prev, next before and after these operations so that front and back can be maintained. This can be seen in my selection_sort() below.

I'm hoping that some experienced members will comment here on how many ways what I'm doing here with these node class member functions is wrong.

These functions simplified the writing of selection_sort() greatly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
void dList::selection_sort(void)
{
    if( front == NULL ) return;// no list to sort!
    if( front->next == NULL ) return;// list is too short to sort!

    int Niter = 0;
    dNode* itBack = back;// node with highest value will be moved to follow itBack in the list
    while( itBack != front )// itBack will move forward each iter until it reaches the front
    {
        ++Niter;
        // find the high node
        dNode *hiNode = front->find_hiNode( itBack );
        
        if( hiNode != itBack )// otherwise it is already where it belongs
        {
            // move hiNode to follow itBack in the list
            if( !hiNode->prev ) front = hiNode->next;
            hiNode->insert_after( itBack );// hiNode extracts itself from the list
                                        // then inserts itself back in the list between itBack and itBack->next
            if( !hiNode->next ) back = hiNode;
        }
        else// hiVal was already at the end
            itBack = itBack->prev;// Move itBack toward front 1 step
    }
    cout << "Niter = " << Niter << endl;
    return;
}// end of selection_sort()

EDIT: corrected function name from insertion_sort
Last edited on
Lowest0ne (1536)
Does your sort work? To me, it seems like there should be something like "while I keep finding things that are greater than me, keep inserting that greater one after me". Then decrement itBack.

closed account (D80DSL3A)
More like:
1) Find the node with highest value from front to itBack (inclusive).
dNode *hiNode = front->find_hiNode( itBack );

2a) If this hiNode != itBack, extract hiNode from where it is in the list and insert it after itBack.
Do NOT decrement itBack. It is one step closer to front because a node was removed between them.
1
2
3
4
5
 
if( hiNode != itBack )// otherwise it is already where it belongs
{//...           
    hiNode->insert_after( itBack );
     //...front, back maintenance details
}


2b) Otherwise, decrement itBack only.
1
2
 
else// hiVal was already at the end
      itBack = itBack->prev;// Move itBack toward front 1 step
Volatile Pulse (1543)
Alright, you've inspired me to work on sort, thanks fun2code. -.-

But doing some research I came across this: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Now, it has code, but I do want to attempt this by myself so as to learn a new sort algorithm. If I am understanding this right, it essentially starts out by have two, essentially, list of k size(1). We compare the first elements of each, place the smaller in list L, our sorted list, and increment that pointer. If there is no elements left in either pseudo list, we take the items from the other pseudo list, and add them to the back of L. Once one pass is complete, lists p and q are of size 2 and point to the head of L and we resort. Is this a proper evaluation of the mergesort?
Volatile Pulse (1543)
Alright, so I've been working on the sort algorithm and I believe I finally have it down. However, I realized almost near the end of the definition that I need to overload the = operator for my list. I did this and came up with this:
1
2
3
4
5
6
 
template<class T>
vp::list<T> vp::list<T>::operator= (list<T> l) {
   clear();
   for (T val : l)
      push_back(val);
}


However, my program crashes as soon as the operation completes and points to my list dtor and in turn my node dtor. Neither of which makes sense in this context since the function doesn't destroy anything. Where am I going wrong here?

Edit: On a side note, I was wondering how you can overload the value? operator. For example, when you do something like if (*node) it returns false if the pointer is NULL, and true if it points to something. Now how do you modify what gets returned from if (node)?

Is it just overloading the comparison operator with no parameters?
Last edited on
cire (8284)
I suspect your copy constructor isn't doing what it's supposed to.

Generally operator= would look more like:
1
2
3
4
5
6
7
 
template<class T>
vp::list<T>& vp::list<T>::operator= (const list<T>& l) {
   clear();
   for (T val : l)
      push_back(val);
   return *this;
}

Volatile Pulse (1543)
I was able to get it work properly doing the same as what you have, without using const. I get these errors using const however:
C:\Programming\List Practice\main.cpp||In instantiation of 'vp::list<T>& vp::list<T>::operator=(const vp::list<T>&) [with T = int]':|
C:\Programming\List Practice\main.cpp|378|required from 'void vp::list<T>::sort() [with T = int]'|
C:\Programming\List Practice\main.cpp|416|required from here|
C:\Programming\List Practice\main.cpp|196|error: passing 'const vp::list<int>' as 'this' argument of 'vp::list<T>::iterator vp::list<T>::begin() [with T = int]' discards qualifiers [-fpermissive]|
C:\Programming\List Practice\main.cpp|196|error: passing 'const vp::list<int>' as 'this' argument of 'vp::list<T>::iterator vp::list<T>::end() [with T = int]' discards qualifiers [-fpermissive]|
||=== Build finished: 2 errors, 3 warnings (0 minutes, 2 seconds) ===|
Last edited on
Pages: 12345