constexpr vector and string in C++20 and One Big Limitation

Table of Contents

constexpr started small in C++11 but then, with each Standard revision, improved considerably. In C++20, we can say that there’s a culmination point as you can even use std::vector and std::string in constant expressions!

Let’s look at use cases, required features to make it work, and finally, one significant limitation that we might want to solve in the future.

Sidenote: is my code run at constexpr?

Before we dive into fun stuff with vectors, it would be good to set some background.

In short: even if your function is marked with constexpr, it doesn’t mean it will always be executed at compile-time.

constexpr function can be both executed at compile-time and runtime.

For example:

constexpr int sum(unsigned int n) {
    return (n*(n+1))/2;
}

int main(int argc, const char**argv) {    
    int var = argc*4;
    int a = sum(var);              // runtime   
    
    static_assert(sum(10) == 55); // compile-time
    constexpr auto res = sum(11); // compile-time
    static_assert(res == 66); 
    int lookup[sum(4)] = { 0 };   // compile-time
}

See at Compiler Explorer

In the above example, the compiler has to evaluate sum() at compile-time only when it’s run in a constant expression. For our example, it means:

inside static_assert,
to perform the initialization of res, which is a constexpr variable,
to compute the size of the array, and the size must be a constant expression.

In a case of sum(var) the compiler might still perform some optimizations and if the compiler sees that the input parameters are constant then it might execute code at compile-time. (See this comment @Reddit).

Let’s now move to vectors and strings; what’s the deal behind them in C++20?

Building blocks for `std::vector` and `std::string`

Before C++20 you could do a lot with constexpr but there was no way to have a “dynamic” content. In most cases you could rely on std::array or somehow deduce the size of passed parameter:

template <size_t N>
constexpr int compute(int n) {
    std::array<int, N> stack;
    // some computations...
}
static_assert(compute<100>(10));

For example, above - in this “pseudo-code” - I had to pass a template argument to indicate the max size of a stack required to perform the computation. It would be much easier to work with std::vector and have a way to grow dynamically.

If we look at the proposal P0784R1 - Standard containers and constexpr the authors mentioned that at some point it would be great to write:

std::vector<std::metainfo> args = std::meta::get_template_args(reflexpr(T));

The code uses compile-time reflection capabilities, and the results are stored in a vector for further computation.

To have vectors and strings working in a constexpr context, the Committee had to enable the following features to be available at compile-time:

