Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

Aufgabe (Bonus) Iteratoren

uint32_t buffer[10] {1, 3, 3, 7, 4, 2, 3, 6, 0, 0};

// points to first element
uint32_t *begin = buffer + 2;
// points to the next position after the last element
uint32_t *end = buffer + 5;

for (uint32_t *p = begin; p != end; ++p) {
    std::cout << *p << "\n";
}

LinkedLists bieten a priori keine Möglichkeit durch einfache Pointerarithmetik über Elemente zu iterieren; Dies liegt daran, dass die Elemente einer doubly_linked_list sich an beliebigen (nicht aufeinanderfolgenden) Positionen im Speicher befinden können. In dieser Aufgabe implementieren Sie eine Klasse, die sich nach außen hin wie ein Pointer verhält, aber intern stattdessen über die im Speicher verteilten Elemente (hier einer doubly_linked_list) iteriert. Ein solches Konstrukt wird im Allgemeinen Iterator genannt.

Im Repository haben wir für Sie bereits eine Implementierung für eine doubly_linked_list hinterlegt. Sie dürfen diese Implementierung anpassen, wenn Sie es für notwendig halten. Die Deklaration des Iterations ist für diese Aufgabe bereits vorgegeben, sie gehört zu den existierenden Deklarationen in den doubly_linked_list-Header:

class linked_list_iterator {

    // all the variables you need go here

public:
    linked_list_iterator(/* ... arguments ... */);

    uint64_t& operator*();
    uint64_t* operator->();

    // pre-increment
    linked_list_iterator& operator++();
    // post-increment
    linked_list_iterator operator++(int);

    // non-standard for LinkedLists due to time complexity
    linked_list_iterator& operator+=(size_t amount);

    // non-standard, very useful for LinkedLists
    void insert_after(uint64_t element);
};

bool operator ==(const linked_list_iterator &lhs, const linked_list_iterator &rhs);
bool operator !=(const linked_list_iterator &lhs, const linked_list_iterator &rhs);

linked_list_iterator begin(doubly_linked_list &l);
linked_list_iterator end(doubly_linked_list &l);

Aufgaben

1. Implementieren Sie die angegebenen Methoden des linked_list_iterators.
   
   • begin gibt hierbei einen Iterator zurück, der auf das erste Element der doubly_linked_list zeigt.
   • end gibt einen Iterator zurück, der "hinter" das letzte Element der doubly_linked_list zeigt - ein solches Element existiert natürlich nicht, überlegen Sie sich daher, wie ein solcher Iterator aussehen könnte.
   • Beachten Sie: Ist eine Liste l leer, so muss notwendigerweise begin(l) == end(l) wahr sein.
   Code zum Testen Ihrer Implementierung:

   doubly_linked_list l;
   l.append(1);
   l.append(2);
   l.append(3);
   l.append(4);
   l.append(5);
   l.append(6);
   
   linked_list_iterator b = begin(l);
   ++b;
   ++b;
   b.insert_after(7);
   linked_list_iterator e = end(l);
   for (linked_list_iterator p = b; p != e; ++p) {
       std::cout << *p << "\n";
   }