面试题：C++ STL空容器end迭代器在自定义数据结构中的应用与实现

Question

假设你要设计一个自定义的类似STL容器的数据结构，该数据结构在空容器状态下对end迭代器的行为要与STL标准容器保持一致。请描述该数据结构的设计思路，并给出关键代码实现，同时说明如何确保其在多线程环境下对end迭代器处理的正确性。

Answer 1

设计思路

1. 数据存储：选择合适的数据结构来存储元素，例如动态数组（类似 std::vector）或链表（类似 std::list）。这里以动态数组为例。
2. 迭代器设计：设计迭代器类，使其行为类似于 STL 迭代器。对于 end 迭代器，它应该指向容器中最后一个元素之后的位置。在空容器中，begin 和 end 迭代器应相等，指向容器数据范围之外的一个“哨兵”位置。
3. 线程安全：为了确保多线程环境下 end 迭代器处理的正确性，需要考虑对容器数据的并发访问控制。可以使用互斥锁（std::mutex）来保护对容器的操作，特别是在修改容器结构（如添加或删除元素）时。

关键代码实现

#include <iostream>
#include <memory>
#include <mutex>

template <typename T>
class MyContainer {
private:
    std::unique_ptr<T[]> data;
    size_t size_;
    size_t capacity_;
    std::mutex mtx;

public:
    class iterator {
    private:
        T* ptr;
    public:
        iterator(T* p) : ptr(p) {}

        T& operator*() { return *ptr; }
        T* operator->() { return ptr; }
        iterator& operator++() { ++ptr; return *this; }
        iterator operator++(int) { iterator temp = *this; ++ptr; return temp; }
        bool operator==(const iterator& other) const { return ptr == other.ptr; }
        bool operator!=(const iterator& other) const { return ptr != other.ptr; }
    };

    MyContainer() : size_(0), capacity_(0), data(nullptr) {}

    ~MyContainer() = default;

    void push_back(const T& value) {
        std::lock_guard<std::mutex> lock(mtx);
        if (size_ == capacity_) {
            capacity_ = capacity_ == 0? 1 : capacity_ * 2;
            std::unique_ptr<T[]> newData(new T[capacity_]);
            for (size_t i = 0; i < size_; ++i) {
                newData[i] = data[i];
            }
            data = std::move(newData);
        }
        data[size_++] = value;
    }

    iterator begin() { return iterator(data.get()); }
    iterator end() { return iterator(data.get() + size_); }
};

多线程环境下 end 迭代器处理的正确性确保

1. 互斥锁保护：在修改容器结构（如 push_back 函数）时，使用 std::lock_guard<std::mutex> 来自动管理锁的获取和释放，保证同一时间只有一个线程能修改容器。这确保了 end 迭代器的位置不会在迭代过程中被其他线程意外修改。
2. 读操作：对于只读操作（如通过迭代器遍历容器），可以选择加读锁（如果使用读写锁 std::shared_mutex），这样多个线程可以同时进行读操作而不会发生数据竞争。

通过以上设计和实现，可以在自定义数据结构中实现类似 STL 容器的行为，并确保在多线程环境下 end 迭代器处理的正确性。