C++

Forum

 
Perfecting my linked list

Pages: 12345
cire (8284)
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]'|


Are you calling operator= from sort?

I would guess this is because iterators can't handle const lists.
Volatile Pulse (1543)
Yes, but I believe it's because my list isn't const correct. I'm having issues posting my code at the moment, but I will update shortly.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
#include <iostream>
#include <stdexcept>

namespace vp {
   template<class T>
   class list {
      private:
         struct node {
            node();
            node(T Value, node *pnode);
            node(T Value, node *Prev, node *Next);
            ~node();
            T value;
            node *prev;
            node *next;
         };
         node *firstNode;
         node *lastNode;
         unsigned int mSize;
      public:
         class iterator {
            private:
               node *current;
            public:
               friend class list<T>;
               iterator();
               iterator(node* node);
               T& operator ->();
               T& operator *();
               bool operator ==(const iterator it) const;
               bool operator !=(const iterator it) const;
               iterator& operator ++();
               iterator operator ++(int);
               iterator& operator --();
               iterator operator --(int);
         };
         list();
         list(unsigned n, const T& value = T());
         list(list<T>& x);
         ~list();
         list<T>& operator =(const list<T> &l);
         T& back();
         iterator begin();
         void clear();
         bool empty();
         iterator end();
         iterator erase(iterator first, iterator last);
         iterator erase(iterator it);
         T& front();
         void pop_back();
         void pop_front();
         void push_back(T x);
         void push_front(T x);
         iterator rbegin();
         void remove(const T& value);
         iterator rend();
         unsigned int size();
         void sort();
         void swap(list<T> lst);
         void unique();
   };
}
// ...
template<class T>
vp::list<T>& vp::list<T>::operator= (const list<T> &l) {
   clear();
   for (T val : l)
      push_back(val);
   return *this;
}
// ...
template<class T>
void vp::list<T>::sort() {   
   for (int merges = 0, k = 1; merges != 1; k *= 2) {
      node *p = firstNode, *q = p;
      list<T> l;
      for (int psize, qsize = merges = 0; p; merges ++, p = q) {
         for (psize = k, qsize = 0; qsize < k && q; qsize ++, q = q->next);
         while (psize || (qsize && q)) {
            if (!psize) {
               l.push_back(q->value);
               q = q->next;
               qsize --;
            }
            else if (!qsize || !q) {
               l.push_back(p->value);
               p = p->next;
               psize --;
            }
            else {
               if (p->value > q->value) {
                  l.push_back(q->value);
                  q = q->next;
                  qsize --;
               }
               else {
                  l.push_back(p->value);
                  p = p->next;
                  psize --;
               }
            }
         }
      }
      *this = l;
   }
}


The sort definition is messy, but works.
Last edited on
cire (8284)
I'm glad it works, but...

merge sort (in fact, any sort) on a linked list just requires rearranging pointers. You're actually copying every T twice.
Last edited on
Volatile Pulse (1543)
I am completely lost as to where to even start when it comes to doing that. I thought I read the instructions perfectly. Where do I start with this? I'm so confused when it comes to sort algorithms to begin with and I thought my way was efficient. -.-
cire (8284)
http://en.wikipedia.org/wiki/Merge_sort

Instead of reading the algorithm, watch the animated gif in the upper right corner and consider how you might implement it, just by manipulating the next/previous links. I think it's a lot easier to visualize these things first.
Volatile Pulse (1543)
Why didn't I just wiki it before attempting it? The concept of the mergesort is, in my opinion, very easy. Coding it, however, wasn't so easy. But, in my head so far, I'm look at, more or less, calling sort recursively with two separate lists, each dwindling down until they're only of size(1), sort those lists, return to the previous section, sort them, etc.?

Would it be more beneficial to do the merge function first? I'm content with a new approach. Also, is the concept of making new lists worthwhile, or should I attempt to just modify the nodes first (I think I'm going to struggle the most with that one though)?

