在C++中列出<Char>类型的constexpr字符串

Question

我试图cons-cell用C++中的函数式编程语言模拟列表结构constexpr.我有一种pair类型,一开始.这是两个不同的东西的持有者,但也支持嵌套对.这是代码.

template <typename E1, typename E2>
struct pair {

    constexpr pair() 
    :_car{E1{}}, _cdr{E2{}}
    {}

    constexpr pair(const E1 &car, const E2 &cdr)
    :_car{car}, _cdr{cdr}
    {}

    constexpr auto car() const{
        return _car;
    }

    constexpr auto cdr() const{
        return _cdr;
    }

    friend std::ostream& operator<<(std::ostream& str,
                                    pair<E1, E2> p){
        if(p == pair{})
            return str;
        str << p.car() << " " << p.cdr();
        return str;
    }

    template <typename Functor>
    friend constexpr auto fmap(Functor f,
                               const pair<E1, E2> p){
        if constexpr (std::is_fundamental<E1>::value &&
                      std::is_fundamental<E2>::value)
            return pair{f(p.car()), f(p.cdr())};
        else if(std::is_fundamental<E1>::value &&
                !std::is_fundamental<E2>::value)
        return pair{f(p.car()), fmap(f, p.cdr())};
    }

    const E1 _car;
    const E2 _cdr;
};

template <typename E1, typename E2>
constexpr bool operator==(const pair<E1, E2>& p1, const pair<E1, E2>& p2)
{
    return (p1.car() == p2.car()) && (p1.cdr() == p2.cdr());
}

作为这种类型的包装,我有一个nested_pair类型.这使我更容易使用nested_pairs .aka列表.实际列表只是这个包装器的一个typedef.这是代码.

template <typename Head, typename Tail>
class nested_pair{
    public:

    constexpr nested_pair():p{}
    {}

    constexpr nested_pair(Head h, Tail t)
    :p{h, t}
    {}

    constexpr auto prepend(Head h) const{ 
        return nested_pair<Head, decltype(p)>{h, p};
    }

    constexpr auto head() const {
        return p.car();
    }

    constexpr auto tail() const {
        return nested_pair<decltype(p.cdr().car()),
                    decltype(p.cdr().cdr())>
                    {p.cdr().car(),
                     p.cdr().cdr()
                    };
    }

    constexpr bool is_empty() const {
        return p == pair<decltype(p.car()),
                         decltype(p.cdr())>
                         {};
    }

    template <typename Functor>
    friend constexpr auto fmap(Functor f, const nested_pair l) {
        const auto res = fmap(f, l.p);
        return nested_pair{res.car(), res.cdr()};
    }

    friend std::ostream& operator<<(std::ostream& str,
                                    nested_pair<Head, Tail> l){
        str << l.p;
        str << "\n";
        return str;
    }

    private:
    const pair<Head, Tail> p;
};

我nested_pair唯一允许prepend,因为如果你将列表存储为一对头尾,则append需要O(n)递归调用.在这里,我委托了很多工作的pair,并nested_pair包含着一个构造函数pair.我相信这些工作很好.我使用以下变量模板将列表定义为嵌套对.

template <typename T>
using list = nested_pair<T, T>;

现在,问题的本质,我想用它list来制作一个string类型,如list<char>.这应该是所有constexpr,我们可以做到这一点.我有另一个版本const char []来构建constexpr字符串,但现在我想使用结构递归.这是我失败的尝试.

class lstring{
    public:

    template <std::size_t N>
    constexpr lstring(const char(&cont)[N]) :size{N} {
        size_t ind = N - 1;
        while(ind >= 0){
            content = content.prepend(cont[ind]);
            ind--;
        }
    }

    private:
    const size_t size;
    const list<char> content;
};

当然这不起作用.constexpr构造函数经历了一个while循环并违反了constexpr的规则,我相信我们不能在constexpr函数中循环.这也不利用列表的递归结构.如何以这种方式构造字符串？我应该使用一个变量模板char... args吗？我怎样才能在结构上拆开它？我希望能够从字符串文字中初始化它list<char> s{"hello world"}.

Answer 1

你有一个概念问题：

你lstring包含一个list<char>，它实际上是一个，nested_pair<char, char>而它又包含一个pair<char, char>。你的字符串总是包含两个chars。

字符串类和列表类都需要将其长度编码为类型的一部分。即，您需要 alist<char, 5>来表示 5 个列表char（因此包含 a pair<char, pair<char, pair<char, pair<char, char>>>>）。否则，您将需要动态内存——这对于编译时常量代码来说显然是不行的。

现在，进行演示。我希望它能给您一些关于如何实施某些事情的想法。这对我来说也很有趣；）与您的设计选择相反，我使用一个特殊的哨兵值 -nil来标记列表的结尾。以下所有代码都在 a 中namespace list：

 struct nil {
  template<typename U>
  constexpr auto prepend(U && u) const;
 };

nil（空列表）有一个成员函数模板可以在前面添加一些东西。此处仅声明（未定义）以打破循环依赖。

注意：这里是否使用成员函数或免费函数取决于个人品味/风格。通常我会使用自由函数 ( prepend(mylist, element))，但我想反映您的预期用法 ( mylist.prepend(element))。

