C++でベクトルをソートしてランク付けする方法（C++ 11を使用せずに）

Question

私は関数takeをベクトル化してランク付けしてソートし、ソートしランク付けしたベクトルを元の値。例：入力：[10,332,42,0.9,0]出力：[3,5,4,2,1]

このスタックオーバーフローquestion（特にMariusの回答）をリファレンスガイドとして使用しましたが、私のコードに悩まされていて、どこに問題があるのか​​分からない。 私はC++ 03を実行しています。

私が取得エラーの一つは、私のif文で

error: invalid types ‘const float*[float]’ for array subscript’ for array subscriptです。

//Rank the values in a vector 
std::vector<float> rankSort(const float *v_temp, size_t size) 
{ 
    vector <float> v_sort; 
    //create a new array with increasing values from 0 to n-1 
    for(unsigned i = 0; i < size; i++) 
    { 
     v_sort.push_back(i); 
    } 
    bool swapped = false; 
    do 
    { 
     for(unsigned i = 0; i < size; i++) 
     { 
      if(v_temp[v_sort[i]] > v_temp[v_sort[i+1]]) //error line 
      { 
       float temp = v_sort[i]; 
       v_sort[i] = v_sort[i+1]; 
       v_sort[i+1] = temp; 
       swapped = true; 
      } 
     } 
    } 
    while(swapped); 
    return v_sort; 
} 

std::vector<float> rankSort(const std::vector<float> &v_temp) 
{ 
    return rankSort(&v_temp[0], v_temp.size()); 
} 

Answer 1

あなたの問題はランキングに誤解です。配列インデックスはsize_tではなくfloatではないので、vector<float>ではなくvector<size_t>を返す必要があります。

あなたの種類はO（n ）となっています。実際にこのうん

：

vector<size_t> rankSort(const float* v_temp, const size_t size) { 
    vector<pair<float, size_t> > v_sort(size); 

    for (size_t i = 0U; i < size; ++i) { 
     v_sort[i] = make_pair(v_temp[i], i); 
    } 

    sort(v_sort.begin(), v_sort.end()); 

    pair<double, size_t> rank; 
    vector<size_t> result(size); 

    for (size_t i = 0U; i < size; ++i) { 
     if (v_sort[i].first != rank.first) { 
      rank = make_pair(v_sort[i].first, i); 
     } 
     result[v_sort[i].second] = rank.second; 
    } 
    return result; 
} 

Live Example

EDITを：あなたはより多くのメモリを使用するために喜んでいる場合は、私たちはダウンO（n）は、n個（ログ）にその時間を得ることができますfloat[]の代わりにvector<float>を使用すると少しシンプルになります。

vector<size_t> rankSort(const vector<float>& v_temp) { 
    vector<pair<float, size_t> > v_sort(v_temp.size()); 

    for (size_t i = 0U; i < v_sort.size(); ++i) { 
     v_sort[i] = make_pair(v_temp[i], i); 
    } 

    sort(v_sort.begin(), v_sort.end()); 

    pair<double, size_t> rank; 
    vector<size_t> result(v_temp.size()); 

    for (size_t i = 0U; i < v_sort.size(); ++i) { 
     if (v_sort[i].first != rank.first) { 
      rank = make_pair(v_sort[i].first, i); 
     } 
     result[v_sort[i].second] = rank.second; 
    } 
    return result; 
} 

Live Example

Answer 2

v_sort[i]のみ整数型が配列添字として使用することができるが（それがv_sortベクトルのちょうど要素の）floatあります。

おそらく、インデックスの配列としてv_sortを意味していたため、std::vector<size_t>またはstd::vector<int>というように宣言する必要があります。

UP：また、渡された配列の値を変更すると、それはconst参照によってエレガントに渡すことはできません。まとめると

は、次のコードは、私のマシン上で正しくコンパイル：

std::vector<unsigned> rankSort(float *v_temp, size_t size) 
{ 
    vector <unsigned> v_sort; 
    //create a new array with increasing values from 0 to n-1 
    for(unsigned i = 0; i < size; i++) 
    { 
     v_sort.push_back(i); 
    } 
    bool swapped = false; 
    do 
    { 
     for(unsigned i = 0; i < size; i++) 
     { 
      if(v_temp[v_sort[i]] > v_temp[v_sort[i+1]]) //error line 
      { 
       unsigned temp = v_sort[i]; 
       v_sort[i] = v_sort[i+1]; 
       v_sort[i+1] = temp; 
       swapped = true; 
      } 
     } 
    } 
    while(swapped); 
    return v_sort; 
} 

