面试题：C++ STL迭代器end在自定义迭代器和算法中的区间判断优化

设计思路

容器设计：
- 类似于std::vector，需要一个动态数组来存储元素。使用指针指向动态分配的内存空间，同时记录当前容量和元素个数。
- 提供常见的操作，如添加元素（push_back）、访问元素（operator[]）等。
迭代器设计：
- 自定义迭代器应支持++（前置和后置）、--（前置和后置，假设容器支持反向遍历）、*（解引用）、!=和==等操作符，以满足标准库算法的需求。
- 对于end迭代器，它应该指向容器最后一个元素的下一个位置。这样在使用标准库算法时，如std::find，算法通过比较迭代器是否到达end来判断是否遍历完整个容器区间。当算法到达end迭代器时，就知道已经遍历完了容器内有效的元素区间，从而停止遍历，保证了高效准确的区间判断。

实现要点

容器部分：
- 内存管理：在需要时动态分配和释放内存，当元素个数超过当前容量时，重新分配更大的内存空间，并将原数据复制过去。
- 元素访问接口：提供operator[]用于直接访问元素，size用于获取当前元素个数，capacity用于获取当前容量。
迭代器部分：
- 迭代器应包含一个指向容器内元素的指针作为其内部状态。
- 实现迭代器的操作符重载，如++、--、*、!=和==，使其行为符合标准库迭代器的要求。end迭代器的指针应指向容器最后一个元素的下一个位置，这样标准库算法在遍历到end迭代器时能够正确判断区间结束。

关键代码

#include <iostream>
#include <memory>

// 自定义容器
template <typename T>
class MyVector {
public:
    // 自定义迭代器
    class Iterator {
    public:
        Iterator(T* ptr) : ptr_(ptr) {}

        // 前置++
        Iterator& operator++() {
            ++ptr_;
            return *this;
        }
        // 后置++
        Iterator operator++(int) {
            Iterator temp = *this;
            ++ptr_;
            return temp;
        }
        // 前置--
        Iterator& operator--() {
            --ptr_;
            return *this;
        }
        // 后置--
        Iterator operator--(int) {
            Iterator temp = *this;
            --ptr_;
            return temp;
        }
        // 解引用
        T& operator*() {
            return *ptr_;
        }
        // 比较
        bool operator!=(const Iterator& other) const {
            return ptr_ != other.ptr_;
        }
        bool operator==(const Iterator& other) const {
            return ptr_ == other.ptr_;
        }

    private:
        T* ptr_;
    };

    MyVector() : data_(nullptr), size_(0), capacity_(0) {}
    ~MyVector() {
        std::free(data_);
    }

    // 添加元素
    void push_back(const T& value) {
        if (size_ == capacity_) {
            capacity_ = capacity_ == 0? 1 : capacity_ * 2;
            T* new_data = static_cast<T*>(std::realloc(data_, capacity_ * sizeof(T)));
            if (!new_data) {
                throw std::bad_alloc();
            }
            data_ = new_data;
        }
        data_[size_++] = value;
    }

    // 访问元素
    T& operator[](size_t index) {
        return data_[index];
    }

    // 获取元素个数
    size_t size() const {
        return size_;
    }

    // 获取容量
    size_t capacity() const {
        return capacity_;
    }

    // 返回begin迭代器
    Iterator begin() {
        return Iterator(data_);
    }
    // 返回end迭代器，指向最后一个元素的下一个位置
    Iterator end() {
        return Iterator(data_ + size_);
    }

private:
    T* data_;
    size_t size_;
    size_t capacity_;
};

可以通过以下方式测试：

int main() {
    MyVector<int> myVec;
    myVec.push_back(1);
    myVec.push_back(2);
    myVec.push_back(3);

    auto it = std::find(myVec.begin(), myVec.end(), 2);
    if (it != myVec.end()) {
        std::cout << "找到元素: " << *it << std::endl;
    } else {
        std::cout << "未找到元素" << std::endl;
    }
    return 0;
}

面试题：C++ STL迭代器end在自定义迭代器和算法中的区间判断优化

知识考点

面试题答案

设计思路

实现要点

关键代码