C++에서 stl-like Iterator를 직접 작성하는 방법

Question

현재 구현 된 다양한 언어의 반복기의 내장 함수를 이해하려고합니다.

예를 들어, 목록 인터페이스를 노출하는 다음 클래스가 있습니다. GoF의에 따르면

template<class T> 
class List 
{ 

    public: 

    virtual void Insert(int beforeIndex, const T item) throw(ListException) =0 ; 
    virtual void Append(const T item) =0; 

    virtual T Get(int position) const throw(ListException) =0; 
    virtual int GetLength() const =0; 

    virtual void Remove(int position) throw(ListException) =0; 


    virtual ~List() =0 {}; 
}; 

, 탐색의 다른 종류를 지원할 수있는 반복자를 구현하는 가장 좋은 방법은 목록의 구성원에 액세스 할 수 있습니다 보호 방법과 기본 반복자 클래스 (목록의 친구)를 만드는 것입니다. Iterator의 구상 구현은 다양한 방법으로 작업을 처리하고 기본 인터페이스를 통해 List의 개인 데이터와 보호 된 데이터에 액세스합니다.

여기부터는 혼란스러워지고 있습니다. List에서 LinkedList와 ArrayList 클래스를 파생 시켰고 이에 상응하는 반복자가 있으며 각 클래스가 리턴합니다. LinkedListIterator를 어떻게 구현할 수 있습니까? 나는 절대적으로 아이디어가 부족합니다. 그리고 기본 이터레이터 클래스가 List로부터 검색 할 수있는 데이터의 종류는 무엇입니까 (이는 모든 파생 클래스의 구현이 크게 다르지만 단순한 인터페이스입니다).

Answer 1

STL은 추상적 인 기본 클래스와 가상 함수를 실제로 사용하지 않습니다. 대신 의도적으로 GoF의 의미에서 OO가되지 않도록 설계되었으며 "컴파일 타임 다형성"을 목표로 템플릿에 전적으로 빌드됩니다. 템플릿은 추상 인터페이스에 신경 쓰지 않습니다. 인터페이스가 충분히 유사하면 (예 : Appendpush_back) 더 많은 코드가 std::back_insert_iterator과 같이 STL 호환 컨테이너를 사용할 수 있다고 예상하는 경우 작동합니다. (- 이중 연결 양방향 경우), *, ->, ++, -- 포함, (가능한 한 컨테이너의 한계 부여) 호환 반복자는 포인터처럼 행동하는 사업자의 많은 과부하해야

STL == 및 !=.

Answer 2

C++ 표준 라이브러리는 이터레이터 구현시 다형성과 상속을 사용하지 않습니다. 대신 C++ 템플릿 메타 프로그래밍과 "개념"의 개념 (공식적인 구문이 아닌)을 사용합니다.

iterator 클래스의 인터페이스가 일부 요구 사항을 준수하는 경우 필수적으로 작동합니다. 이 일련의 요구 사항을 "개념"이라고합니다. 몇 가지 다른 반복자 개념 (this page for a list of all of them 참조)이 있으며 계층 적입니다. 호환되는 C++ 반복기를 만드는 기본 사항은 인터페이스가 개념을 준수하도록 만드는 것입니다. 앞으로 만 간다 간단한 반복자의 경우, 이것은 필요 :

• A는 당신의 반복자를 역 참조의 결과 값에 value_type을 형식 정의를.
• 해당 값 유형의 참조 유형 인 typedef reference_type.
• 해당 값 유형의 포인터 유형 인 typedef pointer.
• typedef iterator_category은 통과 메커니즘에 따라 input_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag 또는 random_access_iterator_tag 중 하나 여야합니다.
• 두 개의 다른 반복기를 뺀 결과를 나타내는 typedef difference_type.
• const value_type& operator*()const 반복기를 역 참조하기위한 함수.
• value_type& operator*() 이터레이터를 사용하여 값을 조작 할 수 있으면 작동합니다.
• 앞으로 검색하기 위해 증가 (operator++() 및 operator++(int) 기능).
• 차이 기능 : difference_type operator-(const type_of_iterator&)

당신이 더 많은 고급 반복자 카테고리 중 하나를 선택하면, 당신은 또한 뒤로 추구 할 수 또는 임의의 거리를 추구하기 위해 감소 플러스 연산자를 지정해야 할 수도 있습니다 .

* C++ 표준 라이브러리는 비공식적으로 개념을 자주 사용하므로 C++ 표준위원회는 C++로 선언 할 수있는 공식 메커니즘을 도입하려고했습니다 (현재 이들은 표준 라이브러리의 문서에만 존재하며 명시 적 코드). 그러나 제안서에 대한 지속적인 불일치로 인해 C++ 0x에서 폐기되었지만 그 이후에는 표준에 대해 다시 고려해야 할 것입니다.