How to compare C++ string using qsort in c?

Question

I tried to learn the qsort function of the c-library stdlib. This is provided even in c++. But i dont understand how to use them for sorting c++ strings. I am not sure of what the parameters should be for the sizeof() operator and whether my compare_str code is right. I tried this code:

    #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;
    }

My output was:

ppoq
tri
get
fine

I am not able to make out the error. Please help.

Answer 1

Works for me:

#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;
}

Answer 2

You cannot and must not use qsort on an array of std::strings. The elements must be of trivial type, which strings are not, and thus the behaviour is undefined. From 25.5/4 ("qsort"):

The behavior is undefined unless the objects in the array pointed to by base are of trivial type.

The reason is that qsort will memcpy the array elements around, which is not possible for C++ objects in general (unless they're sufficiently trivial).

---

If you do have a trivial type, you can use this generic qsorter-comparator (but of course this is a terrible idea, and the inlined std::sort is always preferable):

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;
}

Use: T arr[N]; qsort(arr, N, sizeof *arr, qsort_comp<T>);

Don't use this. Use std::sort instead.

Answer 3

Better be C++ oriented and use std::sort for your array:

#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 uses quick sort.

[UPDATE] See comments, std::sort is not always pure quick sort.

[UPDATE2]

If you want to learn qsort - change std::string to const char* and define function based on strcmp. Remember that qsort passes pointers to elements in an array - so dereference const void* to get const char*. See:

#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"));
}

Answer 4

Your error is in the declaration of the size in qsort. What is expected is the size of a member, which is, in your case, a string. So you want to use:

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

However, you need to work with pointer to string, rather than strings themselves. Then, the code should look like:

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];

Answer 5

The problem is that you give qsort an array of C++ strings. In your comparison function, you seem to except C strings, since you cast them to (const char*).

Also, the third parameter of qsort, the size of data, you actually give wrong value. sizeof(obj[0].length()) will result in sizeof(size_t), which is obviously wrong. sizeof(obj[0]) would be more correct, but remember that qsort won't call copy constructor of string, which might lead to problems.

I would suggest not to use qsort with C++ strings.

See answer provided by PiotrNycz for correct solution.

Answer 6

You should use the std::sort template function provided by the C++ standard library (in the <algorithm> header file). By default, std::sort uses the less than comparison operator to order elements (std::string already implements operator<). If you need to specify an ordering condition (for example, case insensitive string compare), std::sort allows you to specify an ordering function object.

Example:

#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);
}