面试题：C++ 实现自定义随机访问迭代器及相关算法

#include <iostream>
#include <cstddef>

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

    MyRandomAccessIterator(pointer ptr) : ptr_(ptr) {}

    reference operator*() const {
        return *ptr_;
    }

    MyRandomAccessIterator& operator++() {
        ++ptr_;
        return *this;
    }

    MyRandomAccessIterator operator++(int) {
        MyRandomAccessIterator temp(*this);
        ++ptr_;
        return temp;
    }

    MyRandomAccessIterator& operator--() {
        --ptr_;
        return *this;
    }

    MyRandomAccessIterator operator--(int) {
        MyRandomAccessIterator temp(*this);
        --ptr_;
        return temp;
    }

    MyRandomAccessIterator operator+(difference_type n) const {
        return MyRandomAccessIterator(ptr_ + n);
    }

    MyRandomAccessIterator operator-(difference_type n) const {
        return MyRandomAccessIterator(ptr_ - n);
    }

    MyRandomAccessIterator& operator+=(difference_type n) {
        ptr_ += n;
        return *this;
    }

    MyRandomAccessIterator& operator-=(difference_type n) {
        ptr_ -= n;
        return *this;
    }

    reference operator[](difference_type n) const {
        return *(ptr_ + n);
    }

    bool operator==(const MyRandomAccessIterator& other) const {
        return ptr_ == other.ptr_;
    }

    bool operator!=(const MyRandomAccessIterator& other) const {
        return ptr_ != other.ptr_;
    }

    bool operator<(const MyRandomAccessIterator& other) const {
        return ptr_ < other.ptr_;
    }

    bool operator>(const MyRandomAccessIterator& other) const {
        return ptr_ > other.ptr_;
    }

    bool operator<=(const MyRandomAccessIterator& other) const {
        return ptr_ <= other.ptr_;
    }

    bool operator>=(const MyRandomAccessIterator& other) const {
        return ptr_ >= other.ptr_;
    }

private:
    pointer ptr_;
};

template <typename T>
class MyRandomAccessContainer {
public:
    using iterator = MyRandomAccessIterator<T>;

    MyRandomAccessContainer(size_t size) : size_(size), data_(new T[size]) {}

    ~MyRandomAccessContainer() {
        delete[] data_;
    }

    iterator begin() {
        return iterator(data_);
    }

    iterator end() {
        return iterator(data_ + size_);
    }

private:
    size_t size_;
    T* data_;
};

template <typename Iterator>
void mySort(Iterator first, Iterator last) {
    for (Iterator i = first; i != last; ++i) {
        for (Iterator j = i + 1; j != last; ++j) {
            if (*j < *i) {
                std::swap(*i, *j);
            }
        }
    }
}

int main() {
    MyRandomAccessContainer<int> container(5);
    container.begin()[0] = 5;
    container.begin()[1] = 4;
    container.begin()[2] = 3;
    container.begin()[3] = 2;
    container.begin()[4] = 1;

    mySort(container.begin(), container.end());

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

    return 0;
}

MyRandomAccessIterator 类:
- 定义了随机访问迭代器所需的类型别名，如 difference_type、value_type 等。
- 实现了 operator*、operator++、operator-- 等常规操作符。
- 实现了 operator+、operator-、operator+=、operator-=、operator[] 以及比较操作符 <、>、<=、>=。
MyRandomAccessContainer 类:
- 定义了一个简单的数组式容器，包含数据和大小。
- 提供了 begin 和 end 方法，返回自定义的随机访问迭代器。
mySort 函数:
- 基于自定义的随机访问迭代器实现了一个简单的排序算法，类似于 std::sort 的功能，这里使用的是冒泡排序的思想。在 main 函数中进行了简单的测试，创建了一个 MyRandomAccessContainer 并对其进行排序和输出。

星途面试题库

面试题：C++ 实现自定义随机访问迭代器及相关算法

知识考点

面试题答案