Constexpr Iterator in C++

Question

I am interested in creating a very minimal constexpr container for a personal project. The most important thing I need is a container with true constexpr iterators. They are going to be added to the standard eventually (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0858r0.html) but I would like to know how to implement them in current C++.

Let's say I had a data structure like this:

template <typename T, unsigned N>
struct array {
  const T data[N];

  template<typename... Args>
  constexpr array(const Args&... args) : data{args...} {
}
  struct array_iterator {
    T const* ptr;

    constexpr array_iterator(const T* ptr) : ptr(ptr) {}

    constexpr void operator++() { ++ptr; }
    constexpr void operator--() { --ptr; }
    constexpr T const& operator* () const { return *ptr; }
    constexpr bool operator==(const array_iterator& rhs) const { return *(*this) == *rhs; }
    constexpr bool operator!=(const array_iterator& rhs) const { return !(*this == rhs); }
  };

  constexpr array_iterator begin() const { return array_iterator(data); }
  constexpr array_iterator end()   const { return array_iterator(data + N); }
};

What I need is to be able to actually use the iterators in a constexpr context:

constexpr array<int, 3> arr(1, 2, 3);
constexpr auto it = arr.begin();

But obviously, since I am messing around with the non-constexpr ptr sub-object, I encounter errors like so:

iterator.cpp:46:18: error: constexpr variable 'it' must be initialized by a
      constant expression
  constexpr auto it = arr.begin();
                 ^    ~~~~~~~~~~~
iterator.cpp:46:18: note: pointer to subobject of 'arr' is not a constant
      expression
iterator.cpp:45:27: note: declared here
  constexpr array<int, 3> arr(1, 2, 3);
                          ^

So what would be a minimal constexpr iterator for a container like array?

You just need to make arr static: static constexpr array<int, 3> arr(1, 2, 3); — cpplearner
– cpplearner, Commented Oct 26, 2018 at 17:33
That does work in main! But you unfortunately cannot make a variable static if you are in a constexpr function, which is where I imagine this type of data structure would be most useful. — Sam G
– Sam G, Commented Oct 26, 2018 at 17:42

jfh · Accepted Answer · 2019-07-18 00:29:37Z

5

constexpr has a few meanings.

It can mean a value which can always be calculated at compile time. It can mean a function that, given compile time arguments, can generate output that can be calculated at compile time.

You have found that your iterators cannot refer to an automatic storage constexpr object. On the other hand, they can be invoked within a constexpr function.

template <typename T, unsigned N>
struct array {
  const T data[N];

  template<typename... Args>
  constexpr array(const Args&... args) : data{args...} {}

  struct array_iterator {
    T const* ptr;

    constexpr array_iterator(const T* ptr) : ptr(ptr) {}

    constexpr void operator++() { ++ptr; }
    constexpr void operator--() { --ptr; }
    constexpr T const& operator* () const { return *ptr; }
    constexpr bool operator==(const array_iterator& rhs) const { return ptr == rhs.ptr; }
    constexpr bool operator!=(const array_iterator& rhs) const { return !(*this == rhs); }
  };

  constexpr array_iterator begin() const { return array_iterator(data); }
  constexpr array_iterator end()   const { return array_iterator(data + N); }
};

constexpr int sum() {
    int retval = 0;
    constexpr array<int, 3> arr = {1,2,3};
    for (int x : arr)
        retval += x;
    return retval;
}

int main() {
    array<int, sum()> test;
    (void)test;
}

your operator== was broken but after fixing it we can call sum() in a constexpr context, which in turn uses iterators.

edited Jul 18, 2019 at 0:29

jfh

16313 bronze badges

answered Oct 26, 2018 at 17:49

Yakk - Adam Nevraumont

280k31 gold badges367 silver badges585 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sam G Over a year ago

Is there any way to create an iterator that can refer to an automatic storage constexpr object or is that something that would have to require runtime computation?

Yakk - Adam Nevraumont Over a year ago

@SamG Reference and pointers to objects of automatic storage duration are not constexpr. Consider; could you pass it to a template and use its identiy there? I mean, you could create iterators that contain a complete copy of the array they are iterating over, and measure identity based on identity of the array and position within it.

Collectives™ on Stack Overflow

Constexpr Iterator in C++

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related