templates - 如何在编译时捕获递归函数的结果？

Question

#include <iostream>

template <typename T>
struct node {
    T value;
    node const* prev;

    constexpr node(const T& value, node const* prev = nullptr)
        : value{value}, prev{prev} {}

    constexpr node push_front(const T& value) const {
        return node(value, this);
    }
};

struct Something {
    node<int> n;

    constexpr Something(const int i) : n{node<int>(i)} {}

    constexpr Something(const node<int>& n) : n{n} {}
};

constexpr void print(const Something& s) {
    bool first = true;
    for (const node<int>* i = &s.n; i != nullptr; i = i->prev) {
        if (first) {
            first = false;
        } else {
            std::cout << ", ";
        }
        std::cout << i->value;
    }
}

constexpr Something recursive_case(Something& s, const unsigned int i) {
    Something result(s.n.push_front(i % 10));
    auto j = i / 10;
    return j != 0 ? recursive_case(result, j) : result;
}

constexpr Something base_case(const unsigned int i) {
    Something result(i % 10);
    auto j = i / 10;
    return j != 0 ? recursive_case(result, j) : result;
}

int main() { print(base_case(21)); }

我有一个如上所示的递归函数(base_case 和 recursive_case)。我从这个链接得到了 node 对象的想法:https://gist.github.com/dabrahams/1457531#file-constexpr_demo-cpp-L66 , 我对其进行了修改以满足我的需要。我上面遇到的问题是我遇到了段错误。

谢谢。

编辑:

1. 很抱歉没有早点尝试调试器。这是输出:

       $ lldb ./ww                                                                                              ~/scratch/ww
   (lldb) target create "./ww"
   Current executable set to './ww' (x86_64).
   (lldb) run
   Process 32909 launched: './ww' (x86_64)
   Process 32909 stopped
   * thread #1: tid = 0x4d4e8e, 0x000000010000109b ww`print(s=0x00007fff5fbfec80) + 91 at ww.cpp:32, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
       frame #0: 0x000000010000109b ww`print(s=0x00007fff5fbfec80) + 91 at ww.cpp:32
      29           } else {
      30               std::cout << ", ";
      31           }
   -> 32           std::cout << i->value;
      33       }
      34   }
      35
   (lldb)
   

   我会尝试使用 new 或智能指针，但据我所知，它们不能用于 constexpr 函数。

2. 我尝试同时使用 new 和智能指针。

   • 对于 new，我得到这个错误:

         ww.cpp:19:15: error: constexpr constructor never produces a constant expression [-Winvalid-constexpr]
             constexpr Something(const int i) : n{new node<int>(i)} {}
                       ^
         ww.cpp:19:42: note: subexpression not valid in a constant expression
             constexpr Something(const int i) : n{new node<int>(i)} {}
                                                  ^
     

   • 对于 unique_ptr，我得到这个错误:

         ww.cpp:26:11: note: non-constexpr constructor 'unique_ptr' cannot be used in a constant expression
         : n{std::unique_ptr<node<int>, deleter<node<int>>>(new node<int>(i))} {}
     

3. 我进一步研究了它，我认为使用 C++ 模板可以解决这个问题。我只需要一种方法来捕获递归的中间结果，例如某种编译时列表，然后颠倒顺序。

Answer 1

这是一个有趣的问题，但正如 Joachim Pileborg 在评论中所说，在调试器中执行程序会告诉您崩溃的原因。

首先是诊断:

• 点击print时一切正常功能:s包含一个带有前一个节点的节点，仅此而已 ( s.prev->prev == nullptr )
• 在std::cout << i->value;之后它坏了:s.prev->prev != nullptr当指令不应该改变它时!

当它在调用一个函数时中断，它闻起来像周围有一个悬垂的指针或引用......

现在解释:

在你的递归调用中，一切(Something 和 node s 都被分配为局部变量并作为引用传递给递归调用。当向下调用时，一切都很好，一切都在调用函数中分配。但是当你返回时，只有 Something 和它的 node 是正确的:所有后续节点在现在结束的函数中被分配为局部变量并且(调用 result 返回值)result.prev 是一个悬空指针。

使用悬空指针是未定义的行为，SIGSEGV 是可能的。

TL/DR:您在递归调用中将链表的节点分配为局部变量，并以悬空指针结束，因此未定义的行为有望立即导致崩溃。

注意:未定义的行为可能会在您的所有测试中起作用，但稍后会在生产中中断

可能的解决方法:由于类不能包含其自身的实例，因此您不能在链表中使用按值返回，而必须使用动态分配。因此，您必须实现显式析构函数或使用智能指针。

以上主要是对崩溃的解释。它可以通过使用智能指针来修复，但是 constexpr无法再使用。如果struct node是这样修改的:

template <typename T>
struct node {
    T value;
    std::shared_ptr<node const> prev;

    node(const T& value, node const* prev = nullptr)
        : value{value} {
    this->prev = (prev == nullptr)
        ? std::shared_ptr<struct node const>(nullptr)
        : std::make_shared<struct node const>(*prev);
    }

    node push_front(const T& value) const {
        return node(value, this);
    }
};

它可以通过副本安全返回，因为shared_ptr确保您永远不会得到悬空指针。但是构造函数确实不能再是constexpr了。 , 所以只有 print仍然是一个...

但这是有道理的。作为recursive_case递归地构建一个链表，我无法想象有一种方法可以使它成为一个 constexpr。首先分配一个 node 的数组可能是可能的s(因为这里每个数字都需要 node)，然后链接那些现有节点。但是如果它们在递归函数中被分配为局部变量，您将无法避免悬挂问题，如果它们是动态分配的，它就不可能是 constexpr。