研究算法以查看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)

10-06 14:58