Is it possible to require for a certain time complexity in a concept

user_13112530 0
Viewed 41

Accordigly to cppreference named requirements a lot of algorithms requires to perform in certain time complexity (linear, constant). So i wonder is it possible with c++20 concepts to write a constraint for it, and if not is it even considered to be a good idea to be able to check for something like that?

template <class T>
concept linear = requires (T val) {
    // magic here
}
c++-concepts time-complexity c++
1 Answers

No, this is not possible.

In general, C++ abstract machine model does not have any concept of time or steps really.

No, the standard does not specify any time complexities, the only defined complexities are in terms of observable operations - comparisons and such. There is never any true time, step, or instruction complexity for any function in C++ and there cannot be.

The minimal requirements by the Standard on running a C++ program as set by intro.abstract:

  • Accesses through volatile glvalues are evaluated strictly according to the rules of the abstract machine.
  • At program termination, all data written into files shall be identical to one of the possible results that execution of the program according to the abstract semantics would have produced.
  • The input and output dynamics of interactive devices shall take place in such a fashion that prompting output is actually delivered before a program waits for input. What constitutes an interactive device is implementation-defined.

AKA as-if rule - if you cannot tell the difference, compiler can do anything it wants and time or number of executed instructions do not count as observable effects.

user_76917290
Related