Generic utility to create aribtrary tuples of integral_constants

Question

Making use of Scott Schurr's str_const I have a constexpr string.

class StrConst
{
public:
    template<size_t N>
    constexpr StrConst(const char (&str)[N])
        : str_(str)
        , len_(N - 1)
    {
        static_assert(N > 1, "not a string");
    }

    constexpr operator const char*() const
    {
        return str_;
    }

    constexpr size_t size() const
    {
        return len_;
    }

    constexpr char operator[] (size_t i) const
    {
        return i < len_ ? str_[i] : throw std::out_of_range("invalid index");
    }

private:
    const char* const str_;
    const size_t      len_;
};

I have another constexpr function which returns the position of the first caret found in a string, starting from position n:

constexpr int caretPos(const StrConst& str, size_t n = 0)
{
    if (n == str.size())
        return -1;

    if (str[n] == '^')
        return n;

    return caretPos(str, n+1);
}

I can use the results of caretPos to create a typedef for a std::tuple of std::integral_constants, where the size of the tuple is the number of carets found in the string, and each tuple element is an integral constant whose value is the position of the caret in the string.

Here I manually construct this tuple:

int main()
{
    constexpr StrConst s("hello^world^");

    constexpr int pos1 = caretPos(s);
    constexpr int pos2 = caretPos(s, pos1+1);

    using P1 = std::integral_constant<int, pos1>;
    using P2 = std::integral_constant<int, pos2>;

    using PosTuple = std::tuple<P1, P2>;

    static_assert(std::tuple_element_t<0, PosTuple>::value == 5, "");
    static_assert(std::tuple_element_t<1, PosTuple>::value == 11, "");
}

Question:

I would now like to generalise this for any input string with any number of carets.

template<size_t... Ns>
using PosTuple = std::tuple<std::integral_constant<int, Ns>...>;

How can I generate the sequence of Ns... required here using caretPos or some other means?

Working example

Catalan

Answer 1

Intriguing question.

Avoiding the use of StrConst, in the following example you can see a way to get a std::tuple<std::integral_constant<std::size_t, Pos1>, std::integral_constant<std::size_t, Pos2>, ...> type.

First of all, use arrayConverter() to convert a char const * in a std::array<char, N> (lc, in the following code); second: use tupleIndexGenerator<lc.size(), lc, '^'>::type to get the requested type.

So, if "hello^world^" is the string, from tupleIndexGenerator<lc.size(), lc, '^'>::type you get std::tuple<std::integral_constant<std::size_t, 5U>, std::integral_constant<std::size_t, 11U>>

The code

#include <iostream>
#include <array>
#include <tuple>

template <typename, typename>
struct typeConcat;

template <typename T0, template <typename ...> class C, typename ... Ts>
struct typeConcat<T0, C<Ts...>>
 { using type = C<T0, Ts...>; };

template <std::size_t N, std::array<char, N> const & A, char CH,
          std::size_t Pos = 0U, bool EQ = ((Pos < N) && (A.at(Pos) == CH))>
struct tupleIndexGenerator;

template <std::size_t N, std::array<char, N> const & A, char CH>
struct tupleIndexGenerator<N, A, CH, N, false>
 { using type = std::tuple<>; };

template <std::size_t N, std::array<char, N> const & A, char CH,
          std::size_t Pos>
struct tupleIndexGenerator<N, A, CH, Pos, false>
 { using type = typename tupleIndexGenerator<N, A, CH, Pos+1U>::type; };

template <std::size_t N, std::array<char, N> const & A, char CH,
          std::size_t Pos>
struct tupleIndexGenerator<N, A, CH, Pos, true>
 { using type = typename typeConcat<
      std::integral_constant<std::size_t, Pos>,
      typename tupleIndexGenerator<N, A, CH, Pos+1U>::type>::type; };

template <typename T, size_t N, size_t ... Is>
constexpr auto arrayConverter (T const (&arr)[N],
                               std::index_sequence<Is...> const &)
 { return std::array<T, N> { { arr[Is]... } }; }

template <typename T, size_t N>
constexpr auto arrayConverter (T const (&arr)[N])
 { return arrayConverter(arr, std::make_index_sequence<N>{}); }

constexpr auto lc = arrayConverter("hello^world^");

int main ()
 {
   static_assert(std::is_same<
                 typename tupleIndexGenerator<lc.size(), lc, '^'>::type,
                 std::tuple<std::integral_constant<std::size_t, 5U>,
                            std::integral_constant<std::size_t, 11U>>>::value,
                 "!");
 }

Coker

I'm getting an error: "‘lc’ is not a valid template argument for type ‘const std::array<bool, 13ul>&’ because object ‘lc’ has not external linkage". I'm using gcc-5.4.1. Do I need a more recent compiler? – Catalan

Ok, I tried it on godbolt - compiles fine on 6.1, not on 5.4 – Catalan

Thanks for this! I've updated the tags on the question to c++14 – Catalan

@SteveLorimer - I have the same "has not external linkage" with my g++ 4.9.2; usually I use clang++; en passant: I've developed a solution to generate a std::index_sequence with caret positions; I'm trying to semplify this solution but, if you really need the generation of the type std::tuple<std::integral_constant<int, value1>, std::integral_constant<int, value2>, ...>, well, I think I can do it. – Coker

