面试题：C++ STL 迭代器end边界判断在自定义容器中的应用

Question

假设你正在实现一个自定义的双向链表容器`MyList`，并且希望它能够支持STL风格的迭代器。请描述如何在实现`begin()`和`end()`迭代器时，确保`end()`迭代器的边界判断逻辑正确，特别是在插入和删除操作之后，需要考虑双向链表的特性。请给出关键代码片段。

Answer 1

1. 迭代器设计：
   • 首先定义双向链表节点结构和迭代器类。

   template <typename T>
   struct MyListNode {
       T data;
       MyListNode* prev;
       MyListNode* next;
       MyListNode(const T& value) : data(value), prev(nullptr), next(nullptr) {}
   };
   
   template <typename T>
   class MyListIterator {
   public:
       using difference_type = std::ptrdiff_t;
       using value_type = T;
       using pointer = T*;
       using reference = T&;
       using iterator_category = std::bidirectional_iterator_tag;
   
       MyListIterator(MyListNode<T>* node) : current(node) {}
   
       reference operator*() const { return current->data; }
       pointer operator->() const { return &(current->data); }
   
       MyListIterator& operator++() {
           current = current->next;
           return *this;
       }
   
       MyListIterator operator++(int) {
           MyListIterator temp = *this;
           ++(*this);
           return temp;
       }
   
       MyListIterator& operator--() {
           current = current->prev;
           return *this;
       }
   
       MyListIterator operator--(int) {
           MyListIterator temp = *this;
           --(*this);
           return temp;
       }
   
       bool operator==(const MyListIterator& other) const { return current == other.current; }
       bool operator!=(const MyListIterator& other) const { return!(*this == other); }
   
   private:
       MyListNode<T>* current;
   };
   

2. 双向链表容器MyList实现：
   • 实现begin()和end()函数。

   template <typename T>
   class MyList {
   public:
       MyList() : head(nullptr), tail(nullptr) {}
   
       MyListIterator<T> begin() { return MyListIterator<T>(head); }
       MyListIterator<T> end() { return MyListIterator<T>(nullptr); }
   
       void push_back(const T& value) {
           MyListNode<T>* newNode = new MyListNode<T>(value);
           if (!tail) {
               head = tail = newNode;
           } else {
               newNode->prev = tail;
               tail->next = newNode;
               tail = newNode;
           }
       }
   
       void pop_back() {
           if (!tail) return;
           MyListNode<T>* temp = tail;
           tail = tail->prev;
           if (tail) {
               tail->next = nullptr;
           } else {
               head = nullptr;
           }
           delete temp;
       }
   
       ~MyList() {
           while (head) {
               MyListNode<T>* temp = head;
               head = head->next;
               delete temp;
           }
       }
   
   private:
       MyListNode<T>* head;
       MyListNode<T>* tail;
   };
   

3. 边界判断逻辑：
   • begin()返回指向链表头节点的迭代器。
   • end()返回指向nullptr的迭代器，代表链表尾后位置。
   • 在插入操作（如push_back）时，新节点被正确链接到链表尾部，end()迭代器依然指向nullptr，因为end()代表尾后位置。
   • 在删除操作（如pop_back）时，当链表为空，head和tail都被设置为nullptr，begin()返回的迭代器和end()返回的迭代器相等，符合边界判断逻辑。当链表不为空，删除尾节点后tail更新，end()迭代器依然指向nullptr，保持正确的边界判断。