c++ - 使用 qsort 导致段错误

Question

嗯，作为学习C++的一部分，我的项目对它有限制。我不允许使用除基本库之外的任何库，例如 <cstring>和其他一些必需品。

该项目应该从一个包含“n”列字符串的文件中获取输入，并能够根据任何选定列的字典顺序对输出进行排序。例如，给定输入

Cartwright   Wendy    93
Williamson   Mark     81
Thompson     Mark     100
Anderson     John     76
Turner       Dennis   56

它应该按列对它们进行排序。我在 StackOverflow 上的搜索返回了几年前也必须做完全相同项目的其他人的结果哈哈哈 Qsort based on a column in a c-string?

但在我的例子中，我只是为该列使用一个全局变量并继续生活。当我为 qsort 实现比较功能时，我的问题就来了

在我调用的主要方法中

qsort (data, i, sizeof(char*), compare);

其中数据是 char * data[]和 i是要比较的行数。 (在本例中为 5)

下面是比较方法的代码

int compare (const void * a, const void * b){
    char* line1 = new char[1000]; char* line2 = new char[1000];
    strcpy(line1, *((const char**) a));
    strcpy(line2, *((const char**) b));
    char* left = &(strtok(line1, " \t"))[column-1];
    char* right = &(strtok(line2, " \t"))[column-1];
    return strcmp(left, right);
}

1000 是因为我只是概括(并故意编写了糟糕的编码)以过度概括任何行都不会超过 1000 个字符。

让我感到困惑的是，当我在 Eclipse 中使用调试器时，我可以看到它第一次比较成功，然后在第二轮中，当它尝试比较它们时出现段错误。

我还尝试更改将左和右分配给下面内容的代码，但这也无济于事

char* left = new char[100];
strcpy(left, &(strtok(line1, " \t"))[column-1]);
char* right = new char[100];
strcpy(right, &(strtok(line2, " \t"))[column-1]);

请帮助我了解导致此段错误的原因。第一次比较两者时，左 =“Williamson”，右 =“Thompson”。第二次它比较(并尝试崩溃)left = "Cartwright"和 right = "Thompson"

Answer 1

char* line1 = new char[1000]; char* line2 = new char[1000];

这一点都不好。您永远不会释放它，因此每次调用比较函数时都会泄漏 2000 个字节。最终这将导致内存不足的情况，并且 new 将抛出。 (或者在 Linux 上，您的进程可能会被 OOM killer 杀死)。当你可以只说 char line1[1000] 时，它也不是很有效，这是 super 快的，因为它只是从堆栈指针中减去而不是潜在地遍历空闲列表或向内核请求更多内存。

但实际上您可以在不修改或复制字符串的情况下进行比较。例如:

static int
is_end_of_token(char ch)
{
    // If the string has the terminating NUL character we consider it the end.
    // If it has the ' ' or '\t' character we also consider it the end.  This
    // accomplishes the same thing as your strtok call, but WITHOUT modifying
    // the source buffer.
    return (!ch || ch == ' ' || ch == '\t');
}

int
compare(const void *a, const void *b)
{
   const char *strA = *(const char**)a;
   const char *strB = *(const char**)b;

   // Loop while there is data left to compare...
   while (!is_end_of_token(*strA) && !is_end_of_token(*strB))
   {
      if (*strA < *strB)
         return -1;      // String on left is smaller
      else if (*strA > *strB)
         return 1;       // String on right is smaller
      ++strA;
      ++strB;
   }

   if (is_end_of_token(*strA) && is_end_of_token(*strB))
      return 0;    // both strings are finished, so they are equal.
   else if (is_end_of_token(*strA))
      return -1;   // left string has ended, but right string still has chars
   else
      return 1;    // right string has ended, but left string still has chars
}

但最后......你说你正在使用 std::string 吗？好吧，如果是这样的话，那么假设传递给 qsort 的内存与“const char **”兼容就有点奇怪了，我希望它会崩溃。从这个意义上说，也许你应该做这样的事情:

int compare(const void *a, const void *b)
{
    const char *strA = ((const std::string*)a)->c_str();
    const char *strB = ((const std::string*)b)->c_str();

    // ...
}

但实际上，如果您使用的是 C++ 而不是 C，您应该使用 std::sort。