面试题：C++ 自定义容器与泛型算法的适配问题

#include <iostream>
#include <algorithm>

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 MyList {
private:
    MyListNode<T>* head;
    MyListNode<T>* tail;
    size_t size_;

public:
    // 自定义迭代器
    class Iterator {
    private:
        MyListNode<T>* current;
    public:
        Iterator(MyListNode<T>* node) : current(node) {}
        T& operator*() { return current->data; }
        Iterator& operator++() {
            current = current->next;
            return *this;
        }
        Iterator operator++(int) {
            Iterator temp = *this;
            current = current->next;
            return temp;
        }
        Iterator& operator--() {
            current = current->prev;
            return *this;
        }
        Iterator operator--(int) {
            Iterator temp = *this;
            current = current->prev;
            return temp;
        }
        bool operator==(const Iterator& other) const { return current == other.current; }
        bool operator!=(const Iterator& other) const { return current != other.current; }
    };

    MyList() : head(nullptr), tail(nullptr), size_(0) {}

    ~MyList() {
        while (head) {
            MyListNode<T>* temp = head;
            head = head->next;
            delete temp;
        }
    }

    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;
        }
        ++size_;
    }

    Iterator begin() { return Iterator(head); }
    Iterator end() { return Iterator(nullptr); }

    size_t size() const { return size_; }
};

// 比较函数示例
bool compare(int a, int b) {
    return a < b;
}

int main() {
    MyList<int> myList;
    myList.push_back(3);
    myList.push_back(1);
    myList.push_back(4);
    myList.push_back(2);

    std::sort(myList.begin(), myList.end(), compare);

    for (MyList<int>::Iterator it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

双向链表节点定义：
- MyListNode 结构体表示双向链表的节点，包含数据 data，前驱节点指针 prev 和后继节点指针 next。
双向链表容器 MyList 定义：
- 成员变量：head 指向链表头，tail 指向链表尾，size_ 记录链表元素个数。
- 自定义迭代器 Iterator：实现了 *（解引用），++（前置和后置），--（前置和后置），== 和 != 运算符重载，使得可以像使用标准库迭代器一样遍历双向链表。
- 构造函数和析构函数：构造函数初始化链表为空，析构函数释放链表所有节点的内存。
- push_back 函数：在链表尾部添加新节点。
- begin 和 end 函数：返回指向链表头和链表尾后一个位置（实际不存在，用 nullptr 表示）的迭代器，以适配泛型算法。
- size 函数：返回链表中元素的个数。
std::sort 使用示例：
- 在 main 函数中，创建 MyList<int> 对象并添加一些整数。
- 使用 std::sort 对 MyList 中的元素进行排序，传入自定义的比较函数 compare。
- 最后遍历排序后的 MyList 并输出结果。

星途面试题库

面试题：C++ 自定义容器与泛型算法的适配问题

知识考点

面试题答案