constexpr to concatenate two or more char strings

Question

I'm trying to make a constexpr function that will concatenate an arbitrary number of char arrays by working from the following answer by Xeo, which concatenates two char arrays.

https://stackoverflow.com/a/13294458/1128289

#include <array>

template<unsigned... Is> struct seq{};
template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<unsigned... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

template<unsigned N1, unsigned... I1, unsigned N2, unsigned... I2>
constexpr std::array<char const, N1+N2-1> concat(char const (&a1)[N1], char const (&a2)[N2], seq<I1...>, seq<I2...>){
  return {{ a1[I1]..., a2[I2]... }};
}

template<unsigned N1, unsigned N2>
constexpr std::array<char const, N1+N2-1> concat(char const (&a1)[N1], char const (&a2)[N2]){
  return concat(a1, a2, gen_seq<N1-1>{}, gen_seq<N2>{});
}

My attempt thus far:

#include <iostream>
#include <array>

template<unsigned... Is> struct seq{};
template<unsigned N, unsigned... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<unsigned... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

template<unsigned N1, unsigned... I1, unsigned N2, unsigned... I2>
constexpr const std::array<char, N1+N2-1>
concat_impl(
    const char (&a1)[N1], const char (&a2)[N2], seq<I1...>, seq<I2...>)
{
    return {{ a1[I1]..., a2[I2]... }};
}

template<unsigned N1, unsigned N2>
constexpr const std::array<char, N1+N2-1>
concat(const char (&a1)[N1], const char (&a2)[N2])
{
    return concat_impl(a1, a2, gen_seq<N1-1>{}, gen_seq<N2>{});
}

template<unsigned N1, unsigned N2, class... Us>
constexpr auto
concat(const char(&a1)[N1], const char(&a2)[N2], const Us&... xs)
-> std::array<char, N1 + decltype(concat(a2, xs...))::size() - 1>
{
    return concat(a1, concat(a2, xs...));
}

int main()
{
    auto const s = concat("hi ", "there!");
    std::cout << s.data() << std::endl;
    // compile error:
    auto const t = concat("hi ", "there ", "how ", "are ", "you?");
    std::cout << t.data() << std::endl;
}

Both gcc 4.9 and clang 3.5 give errors indicating that no function matching the concat inside the decltype expression can be found.

clang:

error: no matching function for call to 'concat'
    auto const t = concat("hi ", "there ", "how ", "are ", "you?");
                   ^~~~~~
ctconcat.cpp:105:16: note: candidate template ignored: substitution failure [with N1 = 4, N2 = 7, Us = <char [5], char [5], char [5]>]: no matching function for call to 'concat'
constexpr auto concat(const char(&a1)[N1], const char(&a2)[N2], const Us&... xs) -> std::array<char, N1 + decltype(concat(a2, xs...))::size() - 1>
               ^                                                                                                   ~~~~~~
ctconcat.cpp:62:43: note: candidate function template not viable: requires 2 arguments, but 5 were provided
constexpr const std::array<char, N1+N2-1> concat(const char (&a1)[N1], const char (&a2)[N2])
                                          ^
1 error generated.

The errors from gcc and clang both indicate that the second concat function template is not a candidate for the concat in the decltype expression. Only the first template is considered. Why is that and how do I fix this?

Edit: Relevant question on why decltype can't be used recursively

trailing return type using decltype with a variadic template function

Am I missing something but what's wrong with `"hi " "there!"` which will also concatenate the strings? — Neil Kirk, Feb 24 '15 at 23:38
As far as I can see, this is a basic name lookup problem: within the trailing-return-type, the function (template) has not been declared yet and hence is not found by pure unqualified lookup. ADL can find it, though. — dyp, Feb 24 '15 at 23:40
@dyp Ah, makes sense. ADL can find it? How? Wait, no... I'm confused again... the problem occurs upon instantiation, not declaration. — Praxeolitic, Feb 24 '15 at 23:42
@NeilKirk This is for when that's not an option. The strings will not be known until compile time (as opposed to authorship-time of the template). — Praxeolitic, Feb 24 '15 at 23:45
ADL won't find `concat` since that function template is *not* associated with the global namespace e.g. through the types of its function parameters or its template arguments. To look up names of functions in calls that depend on template parameters, ADL will also be performed from the point of instantiation, which is after the declaration is completed and the function template (its name) can be found. For example, try to add a template parameter that is filled with a class type that is declared in the global namespace. See e.g. http://stackoverflow.com/a/21815838 — dyp, Feb 25 '15 at 00:02

Yakk - Adam Nevraumont · Accepted Answer · 2015-02-25T02:26:40.930

template<size_t S>
using size=std::integral_constant<size_t, S>;

template<class T, size_t N>
constexpr size<N> length( T const(&)[N] ) { return {}; }
template<class T, size_t N>
constexpr size<N> length( std::array<T, N> const& ) { return {}; }

template<class T>
using length_t = decltype(length(std::declval<T>()));
constexpr size_t sum_string_sizes() { return 0; }
template<class...Ts>
constexpr size_t sum_string_sizes( size_t i, Ts... ts ) {
  return (i?i-1:0) + sum_sizes(ts...);
}

then

