4

我试图学习 c-library 的 qsort 功能stdlib。这甚至在c++. 但我不明白如何使用它们对c++字符串进行排序。我不确定sizeof()操作员的参数应该是什么以及我的compare_str代码是否正确。我试过这段代码：

    #include<iostream>
    #include<cstdlib>
    using namespace std;
    #include<string>

    int compare_str( const void *a, const void *b){
       string  obj = (const char*)a;
       string obj1 = (const char*)b;
       return obj.compare(obj1);
    }
    int main(){
        string obj[4] = {"fine", "ppoq", "tri", "get"};
        qsort(obj, 4, sizeof(obj[0].length()), compare_str);
        for( int i=0; i<4; i++)
            cout<<obj[i]<<endl;
        return 0;
    }

我的输出是：

ppoq
tri
get
fine

我无法找出错误。请帮忙。

4

6 回答 6

11

您不能也不得qsort在 s 数组上使用std::string。元素必须是普通类型，而字符串不是，因此行为未定义。从 25.5/4（“qsort”）开始：

除非指向的数组中的对象base是普通类型，否则行为是未定义的。

原因是周围qsort的memcpy数组元素，这对于一般的 C++ 对象是不可能的（除非它们足够微不足道）。

如果你确实有一个平凡的类型，你可以使用这个通用的 qsorter-comarator （但当然这是一个糟糕的想法，并且内联std::sort总是更可取的）：

template <typename T>
int qsort_comp(void const * pa, void const * pb)
{
    static_assert<std::is_trivial<T>::value, "Can only use qsort with trivial type!");

    T const & a = *static_cast<T const *>(pa);
    T const & b = *static_cast<T const *>(pb);

    if (a < b)  { return -1; }
    if (b < a)  { return +1; }
    return 0;
}

采用： T arr[N]; qsort(arr, N, sizeof *arr, qsort_comp<T>);


不要使用这个。改为使用std::sort。

于 2012-09-17T12:42:37.947 回答
9

最好是面向 C++ 并为您的数组使用 std::sort ：

#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>

int main() {

   std::string obj[4] = {"fine", "ppoq", "tri", "get"};
   std::sort(obj, obj + 4);
   std::copy(obj, obj + 4, std::ostream_iterator<std::string>(std::cout, "\n"));
}

AFAIK -std::sort使用快速排序。

[更新] 见评论，std::sort 并不总是纯粹的快速排序。

[更新2]

如果您想学习 qsort - 更改std::string为const char*基于strcmp. 请记住， qsort 将指针传递给数组中的元素 - 所以取消引用const void*get const char*。看：

#include <stdlib.h>
#include <string.h>

int compare_cstr(const void* c1, const void* c2) 
{ 
   return strcmp(*(const char**)(c1), *(const char**)(c2)); 
}

int main() {

   const char* obj[4] = {"fine", "ppoq", "tri", "get"};
   qsort(obj, 4, sizeof(obj[0]), compare_cstr);
   std::copy(obj, obj + 4, std::ostream_iterator<const char*>(std::cout, "\n"));
}
于 2012-09-17T12:41:55.953 回答
3

问题是您给 qsort 一个 C++ 字符串数组。在您的比较函数中，您似乎排除了 C 字符串，因为您将它们转换为 (const char*)。

另外，qsort 的第三个参数，数据的大小，你实际上给出了错误的值。sizeof(obj[0].length()) 会导致sizeof(size_t)，这显然是错误的。sizeof(obj[0]) 会更正确，但请记住 qsort 不会调用字符串的复制构造函数，这可能会导致问题。

我建议不要将 qsort 与 C++ 字符串一起使用。

请参阅 PiotrNycz 提供的答案以获得正确的解决方案。

于 2012-09-17T12:43:07.573 回答
0

您应该使用std::sortC++ 标准库（在<algorithm>头文件中）提供的模板函数。默认情况下，std::sort使用小于比较运算符对元素进行排序（std::string已实现operator<）。如果需要指定排序条件（例如，不区分大小写的字符串比较），std::sort允许指定排序函数对象。

例子：

#include <string>
#include <algorithm>

bool caseInsensitiveOrdering(const std::string& lhs, const std::string& rhs)
{
   // return true if lowercase lhs is less than lowercase rhs
}

int main()
{
    std::string names[] = {"chuck", "amy", "bob", "donna"};
    size_t nameCount = sizeof(names) / sizeof(names[0]);

    // Sort using built-in operator<
    std::sort(names, names + nameCount);

    // Sort using comparison function
    std::sort(names, names + nameCount, &caseInsensitiveOrdering);
}
于 2012-09-17T12:47:21.357 回答
-1

您的错误在于qsort. 预期的是成员的大小，在您的情况下，它是一个字符串。所以你想使用：

qsort(obj, 4, sizeof(string), compare_str);

但是，您需要使用指向字符串的指针，而不是字符串本身。然后，代码应如下所示：

int compare_str( const void *a, const void *b){
   const string*  obj = (const string*)a;
   const string* obj1 = (const string*)b;
   return obj->compare(*obj1);
}

// ...

string* obj[4] = { new string("fine"), new string("ppoq"),
                   new string("tri"), new string("get") };
qsort(obj, 4, sizeof(string*), compare_str);
// And delete the objects
for(int i = 0 ; i < 4 ; ++i) delete obj[i];
于 2012-09-17T12:43:36.987 回答
-1

为我工作：

#include<iostream>
#include<cstdlib>
using namespace std;
#include<string>

int compare_str( const void *a, const void *b){
   string* obj = (string*)a;
   string* obj1 = (string*)b;
   return obj->compare(*obj1);
}
int main(){
    string obj[4] = {"fine", "ppoq", "tri", "get"};
    qsort(obj, 4, sizeof(string), compare_str);
    for( int i=0; i<4; i++)
        cout<<obj[i]<<endl;
    return 0;
}
于 2012-09-17T12:44:42.673 回答