Why is non-const std::array::operator[] not constexpr?

Question

I'm trying to fill a 2D array on compile time with a given function. Here is my code:

template<int H, int W>
struct Table
{
  int data[H][W];
  //std::array<std::array<int, H>, W> data;  // This does not work

  constexpr Table() : data{}
  {
    for (int i = 0; i < H; ++i)
      for (int j = 0; j < W; ++j)
        data[i][j] = i * 10 + j;  // This does not work with std::array
  }
};

constexpr Table<3, 5> table;  // I have table.data properly populated at compile time

It works just fine, table.data is properly populated at compile time.

However, if I change plain 2D array int[H][W] with std::array<std::array<int, H>, W>, I have an error in the loop body:

error: call to non-constexpr function 'std::array<_Tp, _Nm>::value_type& std::array<_Tp, _Nm>::operator[](std::array<_Tp, _Nm>::size_type) [with _Tp = int; long unsigned int _Nm = 3ul; std::array<_Tp, _Nm>::reference = int&; std::array<_Tp, _Nm>::value_type = int; std::array<_Tp, _Nm>::size_type = long unsigned int]'
data[i][j] = i * 10 + j;
^
Compilation failed

Obviously, I'm trying to call non-const overload of std::array::operator[], which is not constexpr. The question is, why it is not constexpr? If C++14 allows us to modify variables declared in constexpr scope, why this is not supported by std::array?

I used to think that std::array is just like plain array, only better. But here is an example, where I can use plain array, but cannot use std::array.

Bushweller

Looks like an oversight in the standard. – Diluvium

Once you define constexpr conversion from C-style array to std::array using index std::integer_sequence idiom, it is really helpful for constexpr meta-programming in C++14. – Tonjatonjes

Related to constexpr std::array with static_assert – Hardpressed

Answer 1

Ok, it is indeed an oversight in the standard. There even exists a proposal to fix this: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0107r0.pdf

[N3598] removed the implicit marking of constexpr member functions as const. However, the member functions of std::array were not revisited after this change, leading to a surprising lack of support for constexpr in std::array’s interface. This paper fixes this omission by adding constexpr to the member functions of std::array that can support it with a minimal amount of work.

UPD: Fixed in C++17: https://en.cppreference.com/w/cpp/container/array/operator_at

Bushweller

Oops. (An "oversight in the standard" is one of the worst types of oversight. Ugh. Don't they spend days upon days verifying these things?) – Levant

@JeffY Well, C++ committee mostly consists of volunteers (though first class professionals), they have only several meetings a year (see isocpp.org/std/meetings-and-participation/upcoming-meetings). And they have to decide lots of things (e.g. see field report from Herb Sutter: herbsutter.com/2015/10/25/2568). After std::make_unique() not being a part of C++11, I am not surprized now :) – Bushweller

Answer 2

std::array::operator[] since C++14 is constexpr but is also const qualified:

constexpr const_reference operator[]( size_type pos ) const;
                                                      ^^^^^

Thus you have to cast the arrays to invoke the correct operator[] overload:

template<int H, int W>
struct Table
{
  //int data[H][W];
  std::array<std::array<int, H>, W> data;  // This does not work

  constexpr Table() : data{} {
    for (int i = 0; i < W; ++i)
      for (int j = 0; j < H; ++j)
        const_cast<int&>(static_cast<std::array<int, H> const&>(static_cast<std::array<std::array<int, H>, W> const&>(data)[i])[j]) = 10 + j;
  }
};

Live Demo

Edit:

As opposed by some people, use of const_cast in such a way does not imply undefined behaviour. In fact as proposed in the proposals for the relaxation of constexpr, it is required by the users to do this work around with const_cast in order to evoke the correct subscript operator overload at least until the issue is resolved in C++17 (see link).

Kandykane

Thank for the working example, even though it does not answer my question. Looks like a hack, don't you think? – Bushweller

@101010 I would give the benefit of doubt and say he meant "Is it UB, or is it not?" as opposed to "Can you explain it, or not?". – Netty

@Netty It's not UB, royalties for clarification given to Shafik Yaghmour. https://mcmap.net/q/453175/-filling-a-std-array-at-compile-time-and-possible-undefined-behaviour-with-const_cast – Kandykane

