CPP-101: Двусвързан списък с водещ елемент

Итератор за класа List

За обхождане на елементите на класа List ще дефинираме помощен клас iterator. За да може нашият итератор да имитира итераторите от стандартната библиотека е необходимо да се владеят механизмите за предефиниране на оператори. Поради това на този етап итератора, който ще дефинираме няма да разполага с обичайните за C++ механизми.

[note]
Итераторите са често използван design pattern. Класическият източник за запознаване с общите принципи на този design pattern е:

• Design Patterns: Elements of Reusable Object-Oriented Software.

Други полезни източници са:

• Head First Design Patterns
• Portland Pattern Repository’s Wiki: Iterator Pattern
• Wikipedia: Iterator Pattern

[/note]

Класът итератор за класа List е тясно свързан с вътрешното устройство на контейнера List. Поради това дефинираме класа iterator като вътрешен клас на класа List. Освен това ще направим класа List приятелски клас на класа iterator:

class List {
    ...
public:
    ...
	class iterator {
	    friend class List;
	    
	    List*  list_;
	    Node* current_;

	    iterator(const List* l,Node* current)
	        : list_(const_cast<List*>(l)),
	          current_(current)
	    {}
	public:
        ...	    
	};

    ...  
};

Като член-променливи на класа iterator дефинираме:

• const List *const list_ – указател към списъка, който ще обхождаме с помощта на итератора;
• Node* current_ – указател към елемента на списъка, към който е насочен итератора.

Конструктора е дефиниран в private частта на класа. Това гарантира, че обекти от типа List::iterator могат да се създават само от членовете на самият клас и неговите приятели (в случая класа List). Конструктора на iterator инициализира член-променливите на класа.

class List {
    ...
public:
    ...
	class iterator {
        ...
	public:

	    bool has_next() const {
	        return current_->next_!=list_->head_;
	    }
	    
	    int next() {
	        current_=current_->next_;
	        return current_->data_;
	    }
	    
	    int get_data() const {
	        if(current_!=list_->head_) {
	            return current_->data_;
	        }
	        throw ListError("iterator::get_data()...");
	    }

	};

    ...  
};

Методите на класа iterator имитират начина на работа на итераторите в Java.

• has_next() – проверява дали итератора е стигнал до края на списъка. Ако итератора е позициониран върху последният елемент на списъка, то has_next() връща false, иначе връща true.
• next() – извършва едновременно две операции – позиционира итератора върху следващият елемент на списъка и връща стойността на елемента, върху който е позициониран.
• get_data() – връща стойността на елемента, върху който е позициониран итератора. Ако итератора е позициониран върху фиктивният елемент, то този метод генерира изключение ListError().