C++ doubly linked list printing in reverse - but I don't want it to

Question

I'm creating an STL like container for a doubly linked list. I need it to act like a multiset, where it only contains a single instance of each object, but keeps a count so multiples can be added but only one is actually "stored".

The problem I'm currently having is that when iterating over the an instance of the object I'm getting its elements in reverse order?

I've been pulling my hair on this and can't seem to figure out what's going on... Everything else (so far) is working as expected. It's just the whole reverse thing I can't seem to figure out the cause...

Answer 1

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.