In fact, operations which would lead to UB are explicitly forbidden in constexpr context (i.e. a diagnostic is required, at least), so we can check this on multiple compilers, and if it compiles, it's not UB — unless all the checked compilers are broken. – Sherasherar

Answer 3

While my first thought was "why would you need a constexpr method on a non-const array"? ...

I then sat down and wrote a little test to see if the idea made sense:

#include <iostream>

using namespace std;
struct X{

    constexpr X()
    : _p { 0, 1, 2, 3, 4, 5, 6, 7, 9 }
    {
    }

    constexpr int& operator[](size_t i)
    {
        return _p[i];
    }

    int _p[10];
};

constexpr int foo()
{
    X x;
    x[3] = 4;
    return x[3];
}


auto main() -> int
{
    cout << foo() << endl;

    return 0;
}

It turns out that it does.

So I'm drawing the conclusion that the committee took the same "obvious" view that I did and discounted the idea.

Looks to me as if a proposal could be put forward to the committee to change it in c++17 - giving this question as an example.

Columbic

Makes sense. Can you suggest a person to contact to propose to make a proposal? :) PS didn't you mean return x[3]? – Bushweller

Oh, it already exists! See open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0107r0.pdf – Bushweller

@Bushweller I chose to return a different subscript just in case the optimiser decided that returning x[3] was a nop :) Whenever I'm writing these little tests in a single file I try to pre-empt the optimiser deciding that the entire program can be optimised away! – Columbic

Answer 4

This question intrigued me so much that I decided to figure out a solution that would allow the array to be initialised at compile time with a function that took x and y as parameters.

Presumably this could be adapted for any number of dimensions.

#include <iostream>
#include <utility>


// function object that turns x and y into some output value. this is the primary predicate
struct init_cell_xy
{
    constexpr init_cell_xy() = default;

    constexpr int operator()(int x, int y) const
    {
        return (1 + x) * (1 + y);
    }
};

// function object that applies y to a given x
template<int X = 1>
struct init_cell_for_x
{
    constexpr init_cell_for_x() = default;

    constexpr int operator()(int y) const
    {
        return _xy(X, y);
    }

private:
    init_cell_xy _xy;
};

// an array of dimension 1, initialised at compile time
template<int Extent>
struct array1
{
    template<class F, int...Is>
    constexpr array1(F&& f, std::integer_sequence<int, Is...>)
    : _values { f(Is)... }
    {}

    template<class F>
    constexpr array1(F&& f = init_cell_for_x<>())
    : array1(std::forward<F>(f), std::make_integer_sequence<int, Extent>())
    {}

    constexpr auto begin() const { return std::begin(_values); }
    constexpr auto end() const { return std::end(_values); }
    constexpr auto& operator[](size_t i) const {
        return _values[i];
    }

private:
    int _values[Extent];

    friend std::ostream& operator<<(std::ostream& os, const array1& s)
    {
        os << "[";
        auto sep = " ";
        for (const auto& i : s) {
            os << sep << i;
            sep = ", ";
        }
        return os << " ]";
    }
};

// an array of dimension 2 - initialised at compile time
template<int XExtent, int YExtent>
struct array2
{
    template<int...Is>
    constexpr array2(std::integer_sequence<int, Is...>)
    : _xs { array1<YExtent>(init_cell_for_x<Is>())... }
    {}

    constexpr array2()
    : array2(std::make_integer_sequence<int, XExtent>())
    {}

    constexpr auto begin() const { return std::begin(_xs); }
    constexpr auto end() const { return std::end(_xs); }
    constexpr auto& operator[](size_t i) const {
        return _xs[i];
    }

private:
    array1<YExtent> _xs[XExtent];

    friend std::ostream& operator<<(std::ostream& os, const array2& s)
    {
        os << "[";
        auto sep = " ";
        for (const auto& i : s) {
            os << sep << i;
            sep = ",\n  ";
        }
        return os << " ]";
    }

};




auto main() -> int
{
    using namespace std;

    constexpr array2<6,6> a;

    cout << a << endl;
    return 0;
}

Columbic