如何在编译时捕获递归函数的结果？ [英] How do I capture the results of a recursive function at compile-time?
问题描述
#include< iostream>
模板< typename T>
结构节点{
T值；
node const *上一页;
constexpr节点（常量T&值，节点const * prev = nullptr）
：值{value}，prev {prev} {}
constexpr节点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;
}否则{
std :: cout<< ，;
}
std :: cout<< i->值;
}
}
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）：结果；
}
constexpr base_case（const unsigned int i）{
Something result（i％10）;
auto j = i / 10;
return j！= 0？ recursive_case（result，j）：结果；
}
int main（）{print（base_case（21））; }
我有一个类似于上面所示的递归函数（ base_case 和 recursive_case ）。我从以下链接获得了 node 对象的想法： https://gist.github.com/dabrahams/1457531#file-constexpr_demo-cpp-L66 ，并且我对其进行了修改以满足自己的需求。我上面的问题是我遇到了细分错误。
谢谢。
修改：
-
很抱歉，您未尝试过调试器。输出为：
$ lldb ./ww〜/ scratch / ww
（lldb）target create。 / ww
当前可执行文件设置为'./ww'（x86_64）。
（lldb）运行
启动过程32909：'./ww'（x86_64）
过程32909已停止
*线程＃1：tid = 0x4d4e8e，0x000000010000109b ww`print（s = 0x00007fff5fbfec80）+ 91 at ww.cpp：32，队列='com.apple.main-thread'，停止原因= EXC_BAD_ACCESS（code = EXC_I386_GPFLT）
frame＃0：0x000000010000109b ww`print（s = 0x00007fff5fbfec80） + 91 at ww.cpp：32
29}否则{
30 std :: cout<< ，;
31}
-> 32 std :: cout<< i->值;
33}
34}
35
（lldb）
我将尝试使用
new或智能指针，但是据我所读，它们不能在constexpr 函数。 -
我尝试同时使用
new和智能指针。
-
对于
新，我会收到此错误：ww.cpp：19：15：错误：constexpr构造函数从不生成常量表达式[-Winvalid-constexpr]
constexpr Something（const int i）： n {新节点< int>（i）} {}
^
ww.cpp：19：42：注意：子表达式在常量表达式中无效
constexpr Something（const int i） ：n {新节点< int>（i）} {}
^
-
对于
unique_ptr，我收到此错误：ww.cpp： 26:11：注意：非constexpr构造函数'unique_ptr'不能在常量表达式
中使用：n {std :: unique_ptr< node< int> ;, deleter< node< int>>>（新节点< int< int（i））} {}
-
-
我仔细研究了一下，认为可以使用C ++模板解决此问题。我只需要一种方法来捕获递归的中间结果，例如某种编译时列表，然后颠倒顺序。
这是一个有趣的问题，但是正如Joachim Pileborg在评论中说的那样，在调试器中执行该程序将为您提供崩溃的原因。
首先进行诊断：
- 按
print函数时，一切正常：s包含一个具有前一个节点的节点，仅此而已（s.prev-> prev == nullptr） -
std :: cout<<之后i-> value;坏了：s.prev-> prev！= nullptr当指令不应该改变它的时候！
由于在调用函数时中断，闻起来好像在周围有悬空的指针或引用。
现在说明：
在您的递归调用中，所有内容（某事和 node 都作为局部变量分配，并传递给递归调用作为引用。当调用时，一切都很好，一切都分配在调用者函数中，但是当您返回时，只有某事及其节点是正确的：以下所有节点在现在结束的函数中均被分配为局部变量，并且（ result 返回值） result.prev 是一个悬空指针。
使用悬空指针是未定义的行为，并且可能会出现SIGSEGV。
TL / DR：您正在将链接列表的节点分配为loca l递归调用中的变量以指针悬空结束，因此未定义的行为有望立即导致崩溃。
注意：未定义的行为可以在所有测试中起作用，并在以后破坏生产
可能的解决方法：由于类不能包含其自身的实例，因此不能在链接列表中使用按值返回，而必须使用动态分配。因此，您必须实现显式析构函数或使用智能指针。
以上主要是崩溃的解释。可以使用智能指针进行修复，但 constexpr 不能再使用。如果以这种方式修改结构节点：
template< typename T> ;
结构节点{
T值；
std :: shared_ptr< node const>上一个
node（const T& value，node const * prev = nullptr）
：value {value} {
this-> prev =（prev == nullptr）
？ std :: shared_ptr<结构节点const>（nullptr）
：std :: make_shared< struct节点const>（* prev）;
}
节点push_front（const T& value）const {
return node（value，this）;
}
};
可以安全地通过副本返回，因为 shared_ptr 确保您永远不会得到悬空的指针。但是，确实构造函数不再是 constexpr 的了，所以只有 print 仍然是一个...
但这很有道理。由于 recursive_case 回溯地构建了一个链表，所以我无法想象一种使之成为constexpr的方法。可能有可能通过首先分配一个 node s数组（因为这里每个数字需要一个 node ）和然后链接那些现有的节点。但是，如果在递归函数中将它们作为局部变量进行分配，则您将无法避免这种悬而未决的问题，并且如果它们是动态分配的，则它不能是 constexpr
#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)); }
I have a recursive function like the one shown above (base_case and recursive_case). I got the idea for the node object from this link: https://gist.github.com/dabrahams/1457531#file-constexpr_demo-cpp-L66, and I modified it to suit my needs. The problem with what I have above is that I am getting a segmentation fault.
Thanks.
Edit(s):
Sorry for not trying a debugger earlier. Here is the output:
$ 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)I will try to use
newor smart pointers, but from what I have read, they cannot be used inconstexprfunctions.I tried using using both
newand smart pointers.For
new, I get this error: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)} {} ^For
unique_ptr, I get this error: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))} {}
I looked into it some more, and I think it is possible to solve this problem using C++ templates. I just need a way to capture the intermediate results of the recursion e.g. some kind of compile-time list and then reverse the order.
It is an interesting question, but as Joachim Pileborg said in comment, executing the program in a debugger would have given you the why of the crash.
First the diagnostic:
- all is fine when hitting
printfunction:scontains a node with a previous node and that's all (s.prev->prev == nullptr) - after the
std::cout << i->value;it's broken:s.prev->prev != nullptrwhen the instruction should not have changed that!
As it breaks when calling a function, it smells like there's a dangling pointer or reference around...
Now the explaination:
In your recursive calls, everything (the Something and the nodes are all allocated as local variables and passed to recursive calls as reference. When calling down, all is fine, everything is allocated in a caller function. But when you return, only the Something and its node are corrects: all following nodes were allocated as local variables in now ended function and (calling result the return value) result.prev is a dangling pointer.
Using a dangling pointer is undefined behaviour and a SIGSEGV is possible.
TL/DR: you are allocating nodes of a linked list as local variables in recursive calls and end with dangling pointers so the undefined behaviour that hopefully caused a crash immediately.
BEWARE: undefined behaviour could work in all your tests and break later in production
Possible fix: as a class cannot contain an instance of itself, you cannot use return by value in a linked list and must use dynamic allocation. So you must implement explicit destructors or use smart pointers.
Above was mainly the explaination for the crash. It can be fixed by using smart pointers but constexpr can no longer be used. If struct node is modified that way:
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);
}
};
It can be safely returned by copy, because the shared_ptr ensures that you will never get a dangling pointer. But it is true that the constructor can no longer be a constexpr, so only print remains one...
But it makes sense. As recursive_case recusively builds a linked list, I cannot imagine a way to make that a constexpr. It might be possible by first allocating an array of nodes (since you will need a node per digit here) and then linking those existing nodes. But if they are allocated as local variables in a recursive function you will not be able to avoid the dangling problem, and if they are dynamically allocated, it cannot be a constexpr
这篇关于如何在编译时捕获递归函数的结果？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
