面试题：C++ STL自定义容器中begin()起始定位的设计与实现

Question

请设计并实现一个简单的自定义双向链表容器`MyList`，要求包含`begin()`成员函数来定位起始位置。在实现过程中，阐述如何保证`begin()`返回的迭代器符合STL迭代器的基本要求，以及在多线程环境下，怎样确保`begin()`操作的线程安全性。

Answer 1

自定义双向链表容器MyList的设计与实现

1. 双向链表节点定义

template <typename T>
struct ListNode {
    T data;
    ListNode* prev;
    ListNode* next;
    ListNode(const T& value) : data(value), prev(nullptr), next(nullptr) {}
};

2. 双向链表迭代器定义

template <typename T>
class MyListIterator {
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;

    MyListIterator(ListNode<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 current != other.current;
    }

private:
    ListNode<T>* current;
};

3. 双向链表容器MyList定义

template <typename T>
class MyList {
public:
    MyList() : head(nullptr), tail(nullptr) {}

    ~MyList() {
        clear();
    }

    void push_back(const T& value) {
        ListNode<T>* newNode = new ListNode<T>(value);
        if (!tail) {
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
    }

    MyListIterator<T> begin() {
        return MyListIterator<T>(head);
    }

    void clear() {
        while (head) {
            ListNode<T>* temp = head;
            head = head->next;
            delete temp;
        }
        tail = nullptr;
    }

private:
    ListNode<T>* head;
    ListNode<T>* tail;
};

确保begin()返回的迭代器符合STL迭代器的基本要求

1. 迭代器类别：定义iterator_category为std::bidirectional_iterator_tag，表明这是一个双向迭代器，支持向前和向后遍历。
2. 类型定义：定义了value_type、difference_type、pointer和reference，符合STL迭代器的类型要求。
3. 操作符重载：重载了*、->、++、--、==和!=操作符，使得迭代器能够像STL迭代器一样使用。

在多线程环境下确保begin()操作的线程安全性

1. 使用互斥锁：在MyList类中添加一个互斥锁成员变量，例如std::mutex listMutex。

template <typename T>
class MyList {
public:
    //...
    MyListIterator<T> begin() {
        std::lock_guard<std::mutex> lock(listMutex);
        return MyListIterator<T>(head);
    }
    //...
private:
    std::mutex listMutex;
    ListNode<T>* head;
    ListNode<T>* tail;
};

2. 读写锁：如果有频繁的读操作和少量的写操作，可以使用读写锁（如std::shared_mutex）来提高性能。读操作（如begin()）可以共享锁，写操作（如push_back）需要独占锁。

template <typename T>
class MyList {
public:
    //...
    MyListIterator<T> begin() {
        std::shared_lock<std::shared_mutex> lock(listMutex);
        return MyListIterator<T>(head);
    }
    void push_back(const T& value) {
        std::unique_lock<std::shared_mutex> lock(listMutex);
        //... 插入节点的操作
    }
    //...
private:
    std::shared_mutex listMutex;
    ListNode<T>* head;
    ListNode<T>* tail;
};

通过以上方法，可以确保begin()返回的迭代器符合STL迭代器的基本要求，并在多线程环境下保证begin()操作的线程安全性。