Your bug is in insert
:
node *curr;
curr = head->next; //point to first node since we're using dummy head node
while (curr != tail && c(datum, curr->datum))
{
curr = curr->next;
}
The while
condition should be curr != tail && c(curr->datum, datum)
.
This is because the insertion sort should think "while the current item is less than [before] the one I want to insert, skip to the next." Key: current, less than, inserted. std::less::operator()(a,b)
just does a < b
. Since you want curr->datum < datum
, it should be c(curr->datum, datum)
.
Okay, that took longer than expected, because your code:
cout << "ml Should be aceelppsu: ";
is wrong and should be:
cout << "ml Should be aaceelppsu: ";
because there are two 'a'
s in "applesauce"
.
How to solve the iterator problem: First realize that the iterator needs to remember which one of a duplicated item it is currently on. This means it needs to be a member of the iterator:
class iterator
{
private:
node *p;
unsigned int count;
friend class MutliLink;
// NOT a copy ctor -- an initialize-from-ptr ctor.
iterator(node *ptr) : p(ptr), count(0) { }
// -- A copy ctor would be iterator(const iterator& iter);
Second, I deleted the iterator
default constructor, since there is no need to have iterators that point at nothing. They might make sense as an end
iterator in some containers, but in this case end
is an iterator that points at the dummy tail
so a null-pointing iterator is not needed.
This means that the only public constructor is the default copy constructor that C++ automagically creates for you. Therefore new iterators can only be constructed from other iterators, and the only thing that can spontaneously create an iterator is MultiLink
. This should catch some common user mistakes.
Next, we need to fix the increment and decrement (NOTE: no i
in "decrement") operators. This needs to take count
into account, and more importantly, the increment and decrement operators need to be compatible with each other, so:
iterator i = ml.begin(), j(i);
assert(--++i == j);
works. This means we need to explain the meaning of count
. In this case, I define that meaning to be "count
is the index of the current element, starting at 0, and thus shall not be greater than p->datumCount
at any time." This changes your preincrement operator into:
iterator &operator++() // preincrement
{
assert(p);
if (count + 1 < p->datumCount)
{
// increment count and return *this
count++;
}
else
{
// reset count and return next element
count = 0;
p = p->next;
}
return *this;
}
This can be more concisely expressed as:
iterator &operator++() // preincrement
{
assert(p);
if (++count >= p->datumCount)
{
// reset count and return next element
count = 0;
p = p->next;
}
return *this;
}
The preincrement operator is similarly changed:
iterator &operator--() // predecrement
{
assert(p);
if (count-- == 0)
{
// reset count and return previous element
p = p->prev;
count = p->datumCount - 1;
}
return *this;
}
The post- operators don't need changing since they just call the pre- versions.