CODEWITHSUNDEEP
c++templatesc++17template-meta-programmingconstexpr
Sam G
Sam G

Reputation: 229

Constexpr Iterator in C++

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?

Upvotes: 3

Views: 2910

Answers (1)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275310

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.

Upvotes: 5

Related Questions