c++ - 单链表 push_front 不会重新分配 head

Question

我无法让我的 push_front 正常工作。 new_head->next = head 似乎无法正确链接 new_head 和 head。我的节点类是通常的节点类，其中 next 是节点指针。我的 push_back 函数工作正常。我不明白为什么 head 不会链接到 new_head。

template <class T> class mylist {
public:
    typedef T value_type;
    typedef T& reference;
    typedef const T& const_reference;
    typedef mynode<T>* iterator;
    typedef size_t size_type;
    mylist() { create(); }
    mylist(size_type n, const T& val = T()) { create(n, val); }
    ~mylist() { uncreate(); }
    iterator begin() { return head; }
    iterator end() { return head + size(); }
    size_type size();
    void push_back(const T&);
    void push_front(const T&);
    void pop_back();
    void pop_front();

private:
    std::allocator<mynode<T>> alloc;
    mynode<T>* head;
    mynode<T>* tail;
    void create() { head = tail = 0; }
    void create(size_type, const T&);
    void uncreate();
};

---

template <class T> void mylist<T>::push_front(const T& t)
{
    iterator new_head = alloc.allocate(1);
    new_head->data = t;
    new_head->next = head;
    head = new_head;
    if(tail == 0)
        tail = head;
}

---

template <class T> void mylist<T>::push_back(const T& t)
{
    tail->next = alloc.allocate(1);
    tail = tail->next;
    tail->data = t;
    tail->next = 0;
}

---

主要内容

#include "mylist.h"
int main()
{
    mylist<int> lst(5, 2);
    lst.push_back(22);
    mylist<int>::iterator temp = lst.begin();
    while(temp != lst.end()) {
        std::cout << **temp << " ";
        temp++;
    }
    std::cout << std::endl;
    std::cout << "list size: " << lst.size() << std::endl;
    lst.push_front(80);
    lst.push_back(7);
    lst.push_back(3);
    mylist<int>::iterator inc = lst.begin();
    while(inc != lst.end()) {
        std::cout << **inc << " ";
        inc++;
    }
    std::cout << std::endl;
    std::cout << "list size: " << lst.size() << std::endl;
}

输出

2 2 2 2 2 22 
list size: 6
80 7 3 
list size: 3

---

编辑

template <class T> void mylist<T>::create(size_type n, const T& t)
{
    head = alloc.allocate(1);
    head->data = t;
    head->next = alloc.allocate(1);
    mynode<T>* next = head->next;
    int i = 0;
    while(i != n-2) {
        next->data = t;
        next->next = alloc.allocate(1);
        next = next->next;
        ++i;
    }
    tail = next;
    tail->data = t;
    tail->next = 0;
}

---

类 mynode

template <class T> class mynode {
public:
    mynode() : next(0) {}
    mynode(T a, mynode* n = 0) : data(a), next(n) {}
    mynode* next;
    mynode* operator++() { return this->next; }
    mynode* operator+(size_t n) {
        size_t cnt = 0;
        mynode* count = this;
        while(cnt != n) {
            ++cnt;
            count = count->next;
        }
        return count;
    }
    T& operator*() { return this->data; }
    T data;
};

---

使用运算符+的例子

#include "mylist.h"
int main()
{
    mylist<int> test(5,5);
    mylist<int>::iterator n = test.begin();
    while(n != test.end()) {
        std::cout << **n << " ";
        n = n + 1;
    }
    std::cout << std::endl;

    mylist<int> test2(6,6);
    mylist<int>::iterator m = test2.begin();
    while(m != test2.end() - 1) {
        std::cout << **m << " ";
        m = m->next;
        if(m == test2.end()-1)
            std::cout << **m;
    }
    std::cout << std::endl;
}

示例输出

5 5 5 5 5 
6 6 6 6 6 6

Answer 1

似乎是 push_back 工作不正常。改成下面的方式

template <class T> void mylist<T>::push_back(const T& t)
{
    mynode<T>* new_tail = alloc.allocate(1);
    new_tail->data = t;
    new_tail->next = 0;
    if ( tail == 0 )
    {
        head = new_tail;
    }
    else
    {
        tail->next = new_tail;
    }
    tail = new_tail;
}