ベクトルとして定義された行列をソートする<double>

Question

std::vector<double>と定義されるnの正方行列Aを仮定します。

double a_ij = A[i*n + j]; 

私は最初の列に対して昇順に行列の行をソートする必要がある：マトリックスの

std::vector<double> A(n*n); 

要素は、通常の方法でアクセスされています。

qsort関数は、配列と関数ポインタを使ってqsort関数を実行することができますが、ベクトルとstd::sortでこれを実現する方法を探したいと思います。

また、性能上の理由から私の行列をベクトルのベクトルとして定義したくないことに注意してください。

編集：私はqsort関数に渡された

機能：

static int comparisonFunction(const void* firstRow, const void* secondRow) 
{ 
    if (((double *)firstRow)[0] < ((double *)secondRow)[0]) return -1; 
    else if (((double *)secondRow)[0] < ((double *)firstRow)[0]) return 1; 
    return 0; 
} 

そしてコール：

std::qsort(matrixArray, nbRows, sizeof(double)*nbRows, comparisonFunction); 

Answer 1

根本的な配列をソートするためにstd::sortでqsortを交換することが可能ですただし、定義する必要があります：

• ベクトルの基底の記憶域に直接アクセスする行型です。ここでベクトルを使用することはできません。なぜなら、配列がまだ配列であってもベクトルのベクトルは正方形のサイズのベクトルではないからです。さらに悪いことに、既存のストレージをベクトルに割り当てるポータブルな方法はわかりません。そのRow型はmove-constructibleでmove-assignableで、スワップを正しくサポートする必要があります。
• Row型のRandomAccessIteratorで、基になる配列の末尾を正しく処理できます。

それはそれを行うためにあなた次第ですが、標準Cのすべてのバージョンは、明示的にCライブラリをサポートする++、その害はそれがはるかに簡単かつ少ないエンドであるため、このユースケースでqsortを使用しているが存在しませんエラーを起こしやすい。 qsortの方法では7行しか必要としませんでした。これは制御しやすく、ピアレビューを簡単にします。 素敵な C++の方法では、少なくとも2つのクラスが必要です。そのため、はるかに多くの行と間違いの可能性があります。

qsortを実際に使用することはできませんが、おそらく内部コーディング規則のために、データをベクトルのベクトルにコピーし、ソートして、初期ベクトルにコピーし直します。これには、マトリックスの2つの追加完全コピーが含まれますが、少なくとも標準クラスを使用し、より少ないコーディングが必要です。

Answer 2

はイテレータで動作し、反復子の実装は気にしません。もしメンバーoperator+(size_t)ためsize_t RowSize（及びoperator-、operator++など）とRow operator*() constと、std::vector<double>& matrixをラップstruct RowIterを定義する場合したがって、その後std::sortは、その反復子によってソートすることができます。

残念ながら、まだqsortよりかなり多く働いていますが、非PODタイプに一般化されます。

std::qsort(matrixArray.data(), nbRows, sizeof(double)*nbRows, comparisonFunction); 

std::sort()使用：

Answer 3

最も簡単な解決策は、このように使用すると、Cアレイとしてstd::vectorほぼ同じを使用することができ、qsort()を維持し、単に最初の要素へのポインタを返すstd::vector::data()を使用することですローで反復するためのランダムアクセスイテレータクラスだけでなく、std::sort()がそれらを入れ替えることができるように行を抽象化するクラスも同様に、適切に可能ですが冗長です。

しかし、それでもまだstd::sortを使用している場合は、並べ替える要素をインデックスとともにインデックス番号std::vectorに抽出します。次に、そのベクトルをソートし、最後に元の行列の行をそのベクトルのインデックスで並べ替えます。

#include <vector> 
#include <tuple> 
#include <algorithm> 

const int n = 10; 

std::vector<double> 
row_sort(std::vector<double> const& A) 
{ 
    std::vector<std::tuple<int, double> > first_element(n); 
    for(int i = 0; i < n; ++i) 
    { 
    first_element[i] = std::make_tuple(i, A[i*n]); 
    } 

    std::sort(std::begin(first_element), std::end(first_element), 
      [](std::tuple<int, double> const& lhs, 
       std::tuple<int, double> const& rhs) 
      { 
       return std::get<1>(lhs) < std::get<1>(rhs); 
      }); 

    std::vector<double> result(n*n); 
    for(int i = 0; i < n; ++i) 
    { 
    std::copy_n(&A[std::get<0>(first_element[i])*n], n, &result[i*n]); 
    } 

    return result; 
}