挿入型ソートのテンプレート化バージョンの問題

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が冗長であるため、コンパイラは警告/エラーを発行する必要があります。

次に、そのタイプの変数TmpVecを宣言します。

それ以降はすべて、TmpVecが変数ではなく型であるかのように使用されます。

あなたは、おそらく私も

using tmp_iterator = typename TmpVec::iterator; 

に助言し、代わりにTmpVec::iteratorの種類としてtmp_iteratorを使用したい

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

をしたいです。