c++ - 文字列配列のカスタムソート

Question

虹の 7 色を含むがランダムな順序で配置された文字列の配列が与えられた場合、この配列を並べ替えて、赤、オレンジ、緑、....、紫の順に出力することになっています。虹色の順番。この配列をソートするにはどうすればよいですか?

Answer 1

カスタムコンパレータを作成する必要があります。これが私がそれについてどうするかです。

//somewhere in initalization code;
std::map<string, int> mapOrder;
mapOrder["red"] = 1;
mapOrder["orange"] = 2;
...
mapOrder["violet"] = 7;


bool isRainbowLess(const std::string& a, const std::string& b)
{
    return mapOrder[a] < mapOrder[b];
}


int main()
{
    std::vector<std::string> myVector;
    ....
    std::sort(myVector.begin(), myVector.end(), &isRainbowLess);
}

Answer 2

OK、すぐに反対票を投じないでください。これは悪い例だと思います。私は、OPがSTLなしのソリューションを具体的に要求し、それがどのように（悪い）どのように見えるかを提示するためだと書きました。

さて、あなたは行き​​ます。コードは完成していません。しかし、あなたは一般的な考えを得る必要があります。私がスキップしたことの1つは、整数自体のソートです。些細なことなので。ご覧のとおり、マッピングは少しPIAであり、かなり見栄えが悪いです。ただし、STLの使用を禁止しているため、ありませんstd::map。Nさらに、すべてのテーブルの静的サイズを暗示しました。動的に割り当てることができ、問題はなく、std::vector。

関数を模倣する関数にelse ifsを使用しました。おそらく使用できますが、まともなコンパイラでもほぼ同じように機能するはずです。map*std::mapswitch ... case

以下に書いたコードは、Armenのコードとほとんど同じです。私は彼の解決策をお勧めします。同じ部分をスキップしました。だからあなたはそれが醜くてより多くのタイピングであることがわかります。それはほとんど純粋なCのように見えます。非常に大きなケースでスピードを本当に望んでいるなら、たぶん1つの変更があります。これは、マップされた値を保持する一時的なデータ構造を使用して、それを並べ替えてから、マップし直します。正確には、ハッシュ計算を回避するために、高性能の制約の下での呼び出しmap::operator[](const &T)（またはアクセサー）を避けることをお勧めします。std::stringしかし、それだけです。

議論することもいくつかあります。2つの色に同じ値を設定したい場合や、整数以外の重みを使用したい場合などです。STLベースのソリューションははるかに適応性があります。

乾杯。

コード：

/* This will map color literals (color names) to integers, which will associate them with 
   a numerical value, than can be used for comparison */
enum Colors { Red, Orange, Green, /*...*/ Violet };

/* this should read colors as std::string instances from the input array and assing
   the the appropriate color codes into output array at corresponding indexes     */
void mapString2Color( const std::string* input, int* output, size_t N ){
  for(size_t i = 0; i < N; i++){
    if ( input[i] == std::string("red") ) output[i] = Colors::Red;
    else if ( input[i] == std::string("orange") ) { output[i] = Colors::Orange; }
    else if ( input[i] == std::string("green") )  { output[i] = Colors::Green;  }
    /*...*/
    else if ( input[i] == std::string("violet") ) { output[i] = Colors::Violet; }
    else {/*unspecified color code */}
  }
}
/* this is supposed to do the opposite to mapString (i.e. put appropriate 
   string at output[i] based on input[i])  */
void mapColor2String( const int* input, std::string* output, size_t N ){
  for(size_t i = 0; i < N; i++){
    if ( input[i] == Colors::Red ) output[i] = std::string("red");
    else if ( input[i] == Colors::Orange ) { output[i] = std::string("orange"); }
    else if ( input[i] == Colors::Green  ) { output[i] = std::string("green");  }
    /*...*/
    else if ( input[i] == Colors::Violet ) { output[i] = std::string("violet"); }
    else {/*unspecified color index*/}
  }
}

void sort(int* array, size_t N){
 /* any in-place sort of your liking for table of (unsigned) integers */
}

main(){
  std::string[N] input_array;
  std::string[N] output_array;
  int[N] temp_array;

  //map (translate) colors to their numerical values
  mapString2Color(input_array, temp_array, N);
  //sort it
  sort(temp_array, N);
  //map (translate) the values back to color names
  mapColor2String(temp_array, output_array, N);
}

Answer 3

最初に行うことは、マッピングを作成することです。これは、マップを介して行うか、事前に並べ替えられた文字列の配列を線形に反復し、一致するエントリのインデックスを取得することによって行うことができます。非常に単純な方法 (実際にはデモンストレーション用) は、次のようにロジックをカプセル化された関数にエンコードするだけです。

int intForCol( const string& col ) 
{
    if ( col == "red" ) return 0; 
    else if ( col == "orange" ) return 1;
    else if ( col == "yellow" ) return 2;
    else if ( col == "green" ) return 3;
    else if ( col == "blue" ) return 4;
    else if ( col == "indigo" ) return 5;
    else if ( col == "violet" ) return 6;
    throw "Invalid colour"; 
}

これにより、入力文字列に基づいて順序付け整数が提供されます。次のステップは、コンパレーターを作成することです。

int colComp( const string& lhs, const string& rhs )
{
    return intForCol( lhs ) - intForCol( rhs );
}

これにより、文字列を比較してlhs<の場合は負、 >rhsの場合は正を返すことができます。lhsrhs

これは、STL 内で (連想コンテナー内のコンパレーターとして、またはソート アルゴリズムで直接) 比較的簡単に使用できるようになりました。または、STL を使用することが問題外である場合、またはソートの仕組みを理解することが目的である場合は、以下の単純で (非常に) 非効率的なアルゴリズムのような独自のソートを実装できます。

    const int col_size = 7;
    string input[col_size];
    input[0] = "indigo";
    input[1] = "green";
    input[2] = "red";
    input[3] = "blue";
    input[4] = "yellow";
    input[5] = "violet"; 
    input[6] = "orange";

    // simple bubble sort
    int passes = col_size;
    int last = col_size; 
    while ( passes-- )
    {
        for ( int i = 0; i < last - 1; ++i ) 
            if ( colComp( input[i], input[i+1] ) > 0 )
            {
                string temp = input[i]; input[i] = input[i+1]; input[i+1] = temp;
            }
        last--;
    }