Proper Implementation of Custom Iterators and Const Iterators in C++

Iterator Categories and Selection

Before implementing custom iterators, it's essential to determine the appropriate iterator category. The C++ standard library defines several iterator categories: input iterators, output iterators, forward iterators, bidirectional iterators, and random access iterators. The choice depends on the container's characteristics. For instance, containers supporting random access should use random access iterators to enable arithmetic operations and subscript access.

Template-Based Design to Avoid Code Duplication

To minimize code duplication, design iterators as template classes parameterized by pointer type, value type, or reference type to distinguish between regular and const iterators. Here's a basic template design:

template <typename PointerType>
class CustomIterator {
public:
    using value_type = typename std::remove_pointer<PointerType>::type;
    using pointer = PointerType;
    using reference = value_type&;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;
    
    CustomIterator(PointerType ptr) : current(ptr) {}
    
    reference operator*() const { return *current; }
    pointer operator->() const { return current; }
    
    CustomIterator& operator++() {
        ++current;
        return *this;
    }
    
    CustomIterator operator++(int) {
        CustomIterator temp = *this;
        ++current;
        return temp;
    }
    
    bool operator==(const CustomIterator& other) const {
        return current == other.current;
    }
    
    bool operator!=(const CustomIterator& other) const {
        return current != other.current;
    }
    
private:
    PointerType current;
};

// Type definitions
using iterator = CustomIterator<int*>;
using const_iterator = CustomIterator<const int*>;

Modern C++ Iterator Implementation

Since C++17, std::iterator has been deprecated, so modern implementations should directly define the required type aliases. Here's a complete random access iterator implementation:

template<typename T>
class RandomAccessIterator {
public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;
    
    RandomAccessIterator(pointer ptr = nullptr) : m_ptr(ptr) {}
    
    // Dereference operations
    reference operator*() const { return *m_ptr; }
    pointer operator->() const { return m_ptr; }
    
    // Arithmetic operations
    RandomAccessIterator& operator++() { ++m_ptr; return *this; }
    RandomAccessIterator operator++(int) { 
        RandomAccessIterator temp = *this; 
        ++m_ptr; 
        return temp; 
    }
    
    RandomAccessIterator& operator--() { --m_ptr; return *this; }
    RandomAccessIterator operator--(int) { 
        RandomAccessIterator temp = *this; 
        --m_ptr; 
        return temp; 
    }
    
    RandomAccessIterator& operator+=(difference_type n) { 
        m_ptr += n; 
        return *this; 
    }
    
    RandomAccessIterator& operator-=(difference_type n) { 
        m_ptr -= n; 
        return *this; 
    }
    
    RandomAccessIterator operator+(difference_type n) const {
        return RandomAccessIterator(m_ptr + n);
    }
    
    RandomAccessIterator operator-(difference_type n) const {
        return RandomAccessIterator(m_ptr - n);
    }
    
    difference_type operator-(const RandomAccessIterator& other) const {
        return m_ptr - other.m_ptr;
    }
    
    // Relational operations
    bool operator==(const RandomAccessIterator& other) const {
        return m_ptr == other.m_ptr;
    }
    
    bool operator!=(const RandomAccessIterator& other) const {
        return m_ptr != other.m_ptr;
    }
    
    bool operator<(const RandomAccessIterator& other) const {
        return m_ptr < other.m_ptr;
    }
    
    bool operator>(const RandomAccessIterator& other) const {
        return m_ptr > other.m_ptr;
    }
    
    // Subscript access
    reference operator[](difference_type n) const {
        return m_ptr[n];
    }
    
private:
    pointer m_ptr;
};

// Usage in container class
template<typename T>
class CustomContainer {
public:
    using iterator = RandomAccessIterator<T>;
    using const_iterator = RandomAccessIterator<const T>;
    
    iterator begin() { return iterator(data); }
    iterator end() { return iterator(data + size); }
    
    const_iterator begin() const { return const_iterator(data); }
    const_iterator end() const { return const_iterator(data + size); }
    
    const_iterator cbegin() const { return const_iterator(data); }
    const_iterator cend() const { return const_iterator(data + size); }
    
private:
    T* data;
    size_t size;
};

Implementation Considerations

When implementing iterators, several key points must be addressed: type aliases must be correctly defined to meet STL algorithm requirements; operator overloads should maintain consistent semantics; for const iterators, ensure elements cannot be modified through the iterator. Template parameterization elegantly handles differences between regular and const iterators while minimizing code duplication.

Reverse Iterator Implementation

For containers requiring reverse traversal, implement reverse iterators. Reverse iterators are typically implemented by inheriting from or composing forward iterators, but require overloading relevant operators to provide reverse semantics:

template<typename Iterator>
class ReverseIterator {
public:
    using iterator_type = Iterator;
    using iterator_category = typename Iterator::iterator_category;
    using value_type = typename Iterator::value_type;
    using difference_type = typename Iterator::difference_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
    
    ReverseIterator(Iterator it) : current(it) {}
    
    ReverseIterator& operator++() { 
        --current; 
        return *this; 
    }
    
    ReverseIterator operator++(int) { 
        ReverseIterator temp = *this; 
        --current; 
        return temp; 
    }
    
    ReverseIterator& operator--() { 
        ++current; 
        return *this; 
    }
    
    ReverseIterator operator--(int) { 
        ReverseIterator temp = *this; 
        ++current; 
        return temp; 
    }
    
    reference operator*() const { 
        Iterator temp = current;
        return *--temp;
    }
    
    pointer operator->() const {
        Iterator temp = current;
        --temp;
        return temp.operator->();
    }
    
    bool operator==(const ReverseIterator& other) const {
        return current == other.current;
    }
    
    bool operator!=(const ReverseIterator& other) const {
        return current != other.current;
    }
    
private:
    Iterator current;
};

Testing and Validation

After implementing iterators, thorough testing is essential to ensure correctness. Testing should include basic traversal, boundary conditions, and compatibility with STL algorithms. Write unit tests to verify the correctness of various iterator operators and methods, ensuring they meet the requirements of their respective iterator categories.