C++ Custom iterator dereferencing as a value instead of a reference - Stack Overflow

admin 管理员组

文章数量: 1086019

I am trying to create some C++ types that behave as containers but generate values on the fly (for efficiency reasons).

Here is what I would ideally want (example with a container that generates zeros):

struct Zeros
{
    struct Iterator
    {
        using value_type        = int;
        using pointer           = const int*;
        using reference         = const int&;
        using difference_type   = int;
        using iterator_category = std::input_iterator_tag;

        int idx_;

        int operator*() const { return 0; }
    
        Iterator& operator++() { ++idx_; return *this; }
        Iterator  operator++(int) {
            Iterator res(*this); 
            ++(*this);
            return res;
        }
    
        bool operator==(const Iterator& other) const { return idx_ == other.idx_; }
        bool operator!=(const Iterator& other) const { return !(*this == other);  }
    };

    Iterator begin() const { return Iterator{0}; }
    Iterator end()   const { return Iterator{10}; }
};

The issue is that the iterator of this container dereferences as a value instead of a reference and I saw the standard requires that iterators dereference as a reference.

So I came up with this solution (returning a reference to an attribute. (that I find ugly, but strictly speaking does work and respects input iterator requirements.)

struct Zeros
{
    struct Iterator
    {
        ...

        int idx_;
        mutable int value_ = 0;

        const int& operator*() const { 
            return value_;
        }
    
        ...
    };

    Iterator begin() const { return Iterator{0};  }
    Iterator end()   const { return Iterator{10}; }
};

The thing that bothers me is that I feel the standard iterator requirements were designed with the idea that an iterator points to a memory that exists elsewhere so I have the intuition that I am tinkering with something that might explode in my face later.

Do you see any issue with the second design ? Do I fall in undefined behavior somewhere ?

I am trying to create some C++ types that behave as containers but generate values on the fly (for efficiency reasons).

Here is what I would ideally want (example with a container that generates zeros):

struct Zeros
{
    struct Iterator
    {
        using value_type        = int;
        using pointer           = const int*;
        using reference         = const int&;
        using difference_type   = int;
        using iterator_category = std::input_iterator_tag;

        int idx_;

        int operator*() const { return 0; }
    
        Iterator& operator++() { ++idx_; return *this; }
        Iterator  operator++(int) {
            Iterator res(*this); 
            ++(*this);
            return res;
        }
    
        bool operator==(const Iterator& other) const { return idx_ == other.idx_; }
        bool operator!=(const Iterator& other) const { return !(*this == other);  }
    };

    Iterator begin() const { return Iterator{0}; }
    Iterator end()   const { return Iterator{10}; }
};

The issue is that the iterator of this container dereferences as a value instead of a reference and I saw the standard requires that iterators dereference as a reference.

So I came up with this solution (returning a reference to an attribute. (that I find ugly, but strictly speaking does work and respects input iterator requirements.)

struct Zeros
{
    struct Iterator
    {
        ...

        int idx_;
        mutable int value_ = 0;

        const int& operator*() const { 
            return value_;
        }
    
        ...
    };

    Iterator begin() const { return Iterator{0};  }
    Iterator end()   const { return Iterator{10}; }
};

The thing that bothers me is that I feel the standard iterator requirements were designed with the idea that an iterator points to a memory that exists elsewhere so I have the intuition that I am tinkering with something that might explode in my face later.

Do you see any issue with the second design ? Do I fall in undefined behavior somewhere ?

• c++
• iterator
• undefined-behavior
• dereference

Share Improve this question Follow asked Mar 27 at 11:01 pnarvorpnarvor 15055 bronze badges 5

• 1 "I saw the standard requires that iterators dereference as a reference." but reference type might be a "proxy" and not a reference type, as std::vector<bool>... – Jarod42 Commented Mar 27 at 11:27
• You got me here. I took the reference word literally. It seems to be a good idea to return a proxy type. However, I read that std::vector<bool> was to be avoided because it did not comply with container requirements. Do you think using a proxy type here would lead to the same kind of issue ? – pnarvor Commented Mar 27 at 12:09
• 1 The core problem with std::vector<bool>::iterator is that it's the only vector iterator that's not a std::contiguous_iterator. – MSalters Commented Mar 27 at 12:12
• The std::vector<bool> specialization was a mistake. There should have been a separate std::vector_bool that does all the shenanigans. 20/20 hindsight. "Your programmers were so preoccupied with whether or not they could, they didn't stop to think if they should." – Eljay Commented Mar 27 at 12:31
• 1 What you are implementing is not a container, but a view. Checking the C++20 std::iota_view may help you implement your own view. – Weijun Zhou Commented Mar 27 at 13:20

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 2

What you're overlooking is that not all iterators are equal. Your iterator is a pretty limited one; it only supports the input and forward iterator concepts. The requirements you're assuming apply to more powerful iterator concepts.

You don't need to reinvent the wheel. Everything is already setup in <ranges> header:

#include <ranges>
auto zero_x10 = std::views::repeat(0,10);
auto ones_x20 = std::views::repeat(1)
              | std::views::take(20);

If you are bound to C++17, then range-v3 reference implementation is available too. If you need to count from a given number, std::views::iota serves the purpose. For the most part, you don't need to deal with custom ranges and iterators. You can simply compose them as functional elements in the std library. Iterator design is kind of low-level advanced stuff; you don't usually need to delve into that.

本文标签： C Custom iterator dereferencing as a value instead of a referenceStack Overflow