c++ - 如何将 C++ STL vector 迭代器转换为 vector 反向迭代器？

Question

我使用了嵌套 for -loop 在 C++ STL 上执行插入排序 <vector> .第一for -loop 在迭代器上，第二个在 reverse_itr 上。
我需要将索引(迭代器指针值)从第一个循环传递到第二个循环。我尝试了以下方法，但它给了我这个错误

error: no match for ‘operator!=’ (operand types are 
‘__gnu_cxx::__normal_iterator<int*, std::vector<int> >’ and 
‘std::vector<int>::reverse_iterator’ {aka 
‘std::reverse_iterator<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >’})

void insertionSort(int size, vector<int> arr) {

    for(auto itr = arr.begin(); itr != arr.end() - 1; ++itr) {

        int element = *(itr + 1);
        cout << "Element being compared with preceding sub-array is : " << element << endl;

        for(auto r_itr = (itr + 1); r_itr != arr.rend(); ++r_itr) {

            if(*(r_itr+1) <= element) {
                *r_itr = element;
                break;
            }
            else {
                *r_itr = *(r_itr+1);
            }
        }
    }
}

我在网上搜索了很多，找到了一种将反向迭代器转换为迭代器的方法(使用 itr.base() )，但不是相反。
此外，我是 C++ STL 和算法的新手，请随时提出任何方法来改进我的代码，以提高代码的“干净”性或算法本身!

Answer 1

类(class)模板std::vector具有随机访问迭代器。所以没有必要将给定的“正向”迭代器转换为“反向”迭代器。
只需与迭代器一起使用 operator --而不是 operator ++反之亦然。
注意参数size未在您声明的函数中使用

void insertionSort(int size, vector<int> arr);

如果要对 vector 中的范围进行排序，请使用声明为指定范围的迭代器的两个参数。
例如

void insertionSort( std::vector<int>::iterator first, std::vector<int>::iterator last );

或者，您可以使用模板为任何类型的 vector 编写更通用的函数。
这是一个演示程序。

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cstdlib>
#include <ctime>

void insertionSort( std::vector<int>::iterator first, std::vector<int>::iterator last )
{
    if ( first != last )
    {
        for ( auto current = first; ++current != last; )
        {
            typename std::iterator_traits<decltype( current )>::value_type
                value( *current );

            auto prev = current, next = current;

            while ( next != first && value < *--prev )
            {
                *next-- = *prev;
            }

            if ( next != current ) *next = value;
        }
    }
}

int main() 
{
    std::vector<int> v;
    const int N = 10;
    
    std::srand( ( unsigned int )std::time( nullptr ) );
    
    std::generate_n( std::back_inserter( v ), N, [=]{ return std::rand() % N; } );
    
    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    
    insertionSort( std::begin( v ), std::end( v ) );
    
    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

它的输出可能看起来像

0 6 6 7 4 3 4 6 6 1 
0 1 3 4 4 6 6 6 6 7