挿入ソートを文字列ベクトルで

Question

挿入ソートを使用して文字列ベクトルをソートしようとしています。

これは私のコードです：

void insertionsort(std::vector<std::string> &strings) 
{ 
    typedef std::vector<std::string>::size_type size_type; 
    for(size_type i = 0;i < strings.size(); i++) 
    { 
     std::string const tmp = strings[i]; 
     size_type j = i - 1; 
     while(j >= 0 && tmp < strings[j]) //this is the problem 
     { 
      strings[j + 1]= strings[j]; 
      j--; 

     } 
     strings[j + 1]=tmp; 
    } 
} 

それは私にエラー与える：

comparison of unsigned expression >= 0 is always true

私は> 0 Jを使用した場合の機能が正常に動作します。しかし、それは完全に文字列の最初の行を無視します。

私が持っている場合例えば：

2 line1 
3 line2 
4 line3 
5 line4 
1 line5 

をそれからそれは私を与える：

2 line1 
1 line5 
3 line2 
4 line3 
5 line4 

Answer 1

vector<T>::size_typeのでj >= 0が偽することはできませんby definition符号なしです。 vector<T>::difference_typeを使用してください。

Answer 2

クラステンプレートstd::vectorのタイプ別名size_typeは、常に負ではない整数型です。したがって、エフェクト

j >= 0 

は常にtrueです。

必要なのは、機能の実装に若干の変更を加えることです。 1つの要素だけを含むベクトルは常にソートされることは明らかです。だから、あなたがプログラム出力が

E D C B A 
A B C D E 

ご注意この追加の文

if (j != i) strings[j] = tmp; 

にある

#include <iostream> 
#include <vector> 
#include <string> 

void insertionSort(std::vector<std::string> &strings) 
{ 
    typedef std::vector<std::string>::size_type size_type; 

    for (size_type i = 1; i < strings.size(); ++i) 
    { 
     std::string tmp = strings[i]; 

     size_type j = i; 

     for (; j != 0 && tmp < strings[j-1]; --j) 
     { 
      strings[j] = strings[j-1]; 
     } 

     if (j != i) strings[j] = tmp; 
    } 
} 

int main() 
{ 
    std::vector<std::string> v = { "E", "D", "C", "B", "A" }; 

    for (const auto &s : v) std::cout << s << ' '; 
    std::cout << std::endl; 

    insertionSort(v); 

    for (const auto &s : v) std::cout << s << ' '; 
    std::cout << std::endl; 
} 

です。ここ1

に等しいインデックスを持つ外側のループを開始する必要があります

要素が既にベクトルの必要な位置を占めている場合、意味がありませんそれをそれ自身に割り当てます。これにより、関数の効率が向上します。

タイプdifference_typeとタイプsize_type（メンバー関数size()の返品タイプ）を混在させることは好ましくありません。