研究算法以查看STL字符串(或其他字符串,使其更通用)的STL容器
基本上,它会循环遍历std::list之类的东西,并返回最长的共同点的长度。它用于处理文件列表,如下所示:
C:\Windows\System32\Stuff.exe C:\Windows\Things\InHere.txt C:\Windows\Foo\Bar.txt
This should return 11, because "C:\Windows\
" is in common.
Never written a templatized function before, and my compiler is complaining. Here's my code:
Header:
// longestBegin.h -- Longest beginning subsequence solver
template <typename SequenceSequenceT, typename SequenceT, typename T >
size_t longestBegin(InputIterator firstCandidates, InputIterator lastCandidates);
实现方式:
// longestBegin.cpp -- Longest beginning subsequence solver
#include <stdafx.h>
template <typename SequenceSequenceT, typename SequenceT, typename T >
size_t longestBegin(InputIterator firstCandidates, InputIterator lastCandidates)
{
SequenceT firstString = *firstCandidates;
size_t longestValue = firstString.length();
firstCandidates++;
for(size_t idx = 0; idx < longestValue; idx++)
{
T curChar = firstString[idx];
for(InputIterator curCandidate = firstCandidates;curCandidate != lastCandidates; curCandidate++)
{
if ((*curCandidate)[idx] != curChar)
return idx - 1;
}
}
return longestValue;
}
我有一种奇怪的感觉,我在这里错过了一些基本的东西……
编译器炸弹并出现以下错误:
error C2998: 'size_t longestBegin' : cannot be a template definition
有任何想法吗?谢谢!
比利3
最佳答案
template
行中的参数名称需要包括任何类型的函数参数或返回类型。这意味着您需要在模板参数列表中提及InputIterator
。尝试将函数声明更改为:
template <typename InputIterator>
size_t longestBegin(InputIterator firstCandidates, InputIterator lastCandidates)
您的下一个问题是:编译器如何知道
SequenceT
是什么?答案是,这是取消引用InputIterator
的结果。不是指针的迭代器具有嵌套的typedef
,称为reference
,这正是您在这里需要的。将其添加到函数的开头,以便编译器知道SequenceT
是什么:
template <typename InputIterator>
size_t longestBegin(InputIterator firstCandidates, InputIterator lastCandidates)
{
typedef typename InputIterator::reference SequenceT;
[etc.]
您本可以将
SequenceT
保留为模板参数,但是编译器无法通过查看参数来猜测它的含义,因此您必须通过键入例如来调用函数。 longestBegin<string>(arguments)
,这里不需要。另外,您会注意到,如果
InputIterator
是指针,则此方法不起作用-指针没有嵌套的typedef。因此,您可以使用std::iterator_traits
标准 header 中的特殊结构<iterator>
,它可以为您解决以下问题:
//(At the top of your file)
#include <iterator>
template <typename InputIterator>
size_t longestBegin(InputIterator firstCandidates, InputIterator lastCandidates)
{
typedef typename std::iterator_traits<InputIterator>::reference SequenceT;
[etc.]
最后,除非第一个字符串始终最长,否则您可能最终会在第二个for循环内访问超出其数组末尾的字符串。您可以在访问之前检查字符串的长度:
//(At the top of your file)
#include <iterator>
template <typename InputIterator>
size_t longestBegin(InputIterator firstCandidates, InputIterator lastCandidates)
{
typedef typename std::iterator_traits<InputIterator>::reference SequenceT;
SequenceT firstString = *firstCandidates;
size_t longestValue = firstString.length();
firstCandidates++;
for(size_t idx = 0; idx < longestValue; idx++)
{
T curChar = firstString[idx];
for(InputIterator curCandidate = firstCandidates;curCandidate != lastCandidates; curCandidate++)
{
if (curCandidate->size() >= idx || (*curCandidate)[idx] != curChar)
return idx - 1;
}
}
return longestValue;
}
另请注意,如果没有公共(public)前缀,该函数将返回
(size_t)(-1)
。