不维护迭代器的解引用能力？

Question

这是对双向链表迭代器的第一次尝试：

dlist.h

#ifndef dlist_h
#define dlist_h

/* Node */
template <class Elem>
struct Link
{
    Link();
    Link (Link<Elem>* s, Link<Elem>* p, const Elem& v);
    Link (const Link<Elem>& src);

    Link<Elem>& operator= (const Link<Elem>& src);

    bool operator== (const Link<Elem>& src);
    bool operator!= (const Link<Elem>& src);

    void swap(Link<Elem>& src);

    Link* succ;
    Link* prev;
    Elem val;
};


//----------------------------------------------------------------------------
/* Doubly Linked List */
template <class Elem>
class List
{ 
public:
    class iterator;

    List();

    iterator begin() { return iterator(first, first, last); }
    iterator end() { return iterator(last, first, last); }

    void push_front(const Elem& v);
    Elem& front();

    size_t size(); 
    void print();

private:
    Link<Elem> *first;
    Link<Elem> *last;
};

//----------------------------------------------------------------------------
/* a range-checked bidirectional iterator */
template <class Elem>
class List<Elem>::iterator
{
public:
    iterator();                                         // default constructor
    iterator(Link<Elem>* c, Link<Elem>* b, Link<Elem>* e);                  
    iterator(const iterator& src);                      // copy constructor
    iterator operator= (const iterator& src);           // copy assignment 

    iterator& operator++();                             // incrementations
    iterator operator++(int);                           // postfix
    iterator& operator--();                             // decrementations
    iterator operator--(int);                           // postfix

    Elem& operator*();                                  // dereferenceable lvalue
    const Elem& operator*() const;                      // dereferenceable rvalue

    bool operator== (const iterator& b) const;          // equality comparisons
    bool operator!= (const iterator& b) const;

    void swap(iterator& src);

private:
    Link<Elem>* curr;
    Link<Elem>* begin;
    Link<Elem>* end;
};

#include "dlist.cpp"

#endif

dlist.cpp

//-----------------------------------------------------------------------------

template <class Elem>
Link<Elem>::Link()
    : succ(nullptr), prev(nullptr), val(Elem())
{

}

//-----------------------------------------------------------------------------

template <class Elem>
Link<Elem>::Link (Link<Elem>* s, Link<Elem>* p, const Elem& v)
    : succ(s), prev(p), val(v)
{

}

//-----------------------------------------------------------------------------

template <class Elem>
Link<Elem>::Link (const Link<Elem>& src)
   : succ(src.succ), prev(src.prev), val(src.val)
{

}

//-----------------------------------------------------------------------------
template <class Elem>
Link<Elem>& Link<Elem>::operator= (const Link<Elem>& src)
{
    Link<Elem> temp(src);
    swap(*this, temp);
    return *this;
}

//-----------------------------------------------------------------------------
template <class Elem>
bool Link<Elem>::operator== (const Link<Elem>& src)
{
    return succ = src.succ && prev = src.prev;
}

//-----------------------------------------------------------------------------

template <class Elem>
bool Link<Elem>::operator!= (const Link<Elem>& src)
{
    return !(*this == src);
}

//-----------------------------------------------------------------------------

template <class Elem>
void Link<Elem>::swap(Link<Elem>& src)
{
    std::swap(prev, src.prev);
    std::swap(succ, src.succ);
    std::swap(val, src.val);
}

//-----------------------------------------------------------------------------

template<class Elem>
void swap(Link<Elem>& lhs, Link<Elem>& rhs)
{
    lhs.swap(rhs);
}

//-----------------------------------------------------------------------------

template<class Elem> 
List<Elem>::List()
    : first(new Link<Elem>()), last(first)
{

}

//-----------------------------------------------------------------------------

template<class Elem>
void List<Elem>::push_front(const Elem& v)
{  
    first = new Link<Elem>(first, nullptr, v); 
}

//-----------------------------------------------------------------------------

template<class Elem>
Elem& List<Elem>::front()
{
    return first->val; 
}

//-----------------------------------------------------------------------------

template<class Elem>
size_t List<Elem>::size() 
{
    size_t count = 0;
    for (iterator p = begin(); p != end(); ++p)
    {
        ++count;     
    }
    return count;
}

//-----------------------------------------------------------------------------

template<class Elem>
void List<Elem>::print()
{
    for (iterator p = begin(); p != end(); ++p)
    {
         std::cout << *p <<' ';  
    }
}

//-----------------------------------------------------------------------------

template<class Elem>
List<Elem>::iterator::iterator()
    : curr(nullptr), begin(nullptr), end(nullptr)
{

}

//-----------------------------------------------------------------------------

template<class Elem>
List<Elem>::iterator::iterator(Link<Elem>* p, Link<Elem>* b, Link<Elem>* e)
    : curr(p), begin(b), end(e)
{

}

//-----------------------------------------------------------------------------

