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

C++链表印刷反-但是我不想要它

问题 (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.

Here's what I have so far:

#ifndef _MULTILINK_H_INCLUDED_
#define _MULTILINK_H_INCLUDED_

#include <cassert>
#include <functional>
#include <algorithm>

template <typename T, typename Compare = std::less<T> >
class MutliLink
{
private:
    class node // our node "Object"
    {
    public:
        // node ctor - sets up a node with the data and next/prev pointers
        node(const T &d = T(), node *p = NULL, node *n = NULL) : datum(d), prev(p), next(n) { }
        T datum; // the data
        unsigned int datumCount = 1; // the count of the data (no duplicates), intially 1
        struct node *prev, *next;
    };
    // local variables for bookkeeping
    unsigned int theSize;
    struct node *head, *tail;
    // init method to set things up
    void init()
    {
        // node with dummy 'head' and 'tail' for easy removal/adding
        theSize = 0;
        head = new node;
        tail = new node;
        head->next = tail;
        tail->prev = head;
    }
public:
    typedef unsigned int size_type;
    typedef T key_type;
    typedef T value_type;
    // iterator sub-class of MutliLink
    class iterator
    {
    private:
        node *p;
        friend class MutliLink;
        // copy ctor
        iterator(node *ptr) : p(ptr) { }

    public:
        // default iterator ctor
        iterator() : p(NULL) { }
        // using default dtor and assign op
        iterator &operator--()      // predecriment
        {
            assert(p);
            static unsigned int count = 1;
            if (count < p->datumCount)
            {
                // increment count and return *this
                count++;
            }
            else
            {
                // reset count and return previous element
                count = 1;
                p = p->prev;
            }
            return *this;
        }
        iterator operator--(int)    // postdecriment
        {
            const iterator tmp = *this;
            // delegate to predecriment method
            --*this;
            return tmp;
        }
        iterator &operator++()      // preincrement
        {
            assert(p);
            static unsigned int count = 1;
            if (count < p->datumCount)
            {
                // increment count and return *this
                count++;
            }
            else
            {
                // reset count and return next element
                count = 1;
                p = p->next;
            }
            return *this;
        }
        iterator operator++(int)    // postincrement
        {
            const iterator tmp = *this;
            // delegate to preincrement method
            ++*this;
            return tmp;
        }
        // *iterator - return a reference to the datum
        const T &operator*() const
        {
            assert(p);
            return p->datum;
        }
        // iterator-> - return the address of the datum
        const T *operator->() const
        {
            assert(p);
            return &p->datum;
        }
        // equality check
        bool operator==(const iterator &rhs) const
        {
            return p == rhs.p;
        }
        // not equal
        bool operator!=(const iterator &rhs) const
        {
            return !(*this == rhs);
        }
    }; // end iterator sub-class

    /*
    *   Start MutliLink ctors
    */

    // ctor
    MutliLink()
    {
        // delegate to init to set things up
        init();
    }
    // copy ctor - calls assign op
    MutliLink(const MutliLink &rhs)
    {
        init();
        // delegate to assign op
        *this = rhs;
    }
    // dtor
    ~MutliLink()
    {
        // clear out list and remove head/tail dummy nodes
        clear();
        delete head;
        delete tail;
    }
    // assign op
    const MutliLink &operator=(const MutliLink &rhs)
    {
        if (this != &rhs) // checking for self assignment
        {
            clear(); // clear it out and add rhs elements to this
            for (iterator itr = rhs.begin(); itr != rhs.end(); ++itr)
                insert(*itr);
            return *this;
        }
    }
    // construct MutliLink using half-open interval
    template <class Iter>
    MutliLink(Iter first, Iter last) : MutliLink()
    {
        // iterate through adding items
        while (first != last)
        {
            insert(*first);
            ++first;
        }
    }

    // insertion sort method
    void insert(const T &datum)
    {
        Compare c;
        node *p;

        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;
        }

        /*
        *   when here curr is ≥ item being inserted; insert item before curr
        *   create the current node p
        *   set p->prev = curr->prev
        *   set p->next = curr
        *   set curr->prev->next = p
        *   set curr->prev = p
        */

        // check for equality, if (this < that) == (that < this) they are equal
        if (c(datum, curr->datum) == c(curr->datum, datum))
        {
            // items are equal
            curr->datumCount++;
        }
        else
        {
            // insert into correct position
            // node ctor = node(datum, prev node, next node)
            p = new node(datum, curr->prev, curr);
            curr->prev->next = p;
            curr->prev = p;
            // increment container size
            theSize++;
        }

    }

    // return begin iterator
    iterator begin()
    {
        return head->next;
    }
    // return end iterator
    iterator end()
    {
        return tail;
    }

}; // end MutliLink class

