c++ - 对字符串数组进行自定义排序

Question

给定一个包含彩虹七种颜色但以随机顺序排列的字符串数组，我应该以某种方式对该数组进行排序以按该顺序输出红色、橙色、绿色、....、紫罗兰色。彩虹颜色的顺序。如何对这个数组进行排序？

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

好的，请不要马上投反对票。我知道这是一个不好的例子。我写它是因为 OP 专门要求一个非 STL 解决方案，并展示它（坏）会/可能会是什么样子。

好吧，你去。代码未完成。但是您应该了解总体思路。我跳过的一件事是整数本身的排序。因为它应该是微不足道的。如您所见，映射有点 PIA，看起来很糟糕。但是由于您禁止使用 STL，因此没有std::map. 此外，我暗示所有表的静态大小N。可以动态分配，没问题，也没有std::vector。

我使用else ifsmap*来模仿std::map功能。可能switch ... case可以使用，但它应该在一个体面的编译器上工作几乎相同。

我在下面编写的代码在提供的功能方面与 Armen 的代码几乎相同。我会推荐他的解决方案。我跳过了相同的部分。所以你可以看到它更丑，打字更多。它看起来几乎像纯 C。如果您真的渴望在非常大的情况下实现速度，也许可以进行一次修改。那将使用一个临时数据结构来保存映射值，对其进行排序，然后将其映射回来。确切地说，我建议避免在高性能约束下调用map::operator[](const &T)（或任何访问器）以避免散列计算。std::string但仅此而已。

还有一些要讨论的。就像您希望两种颜色具有相同的值或使用非整数权重一样。基于 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 );
}

这将允许我们将字符串一起比较返回负 if lhs<rhs和正 if lhs>rhs

现在可以在 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--;
    }