Edit: Trying to run some code examples of merge through my head, I'm having a hard time figuring out a way to properly merge two lists without copying T. This would put me right back to where I was before. Maybe I'll take a few minutes to write out how exactly it should work. I'm running out of tablet paper. -.-
Last edited on
closed account (D80DSL3A)
According to the above link, Merge sort is often the best choice for a linked list. I'll have to give it a crack too.

I have some ideas for functions which will move a node from one list to another by re assigning links.
This might be useful in merge sort.
I presented several node class member functions a few posts ago which could be quite useful here. I'm a bit disappointed that those posts drew no discussion at all.

I'll re-present one of them here briefly:

Here's a function which will cause the calling node to be extracted from the list it is in, then insert itself into a list following the given pNode, which could be in another list. This is done by changing pointer assignments only. There is no copying of T involved.
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;
    }
}

Again, that's a function for moving a node from one list to another, or for moving a node within a list.

Here's the extract function too, since it's called by insert_after.
This function does the same as your destructor, except it doesn't delete the node. Thanks for the dextructor idea. I'm using that now too.
1
2
3
4
5
6
7
8
9
10
11
 
// extract this node from a list
void dNode::extract(void)
{
    if( prev )
        prev->next = next;

    if( next )
        next->prev = prev;

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

This could be called in your dtor too:
1
2
3
4
 
dNode::~dNode()
{
    extract();
}

I hope you find this useful.
Last edited on
Volatile Pulse (1543)
I found it very useful the first time you posted it. I just didn't see a need for it at the moment and was looking towards ways I could improve upon it or see if it possibly could be better implemented in the list class rather than just the node class. I changed extract to remove and I tidied up the insert function and also created an insert_before function.

Insert After Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template<class T>
void vp::list<T>::node::insert_after(node *pnode) {
   if (!pnode || pnode == this)
      return;

   remove();
   prev = pnode;
   next = pnode->next;

   if (pnode->next)
      pnode->next->prev = this;

   pnode->next = pnode;
}


Insert Before Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template<class T>
void vp::list<T>::node::insert_before(node *pnode) {
   if (!pnode || pnode == this)
      return;

   remove();
   next = pnode;
   prev = pnode->prev;

   if (pnode->prev)
      pnode->prev->next = this;

   pnode->prev = pnode;
}



Remove Code:
1
2
3
4
5
6
7
8
9
10
 
template<class T>
void vp::list<T>::node::remove() {
   if (prev)
      prev->next = next;

   if (next)
      next->prev = prev;

   next = prev = NULL;
}


Merge Code:
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>
void vp::list<T>::merge(list<T> l) {
   node *p = firstNode;
   
   while (l.size()) {
      node *q = l.firstNode;
      if (q->value < p->value) {
         l.firstNode = l.firstNode->next;
         q->insert_before(p);
         if (p == firstNode)
            firstNode = q;
         mSize ++;
         l.mSize --;
      }
      else if(p == lastNode) {
         l.firstNode = l.firstNode->next;
         q->insert_after(p);
         p = lastNode = q;
         mSize ++;
         l.mSize --;
      }
      else
         p = p->next;
   }
}


I'm running into an issue that once merged, I try to display the list and it doesn't display as intended. I have ran through the list about 10 times on paper and everything seems right, but maybe I'm just getting tired of looking at the same thing over and over again and missing something obvious.

Here is the code for main:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
int main() {
   // Default Ctor
   vp::list<int> myList1;
   myList1.push_back(1);
   myList1.push_back(3);
   vp::list<int> myList2(2, 2);
   myList1.merge(myList2);

   //for (int val : myList1)
      //std::cout << val << "\n";
   for (auto it(myList1.begin()); it != myList1.end(); it ++) {
      std::cout << *it;
      std::cin.ignore();
   }
   
   return 0;
}
 
1
2
3
2
3
2
3
2
3 // And so on...
Last edited on
closed account (D80DSL3A)
I'm having trouble too.

Are you finding that those odd insert_before and insert_after functions work OK?
I'm sorry. I thought you hadn't seen them since I saw no mention.
I should chill.

I see you used them in your merge(), so they must work OK there?

I am able to get my list to split recursively until each sub-list is 1 node long.
I'm having trouble merging them back together as the calls to split() unwind.

Output presently (initial list output first):

6 5 3 1 8 7 2 4

pA = 6 2 8 3
pB = 5 4 7 1 calling split(): pA->x = 6

pA = 6 8
pB = 2 3 calling split(): pA->x = 6

pA = 6
pB = 8
merge() called
pFront = 8 6
calling split(): pB->x = 2

pA = 2
pB = 3
merge() called
pFront = 3 2                            <---- OK to here

merge() called
pFront = 8 2 3                     <--- wrong order, lost the 6
calling split(): pB->x = 5

pA = 5 7
pB = 4 1 calling split(): pA->x = 5

pA = 5
pB = 7
merge() called
pFront = 7 5
calling split(): pB->x = 4

pA = 4
pB = 1                             
merge() called
pFront = 4 1                   <--- OK to here

merge() called
pFront = 7 1 4 5             <--- wrong order

merge() called
pFront = 8 5 4 1 3 2 7   <--- wrong order, lost a node (6)
8 5 4 1 3 2 7

dList.dtor(): 7 dNodes destroyed.

EDIT: When writing the sorted list to the screen. Try writing it in reverse too so you can verify that all the prev pointer assignments are correct.
Last edited on
Volatile Pulse (1543)
I'm unsure where the issue lies, but I can't even merge two presorted lists. I'm assuming something is floating away during one of the moves, but I haven't taken much time to figure it out.

Believe me, it looks great on paper, however, but it doesn't behave like it's supposed to. My next attempt is going to be backwards iteration and see what I get.

Edit: Upon doing a reverse iteration over my list, it appears that lastNode just points to itself so it's quite possible that prev is failing to link properly.

Sigh, this is going to be a late night.

Something that's interesting in insert_before. These two nodes were insert_before back to back. Look at the memory locations -.-
0x3e2638 prev
0x3e2650 next
2 value
0x3e2698 this
0x3e2650 prev
0x3e2650 next
2 value
0x3e26b0 this



Edit: I fixed my problem

These functions:
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
28
29
 
template<class T>
void vp::list<T>::node::insert_after(node *pnode) {
   if (!pnode || pnode == this)
      return;

   remove();
   prev = pnode;
   next = pnode->next;

   if (pnode->next)
      pnode->next->prev = this;

   pnode->next = pnode;
}

template<class T>
void vp::list<T>::node::insert_before(node *pnode) {
   if (!pnode || pnode == this)
      return;

   remove();
   next = pnode;
   prev = pnode->prev;

   if (pnode->prev)
      pnode->prev->next = this;

   pnode->prev = pnode;
}


Needed to be this:
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
28
29
 
template<class T>
void vp::list<T>::node::insert_after(node *pnode) {
   if (!pnode || pnode == this)
      return;

   remove();
   prev = pnode;
   next = pnode->next;

   if (pnode->next)
      pnode->next->prev = this;

   pnode->next = this;
}

template<class T>
void vp::list<T>::node::insert_before(node *pnode) {
   if (!pnode || pnode == this)
      return;

   remove();
   next = pnode;
   prev = pnode->prev;

   if (pnode->prev)
      pnode->prev->next = this;

   pnode->prev = this;
}
Last edited on
Volatile Pulse (1543)
I'm so excited!

It only took me about 12 hours to finally get it, but I managed to work out a sort and merge algorithm without copying values. I just want to jump up and down to be honest.

I'll hold off on posting the code if you don't want me to spoil it for you, but once you get the hang of merging properly, the sort function is almost as easy. A few extra variables, one less list to manage, but essentially the same thing. You have one extra loop as well.

Good luck man. I'm rooting for you. And thanks again for those nifty functions.
closed account (D80DSL3A)
I'm quite stoked too!

My merge_sort function is also working.
No copying of nodes, just changing links. My algorithm does use some auxiliary node*'s, but no auxiliary nodes. This was the goal.

Glad you got yours. Will look forward to comparing functions.
I need to test mine much more. I'll post it when I'm confident it works right.
I was goofing both the split (failing to assign prev pointers properly) and the merge (doing some kind of weird push from the middle, instead of a straight push_back operation).

You're welcome for those nifty functions. They appear to work as desired. I was concerned that I was building a bomb with those things.

I'm kinda fascinated with what can be done with node class member functions here.
Last edited on
Volatile Pulse (1543)
Ah you did the top down method, I used the bottom up method. Essentially, I started with each node, I'm assuming you started with halves to compare.

Anyways, here is my code for sort:
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
28
29
30
31
32
33
34
 
template<class T>
void vp::list<T>::sort() {
   if (size() <= 1)
      return;

   for (int merges = 0, k = 1; merges != 1; k *= 2) {
      node *p = firstNode, *q = p;

      for (int qsize = merges = 0; p; merges ++, p = q) {
         for (qsize = 0; qsize < k && q; qsize ++, q = q->next);

         while (qsize && q && p != q) {
            if (q->value < p->value) {
               if (q == lastNode)
                  lastNode = lastNode->prev;

               if (q->next) {
                  q = q->next;
                  q->prev->insert_before(p);
               } else {
                  q->insert_before(p);
                  q = NULL;
               }

               if (p == firstNode)
                  firstNode = firstNode->prev;

               qsize --;
            } else
               p = p->next;
         }
      }
   }
}


I haven't quite gotten to test mine a whole lot, but I tested it with a list of 7 ints and 8 ints and both sorted perfectly. I think I'm going to get a random number generater and see how this looks :D

Edit: Well, it looks like it's back to the drawing board for me. Here is some quick code if you want to test yours.
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
28
29
30
31
32
33
 
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>

int main() {
   srand(time(0));
   // Default Ctor
   vp::list<int> myList1;

   for (int i = 0; i < 500; i ++)
      myList1.push_back(rand() % 10000);

   int i = 0;

   for (auto it(myList1.begin()); it != myList1.end(); it ++, i ++)
      if ((i + 1) % 10)
         std::cout << std::setw(5) << *it;
      else
         std::cout << std::setw(5) << *it << "\n";

   myList1.sort();
   std::cout << "\n\n";
   i = 0;

   for (auto it(myList1.begin()); it != myList1.end(); it ++, i ++)
      if ((i + 1) % 10)
         std::cout << std::setw(5) << *it;
      else
         std::cout << std::setw(5) << *it << "\n";

   return 0;
}


Mine is sorting some of the list into sections, then it stops, so I need to figure out why it breaks on a larger scale.

Edit: I fixed it again, it was some stupid condition I thought was a good idea to add to the while statement. Removing a whole 4 characters fixed my sort problem.

All 500 items are sorted, go me!
Last edited on
closed account (D80DSL3A)
Awesome! That is some tight code there.

My sort() has survived testing so far.
My functions total about 3xlength of yours just now, but I see room for simplifying.

I see your solution is strictly iterative. This must be how the bottom up method works.
I guess I stopped reading as soon as the top down method was outlined. I went straight for the recursive approach, hence I have separate split() and merge() functions.
The merge function is iterative, which doesn't seem right. I feel like I'm mixing methods. I'll try to gain consistency there.
cire (8284)
That's an interesting abuse of the for loops you've got going there.

If you need some inspiration:
https://gist.github.com/4239718

I used a queue of pointers to avoid the need for a nested loop and excessive list iteration, which would be hard to avoid without some kind of container for pointers in an iterative (as opposed to recursive) implementation.
Volatile Pulse (1543)
The merge function should be iterative, at least in the sense I'm thinking. A pointer should step across each "list" and compare each other, and if it's less than, move it. If you need, scroll up to my merge function since that's exactly how it should look, at least with using two lists. Using nodes won't be much different, just need to create a size variable and make sure you're keeping track of your first/last nodes, otherwise begin/end will no longer work and you'll probably get a segfault.

Since I was curious, I wanted to time my sort function with some impressive numbers...look what I found :D

It took 923.997ms to add items.

It took 3551.16ms to sort items.


Process returned 0 (0x0)   execution time : 5.641 s
Press any key to continue.



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

int main() {
   srand(time(0));
   // Default Ctor
   vp::list<int> myList1;

   StartCounter();

   for (int i = 0; i < 1000000; i ++)
      myList1.push_back(rand());

   std::cout << "It took " << GetCounter() << "ms to add items.\n\n";

   StartCounter();
   myList1.sort();
   std::cout << "It took " << GetCounter() << "ms to sort items.\n\n";

   return 0;
}


What's impressive about that is 1,000,000 push backs. Sorting them looks pretty good too:

5082    5082    5082    5082    5082    5082    5082    5082    5082    5082    5082    5082    5083    5083    5083
5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083
5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083    5083
5084    5084    5084    5084    5084    5084    5084    5084    5084    5084    5084    5084    5084    5084    5084
5084    5084    5084    5084    5084    5084    5084    5084    5084    5084    5084    5084    5085    5085    5085
5085    5085    5085    5085    5085    5085    5085    5085    5085    5085    5085    5085    5085    5085    5085
5085    5085    5085    5085    5086    5086    5086    5086    5086    5086    5086    5086    5086    5086    5086
5086    5086    5086    5086    5086    5086    5086    5086    5086    5086    5086    5086    5086    5086    5086
5086    5086    5086    5086    5086    5086    5086    5086    5086    5086    5087    5087    5087    5087    5087
5087    5087    5087    5087    5087    5087    5087    5087    5087    5087    5087    5087    5087    5087    5087
5087    5087    5087    5088    5088    5088    5088    5088    5088    5088    5088    5088    5088    5088    5088
5088    5088    5088    5088    5088    5088    5088    5088    5088    5088    5088    5088    5088    5088    5088
5088    5088    5088    5088    5089    5089    5089    5089    5089    5089    5089    5089    5089    5089    5089
5089    5089    5089    5089    5089    5089    5089    5089    5089    5089    5089    5089    5089    5089    5089
5089    5089    5089    5089    5089    5090    5090    5090    5090    5090    5090    5090    5090    5090    5090
5090    5090    5090    5090    5090    5090    5090    5090    5090    5090    5090    5090    5090    5090    5091
5091    5091    5091    5091    5091    5091    5091    5091    5091    5091    5091    5091    5091    5091    5091
5091    5091    5091    5091    5091    5091    5091    5091    5091    5091    5092    5092    5092    5092    5092
5092    5092    5092    5092    5092    5092    5092    5092    5092    5092    5092    5092    5092    5092    5092
5092    5092    5092    5092    5092    5092    5092    5092    5092    5093    5093    5093    5093    5093    5093
5093    5093    5093    5093    5093    5093    5093    5093    5093    5093    5093    5093    5093    5094    5094
5094    5094    5094    5094    5094    5094    5094    5094    5094    5094    5094    5094    5094    5094    5094
5094    5094    5094    5094    5094    5094    5094    5094    5094    5094    5094    5094    5094    5095    5095
5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095
5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095    5095
5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096
5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096    5096
5096    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097
5097    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097    5097
5097    5097    5097    5097    5097    5097    5097    5097    5097    5098    5098    5098    5098    5098    5098
5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098
5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098    5098
5098    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099
5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099
5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099    5099
Volatile Pulse (1543)
@cire
Don't hate on my for loops. It takes some practice to use for loops like that...you should have seen what I had when I first started working on my sort function...there were three for loops, each one with anywhere from 1-4 elements in each statement. It was brutal. I'm having fun with this however, and I really enjoyed the challenge, more so now that I completed it.

Edit: It's also impressive at the fact that those times are on a 1.6GHz atom processor...
Last edited on
cire (8284)
The merge function is iterative, which doesn't seem right. I feel like I'm mixing methods. I'll try to gain consistency there


The merge doesn't lend itself to a recursive solution, but the splitting certainly does.

[Edit: You should compile in release mode with optimizations if you're going to time it.]
Last edited on
closed account (D80DSL3A)
Good job!

Thanks for the the assurance regarding the iterative nature of the merge operation.
It makes sense.

I have 3 functions. First, merge_sort():
1
2
3
4
5
6
7
8
9
10
 
void dList::merge_sort(void)
{
    front =  front->split();
    
    back = front;// back got lost. Find it!
    while( back->next )
        back = back->next;

    return;
}

Which calls the (recursive) split():
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
28
29
30
 
dNode* dNode::split(void)
{
    if( !next ) return this;

    dNode *pA = this, *pB = this->next, *iter = pB->next;

    while( iter )// split the list in 2
    {
        bool toA = true;
        dNode* pNext = iter->next;// save this
        if( toA )
            iter->insert_after( pA );
        else
            iter->insert_after( pB );

        toA = !toA;// toggle value
        iter = pNext;
    }
    if( pB->prev ) pB->prev->next = NULL;
    if( pA->prev ) pA->prev->next = NULL;
    pA->prev = NULL;
    pB->prev = NULL;

    if( pA->next )
        pA = pA->split();
    if( pB->next )
        pB = pB->split();

    return pA->merge( pB );
}

Which calls the (iterative) merge():
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
 
dNode* dNode::merge( dNode* pB )
{
    dNode *pFront = NULL, *pBack = NULL;
    dNode* pA = this;
    dNode* pNext = NULL;

    dNode** ppLo = pA->x < pB->x ? &pA : &pB;
    pFront = pBack = *ppLo;
    *ppLo = (*ppLo)->next;

    while( pA || pB )
    {
        if( pA && pB )
            ppLo = pA->x < pB->x ? &pA : &pB;
        else if( pA )
            ppLo = &pA;
        else
            ppLo = &pB;

        pNext = (*ppLo)->next;
        (*ppLo)->insert_after( pBack );
        pBack = pBack->next;
        *ppLo = pNext;
    }

    return pFront;
}

I caught some output before stripping all the test output code from those functions. I think it shows the splitting and merging process well.
Given an 8 node list, shown at top:

6 5 3 1 8 7 2 4

pA = 6 2 8 3
pB = 5 4 7 1
calling split(): pA->x = 6

pA = 6 8
pB = 2 3
calling split(): pA->x = 6

pA = 6
pB = 8

merge() called
pFront = 6 8
calling split(): pB->x = 2

pA = 2
pB = 3

merge() called
pFront = 2 3

merge() called
pFront = 2 3 6 8
calling split(): pB->x = 5

pA = 5 7
pB = 4 1
calling split(): pA->x = 5

pA = 5
pB = 7

merge() called
pFront = 5 7
calling split(): pB->x = 4

pA = 4
pB = 1

merge() called
pFront = 1 4

merge() called
pFront = 1 4 5 7

merge() called
pFront = 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1


dList.dtor(): 8 dNodes destroyed.

Now to test it as you have for a 1,000,000 node list.
Since I also have selection_sort(), I'll have to compare performance.
Last edited on
closed account (D80DSL3A)
I would like to make an interesting observation here. This is something I've never noticed before. In the snippet below (from my split() ), the differing behaviors of lines 3 and 4 had me confuzzled (term recently encountered in another thread).

1
2
3
4
5
6
7
8
9
10
11
12
 
while( iter )// split the list in 2
    {
        bool toA = true;
        dNode* pNext = iter->next;// save this
        if( toA )
            iter->insert_after( pA );
        else
            iter->insert_after( pB );

        toA = !toA;// toggle value
        iter = pNext;
    }


line 3 does not cause toA to be assigned true every iteration. This assignment applies to only the 1st iteration. My function would not work otherwise (line 10 would have no effect).

Line 4 however, does cause the value of pNext to be reassigned each iteration!! WTF?????????????

Surely, it's because these variables are used differently in the while body.
toA appears as an lvalue (line 10), but pNext does not. This must be what determines how lines 3 and 4 behave each iteration.

Why have I never noticed this before?

@cire. I shall observe your recommended compiler settings.
I've got half that already. I habitually develop in release mode.

@Volatile Pulse: I haven't done any large scale testing (suddenly got lazy).
I will adapt from your test code when I do (well suited to sudden laziness). Thanks for that.
Last edited on
Pages: 12345