容器与迭代器实现详解

在C++编程语言中，容器是指用于存储和管理数据的各种数据结构，包括但不限于列表（list）、向量（vector）、双端队列（deque）、队列（queue）、优先队列（priority_queue）、堆栈（stack）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）。

迭代器是一种提供访问容器中元素方式的对象，类似于指针，它允许程序员遍历容器中的元素而无需暴露容器内部的具体实现细节。

节点是构成某些类型容器的基本单元，例如，在链表中，每个节点通常是一个包含数据成员和指向下一个节点指针的结构体。

#include 
#include 
#include 
using namespace std;

// 定义链表节点类
template
class Node {
public:
    T data;
    Node* next;
public:
    Node(T val) : data(val), next(nullptr) {}
    T getData() const { return data; }
    Node* getNext() const { return next; }
    bool operator==(const Node& other) const {
        return data == other.data;
    }
};

// 定义链表类
template
class LinkedList {
private:
    Node* head;
    Node* tail;
    int length;
public:
    LinkedList() : head(nullptr), tail(nullptr), length(0) {}
    ~LinkedList();
    void addFront(T value);
    void addBack(T value);
    void printList() const;
    Node* getHead() const { return head; }
    Node* getTail() const { return tail; }
    int getSize() const { return length; }
};

// 链表析构函数
template
LinkedList::~LinkedList() {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

// 在链表头部添加元素
template
void LinkedList::addFront(T value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = tail = newNode;
    } else {
        newNode->next = head;
        head = newNode;
    }
    length++;
}

// 在链表尾部添加元素
template
void LinkedList::addBack(T value) {
    Node* newNode = new Node(value);
    if (tail == nullptr) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        tail = newNode;
    }
    length++;
}

// 打印链表
template
void LinkedList::printList() const {
    Node* current = head;
    while (current != nullptr) {
        cout <data <<" ";
        current = current->next;
    }
    cout <}

// 定义迭代器类
template
class ListIterator {
private:
    Node* node;
public:
    ListIterator(Node* n = nullptr) : node(n) {}
    T& operator*() const { return node->data; }
    Node* operator->() const { return node; }
    ListIterator& operator++() {
        if (node != nullptr) {
            node = node->next;
        }
        return *this;
    }
    bool operator==(const ListIterator& other) const {
        return node == other.node;
    }
    bool operator!=(const ListIterator& other) const {
        return node != other.node;
    }
};

// 主函数示例
int main() {
    LinkedList list;
    list.addFront(1);
    list.addFront(3);
    list.addFront(2);
    list.addBack(4);
    list.addBack(5);
    list.printList();

    typedef ListIterator Iterator;
    Iterator begin(list.getHead());
    Iterator end(nullptr);
    Iterator it = find(begin, end, 3);
    if (it == end) {
        cout <<"Element not found" <    } else {
        cout <<"Element found" <    }

    return 0;
}