#endif /* _MULTILINK_H_INCLUDED_ */

And here is my test code:

#include "MutliLink.h"
#include <iostream>
#include <string>

using namespace std;

int main(){
    const string s = "applesauce";
    MutliLink<char> ml(s.begin(), s.end());
    cout << "ml Should be aaceelppsu: ";

    for (auto iter=ml.begin(); iter!=ml.end(); ++iter)
        cout << *iter;
    cout << endl;
}

The problem is I'm getting usppleecaa when it should be aaceelppsu?

我创建一个STL像一个链表。我需要它来像个multiset,其中只包含每个对象的一个实例,也可以增加倍数计数,但只有一个是真的“储存”。

我目前遇到的问题是,当重复的一个实例,我以相反的顺序将其元素的对象?

我一直拉我的头发上,似乎不知道发生了什么…一切(到目前为止)按预期工作。这只是整个反的事,我似乎无法找出原因。

这就是我所到目前为止:

#ifndef _MULTILINK_H_INCLUDED_
#define _MULTILINK_H_INCLUDED_

#include <cassert>
#include <functional>
#include <algorithm>

template <typename T, typename Compare = std::less<T> >
class MutliLink
{
private:
    class node // our node "Object"
    {
    public:
        // node ctor - sets up a node with the data and next/prev pointers
        node(const T &d = T(), node *p = NULL, node *n = NULL) : datum(d), prev(p), next(n) { }
        T datum; // the data
        unsigned int datumCount = 1; // the count of the data (no duplicates), intially 1
        struct node *prev, *next;
    };
    // local variables for bookkeeping
    unsigned int theSize;
    struct node *head, *tail;
    // init method to set things up
    void init()
    {
        // node with dummy 'head' and 'tail' for easy removal/adding
        theSize = 0;
        head = new node;
        tail = new node;
        head->next = tail;
        tail->prev = head;
    }
public:
    typedef unsigned int size_type;
    typedef T key_type;
    typedef T value_type;
    // iterator sub-class of MutliLink
    class iterator
    {
    private:
        node *p;
        friend class MutliLink;
        // copy ctor
        iterator(node *ptr) : p(ptr) { }

    public:
        // default iterator ctor
        iterator() : p(NULL) { }
        // using default dtor and assign op
        iterator &operator--()      // predecriment
        {
            assert(p);
            static unsigned int count = 1;
            if (count < p->datumCount)
            {
                // increment count and return *this
                count++;
            }
            else
            {
                // reset count and return previous element
                count = 1;
                p = p->prev;
            }
            return *this;
        }
        iterator operator--(int)    // postdecriment
        {
            const iterator tmp = *this;
            // delegate to predecriment method
            --*this;
            return tmp;
        }
        iterator &operator++()      // preincrement
        {
            assert(p);
            static unsigned int count = 1;
            if (count < p->datumCount)
            {
                // increment count and return *this
                count++;
            }
            else
            {
                // reset count and return next element
                count = 1;
                p = p->next;
            }
            return *this;
        }
        iterator operator++(int)    // postincrement
        {
            const iterator tmp = *this;
            // delegate to preincrement method
            ++*this;
            return tmp;
        }
        // *iterator - return a reference to the datum
        const T &operator*() const
        {
            assert(p);
            return p->datum;
        }
        // iterator-> - return the address of the datum
        const T *operator->() const
        {
            assert(p);
            return &p->datum;
        }
        // equality check
        bool operator==(const iterator &rhs) const
        {
            return p == rhs.p;
        }
        // not equal
        bool operator!=(const iterator &rhs) const
        {
            return !(*this == rhs);
        }
    }; // end iterator sub-class

    /*
    *   Start MutliLink ctors
    */

