C++:在迭代器之间计算距离上的类型混淆

Question

我需要在一个元素中旋转元素std::vector,使它在第一个重复元素的开头保存.为了更清楚,如果我有:

1 2 3 4 5 6 3 7 8

然后我想:

3 4 5 6 3 7 8 1 2   

好的,让我们使用std::rotate(),并构建一个函数来获得第一个重复的位置:

int main() {
   std::vector<int> v = { 1,2,3,4,5,6,3,7,8 };
   auto it = FindFirstDuplicate(v);
   cout << "first dupe is " << *it << " at " << it - v.begin() << endl;
   std::rotate( v.begin(), it, v.end() );
}

该任务的想法是逐个存储新向量中的元素,直到我发现我要添加的元素已经在这个新向量中.

但我偶然发现了迭代器问题,因此无法编译.我对不同迭代器的类型以及const/non const迭代器问题感到困惑.

这是我目前的代码,在线尝试(跳过std::可读性):

template<typename T>
typename vector<T>::iterator FindFirstDuplicate( const vector<T>& v )
{
   vector<T> nv; // new temp vector
   nv.reserve( v.size() );
   for( auto it1 = v.cbegin(); it1 != v.cend(); it1++ )
   {
      auto it2 = find( nv.begin(), nv.end(), *it1 ); // search elem in new vector
      if( it2 == nv.end() )                          // if not present,
         nv.push_back( *it1 );                       //   add in new vector
      else                                           // else, we found a dupe
         return v.begin() + (it2-nv.begin());
   }
   return v.begin();
}

为了挽救你的眼睛,我不发布错误消息,但对我来说似乎编译器抱怨最后一行上的迭代器的不同类型.我也试过使用非const迭代器it1,但我仍然遇到了这个问题.

任何帮助,在这个迭代器问题,但也有任何关于算法的建议本身.

Answer 1

问题是你试图iterator从const引用返回vector.您可以在此最小示例中查看问题:

#include <iostream>
#include <vector>

template <typename T>
typename std::vector<T>::iterator foo(const std::vector<T>& v)
{
    return v.begin(); // const overload returns const_iterator
}

int main() {
    std::vector<int> v(42);
    foo(v); // Instantiate function template: ERROR
}

你可以做的是将非const引用传递给你的finder函数:

template<typename T>
typename vector<T>::iterator FindFirstDuplicate( vector<T>& v )
{
   ...