模板和语法

Question

使用算法查看STL字符串的STL容器(或其他字符串,使其成为通用字符串)

基本上它循环通过类似std :: list的东西,并返回最常见的最长开头的长度.它用于处理文件列表,如下所示:

C:\Windows\System32\Stuff.exe
C:\Windows\Things\InHere.txt
C:\Windows\Foo\Bar.txt

这应该返回11,因为" C:\Windows\"是共同的.

从来没有写过一个模板化的函数,我的编译器在抱怨.这是我的代码:
标题:

// 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

有任何想法吗？谢谢!

Billy3

Answer 1

行中的参数名称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作为模板参数,但编译器无法猜测查看参数是什么,并且您必须通过键入eg来调用您的函数longestBegin<string>(arguments),这在此处是不必要的.

此外,您会注意到,如果InputIterator是指针,这不起作用- 指针没有嵌套的typedef.因此,您可以使用std::iterator_traits从<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;
}

另请注意,(size_t)(-1)如果没有公共前缀,则函数返回.