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

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 2

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