C++20 Concepts – Why Non-ranged STL Algorithms Aren’t Constrained with Concepts in C++20

c++c++20std-ranges

Take std::sort and std::ranges::sort as examples, the iterator class in std::ranges::sort is constrained with the concept std::random_access_iterator:

template< std::random_access_iterator I, std::sentinel_for<I> S,
          class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
constexpr I
    sort( I first, S last, Comp comp = {}, Proj proj = {} );

But std::sort is not:

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

Why isn't std::sort (and all non-ranged algorithms) constrained?

Best Answer

It is "constrained", just not in the concept sense:

[algorithm.requirements]p(4.7)

If an algorithm's template parameter is named RandomAccessIterator, RandomAccessIterator1, or RandomAccessIterator2, the template argument shall meet the Cpp17RandomAccessIterator requirements ([random.access.iterators]) if it is required to be a mutable iterator, or model random_access_iterator ([iterator.concept.random.access]) otherwise.

This "shall" requirement could be tested with a static_assert in your C++ standard library (and has always been able to). It's just a quality-of-implementation issue if the standard library implementors look for stuff that isn't actually used.

This is different from a concept constrained parameter, where the function does not participate in overload resolution.

template<typename T>
concept is_std_sortable = requires(T t) { std::sort(t, t); };
template<typename T>
concept is_std_ranges_sortable = requires(T t) { std::ranges::sort(t, t); };

static_assert(is_std_sortable<int>);
static_assert(!is_std_ranges_sortable<int>);

You can see how this would be necessary with the multiple overloads (range or iterator pair) and default arguments to select the correct function when called.
It isn't necessary for the non-ranges algorithms, which only have a single overload. The ones that have multiple overloads take an execution policy as the first argument and the second overload is essentially concept constrained ([algorithms.parallel.overloads]p4)

Related Solutions

C++ STL – Why No Tree Containers?

There are two reasons you could want to use a tree:

You want to mirror the problem using a tree-like structure:
For this we have boost graph library

Or you want a container that has tree like access characteristics For this we have

std::map (and std::multimap)
std::set (and std::multiset)

Basically the characteristics of these two containers is such that they practically have to be implemented using trees (though this is not actually a requirement).

See also this question: C tree Implementation

Why Variable-Length Arrays Aren’t Part of the C++ Standard

(Background: I have some experience implementing C and C++ compilers.)

Variable-length arrays in C99 were basically a misstep. In order to support VLAs, C99 had to make the following concessions to common sense:

sizeof x is no longer always a compile-time constant; the compiler must sometimes generate code to evaluate a sizeof-expression at runtime.
Allowing two-dimensional VLAs (int A[x][y]) required a new syntax for declaring functions that take 2D VLAs as parameters: void foo(int n, int A[][*]).
Less importantly in the C++ world, but extremely important for C's target audience of embedded-systems programmers, declaring a VLA means chomping an arbitrarily large chunk of your stack. This is a guaranteed stack-overflow and crash. (Anytime you declare int A[n], you're implicitly asserting that you have 2GB of stack to spare. After all, if you know "n is definitely less than 1000 here", then you would just declare int A[1000]. Substituting the 32-bit integer n for 1000 is an admission that you have no idea what the behavior of your program ought to be.)

Okay, so let's move to talking about C++ now. In C++, we have the same strong distinction between "type system" and "value system" that C89 does… but we've really started to rely on it in ways that C has not. For example:

template<typename T> struct S { ... };
int A[n];
S<decltype(A)> s;  // equivalently, S<int[n]> s;

If n weren't a compile-time constant (i.e., if A were of variably modified type), then what on earth would be the type of S? Would S's type also be determined only at runtime?

What about this:

template<typename T> bool myfunc(T& t1, T& t2) { ... };
int A1[n1], A2[n2];
myfunc(A1, A2);

The compiler must generate code for some instantiation of myfunc. What should that code look like? How can we statically generate that code, if we don't know the type of A1 at compile time?

Worse, what if it turns out at runtime that n1 != n2, so that !std::is_same<decltype(A1), decltype(A2)>()? In that case, the call to myfunc shouldn't even compile, because template type deduction should fail! How could we possibly emulate that behavior at runtime?

Basically, C++ is moving in the direction of pushing more and more decisions into compile-time: template code generation, constexpr function evaluation, and so on. Meanwhile, C99 was busy pushing traditionally compile-time decisions (e.g. sizeof) into the runtime. With this in mind, does it really even make sense to expend any effort trying to integrate C99-style VLAs into C++?

As every other answerer has already pointed out, C++ provides lots of heap-allocation mechanisms (std::unique_ptr<int[]> A = new int[n]; or std::vector<int> A(n); being the obvious ones) when you really want to convey the idea "I have no idea how much RAM I might need." And C++ provides a nifty exception-handling model for dealing with the inevitable situation that the amount of RAM you need is greater than the amount of RAM you have. But hopefully this answer gives you a good idea of why C99-style VLAs were not a good fit for C++ — and not really even a good fit for C99. ;)

For more on the topic, see N3810 "Alternatives for Array Extensions", Bjarne Stroustrup's October 2013 paper on VLAs. Bjarne's POV is very different from mine; N3810 focuses more on finding a good C++ish syntax for the things, and on discouraging the use of raw arrays in C++, whereas I focused more on the implications for metaprogramming and the typesystem. I don't know if he considers the metaprogramming/typesystem implications solved, solvable, or merely uninteresting.

A good blog post that hits many of these same points is "Legitimate Use of Variable Length Arrays" (Chris Wellons, 2019-10-27).

Best Answer

Related Solutions

C++ STL – Why No Tree Containers?

Why Variable-Length Arrays Aren’t Part of the C++ Standard

Related Question