递归传递字符串而不需要重新创建
Pass a string Recursively without Recreation
我在这里回答了一个问题: 我需要使用递归来单步执行 string
。我想在每个函数上使用 const string&
作为我的参数,但除非我想在每次递归时重建字符串,否则我发现我需要传递 start
和 finish
位置以及string
本身。所以通过 string
变得毫无意义。
最后我选择只传递 start
和 finish
指向 char[]
的指针。
举个例子,假设我得到一个包含嵌套括号的字符串(但没有并排的括号插入)。就像这样:
(abc(def(ghi((j)klm)nop)qrs)tuv)wxyz
但不是这样的:
(abc(def)(ghi)(j)(klm)(nop)(qrs)tuv)wxyz
我想写一个递归程序来提取最深嵌套括号中的字符串。类似于:
string foo(const string& bar){
auto start = bar.find('(') + 1;
return start == string::npos + 1 ? bar : foo(bar.substr(start, bar.find_last_of(')') - start));
}
然而,我不高兴为 foo
的每次重复重建 string
。另一种方法是像链接示例中那样传递 start
和 finish
指针(或传递 string::const_iterator
s.)
是否有允许我使用 string
功能但不重建 string
的包装器或其他东西?
string_view
来自库基础 TS 可能是一个想法,GCC 提供支持。
界面与string
几乎相同
#include <experimental/string_view>
using std::experimental::string_view;
string_view foo(const string_view& bar){
auto start = bar.find('(') + 1;
return start == string_view::npos + 1 ? bar : foo(bar.substr(start, bar.find_last_of(')') - start));
}
最后一行也可以是
return start ? foo(bar.substr(start, bar.find_last_of(')') - start)) : bar;
尽管他们都很神秘。
自己写 array_view<T>
。就是几十行代码。
使用std::find
替换两种算法。在一种情况下,使用反向迭代器。 (或者写一个基于范围的查找和基于范围的backwards
)
使用{T*,T*}
ctor 进行递归。
array_view<const char> foo(array_view<const char> bar)
这是一个原始的array_view<T>
:
template<class T>
struct array_view {
using mutable_T = typename std::remove_reference<T>::type;
// 3 primitive functions:
T* begin() const { return b; }
T* end() const { return e; }
array_view(T* s, T* f):b(s), e(f) {};
// everything else based on them:
size_t size() const { return end()-begin(); }
array_view(T* s, size_t l):array_view(s,s+l) {}
array_view():array_view(nullptr, nullptr) {}
// repeat next 3 for string, array, initializer list, C array as required:
template<class A>
array_view( std::vector<T,A>& v ):array_view(v.data(), v.size()) {}
// may not compile for non-const T, but that is ok you get an error:
template<class A>
array_view( std::vector<mutable_T,A>const & v ):array_view(v.data(), v.size()) {}
// in a better world, you'd SFINAE remove the above from consideration
// consider it for your next iteration of array_view.
// conversion to containers:
template<class A>
explicit operator std::vector<mutable_T,A>() const {
return convert_to< std::vector<mutable_T, A> >();
}
template<class C>
C convert_to() const {
C retval(begin(), end());
return retval;
}
// utility functions:
T& front() const { return *begin(); }
T& back() const { return std::prev(*end()); }
// Also rbegin, rend, and whatever else you find you are missing
// inspired by std::experimental:
void pop_front() { *this = {std::next(begin()), end()}; }
void pop_back() { *this = {begin(), std::prev(end())}; }
// but I find direct use of `view = {x,y}` almost as good
// these kind of operations are the ONLY ones that are non-const
// remember this is a view. If you want a view of const data, make it
// an array_view<const T>, not a const array_view<T>. It really works
// out better.
private:
T* b
T* e;
};
以上示例代码未经测试
我在这里回答了一个问题:string
。我想在每个函数上使用 const string&
作为我的参数,但除非我想在每次递归时重建字符串,否则我发现我需要传递 start
和 finish
位置以及string
本身。所以通过 string
变得毫无意义。
最后我选择只传递 start
和 finish
指向 char[]
的指针。
举个例子,假设我得到一个包含嵌套括号的字符串(但没有并排的括号插入)。就像这样:
(abc(def(ghi((j)klm)nop)qrs)tuv)wxyz
但不是这样的:
(abc(def)(ghi)(j)(klm)(nop)(qrs)tuv)wxyz
我想写一个递归程序来提取最深嵌套括号中的字符串。类似于:
string foo(const string& bar){
auto start = bar.find('(') + 1;
return start == string::npos + 1 ? bar : foo(bar.substr(start, bar.find_last_of(')') - start));
}
然而,我不高兴为 foo
的每次重复重建 string
。另一种方法是像链接示例中那样传递 start
和 finish
指针(或传递 string::const_iterator
s.)
是否有允许我使用 string
功能但不重建 string
的包装器或其他东西?
string_view
来自库基础 TS 可能是一个想法,GCC 提供支持。
界面与string
#include <experimental/string_view>
using std::experimental::string_view;
string_view foo(const string_view& bar){
auto start = bar.find('(') + 1;
return start == string_view::npos + 1 ? bar : foo(bar.substr(start, bar.find_last_of(')') - start));
}
最后一行也可以是
return start ? foo(bar.substr(start, bar.find_last_of(')') - start)) : bar;
尽管他们都很神秘。
自己写 array_view<T>
。就是几十行代码。
使用std::find
替换两种算法。在一种情况下,使用反向迭代器。 (或者写一个基于范围的查找和基于范围的backwards
)
使用{T*,T*}
ctor 进行递归。
array_view<const char> foo(array_view<const char> bar)
这是一个原始的array_view<T>
:
template<class T>
struct array_view {
using mutable_T = typename std::remove_reference<T>::type;
// 3 primitive functions:
T* begin() const { return b; }
T* end() const { return e; }
array_view(T* s, T* f):b(s), e(f) {};
// everything else based on them:
size_t size() const { return end()-begin(); }
array_view(T* s, size_t l):array_view(s,s+l) {}
array_view():array_view(nullptr, nullptr) {}
// repeat next 3 for string, array, initializer list, C array as required:
template<class A>
array_view( std::vector<T,A>& v ):array_view(v.data(), v.size()) {}
// may not compile for non-const T, but that is ok you get an error:
template<class A>
array_view( std::vector<mutable_T,A>const & v ):array_view(v.data(), v.size()) {}
// in a better world, you'd SFINAE remove the above from consideration
// consider it for your next iteration of array_view.
// conversion to containers:
template<class A>
explicit operator std::vector<mutable_T,A>() const {
return convert_to< std::vector<mutable_T, A> >();
}
template<class C>
C convert_to() const {
C retval(begin(), end());
return retval;
}
// utility functions:
T& front() const { return *begin(); }
T& back() const { return std::prev(*end()); }
// Also rbegin, rend, and whatever else you find you are missing
// inspired by std::experimental:
void pop_front() { *this = {std::next(begin()), end()}; }
void pop_back() { *this = {begin(), std::prev(end())}; }
// but I find direct use of `view = {x,y}` almost as good
// these kind of operations are the ONLY ones that are non-const
// remember this is a view. If you want a view of const data, make it
// an array_view<const T>, not a const array_view<T>. It really works
// out better.
private:
T* b
T* e;
};
以上示例代码未经测试