이중 연결 목록의 begin() 및 end() 구현

Question

원래 내부 데이터 구조가 std::list 인 컨테이너 클래스를 작성했습니다. 그런 다음 자신의 이중 연결 목록을 만들어야했습니다. 이제 연결된 목록에 대한 내 자신의 이중 반복 목록과 자체 반복자를 구현했지만 std::list, 특히 begin() 및 end()과 같이 작동하도록하는 데 문제가 있습니다.

내가 이해 한대로 begin()은 첫 번째 노드를 가리켜 야하고 end()은 마지막 요소보다 한 요소를 가리켜 야합니다. 내가 end()을 호출 할 때 유효한 마지막 요소로 감소시킬 수 있는지 확인해야합니다. 또한

while (beg != end) { do something; beg++; } 

은 본질적으로 내 연결리스트는 단지 데이터 요소, 이전 노드에 대한 포인터와 다음 노드에 대한 포인터를 포함하는 노드를 사용하여 ... 내가 좋아하는 일반 순회를 할 수 있는지 확인해야합니다 .

내가 처음에 end()을 구현하려고 시도했을 때 나는 마지막 노드의 다음 포인터가 nullptr이었습니다. 그것은 독자적으로 작동하지만 stl과 같은 방식으로 작동하지 않습니다.

표준 라이브러리와 동일한 방법으로 begin() 및 end()을 구현하는 방법에 대한 조언이 있으십니까?

Answer 1

센티넬 노드를 도입하고 순환 링크 된 목록을 가질 수 있습니다.

스케치 :

class List 
{ 
    private: 
    struct Node { 
     Node* previous; 
     Node* next; 

     Node() : previous(this), next(this) {} 
    }; 

    struct DataNode : Node { 
     int data; 
    }; 

    public: 
    class iterator 
    { 
     friend class List; 

     private: 
     iterator(Node* node) : m_node(node) {} 

     public: 
     iterator() : m_node(0) {} 

     iterator& operator ++() { 
      m_node = m_node->next; 
      return *this; 
     } 

     int& operator *() { 
      // Note: Dereferncing the end (sentinal node) is undefined behavior. 
      return reinterpret_cast<DataNode*>(m_node)->data; 
     } 

     // More iterator functions. 

     private: 
     Node* m_node; 
    }; 

    public: 
    List() : m_sentinal(new Node) {} 

    iterator begin() { return iterator(m_sentinal->next); } 
    iterator end() { return iterator(m_sentinal); } 

    iterator insert(iterator position, int data) { 
     DataNode* data_node = new DataNode; // pass data 
     Node* current = position.m_node; 
     data_node->next = current; 
     data_node->previous = current->previous; 
     current->previous->next = data_node; 
     current->previous = data_node; 
     return iterator(current); 
    } 

    void append(int data) { 
     insert(end(), data); 
    } 

    private: 
    Node* m_sentinal; 
}; 

Answer 2

컨테이너는 항상 사용할 수있는 끝 노드를 만들어야합니다. 컨테이너가 비었을 때 begin()에서 반환 할 내용입니다. 마지막 실제 노드는 항상이 노드의 다음 노드로 설정해야합니다.

Answer 3

귀하의 모든 노드가 null 인 경우 역순으로 구현할 수 없기 때문에 최종 노드를 null로 설정할 수 없습니다. 최종 노드에 대해 최소한 목록에있는 마지막 노드로 돌아가는 방법을 알고있는 센티널을 만들어야합니다.