您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

C++ 實現 STL 風格鏈表迭代器：ListIterator 完整設計與代碼詳解

編輯：關於C++

為了向 C++ 標準模板庫（STL）致敬，我們將模仿 std::list 的迭代器設計，為自定義的鏈表容器 MyList 實現一個功能完整的 ListIterator，以便遍歷鏈表中的所有元素。

核心修改：Node 節點與 MyList 類

首先，Node 節點類需要聲明 ListIterator 為友元類，以便迭代器能夠訪問節點的私有成員：

// 鏈表節點
template <typename Type>
class Node {
    friend class MyList<Type>;
    friend class ListIterator<Type>; // 新增友元聲明
    template <typename T>
    friend std::ostream &operator<<(std::ostream &os, const MyList<T> &list);

private:
    Node(const Type &dataValue) : data(dataValue), next(nullptr) {}
    Type data;       // 數據域
    Node *next;      // 指針域：指向下一個節點
};

MyList 類同樣需要將 ListIterator 聲明為友元，由於代碼較長，此處不再重複貼出，完整代碼請見文末附錄。

ListIterator 類的設計

迭代器類提供了解引用（*）、成員訪問（->）、前置/後置遞增（++）以及判空（isEmpty）等核心操作，並通過拋出 std::out_of_range 異常來處理越界訪問：

template <typename Type>
class ListIterator {
public:
    ListIterator(const MyList<Type> &_list)
        : list(_list), currentNode((_list.first)->next) {}

    // 解引用運算符重載（const 版本與非 const 版本）
    const Type &operator*() const throw(std::out_of_range);
    Type &operator*() throw(std::out_of_range);

    // 成員訪問運算符重載
    const Node<Type> *operator->() const throw(std::out_of_range);
    Node<Type> *operator->() throw(std::out_of_range);

    // 遞增運算符重載
    ListIterator &operator++() throw(std::out_of_range);      // 前置++
    ListIterator operator++(int) throw(std::out_of_range);    // 後置++

    bool isEmpty() const;

private:
    const MyList<Type> &list;      // 關聯的鏈表引用
    Node<Type> *currentNode;       // 當前指向的節點
};

關鍵成員函數實現詳解

1. 解引用運算符 `operator*()`

採用「const 版本實現核心邏輯，非 const 版本通過 const_cast 調用」的經典模式，避免代碼重複：

template <typename Type>
const Type &ListIterator<Type>::operator*() const throw(std::out_of_range) {
    if (isEmpty()) throw std::out_of_range("iterator is out of range");
    return currentNode->data;
}

template <typename Type>
Type &ListIterator<Type>::operator*() throw(std::out_of_range) {
    return const_cast<Type &>(
        static_cast<const ListIterator<Type> &>(*this).operator*()
    );
}

2. 成員訪問運算符 `operator->()`

直接返回當前節點指針，同樣採用 const/非 const 雙版本模式：

template <typename Type>
const Node<Type> *ListIterator<Type>::operator->() const throw(std::out_of_range) {
    if (isEmpty()) throw std::out_of_range("iterator is out of range");
    return currentNode;
}

template <typename Type>
Node<Type> *ListIterator<Type>::operator->() throw(std::out_of_range) {
    return const_cast<Node<Type> *>(
        static_cast<const ListIterator<Type> >(*this).operator->()
    );
}

3. 遞增運算符

前置遞增返回引用，後置遞增返回舊值副本：

template <typename Type>
ListIterator<Type> &ListIterator<Type>::operator++() throw(std::out_of_range) {
    if (isEmpty()) throw std::out_of_range("iterator is out of range");
    currentNode = currentNode->next;
    return *this;
}

template <typename Type>
ListIterator<Type> ListIterator<Type>::operator++(int) throw(std::out_of_range) {
    ListIterator tmp(*this);
    ++(*this);  // 復用前置遞增
    return tmp;
}

4. 判空檢查

template <typename Type>
bool ListIterator<Type>::isEmpty() const {
    return currentNode == nullptr;
}

測試代碼與運行示例

以下測試代碼對比了標準庫 std::list 與自製 MyList 的迭代器遍歷效果：

int main() {
    std::list<int> iStdList;
    MyList<int> iMyList;

    for (int i = 0; i < 10; ++i) {
        iStdList.push_back(i + 1);
        iMyList.insert(i + 1, i + 1);
    }

    // std::list 遍歷
    for (auto iter = iStdList.begin(); iter != iStdList.end(); ++iter) {
        std::cout << *iter << ' ';
    }
    std::cout << std::endl;

    // MyList 遍歷
    for (ListIterator<int> iter(iMyList); !iter.isEmpty(); ++iter) {
        std::cout << *iter << ' ';
    }
    std::cout << std::endl;

    std::cout << "Test: \n\t" << iMyList << std::endl;
    ListIterator<int> iter(iMyList);
    std::cout << "first = " << *iter << std::endl;
}

