2016-11-26 2 views
1

イテレータを使用して二重リンクリストを実装しています。 iterator::end()を使用する場合を除いて、コードは正常に動作します。リストの最後の要素にアクセスすることはできません。たとえば、コピーコンストラクタは最後の要素にアクセスできません(!! for(iterator it = lst.begin(); it != lst.end();++it)を使用するたびに!!)。問題はシンプルに見えますが、私はそれの周りに私の頭を得ることができません。forループでend()を使用すると、二重リンクリストの最後の要素にアクセスできません

#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()); 
    } 
}; 

これは私のコードをテストしています。コードが動作しているときと失敗しているときは、()でわかります。

//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; 
+0

、このような問題を解決するための適切なツールは、あなたのデバッガである:あなたの実装で

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

は、iterator end()明らかに、forループでit != lst.end()状態でスキップされ、実際の最後の要素を返します。 。スタックオーバーフローを尋ねる前に、コードを一行ずつ進める必要があります。詳しいヘルプは、[小さなプログラムをデバッグする方法(Eric Lippert)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/)を参照してください。最低でも、あなたはあなたが行った観察と一緒に、[編集]あなたの質問あなたの問題を再現[、最小完全、かつ検証](http://stackoverflow.com/help/mcve)の例を含むようにする必要があります\しますデバッガ。 –

+0

@πάνταῥεῖもちろん、私はすでに投稿する前にコードをデバッグしようとしました。何か有用なことがあればそれは言うか何も言わないでください – Bob

+1

看守のノードを使用してください!チュートリアル[here](http://pastebin.com/DXunz58Q) – sp2danny

答えて

2

C++での標準的な慣習が最後の後ではない最後の要素までが、次のnonexsitent-れることになる要素をend()ポイントということだからです。

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

+0

nullptrを返すことで既にこれを試してみましたが、上記のコードでも動作しますが、MyListのようにすると(MyList tmp {20,21,23,24 }; it = ml.insert(it、++(tmp.begin())、 - (tmp.end()));)--tmp.end()がnullのためにコードがクラッシュしました。末尾のnullptr – Bob

+1

注意end *からnullptrを返すようには勧められませんでした。それは全く間違っています。イテレータをデクリメントできるように、擬似/ダミー要素を返すべきです。つまり、実装には問題があります。 – Karadur

+0

@ karadur thnx man it worked – Bob

関連する問題