Destructors can now be constexpr,
Dynamic memory allocation/deallocation (see my separate blog post: [constexpr Dynamic Memory Allocation, C++20],(https://www.cppstories.com/2021/constexpr-new-cpp20/))
In-place construction using placement-new,
try-catch blocks - solved by P1002
some type traits like pointer_traits or char_traits.

And all of those improvements that we got so far between C++11 and C++17.

Additionally, in C++20, we have constexpr algorithms so that we can use them together (along with ranges versions).

Experiments

Let’s try something simple:

#include <vector>

constexpr bool testVector(int n) {
    std::vector<int> vec(n, 1);

    int sum = 0;

    for (auto& elem : vec)
        sum += elem;

    return n == sum;
}

int main() {
    static_assert(testVector(10));
}

Play at @Compiler Explorer

As you can see, the code looks like a regular function, but it’s executed solely at compile-time!

A corresponding C++17 version would be with std::array and explicit template argument that represents the size of the array:

#include <array>
#include <algorithm>

template <size_t N>
constexpr bool testArray() {
    std::array<int, N> arr;
    std::fill(begin(arr), end(arr), 1);

    size_t sum = 0;

    for (auto& elem : arr)
        sum += elem;

    return N == sum;
}

int main() {
    static_assert(testArray<10>());
}

Play @Compiler Explorer

Let’s try something with new:

#include <vector>

constexpr bool testVector(int n) {
    std::vector<int*> vec(n);

    int sum = 0;

    for (auto& i : vec)
        i = new int(n);
    
    for (const auto &i : vec)
        sum += *i;

    for (auto& i : vec)
        delete i;

    return n*n == sum;
}

int main() {
    static_assert(testVector(10));
}

Play at @Compiler Explorer

This time we allocated each element on the heap and performed the computation.

Vector of Custom objects

We can also put something more complicated than just an int:

#include <vector>
#include <numeric>
#include <algorithm>

struct Point {
    float x, y;

    constexpr Point& operator+=(const Point& a) noexcept {
        x += a.x;
        y += a.y;
        return *this;        
    }
};

constexpr bool testVector(int n) {
    std::vector<Point*> vec(n);

    for (auto& pt : vec) {
        pt = new Point;
        pt->x = 0.0f;
        pt->y = 1.0f;
    }

    Point sumPt { 0.0f, 0.0f};

    for (auto &pt : vec)
        sumPt += *pt;

    for (auto& pt : vec)
        delete pt;

    return static_cast<int>(sumPt.y) == n;
}

int main() {
    static_assert(testVector(10));
}

Play with code @Compiler Explorer

`constexpr` std::string

Strings work similarly to a vector inside constexpr functions. I could easily convert my routine for string split (explained in this article: Performance of std::string_view vs std::string from C++17) into a constexpr version:

#include <vector>
#include <string>
#include <algorithm>

constexpr std::vector<std::string> 
split(std::string_view strv, std::string_view delims = " ") {
    std::vector<std::string> output;
    size_t first = 0;

    while (first < strv.size()) {
        const auto second = strv.find_first_of(delims, first);

        if (first != second)
            output.emplace_back(strv.substr(first, second-first));

        if (second == std::string_view::npos)
            break;

        first = second + 1;
    }

    return output;
}

constexpr size_t numWords(std::string_view str) {
    const auto words = split(str);

    return words.size();
}

int main() {
    static_assert(numWords("hello world abc xyz") == 4);
}

Play at Compiler Explorer

While it’s best to rely on string_views and not create unnecessary string copies, the example above shows that you can even create pass vectors of strings inside a constexpr function!

Limitations

The main problem is that we cannot easily store the output in a constexpr string or vector. We cannot write:

constexpr std::vector vec = compute();

Because vectors and strings use dynamic memory allocations, and currently, compilers don’t support so-called “non-transient” memory allocations. That would mean that the memory is allocated at compile-time but then somehow “passed” into runtime and deallocated. For now, we can use memory allocations in one constexpr context, and all of them must be deallocated before we leave the context/function.

I wrote about that in a separate post: constexpr Dynamic Memory Allocation, C++20

As a use case, let’s try wring a code that takes a string literal and returns the longest word, uppercase:

constexpr auto str = "hello world abc programming";
constexpr auto word = longestWord(str); // how to make it compile...

int main() {
    static_assert(longestWordSize("hello world abc") == 5);
    static_assert(std::ranges::equal(word, "PROGRAMMING"));
}

The main problem here is that we have to:

set the max size for the word (like take the size of the input string)
or somehow run the computation twice and get the proper size

My solution is to run the computation twice:

constexpr std::vector<std::string_view>
splitSV(std::string_view strv, std::string_view delims = " ") { 
    /*skipped here, full version in online compiler link...*/ 
}

constexpr size_t longestWordSize(std::string_view str) {
    const auto words = splitSV(str);

    const auto res = std::ranges::max_element(words, 
        [](const auto& a, const auto& b) {
            return a.size() < b.size();
        }
    );

    return res->size();
}

constexpr char toupper(char ch) {
    if (ch >= 'a' && ch <= 'z')
        return ch - 32;
    return ch;
}

template <size_t N> 
constexpr std::array<char, N+1> longestWord(std::string_view str) {
    std::array<char, N+1> out { 0 };

    const auto words = splitSV(str);

    const auto res = std::ranges::max_element(words, 
        [](const auto& a, const auto& b) {
            return a.size() < b.size();
        }
    );

    std::ranges::transform(*res, begin(out), [](auto& ch) {
            return toupper(ch);
        }
    );
    return out;
}

constexpr auto str = "hello world abc programming";
constexpr auto word = longestWord<longestWordSize(str)>(str);

int main() {
    static_assert(longestWordSize("hello world abc") == 5);
    static_assert(std::ranges::equal(word, "PROGRAMMING"));
}

Play with code here @Compiler Explorer

Would you like to see more?
I wrote a constexpr string parser and it's available for C++ Stories Premium/Patreon members. See all Premium benefits here.

Summary

In this blog post, we run through a set of examples with std::vector and std::string in constexpr functions. I hope you see how powerful those techniques are, and you also understand limitations. The main issue is with dynamic memory allocation and that they cannot “leak” outside the constant expression. Still, there are ways to solve this problem.

Compiler Support: As of August 2021, this feature works only in one major compiler - MSVC, starting from Visual Studio 2019 16.10.

Back to you

how do you use constexpr functions?
do you have use cases for vectors and strings?

Let us know in the comments below the article.