如何在std::list中使用递归？

Question

我在执行这段代码时遇到问题。此代码的第一个基本条件（用于在字符串列表中搜索字符串）不起作用。谢谢

int string_check(list<string> l,list<string>::iterator it,string s)
{   
if(it==l.end()) return 0;
if(*it==s) return 1;
return(string_check(l,++it,s));
}

Answer 1

您需要改为写 int string_check(const list<string>& l, const list<string>::iterator it&, const string& s)。

否则您将获取 std::list 和迭代器的值副本，因此对它们的任何修改都不会反映在调用方中。

我通过常量引用传递对象。这有助于程序稳定性，因为函数体无法修改传递的参数。我也以这种方式传递 string 以防止不必要的值复制。

Answer 2

您正在按值传递列表，因此 l.end() 每次都是不同列表的末尾，而不是 it 来自的列表。

通过引用传递列表；或传递结束迭代器而不是列表本身。这将是一个更灵活的解决方案，允许您将函数与特定容器类型分离并支持任何范围的输入迭代器：

template <typename InIter, typename T>
bool contains(InIter begin, InIter end, T const & value) {
    if (begin == end) return false;
    if (*begin == value) return true;
    return contains(++begin, end, value);
}

递归通常不是一个好主意，因为堆栈通常相当小，如果溢出会导致可怕的错误。除非这是实现此类功能的练习，否则请使用迭代：

for (; begin != end; ++begin) {
    if (*begin == value) return true;
}
return false;

或标准库：

return std::find(begin, end, value) != end;

Answer 3

我会以不同的方式定义函数。在列表中指定一对指定目标范围的迭代器就足够了。

bool string_check( std::list<std::string>::const_iterator first,
                   std::list<std::string>::const_iterator last,
                   const std::string &s )
{
    return ( first != last ) && 
           ( *first == s || string_check( ++first, last, s ) );
}

也就是说，没有必要也传递列表本身。

您可以用同样的方式定义一个可以处理任何类型列表的模板函数。只是你的函数名应该select比较合适。例如

template <class InputIterator, class T>
bool find( InputIterator first,
           InputIterator last,
           const T &value )
{
    return ( first != last ) && 
           ( *first == value || string_check( ++first, last, value ) );
}

至于你的函数实现，那么作为列表的第一个参数应该被声明为引用

list<string> &l

Moover 它应该声明为 const 引用

const list<string> &l

可以为常量列表调用该函数。在这种情况下，您还必须更改迭代器的类型。

如何在std::list中使用递归？

How to use recursion in std::list?

c++

string

recursion

stdlist