2

入力のいくつかの行を受け取り、与えられたいくつかのコマンドライン引数に基づいて並べ替えるプログラムを作成する必要があります。行は可変長にすることができ、行の各項目は次のようにコンマで区切られます。

a,b,c,12,3
d,e,f,4,56
a,g,h,8,5

プログラムがしなければならないことは、与えられた引数に基づいて特定の列で入力をソートすることです。それは簡単ですが、難しいのは、複数の引数を並べ替えることができる必要があることです。

たとえば、コマンド ライン引数 1,4 (両方とも昇順) は次のように出力されます。

a,g,h,8,5
a,b,c,12,3
d,e,f,4,56

したがって、最初の列に基づいてソートされ、次に 4 番目の列に基づいてソートされます。何かを並べ替える方法がわからない場合は、列全体を再利用せずに、次の引数を使用して競合する要素のみを並べ替えます。現在、入力をベクトルのベクトルに格納しています。

補足として、私はいくつかの同様の質問を読みましたが、それらはすべて、並べ替える項目の数が決まっているだけです。このプログラムでは、1 行あたりの項目数は 1 以上で、並べ替えの基準となる引数の数も可変です。

4

1 に答える 1

1

まず、イテレータを最初に処理し、最後に入力として処理する std::sort() を使用します。次に、再帰を使用します。再帰はソリューションの鍵です。

各引数、つまりソート基準 C_i に対して、1 つの再帰レベル R_i があります。各再帰レベル R_i 内には、次の 2 つのステップがあります。

  1. 基準 C_i に従って、指定されたデータ範囲を並べ替えます。
  2. データ範囲をループします。値 C_i が変更されるたびに、引数を指定して次の再帰レベル R_{i+1} を呼び出します。
    • first: 最後の変更への反復子、または範囲の先頭
    • last: 現在の要素への反復子 (C_i が変更された最初の要素)
    • 基準リストへの参照/ポインタおよび i+1

それでおしまい！

このソリューションの説明:

  • イテレータにより、基礎となるデータ構造を再初期化したりコピーしたりする必要がないため、この方法は効率的です。
  • i で初期化され、ベクトルの要素 i に従って常に比較されるカスタム比較ファンクターを作成する必要があります。
  • 比較ごとにすべてのソート基準を通過する必要がある1つのグランドソートを実行するか、私のアプローチのように複数回ソートし、それぞれ1つの基準のみをチェックするかは議論の余地があります。
  • このソリューションでは、多くのベクトルが交換されます。ただし、 std::vector スワップは安価であるため、これは問題ではありません。
于 2013-03-03T10:18:10.067 に答える