c++ - 在 for 循环中使用 end() 时无法访问双向链表中的最后一个元素

Question

我正在使用迭代器实现一个双向链表。代码工作正常，除非使用 iterator::end() 我无法访问列表中的最后一个元素。例如，复制构造函数无法访问最后一个元素(!!每当我使用 for(iterator it = lst.begin(); it != lst.end();++it))。这个问题看起来很简单，但我无法理解它。

#pragma once

#include <iterator>
#include <initializer_list>
#include <iostream>


using namespace std;

template <typename T, class Allocator = std::allocator<T>>
class MyList {
private:
    class Link {
    public:
        Link(const T& d, Link *n = NULL, Link *p = NULL) :next(n), prev(p), data(d) {}
        ~Link() { }

        T data;
        Link *next;
        Link *prev;
    };
    Link *head ;
    Link *tail ;
    size_t s = 0; // ease things up

public:

    class iterator:public std::iterator<std::bidirectional_iterator_tag, Link>
    {
    private:
        Link *itr;
    public:
        iterator() :itr(nullptr) {}
        iterator(Link* x) :itr(x) {}
       // iterator& operator=(const iterator& i2) {itr = i2.itr;}
        iterator(const iterator& i2) : itr(i2.itr) {}
        iterator& operator++() {
            itr=itr->next;
            return *this;
        }

        iterator& operator--() {
            itr = itr->prev;
            return *this;
        }


        bool operator==(const iterator& rhs) {
            return itr == rhs.itr;
        }
        bool operator!=(const iterator& rhs) {
            return itr != rhs.itr;
        }
        T& operator*() {
            return itr->data;
        }
        Link* getLink()const{
            return itr;
        }



    };

    MyList() {

        head = nullptr;
        tail= head;

        s=0;

    }

    MyList(std::initializer_list<T> l)
            :MyList(){
        for(const auto& i : l){
            push_back(i);}
    }
//copy consructor
    MyList( const MyList<T> &lst)
            :MyList(){

        for(iterator it = lst.begin(); it != lst.end(); ++it){
            push_back(it.getLink()->data);
        }
    }

   MyList& operator=(std::initializer_list<T> &lst) {
        //clear any data before adding new one
        while(head){
            Link *tmp = head;
            head = head->next;
            delete tmp;
        }
        head = nullptr;
        tail = nullptr;
        s = 0;
        for(auto i: lst){
            push_back(i);
        }
    }

    MyList& operator=(MyList<T> &lst) {
        while(head){
            Link *tmp = head;
            head = head->next;
            delete tmp;
        }
        head = nullptr;
        tail = nullptr;
        s = 0;
        for(iterator it = lst.begin(); it != lst.end();++it)       {push_back(it.getLink()->data);}
    }




    ~MyList() {
        Link* temp = head;
        while (temp != nullptr)
        {
            temp = temp->next;
            delete(head);
            head = temp;
        }
    }

    iterator begin() const{
        iterator i(this->head);
        return i;
    }

    iterator end() const{

        iterator return{tail};

    }

    void push_back(const T& t) {

        Link* newnode = new Link(t);
        if (empty()) {
            head = newnode;
            tail = head;
        }
        else {
            tail->next = newnode;
            newnode->prev = tail;
            tail = newnode;
        }
        s++;
    }
std::size_t size() const {
        return s;
}
bool empty() const {
        return !(this->size());
    }
};

这是我正在测试我的代码的 main.cpp，您可以在 () 中看到代码何时工作以及何时失败。

 //test default constructor(works!!!)

        std::cout << "Testing default constructor"<< std::endl;
        MyList<int> a{};
        std::cout << "a should be empty: " << (a.empty() ? string("and it is!") : string("but it is not!")) << std::endl;

        // push_back two elements(works!!!)
        std::cout << "Testing push_back"<< std::endl;
        a.push_back(1);
        a.push_back(2);
        std::cout << "a should be 1,2, and is: " << a << std::endl;




        // test initializer list constructor(works!!!!)

        std::cout << "Testing initializer list constructor"<< std::endl;
        MyList<int> b{1, 2, 3, 4};
        std::cout << "b should be 1,2,3,4, and is: " << b << std::endl;


          //test copy constructor(doesnt work!! Misses the last element)

       std::cout << "Testing copy constructor"<< std::endl;
        MyList<int> c(b);
        std::cout << "c should be " << b << " and is: " << c << std::endl;

 MyList<int> ml{1,2,3,4,5,6};

    // (doesnt work!! misss the last element)

    for(const int& elem : ml)
        std::cout << elem << std::endl;

Answer 1

这是因为 C++ 中的标准约定是 end() 不指向最后一个元素，而是指向最后一个元素之后的下一个不存在的可能元素。

http://www.cplusplus.com/reference/list/list/end/

在您的实现中，iterator end() 返回一个实际的最后一个元素，它显然在 for 循环的 it != lst.end() 条件中被跳过:

for(iterator it = lst.begin(); it != lst.end();++it)