template
template<unsigned N1, unsigned N2, class... Us>
constexpr auto
concat(const char(&a1)[N1], const char(&a2)[N2], const Us&... xs)
-> std::array<char, sum_string_sizes( N1, N2, length_t<Us>::value... )+1 >
{
  return concat(a1, concat(a2, xs...));
}

which gets rid of the recursion-in-decltype.

Here is a full example using the above approach:

template<size_t S>
using size=std::integral_constant<size_t, S>;

template<class T, size_t N>
constexpr size<N> length( T const(&)[N] ) { return {}; }
template<class T, size_t N>
constexpr size<N> length( std::array<T, N> const& ) { return {}; }

template<class T>
using length_t = decltype(length(std::declval<T>()));

constexpr size_t string_size() { return 0; }
template<class...Ts>
constexpr size_t string_size( size_t i, Ts... ts ) {
  return (i?i-1:0) + string_size(ts...);
}
template<class...Ts>
using string_length=size< string_size( length_t<Ts>{}... )>;

template<class...Ts>
using combined_string = std::array<char, string_length<Ts...>{}+1>;

template<class Lhs, class Rhs, unsigned...I1, unsigned...I2>
constexpr const combined_string<Lhs,Rhs>
concat_impl( Lhs const& lhs, Rhs const& rhs, seq<I1...>, seq<I2...>)
{
  // the '\0' adds to symmetry:
  return {{ lhs[I1]..., rhs[I2]..., '\0' }};
}

template<class Lhs, class Rhs>
constexpr const combined_string<Lhs,Rhs>
concat(Lhs const& lhs, Rhs const& rhs)
{
  return concat_impl(
    lhs, rhs,
    gen_seq<string_length<Lhs>{}>{},
    gen_seq<string_length<Rhs>{}>{}
 );
}

template<class T0, class T1, class... Ts>
constexpr const combined_string<T0, T1, Ts...>
concat(T0 const&t0, T1 const&t1, Ts const&...ts)
{
  return concat(t0, concat(t1, ts...));
}

template<class T>
constexpr const combined_string<T>
concat(T const&t) {
  return concat(t, "");
}
constexpr const combined_string<>
concat() {
  return concat("");
}

live example

I have a follow up question on this, if you would be so kind! http://stackoverflow.com/questions/39199564/c-constexpr-c-string-concatenation-parameters-used-in-a-constexpr-context — Short, Aug 29 '16 at 06:12
The example doesn't compile for Visual Studio 2015. ........\src\tsd.nav.sdk.mapdisplay.rmw\app\rmw_test\test2.cpp(30): error C2059: Syntaxfehler: "..." (more following) Ideas? — user5024425, Oct 17 '16 at 09:48
@user MSVC has poor `decltype` support. I would try, on clsng/gcc, taking my code and moving the `length_t` `decltype` aliases and bubbling them up towards the plades they are used so `length` is used directly there in trailing return types. — Yakk - Adam Nevraumont, Oct 17 '16 at 11:08
`clang++` on **coliru** fails with long error list, rest of message `fatal error: too many errors emitted, stopping now [-ferror-limit=] 20 errors generated.` — kyb, Oct 31 '17 at 10:02
Can you please add comments to code to explain what every element do. — kyb, Oct 31 '17 at 10:05
@kyb C++1z on coliru needs a different standard library. Or just chang it to C++14 (or probably C++11) and the live example still compiles. I am uncertain what parts of my code confuse you. The code was aimed at someone who would write the OP's code and understand it, or read it and ponder why it isn't working. All I did was write a constexpr and template length calculator and modify the OP's solution to use it. — Yakk - Adam Nevraumont, Oct 31 '17 at 11:31

score 6 · Answer 2 · answered Dec 24 '20 at 15:55

With C++17 the solution becomes very simple (here's the live version):

#include <initializer_list>

// we cannot return a char array from a function, therefore we need a wrapper
template <unsigned N>
struct String {
  char c[N];
};

template<unsigned ...Len>
constexpr auto cat(const char (&...strings)[Len]) {
  constexpr unsigned N = (... + Len) - sizeof...(Len);
  String<N + 1> result = {};
  result.c[N] = '\0';

  char* dst = result.c;
  for (const char* src : {strings...}) {
    for (; *src != '\0'; src++, dst++) {
      *dst = *src;
    }
  }
  return result;
}

// can be used to build other constexpr functions
template<unsigned L>
constexpr auto makeCopyright(const char (&author)[L]) {
  return cat("\xC2\xA9 ", author);
}

constexpr char one[] = "The desert was the apotheosis of all deserts";
constexpr char two[] = "huge, standing to the sky";

constexpr auto three = cat(
  cat(one, ", ", two).c, // can concatenate recursively
  " ",
  "for what looked like eternity in all directions."); // can use in-place literals

constexpr auto phrase = cat(
  three.c, // can reuse existing cats
  "\n",
  makeCopyright("Stephen King").c);

#include <cstdio>
int main() {
  puts(phrase.c);
  return 0;
}

Hi. Why multilevel `cat` stops work if I change `String result = {};` to local `struct { char c[N]; } result = {};`? — magrif, May 03 '22 at 18:33

constexpr to concatenate two or more char strings

2 Answers2

Linked