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 迭代器问题感到困惑。

这是我目前的代码，try it online here（为了便于阅读跳过 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();
}

为了保护您的眼睛，我没有 post 错误消息，但对我来说，编译器似乎在最后一行抱怨不同类型的迭代器。我也尝试过对 it1 使用非 const 迭代器，但我仍然遇到这个问题。

在此迭代器问题上的任何帮助，以及对算法本身的任何建议。

Answer 1

问题是您正试图从 const 对 vector 的引用中 return 一个 iterator。您可以在这个最小示例中看到问题：

#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
}

您可以做的是将非常量引用传递给您的查找器函数：

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

Answer 2

根据@James Kanze（归功于他）的建议，作为记录，这是一个更短、更正和完整的版本。这也是 returns 找到重复项的位置。

template<typename T>
typename vector<T>::iterator
FindFirstDuplicate( vector<T>& v, typename vector<T>::iterator& dupe )
{
   auto current = v.begin();
   while (
      current != v.end() &&
      (dupe = std::find( std::next( current ), v.end(), *current )) == v.end()
   )
   {
       ++current;
   }
   return current;
}

// test case
int main()
{   
   vector<int> v = { 1,2,3,4,5,6,5,4,3 };
   auto dupe = v.begin();
   auto it = FindFirstDuplicate(v,dupe);
   cout << "first dupe is " << *it << " at pos " << it - v.cbegin() << endl;
   cout << "dupe is " << *dupe << " at pos " << dupe - v.cbegin() << endl;
}

可以here 进行试验。完整地说，我使用的版本 returns 实际上是两个迭代器的 std::pair。

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

C++: confused by type on computing distances between iterators

c++

algorithm

c++11

iterator