不維持迭代器的引用？

這是一個雙向鏈表的迭代器第一次嘗試：不維持迭代器的引用？

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

當它到達拉斯維加斯t for循環遞減operator--以某種方式使ii迭代器失效，我無法弄清楚，儘管已經完成了^IMO調試。

這裏是一個runnable sample。

來源

2017-02-24 Ziezi

你從來沒有任何一個環節的上一個指針，他們總是空。 'operator - '將始終賦值'curr = curr-> prev;'，這基本上是'curr = nullptr;'。 –

錯誤：你在'鏈接 :: operator =='中偶然分配'prev'一次。 –

爲什麼你的'iterator'需要3個指針？只有'curr'應該足夠了。 – tntxtnt

的問題是你的push_front方法，你忘了鏈接first->succ->prev回新的節點，因此您的雙向鏈表基本上是一個單向鏈表

第一i--成功，因爲last指向一個默認的節點，但curr->prev是一個nullptr，因爲您忘記鏈接回去了，所以下一個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 
}

來源

2017-02-24 21:02:55 tntxtnt

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。

來源

2017-02-24 19:41:25

不維持迭代器的引用？

回答

相關問題