std::vector<unsigned> rankSort(std::vector<float> &v_temp) 
{ 
    return rankSort(&v_temp[0], v_temp.size()); 
} 

Answer 3

//Rank the values in a vector 
std::vector<size_t> rankSort(const std::vector<float> &v_temp) 
{ 
    vector <size_t> v_sort; 
    //create a new array with increasing values from 0 to size-1 
    for(size_t i = 0; i < v_temp.size(); i++) 
     v_sort.push_back(i); 

    bool swapped = false; 
    do 
    { 
     swapped = false; //it's important to reset swapped 
     for(size_t i = 0; i < v_temp.size()-1; i++) // size-2 should be the last, since it is compared to next element (size-1) 
      if(v_temp[v_sort[i]] > v_temp[v_sort[i+1]]) 
      { 
       size_t temp = v_sort[i]; // we swap indexing array elements, not original array elements 
       v_sort[i] = v_sort[i+1]; 
       v_sort[i+1] = temp; 
       swapped = true; 
      } 
    } 
    while(swapped); 

    return v_sort; 
} 

Answer 4

私は、あなたがSTLで持っているものを活用することにより、より堅牢なソリューションを採用することをお勧めします。これを行うには、最初に "インデックスベクトル"を作成します。 std::vector<std::size_t> vなどは、任意のiため、v[i] == iは真であること：

// I'm sure there's a more elegant solution to generate this vector 
// But this will do 
std::vector<std::size_t> make_index_vector(std::size_t n) { 
    std::vector<std::size_t> result(n, 0); 
    for (std::size_t i = 0; i < n; ++i) { 
     result[i] = i; 
    } 
    return result; 
} 

は、今、私たちがしなければならないすべては、入力ベクトルを使用する特定の比較関数に応じて、このベクトルをソートすることです。、index[0]は入力ベクトルで最も低い値の指標である、ソートされたインデックスベクトルで

template <typename T, typename A, typename Cmp> 
struct idx_compare { 
    std::vector<T, A> const& v; 
    Cmp& cmp; 
    idx_compare(std::vector<T, A> const& vec, Cmp& comp) : v(vec), cmp(comp) {} 

    bool operator()(std::size_t i, std::size_t j) { 
     return cmp(v[i], v[j]); 
    } 
}; 

template <typename T, typename A, typename Cmp> 
std::vector<std::size_t> sorted_index_vector(std::vector<T, A> const& vec, Cmp comp) { 
    std::vector<std::size_t> index = make_index_vector(vec.size()); 
    std::sort(index.begin(), index.end(), 
     idx_compare<T, A, Cmp>(vec, comp)); 

    return index; 
} 

index[1]：さらに、我々はユーザーに任意の比較ファンクタを使用する機会を与える最も一般的なアプローチを可能にします2番目に低いなどです。したがって、我々はこの1からランクベクトルを取得するための一つの追加のステップが必要になります。

std::vector<std::size_t> get_rank_vector(std::vector<std::size_t> const& index) { 
    std::vector<std::size_t> rank(index.size()); 
    for (std::size_t i = 0; i < index.size(); ++i) { 
     // We add 1 since you want your rank to start at 1 instead of 0 
     // Just remove it if you want 0-based ranks 
     rank[index[i]] = i + 1; 
    } 
    return rank; 
} 

今、私たちは一緒にすべてのピースを組み合わせる：

template <typename T, typename A, typename Cmp> 
std::vector<std::size_t> make_rank_vector(
    std::vector<T, A> const& vec, Cmp comp) { 
    return get_rank_vector(sorted_index_vector(vec, comp)); 
} 

// I had to stop using default template parameters since early gcc version did not support it (4.3.6) 
// So I simply made another overload to handle the basic usage. 
template <typename T, typename A> 
std::vector<std::size_t> make_rank_vector(
    std::vector<T, A> const& vec) { 
    return make_rank_vector(vec, std::less<T>()); 
} 

結果[10、332、42、0.9、0で]：[3,5,4,2,1]。 gcc 4.3.6でLive Demoが見つかりました。

Answer 5

ここではSTLを使用してこれを簡潔な方法でランク付けするコードを示します。

template <typename T> 
vector<size_t> calRank(const vector<T> & var) { 
    vector<size_t> result(var.size(),0); 
    //sorted index 
    vector<size_t> indx(var.size()); 
    iota(indx.begin(),indx.end(),0); 
    sort(indx.begin(),indx.end(),[&var](int i1, int i2){return var[i1]<var[i2];}); 
    //return ranking 
    for(size_t iter=0;iter<var.size();++iter){ 
     result[indx[iter]]=iter+1; 
    } 
    return result; 
}