接下来是最重要的结构——“对”——构建列表的基础。以 Lisp 的 cons 单元命名：

 namespace implementation {
  template<typename T>
  using no_ref_cv = std::remove_cv_t<std::remove_reference_t<T>>;
 }

 template<typename Car, typename Cdr>
 struct cons {
  Car car;
  Cdr cdr;

  template<typename U>
  constexpr auto prepend(U && u) const {
   using implementation::no_ref_cv;
   return cons<no_ref_cv<U>, cons<Car, Cdr>>{std::forward<U>(u), *this};
  }
 };

这只是简单的一对。prepend创建一个新的 cons，其中新元素作为其第一个元素，当前 cons（的副本）作为第二个元素。我删除了constandvolatile因为它有点令人头疼（尝试找出为什么cons<char, cons<char, cons<const char, cons<char, nil>>>>不会转换为cons<char, cons<const char, cons<char, cons<char, nil>>>>）

也就是说，实现nil::prepend基本上是相同的：

 template<typename U>
  constexpr auto nil::prepend(U && u) const {
   using implementation::no_ref_cv;
   return cons<no_ref_cv<U>, nil>{std::forward<U>(u), *this};
  }

我也喜欢用自由函数来“制作”东西，所以：

 template<typename Car, typename Cdr>
 constexpr auto make_cons(Car && car, Cdr && cdr) {
  using implementation::no_ref_cv;
  return cons<no_ref_cv<Car>, no_ref_cv<Cdr>>{
    std::forward<Car>(car), std::forward<Cdr>(cdr)};
 }

现在，回答您的问题：

我怎样才能从结构上解开它？我希望能够从字符串文字（如list<char> s{"hello world"}.

list<char>这是不可能的（记住——你也需要那里的长度！）。但auto s = list::make_list("hello world")。

您已经有代码来获取字符串文字（参数 type CharT (&array)[N]）的长度，并且N可以使用它构建一个具有足够嵌套cons来保存列表的类型：

 namespace implementation {
  template<typename T, std::size_t N>
  struct build_homo_cons_chain {
   using type = cons<T, typename build_homo_cons_chain<T, N - 1u>::type>;
  };

  template<typename T>
  struct build_homo_cons_chain<T, 0u> {
   using type = nil;
  };
 }

N == 0只是一个nil（空列表），其他所有内容都是cons带有元素和 length 的列表N - 1。这允许您为列表定义正确的类型，您可以使用它来默认初始化它的实例，然后循环遍历成员car以填充它。像这样的东西：

using list_t = typename implementation::build_homo_cons_chain<char, N>::type;
list_t my_new_list;
// fill my_new_list.car, my_new_list.cdr.car, ... probably with recursion

这种方法的问题是您要求列表的元素类型既可默认构造又可分配。对于 来说不是问题char，但这些都是严格的要求，因此我们最好从数组（字符串文字）中提供的元素复制/移动构造列表的元素：

 namespace implementation {
  template<std::size_t O, std::size_t C>
  struct offset_homo_builder {
   template<typename T, std::size_t N>
   constexpr auto from( T (&array)[N]) {
    return offset_homo_builder<O - 1u, C - 1u>{}.from(array).prepend(array[N - O]);
   }
  };
  template<std::size_t O>
  struct offset_homo_builder<O, 0u> {
   template<typename T, std::size_t N>
   constexpr auto from( T (&array)[N]) {
    return nil{};
   }
  };
 }

O是相对于数组末尾C的偏移量，我们仍然需要构建列表的 cons 计数。成员from函数模板采用一个长度数组N，并将数组中的元素添加N - O到它递归构建的（较短的）列表中。

例子：implementation::offset_homo_builder<3,2>::from("ab")

offset_homo_builder<3,2>::from("ab") --> N = 3, O = 3, C = 2
: cons{'b', nil}.prepend('a') => cons{'a', cons{'b', nil}}
  ^
  |--- offset_homo_builder<2, 1>::from("ab") --> N = 3, O = 2, C = 1
       : nil.prepend('b') => cons{'b', nil}
         ^
         |--- offset_homo_builder<1, 0>::from("ab") --> N = 3, O = 1, C = 0 (!specialisation!)
              : nil

计数C对于省略'\0'字符串文字末尾的 很重要。现在您可以创建一个包含数组所有元素的列表：

 template<typename T, std::size_t N>
 constexpr auto make_homogenous(T (&array)[N]) {
  return implementation::offset_homo_builder<N, N>{}.from(array);
 }

或者构建一个省略最后一个元素的字符串：

 template<std::size_t N, typename CharT, typename = typename std::char_traits<CharT>::char_type>
 constexpr auto make_string(CharT (& array)[N]) {
  static_assert(N > 0, "assuming zero terminated char array!");
  return implementation::offset_homo_builder<N, N - 1>{}.from(array);
 }

最后，要使用此列表，您不需要查看元素的类型。只需停在nil：

 template<typename F, typename Car, typename Cdr>
 constexpr auto fmap(F functor, cons<Car,Cdr> const & cell) {
  return make_cons(functor(cell.car), fmap(functor, cell.cdr));
 }
 template<typename F>
 constexpr auto fmap(F functor, nil const &) {
  return nil{};
 }

foldl，foldr朋友们也可以类似的实现。您operator<<可以使用 来实现foldl。

结束了namespace list。

另外，检查我们是否仍然constexpr：

constexpr char inc(char c) {
 return c + 1;
}

static_assert(fmap(inc, list::make_string("ab").prepend('x')).car == 'y', "");

请注意参数相关查找(ADL)的美妙之处...我可以说fmap而不是list::fmap. 适合通用代码。