Compile time function for array generating

[CakeByTheOcean]

A general but simple question. How could I generate a int array like from 1 to 100 in the Compile time?

[Ganado]

Yes, it's possible, but it isn't exactly simple.

std::generate will be constexpr in C++20, but that isn't a thing yet.
https://en.cppreference.com/w/cpp/algorithm/generate

Here's an example of an array-like structure being generated at compile-time

Borrowed from: https://stackoverflow.com/a/37447199/8690169

template <int I>
struct squared {
  squared<I - 1> rest;
  static const int x = I * I ;
  constexpr int operator[](int const &i) const { return (i == I ?  x : rest[i]); }
  constexpr int size() const { return I; }
};

template <>
struct squared<0> {
  static const int x = 0;
  constexpr int operator[](int const &i) const { return x; }
  constexpr int size() const { return 1; }
};

#include <iostream>

int main()
{
    squared<10> Squares;
    
    std::cout << Squares[5] << std::endl;
}

Change it just a bit to make it as you suggested:

template <int I>
struct sequence {
  sequence<I - 1> rest;
  static const int x = I + 1;
  constexpr int operator[](int const &i) const { return (i == I ?  x : rest[i]); }
  constexpr int size() const { return I; }
};

template <>
struct sequence<0> {
  static const int x = 1;
  constexpr int operator[](int const &i) const { return x; }
  constexpr int size() const { return 1; }
};

#include <iostream>

int main()
{
    sequence<10> elements;
    
    std::cout << elements[0] << " " << elements[5] << " " << elements[9] << std::endl;
}

Edit: Someone that knows C++14/17 better than me might be able to simplify this with constexpr.
Edit 2: As mbozzi just proved :D

[mbozzi]

#include <array>
#include <cstddef>
#include <iostream>

/* Compute std::array of size U - L filled with integers in the half-open
 * interval [L, U). */
template <std::size_t L, std::size_t U>
constexpr std::array<int, U - L> index_array() {
  std::array<int, U - L> result{};
  for (std::size_t i = L; i < U; ++i)
    result[i - L] = i;

  return result;
}

int main() {
  constexpr auto indices = index_array<1, 10 + 1>();
  for (auto const &i : indices)
    std::cout << i << ' ';
  std::cout << '\n';
}

If you really wanted generality, you could reach for a fully-featured metaprogramming library.

[Grime]

I don't get it.. Whether the computation is exclusively marked as to be done at compile time or whether the assigning is left to be done at run-time, what is the difference?

Both should do the same thing right? Both would produce assembly code that would say "allocate memory and put value so and so".

Computations can be done at compile-time but you can't allocate and assign values at compile time. So what is the difference between a for-loop and using templates and constexpr? Do they at all even produce different results?

Somebody pls enlighten me. 0_0

[mbozzi]

C++ has three major ways to write compile-time computations. Those are templates, constexpr objects and functions evaluated as part of a constant expression, and the C preprocessor. (Parts of) programs written using those techniques are called "meta-programs".

The best way (that I know of) to conceptualize metaprograms are as programs that write code for you.

While the problem that OP poses doesn't make a lot of sense by itself (I don't know what this is needed for), we might imagine there's a bunch of hand-written arrays scattered all around his codebase:

constexpr int a[5] = { 6, 7, 8, 9, 10 };
constexpr int b[10] = { -2, -1, 0, 1, 2, 3, 4, 5, 6, 7 };
constexpr int c[1] = { 42 };
// ...etc 

If we assume that those arrays are actually necessary, then we've found a good candidate for automation. Writing all those arrays out by hand, especially the ones with a few thousand elements, is tedious at best, and a source of errors at worst.

We can have the compiler write that code for us. Notice that the compiler optimizer generates the same code whether we hand-code the array or call the constexpr function above:
https://godbolt.org/z/KFifue

In general, we might reach for compile-time computation either to
a.) eliminate boilerplate, code duplication, and facilitate better error-checking; or, more rarely, to
b.) have the compiler do something that would otherwise happen at runtime.

If our compiler's optimizer was impossibly perfect, we'd never need to consider point b, because the compiler would emit optimal code without our help. In practice, the optimizer can only make the simplest transformations on its own, and needs human help for anything more complicated.

[Grime]

Thanks mbozzi

I thought the constexpr and templates would still be defined as usable functions if there was no run time call. That's cool though!

[mbozzi]

I thought the constexpr and templates would still be defined as usable functions if there was no run time call.

A template function won't generate any code if it is not instantiated. constexpr doesn't confer any such property.

[Grime]

Okay thanks mbozzi. So constexpr functions are always generated. And templates are too for that particular type.

Can you make compile time only functions? This could be useful for op's example for instance.

[mbozzi]

N.B.: I accidentally wrote "template function", but meant "template". (The right term is function template, as opposed to class template or variable template; the discussion about instantiation applies to all kinds of templates).

Roughly speaking, instantiation is the process the compiler performs to write a real function/variable/class from the instructions provided by a template. I might go into more detail, but I don't know how much you know.

What counts as instantiating for a [template]?

Most commonly, it's usage. For example, the first time I create an object of type std::vector<int>, the compiler will look into the standard library header <vector> and write the actual class std::vector<int> from the template definition.

This process is called implicit instantiation. It's also possible to tell the compiler to do this upon request. This is called explicit instantiation.

More information here:
https://en.cppreference.com/w/cpp/language/templates

So constexpr functions are always generated.

No, I didn't say that. (And what does "generated" mean? Emit machine code into the object file? That a symbol appears in the binary?)

With only a few exceptions, the C++ standard enables the compiler optimizer with the so-called as-if rule, which says the implementation can do anything to your program, as long as the observable behavior doesn't change.

A constexpr function might be called at run-time. In which case these optimizations might or might not be made.

[Grime]

So can you make a compile-time function that is sure not to appear in the binary? That would be useful for OP's purposes right..

[mbozzi]

I guess you edited your question while I was writing:

Can you make compile time only functions? / Can you make a compile-time function that is sure not to appear in the binary?

In some circumstances. The conventional practice is to lift data into types. We then proceed to write templates instead, which manipulate the types instead of data.

constexpr was designed explicitly to allow calls at run-time too.

C++20 offers consteval, which will solve the problem directly.

It is possible to workaround the issue currently using lots of magic - borrowing heavily from functional programming, but my experience is that these experiments tend to crash the compiler.