표준 라이브러리 목록에 대한 질문

Question

이전에는 노드를 사용하여 연결된 목록을 구현했습니다.

표준 라이브러리 목록의 일부 속성을 살펴보고 iterators와 적절한 멤버 함수가 있습니다.

리스트의 반복자는 무엇입니까? 노드 포인터입니까?

벡터의 경우 기본적으로 요소 유형에 대한 포인터가 있으며 데이터 구조는 해당 유형의 기본 동적 배열을 기반으로 작성됩니다.

목록의 경우 노드 시퀀스, 노드 배열 인 것 같습니다. 그래서 이터레이터는 노드 데이터 타입에 대한 포인터가 아니라 노드 포인터입니까? 벡터 내가이 반복자가 있다면

기본적으로 내가 무엇을 해달라고 부탁하는 것입니다 :

tyepdef T* iterator; 

목록에 대한 반복자가 될 것인가를

typedef node* iterator; 

곳 노드 뭔가 같은 :

template <class T> struct node { 
    node() { next = 0; } 
    node(T i, node* n = 0) : data(i), next(n) {} 
    node* next; 
    T data; 
} 

이 경우 dereferencing과 같은 작업이 오버로드되어야합니다.

Answer 1

std::list<T>::iterator 개체는 노드를 내부적으로 가리 키지 만 다음 또는 이전 노드에 대한 포인터를 적절히 따르는 연산자가 있습니다. 포인터를 증가 시키면 링크를 따르기보다는 포인터를 하나씩 추가하기 때문에 포인터가 아닙니다. 당신은리스트 반복자가 다소 다음과 같습니다 inagine 수 있습니다

이

template <typename T> 
class list_iterator { 
    friend list<T> 
    Node* node; 
    list_iterator(T* node):node(node) {} 
    list_iterator& operator++() { 
     node = node->next; 
     return *this; 
    } 
    T& operator*() { return *node; } 
    // ... 
}; 

Answer 2

목록에 반복자는 vector 같은 다른 시퀀스 컨테이너의 반복자와 유사한 행동해야한다. 나는. list :: value_type에 대한 포인터처럼 동작해야합니다 (예 : ++ 및 - 예상되는 작업을 다음 및 이전으로 진행). 지주 구조의 내부는 반복기를 통해 실제로 노출되지 않습니다. 반복자 추상화는 일반적으로 프로그래머가 데이터가 저장되는 방법을 생각할 수 없게합니다. 앞으로는 std::list을 std::vector으로 이론적으로 교환 할 수 있습니다. 코드를 변경하지 않고도 두 가지 작업 만 사용할 수 있습니다.