c++ - 模板和语法

Question

研究一种算法来查看 STL 字符串(或其他字符串，使其通用)的 STL 容器

基本上它循环遍历类似于 std::list 的东西并返回最长的共同开头的长度。它用于处理文件列表，如下所示:

C:\Windows\System32\Stuff.exeC:\Windows\Things\InHere.txtC:\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

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作为模板参数，但是编译器无法通过查看参数来猜测它是什么，您必须通过键入例如调用您的函数longestBegin<string>(arguments) ，这里没有必要。

此外，您会注意到，如果 InputIterator，这将不起作用。是一个指针——指针没有嵌套的类型定义。所以你可以使用一个名为 std::iterator_traits 的特殊结构来自 <iterator>可以为您解决这些问题的标准 header :

//(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)如果没有共同的前缀。