4

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.

Improve this question
1
  • 5
    I am very suspicious of this part "sizeof(obj[0].length())" Commented Sep 17, 2012 at 12:40

6 Answers 6

Reset to default
12

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Any indications that this will ever break for a string?
(+1) True. I forgot to mention this in my answer - and it is the most important thing in this case.
@themel Any indications it will never break (except that it "should work" or "works for you")? Knowing that something won't ever break is far better than assuming that something should never break.
Well, it's really "knowing that it won't break because you know how this is implemented in every compiler the asker will ever see" vs "knowing that it won't break because there's a standard that says it won't". Both kinds of knowledge have their uses, but when your program breaks, pointing out that it's a standard violation won't make it run.
@themel I agree about ignoring trivial UB and IB cases, like evil reinterpret_casts, union aliasing or twos-complement integers when the situation requires and allows it, but I won't ever make any assumptions about the implementation of something as abstract as std::string or qsort (which of course shouldn't copy/destroy anything and only shuffle around existing data, but well).
|
11

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

2 Comments

In the implementations I've looked at, std::sort was actually an introsort (which basically is a Quicksort, except that it tracks the recursion depth, and if it goes too deep uses a heapsort instead).
@Jerry Seems my knowledge does not go as far as yours ;)
3

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.

Improve this answer

Comments

0

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);
}
Improve this answer

Comments

-1

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];
Improve this answer

1 Comment

What the...? Ok, at least the code is correct now, at least if you change obj and obj1 to be const std::string**s.
-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;
}
Improve this answer

2 Comments

Indeed: undefined behavior often looks like it "works". And it will continue to work, until you do that critical demo for your most important customer, and then it will fall on its face.
-1 - "works for me" is never a proof of correctness in C++, especially when the UB is as obvious as in this case (and the alternatives are far superior in each aspect).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.