c++ - List 在 C++ 中键入 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_pair s .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) 递归调用。在这里，我将大量工作委托(delegate)给了 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> . 您的字符串始终包含两个 char s。

字符串类和列表类都需要将它们的长度编码为它们的类型的一部分。 IE。你需要一个 list<char, 5>获取 5 个列表 char (因此包含 pair<char, pair<char, pair<char, pair<char, char>>>> )。否则，您将需要动态内存——这对于编译时常量代码来说是明确的。

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

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

nil (空列表)有一个成员函数模板，可以在前面添加一些东西。它只是声明 - 未定义 - 在这里打破循环依赖。

注意:这里是使用成员函数还是免费函数是个人品味/风格的问题。通常我会使用免费功能( prepend(mylist, element) )，但我想反射(reflect)您的预期用途( 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(的拷贝)作为第二个元素。我删除 const和 volatile因为否则有点头疼(尝试弄清楚为什么 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)};
 }

现在，回答你的问题:

How can I unpack this structurally? I want to be able to initialize this from a string literal like list<char> s{"hello world"}.

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

您已经有代码来获取字符串文字的长度(参数类型 CharT (&array)[N] )并使用该 N您可以构建具有足够嵌套的类型 cons保存您的 list :

 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带有元素和长度列表 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我们仍然需要构建列表的缺点计数。 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和 friend 可以类似地实现。您的 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', "");

注意 argument dependent lookup的美(ADL) ... 我可以说 fmap而不是 list::fmap .适用于通用代码。