I was looking for a tuple of int consts because I already have a tuple for another piece of the required code, and I need to operate on that tuple element by element. I don't know how to index into an integer_sequence – Catalan

@SteveLorimer - OK: I'll try to write the improved version to generate a tuple of integral constants – Coker

@SteveLorimer - answer rewritten and (I hope) improved; I give you a std::tuple of std::integral_constants of type std::size_t, not of type int as you requested, because I think (maybe I'm wrong) that index positions should be of an unsigned type (usually is used std::size_t). – Coker

Thanks for this, very neat! – Catalan

Answer 2

Here's an example using Boost.Hana (which advertises C++14). It results in a tuple of integral constants, which is directly what was asked for.

#include <cstddef>
#include <utility>

#include <boost/hana.hpp>

namespace hana = boost::hana;
using namespace boost::hana::literals;

template<typename Str, int... Is>
constexpr auto unfilteredCaretsImpl(Str str, std::integer_sequence<int, Is...>) {
    return hana::make_tuple(boost::hana::if_(str[hana::int_c<Is>] == hana::char_c<'^'>, hana::just(hana::int_c<Is>), hana::nothing)...);
}

template<typename Str>
constexpr auto unfilteredCarets(Str str) {
    return unfilteredCaretsImpl(str, std::make_integer_sequence<int, hana::length(str)>{});
}

template<typename Str>
constexpr auto allCarets(Str str) {
    auto unfiltered = unfilteredCarets(str);
    auto filtered = hana::filter(unfiltered, [](auto opt) { return opt != hana::nothing; });
    return hana::transform(filtered, [](auto opt) { return opt.value(); });
}

int main() {
    constexpr auto carets = allCarets(BOOST_HANA_STRING("hello^world^"));

    static_assert(hana::length(carets) == std::size_t{2});
    static_assert(carets[0_c] == 5);
    static_assert(carets[1_c] == 11);
}

Most of the work is getting around the fact that each value is a different type. Hana encodes the values as part of the type, which means it's possible to use a parameter in a constant expression. For example, a Hana string is of type String<'a', 'b', 'c'> for some artificial String. That means that when using a parameter to compare a character, that character is known as part of the type. This is different from Scott's string, which goes full on constexpr and cannot lift a parameter to a constant expression within the function.

Jacquie

Answer 3

Here's the best I can do with Scott's string:

#include <cstddef>
#include <stdexcept>

class StrConst
{
public:
    template<size_t N>
    constexpr StrConst(const char (&str)[N])
        : str_(str)
        , len_(N - 1)
    {
        static_assert(N > 1, "not a string");
    }

    constexpr operator const char*() const
    {
        return str_;
    }

    constexpr size_t size() const
    {
        return len_;
    }

    constexpr char operator[] (size_t i) const
    {
        return i < len_ ? str_[i] : throw std::out_of_range("invalid index");
    }

private:
    const char* const str_;
    const size_t      len_;
};

template<typename T, size_t MaxSize>
class VectorConst
{
public:
    constexpr VectorConst() = default;

    constexpr size_t size() const 
    {
        return _size; 
    }

    constexpr void push_back(const T& value) {
        _data[_size++] = value;
    }

    constexpr T& operator[](size_t i) 
    {
        return _data[i];
    }

    constexpr const T& operator[](size_t i) const
    {
        return _data[i];
    }

private:
    T _data[MaxSize]{};
    size_t _size = 0;
};

template<size_t Size>
constexpr auto allCarets(const StrConst& str) {
    VectorConst<size_t, Size> result;

    for (size_t i = 0; i < str.size(); ++i) {
        if (str[i] == '^') {
            result.push_back(i);
        }
    }

    return result;
}

int main() {
    constexpr StrConst s("hello^world^");
    constexpr auto carets = allCarets<s.size()>(s);

    static_assert(carets.size() == 2);
    static_assert(carets[0] == 5);
    static_assert(carets[1] == 11);
}

With ordinary constexpr and values not being encoded in types, we're a bit more limited. We simply can't form a tuple of integral constants because the string content in the parameter is unusable in constant expressions. Instead, I made a small constexpr vector that we can use just like a runtime one to push locations as we find them, but even then, we can't do any dynamic allocations at compile-time, so it has a max size that needs to be a template parameter. With C++11, you can possibly also write this recursively instead of iteratively, but I'm not sure how you'd implement push_back. You need to copy the array and change a value. As far as I know, you'd have to do it through an initializer list for the array and would essentially need a parameter pack of indices whose size is based on a variable that isn't a constant expression, which is possible (though I don't know about C++11), but really complicated.

Jacquie

Thanks for this! I've updated the question's tags to c++14. Additionally, for my particular use case it is possible to know the size of the vector at compile time. I didn't reflect this in the question, but there are also a number of variadic arguments, 1 per caret in the string, so we could use sizeof...(ts) as the vector capacity. With these changes in requirements in mind, is it possible to go from your VectorConst to std::tuple<std::integral_constant<int, Ns>...>? – Catalan

@SteveLorimer, If you have the positions encoded as part of a type or in the template parameters somewhere, then it's possible to convert them to the std::tuple you want. However, VectorConst was built specifically not to encode data in its type - that sort of thing is what Hana is really good for. So it's theoretically possible with the technique in the link at the end of the question, but that requires first going through all possible tuples (even the true/false approach in the other answer gives 2^strlength many) and picking the right one. – Jacquie