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

Член-функция erase

За изтриване на елемент от списъка се използва член-функцията erase. Семантиката на тази член-функция ще имитира поведението на член-функцията erase в класа std::list на стандартната библиотека.

iterator erase ( iterator position );

Член-функцията изтрива елемента, към който е насочен итератора position. Функцията връща итератор, насочен към елемента, следващ изтрития елемент. Ако се изтрива последният елемент, то върнатият итератор е насочен към фиктивния елемент.

Изтриване на елемент от списък

При реализиране на член-функцията erase първо проверяваме дали в списъка има елементи и дали итератора position е насочен към елемент на списъка. Ако списъка е празен или position е насочен към фиктивният елемент, то функцията erase генерира изключение.

Дефинираме указатели ptr, prev и next:

• ptr – насочен към елемента, който подлежи на изтриване;
• prev – предходния елемент;
• next – следващият елемент.

Node* ptr=it.current_;
Node* prev=it.current_->prev_;
Node* next=it.current_->next_;

При изтриване на елемента ptr трябва да свържем елементите prev и next след което освобождаваме паметта заемана от елемента ptr.

Изтриване на елемент от списък

Функцията връща итератор, насочен към елемента next.

class List {
    ...
public:
    ...
    
    iterator erase(iterator it) {
        if(empty()) {
            throw ListError("erase(): empty list...");
        }
        if(it.current_==it.list_->head_) {
            throw ListError(
                "erase(): positioned on head...");
        }
        
        Node* ptr=it.current_;
        Node* prev=it.current_->prev_;
        Node* next=it.current_->next_;
        
        prev->next_=next;
        next->prev_=prev;
        
        delete it.current_;
        
        return iterator(it.list_,next);
    }
    
    ...
};