template<class Elem>
List<Elem>::iterator::iterator(const iterator& src)
    : curr(src.curr), begin(src.begin), end(src.end)
{

}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator List<Elem>::iterator::operator= (const iterator& src)
{
    iterator temp(src);
    this->swap(temp);
    return *this;
}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator& List<Elem>::iterator::operator++()
{
    if (curr == end)
    {
        throw std::out_of_range("List<Elem>::iterator::operator++(): out of range!\n");
    }

    curr = curr->succ;

    return *this; 
}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator List<Elem>::iterator::operator++(int)
{
    if (curr == end)
    {
        throw std::out_of_range("List<Elem>::iterator::operator++(): out of range!\n");
    }

    Link<Elem>* old = curr;
    curr = curr->succ;
    return old; 
}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator& List<Elem>::iterator::operator--()
{ 
    if (curr == begin)
    {
        throw std::out_of_range("List<Elem>::iterator::operator--(): out of range!\n");
    }

    curr = curr->prev;

    return *this; 
}

//-----------------------------------------------------------------------------

template<class Elem>
typename List<Elem>::iterator List<Elem>::iterator::operator--(int)
{ 
    if (curr == begin)
    {
        throw std::out_of_range("List<Elem>::iterator::operator--(): out of range!\n");
     }

     iterator old(*this);
     curr = curr->prev; 
     return old; 
 }

//-----------------------------------------------------------------------------

template<class Elem>
Elem& List<Elem>::iterator::operator*() 
{ 
    return curr->val; 
}   

//-----------------------------------------------------------------------------

template<class Elem>
const Elem& List<Elem>::iterator::operator*() const
{  
    return curr->val;
}

//-----------------------------------------------------------------------------

template<class Elem> 
bool List<Elem>::iterator::operator== (const iterator& b) const
{ 
    return curr == b.curr; 
} 

//-----------------------------------------------------------------------------

template<class Elem>
bool List<Elem>::iterator::operator!= (const iterator& b) const
{ 
    return curr != b.curr; 
}

//-----------------------------------------------------------------------------

template<class Elem>
void List<Elem>::iterator::swap(iterator& src)
{
    std::swap(curr, src.curr); 
    std::swap(begin, src.begin);
    std::swap(end, src.end);
}

//-----------------------------------------------------------------------------

template<class Elem>
void swap(typename List<Elem>::iterator& lhs, typename List<Elem>::iterator& rhs)
{
    lhs.swap(rhs);
}

main.cpp

 #include <iostream>
 #include "dlist.h"
 /* simple test for iterator */ 

int main() 
{
    List<int> l;
    l.push_front(1);
    l.push_front(2);
    l.push_front(3);
    l.push_front(4);
    l.push_front(5);

    // default constructor, copy assignment
    List<int>::iterator p = l.begin();

    // lvalue dereferencing 
    *p = 100;

    // incrementation, rvalue dereferencing
    List<int>::iterator i;
    for (i = l.begin(); i != l.end(); ++i)
    {
        std::cout << *i <<' ';
    }

    if (i == l.end() && i != l.begin())
    {
        std::cout <<"\ncomparison correct!\n";
    }

    // postfix and prefix decrementation; maintain dereferenceability

    List<int>::iterator ii = l.end();
    --ii;
    for (; ii != l.begin(); ii--)
    {
        std::cout << *ii <<' ';
    } 

    return 0;
}

当它到达最后一个 for 循环时，递减 operator-- 以某种方式使 ii 迭代器无效，尽管我进行了彻底的 ^IMO调试。

这里是runnable sample.

Answer 1

Link 的构造函数没有正确更新作为参数给出的元素。在两个元素之间插入一个元素会破坏之前的 link.

这是一个更合适的构造函数：

template <class Elem>
Link<Elem>::Link(Link<Elem>* s, const Elem& v)
    : succ(s), prev(s->prev), val(v)
{
    // Update next and previous nodes to make them aware of this
    s->prev = this;
    if(prev) prev->succ = this;
}

如果您更新 List::push_front 以改为使用此构造函数，您会发现您的代码可以编译并运行。

您应该考虑在适当的时候制作方法 const 以避免错误（或者在 bool operator== (const Link<Elem>& src) const 的情况下发现现有方法）。 Link.

Answer 2

问题是你的push_front方法，你忘了link first->succ->prev回到新节点，因此你的双linked列表基本上是一个单link编辑列表

第一个 i-- 成功，因为 last 指向默认节点，但是 curr->prev 是一个 nullptr，因为您忘记 link 返回，所以下一个 i-- 将取消引用 nullptr curr 导致错误。

修复您的 push_front 方法：

template<class Elem>
void List<Elem>::push_front(const Elem& v)
{
    first = new Link<Elem>(first, nullptr, v);
    first->succ->prev = first; //link back
}

不维护迭代器的解引用能力？

Not maintaining iterator dereferenceability?

c++

iterator

dereference

doubly-linked-list