在STL容器中查找迭代器的索引 - 需要模板函数

Question

我希望有一个像这样的接口函数:

template<typename T, typename R> int find_index (const T& list, const R& value);

据我所知,find()STL中有返回迭代器的东西.我需要返回迭代器的索引(即使对于非索引的容器,例如std::list).我试过这段代码:

template<typename T, typename R>
int find_index (const T& list, const R& value)
{
    int index = 0;
    for (T::const_iterator it = list.begin(); it != list.end(); it++, index++)
        if ((*it) == value)
            return index;
    return -1;
}

但编译器显示错误it- 似乎不允许const_iterator从模板化的typename 获取.我可以到处走走吗？

在最坏的情况下,我可以将开始和结束迭代器传递给find_index参数,但它看起来不太好.会感谢优雅的解决方案.

Answer 1

for (typename T::const_iterator it = list.begin(); it != list.end(); ++it, ++index)

应该解决你的问题.

当使用依赖类型(类型取决于模板参数)时,编译器不知道它const_iterator是一个类型,直到它用具体类型实例化模板,它也可能只是一个静态变量或其他.使用typename关键字,你告诉他这const_iterator是一个真正的类型.

在C++ 11中,您还可以typename使用auto关键字来规避整个问题:

for (auto it = list.begin(); it != list.end(); ++it, ++index)

如果你已经有了迭代器(可能来自其他一些操作),你也可以计算从列表的开始到这个迭代器的距离:

#include <iterator>

int index = std::distance(list.begin(), it);

但由于这对于a来说具有线性复杂性std::list,因此使用自制find_index函数比std::find后续更好std::distance,至少在性能方面如此.