附錄：MyList 完整源代碼

完整頭文件包含節點定義、鏈表核心操作（插入、刪除、反轉、連接）、輸出運算符重載以及 ListIterator 的完整實現：

// MyList.h
#ifndef MYLIST_H_INCLUDED
#define MYLIST_H_INCLUDED

#include <iostream>
#include <stdexcept>

using namespace std;

// 前向聲明
template <typename Type> class MyList;
template <typename Type> class ListIterator;

// 鏈表節點
template <typename Type>
class Node {
    friend class MyList<Type>;
    friend class ListIterator<Type>;
    template <typename T>
    friend ostream &operator<<(ostream &os, const MyList<T> &list);

private:
    Node(const Type &dataValue) : data(dataValue), next(nullptr) {}
    Type data;
    Node *next;
};

// 鏈表類
template <typename Type>
class MyList {
    template <typename T>
    friend ostream &operator<<(ostream &os, const MyList<T> &list);
    friend class ListIterator<Type>;

public:
    MyList();
    ~MyList();
    void insertFront(const Type &data);
    void insert(const Type &data, int index);
    void remove(const Type &data);
    bool isEmpty() const;
    void invort();                           // 鏈表反轉
    void concatenate(const MyList<Type> &list); // 鏈表連接

private:
    Node<Type> *first;  // 指向頭哨兵節點
};

// --- 成員函數實現 ---

template <typename Type>
MyList<Type>::MyList() {
    first = new Node<Type>(0);  // 頭哨兵節點
    first->next = nullptr;
}

template <typename Type>
MyList<Type>::~MyList() {
    Node<Type> *deleteNode = nullptr;
    while (first != nullptr) {
        deleteNode = first;
        first = first->next;
        delete deleteNode;
    }
}

template <typename Type>
void MyList<Type>::insertFront(const Type &data) {
    Node<Type> *newNode = new Node<Type>(data);
    newNode->next = first->next;
    first->next = newNode;
}

template <typename Type>
void MyList<Type>::insert(const Type &data, int index) {
    int count = 1;
    Node<Type> *searchNode = first;
    while (count < index && searchNode->next != nullptr) {
        ++count;
        searchNode = searchNode->next;
    }
    Node<Type> *newNode = new Node<Type>(data);
    newNode->next = searchNode->next;
    searchNode->next = newNode;
}

template <typename Type>
void MyList<Type>::remove(const Type &data) {
    if (isEmpty()) return;
    Node<Type> *previous = first;
    for (Node<Type> *searchNode = first->next; searchNode != nullptr; searchNode = searchNode->next) {
        if (searchNode->data == data) {
            previous->next = searchNode->next;
            delete searchNode;
            if (previous->next == nullptr) break;
            searchNode = previous->next;
        }
        previous = searchNode;
    }
}

template <typename Type>
bool MyList<Type>::isEmpty() const {
    return first->next == nullptr;
}

template <typename Type>
void MyList<Type>::concatenate(const MyList<Type> &list) {
    if (isEmpty()) { first = list.first; return; }
    if (list.isEmpty()) return;

    Node<Type> *endNode = first->next;
    while (endNode->next != nullptr) endNode = endNode->next;

    Node<Type> *secondListNode = list.first->next;
    while (secondListNode != nullptr) {
        Node<Type> *newNode = new Node<Type>(secondListNode->data);
        newNode->next = nullptr;
        endNode->next = newNode;
        endNode = endNode->next;
        secondListNode = secondListNode->next;
    }
}

template <typename Type>
void MyList<Type>::invort() {
    if (!isEmpty()) {
        Node<Type> *p = first->next;
        Node<Type> *q = nullptr;
        while (p != nullptr) {
            Node<Type> *r = q;
            q = p;
            p = p->next;
            q->next = r;
        }
        first->next = q;
    }
}

// 輸出運算符重載
template <typename Type>
ostream &operator<<(ostream &os, const MyList<Type> &list) {
    for (Node<Type> *searchNode = list.first->next; searchNode != nullptr; searchNode = searchNode->next) {
        os << searchNode->data;
        if (searchNode->next != nullptr) cout << " -> ";
    }
    return os;
}

// ListIterator 完整定義與實現（同上文）
// ... 此處省略，與前文實現一致 ...

#endif // MYLIST_H_INCLUDED