插入排序的模板化版本問題

Question

下面是插入排序的模板化版本，它會導致編譯錯誤，無需任何額外空間就可以執行插入排序。

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

using namespace std; 

template <typename T> 
insertSort(T start, T end) 
{ 
    typename std::vector<typename std::iterator_traits<T>::value_type> TmpVec; 
    TmpVec tmp(std::make_move_iterator(start), std::make_move_iterator(end)); 
    TmpVec::iterator begin = std::begin(tmp); 
    TmpVec::iterator end = std::end(tmp); 
    for(TmpVec::iterator i = begin; i != end; i++) 
    { 
     typename std::iterator_traits<T>::value_type value = *i; 
     TmpVec::iterator pos = i; 
     while (pos > start && *(pos-1) > value) 
     { 
      *pos = std::move(*(pos-1)); 
      --pos; 
     } 
     *pos = value; 
    } 
} 

int main(int argc, char** argv) { 

    std::vector<double> arr = {1,5,3,2,6,3,9,8}; 
    insertSort<double>(arr.begin(), arr.end()); 
    for(int i=0; i<arr.size(); i++) 
    { 
     std::cout << arr[i] << " "; 
    } 
    return 0; 
} 

我正在用下面的編譯行來編譯它。

g++ -std=c++11 -c -g -MMD -MP -MF "build/Debug/MinGW-Windows/main.o.d" -o build/Debug/MinGW-Windows/main.o main.cpp 

這會產生以下錯誤。

main.cpp: In function 'int insertSort(T, T)': 
main.cpp:21:12: error: expected ';' before 'tmp' 
    TmpVec tmp(std::make_move_iterator(start), std::make_move_iterator(end)); 
      ^
main.cpp:22:5: error: 'TmpVec' is not a class, namespace, or enumeration 
    TmpVec::iterator begin = std::begin(tmp); 
    ^
main.cpp:23:5: error: 'TmpVec' is not a class, namespace, or enumeration 
    TmpVec::iterator end = std::end(tmp); 
    ^
main.cpp:24:9: error: 'TmpVec' is not a class, namespace, or enumeration 
    for(TmpVec::iterator i = begin; i != end; i++) 
     ^
main.cpp:24:37: error: 'i' was not declared in this scope 
    for(TmpVec::iterator i = begin; i != end; i++) 
            ^
main.cpp:27:9: error: 'TmpVec' is not a class, namespace, or enumeration 
     TmpVec::iterator pos = i; 
     ^
main.cpp:28:16: error: 'pos' was not declared in this scope 
     while (pos > start && *(pos-1) > value) 
       ^
main.cpp:33:10: error: 'pos' was not declared in this scope 
     *pos = value; 
     ^
main.cpp: In function 'int main(int, char**)': 
main.cpp:40:46: error: no matching function for call to 'insertSort(std::vector<double>::iterator, std::vector<double>::iterator)' 
    insertSort<double>(arr.begin(), arr.end()); 
              ^
main.cpp:40:46: note: candidate is: 
main.cpp:18:1: note: template<class T> int insertSort(T, T) 
insertSort(T start, T end) 
^ 
main.cpp:18:1: note: template argument deduction/substitution failed: 
main.cpp:40:46: note: cannot convert 'arr.std::vector<_Tp, _Alloc>::begin<double, std::allocator<double> >()' (type 'std::vector<double>::iterator {aka __gnu_cxx::__normal_iterator<double*, std::vector<double> >}') to type 'double' 
    insertSort<double>(arr.begin(), arr.end()); 

請幫忙解決上述問題。

Answer 1

typename std::vector<typename std::iterator_traits<T>::value_type> TmpVec; 

這個狀態std::vector<typename std::iterator_traits<T>::value_type>是一個typename。編譯器應該發出警告/錯誤，因爲typename是多餘的。

然後它聲明該類型的變量TmpVec。

之後每次使用TmpVec就好像它是一個類型，而不是一個變量。

你可能想

typedef std::vector<typename std::iterator_traits<T>::value_type> TmpVec; 

我還告訴

using tmp_iterator = typename TmpVec::iterator; 

，並使用tmp_iterator作爲一個類型，而不是TmpVec::iterator。