    // ctor
    MutliLink()
    {
        // delegate to init to set things up
        init();
    }
    // copy ctor - calls assign op
    MutliLink(const MutliLink &rhs)
    {
        init();
        // delegate to assign op
        *this = rhs;
    }
    // dtor
    ~MutliLink()
    {
        // clear out list and remove head/tail dummy nodes
        clear();
        delete head;
        delete tail;
    }
    // assign op
    const MutliLink &operator=(const MutliLink &rhs)
    {
        if (this != &rhs) // checking for self assignment
        {
            clear(); // clear it out and add rhs elements to this
            for (iterator itr = rhs.begin(); itr != rhs.end(); ++itr)
                insert(*itr);
            return *this;
        }
    }
    // construct MutliLink using half-open interval
    template <class Iter>
    MutliLink(Iter first, Iter last) : MutliLink()
    {
        // iterate through adding items
        while (first != last)
        {
            insert(*first);
            ++first;
        }
    }

    // insertion sort method
    void insert(const T &datum)
    {
        Compare c;
        node *p;

        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;
        }

        /*
        *   when here curr is ≥ item being inserted; insert item before curr
        *   create the current node p
        *   set p->prev = curr->prev
        *   set p->next = curr
        *   set curr->prev->next = p
        *   set curr->prev = p
        */

        // check for equality, if (this < that) == (that < this) they are equal
        if (c(datum, curr->datum) == c(curr->datum, datum))
        {
            // items are equal
            curr->datumCount++;
        }
        else
        {
            // insert into correct position
            // node ctor = node(datum, prev node, next node)
            p = new node(datum, curr->prev, curr);
            curr->prev->next = p;
            curr->prev = p;
            // increment container size
            theSize++;
        }

    }

    // return begin iterator
    iterator begin()
    {
        return head->next;
    }
    // return end iterator
    iterator end()
    {
        return tail;
    }

}; // end MutliLink class

#endif /* _MULTILINK_H_INCLUDED_ */

这是我的测试代码:

#include "MutliLink.h"
#include <iostream>
#include <string>

using namespace std;

int main(){
    const string s = "applesauce";
    MutliLink<char> ml(s.begin(), s.end());
    cout << "ml Should be aaceelppsu: ";

    for (auto iter=ml.begin(); iter!=ml.end(); ++iter)
        cout << *iter;
    cout << endl;
}

问题是我得到的usppleecaa当它应该是aaceelppsu

最佳答案 (Best Answer)

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.

你的错误是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;
    }

while条件应该是curr != tail && c(curr->datum, datum)

这是因为插入排序应该认为“在目前的项目不超过[之前]我想插入一个,跳到下一个。”键:电流,小于,插入。std::less::operator()(a,b)只是做a < b。因为你想要的curr->datum < datum,它应该是c(curr->datum, datum)


好的,那用了比预期更长的时间,因为你的代码:

cout << "ml Should be aceelppsu: ";

是错误的,应该是:

cout << "ml Should be aaceelppsu: ";

因为有两个'a'"applesauce"

如何解决问题:首先实现迭代器迭代器需要记住一个重复的项目,这是目前。这意味着需要对迭代器的一员:

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);

第二,我删除了iterator默认构造函数,因为不需要有点没有迭代器。他们可能是有意义的一个end在一些容器的迭代器,但在这种情况下end是一个迭代器,在虚拟点tail所以一个空的指向迭代器不需要。

这意味着,只有公共构造函数是默认的复制构造函数,C + +自动为您创建。因此,新的迭代器只能由其他迭代器,并能自发地创建迭代器的唯一一件事就是MultiLink。这应该抓住一些普通用户的错误。

接下来,我们需要修复的递增和递减(注:无i在“减量化”)算子。这需要count考虑,更重要的是,递增和递减运算符需要互相兼容,所以:

iterator i = ml.begin(), j(i);
assert(--++i == j);

作品。这意味着我们需要解释意义count。在这种情况下,我认为是“意义count是当前元素的索引,从0开始,因此不应大于p->datumCount在任何时间。“这改变了你的preincrement算子:

    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;
    }

这可以更简洁地表达:

    iterator &operator++()      // preincrement
    {
        assert(p);
        if (++count >= p->datumCount)
        {
            // reset count and return next element
            count = 0;
            p = p->next;
        }
        return *this;
    }

该preincrement算子是同样的改变:

    iterator &operator--()      // predecrement
    {
        assert(p);
        if (count-- == 0)
        {
            // reset count and return previous element
            p = p->prev;
            count = p->datumCount - 1;
        }
        return *this;
    }

后运营商不需要改变,因为他们只是打电话前的版本。

本文翻译自StackoverFlow,英语好的童鞋可直接参考原文:http://stackoverflow.com/questions/23450666