1

I am using qsort to sort an array of string in c++. My code is as follows:

#include <iostream>
#include <cstdlib>
using namespace std;
int CompareString( const void * e1, const void * e2) {
    string * s1 = (string * ) e1;
    string * s2 = (string * ) e2;
    if( *s1 < *s2 )     return -1;
    else if( *s1 == *s2 ) return 0;
    else if( *s1 > *s2 ) return 1;
}
int main() {
    string Array[4] = {"hehe","789","456","123"};
    qsort(Array,4,sizeof(string),CompareString);
    for( int i = 0;i < 4;++i )
        cout << Array[i] << endl;
    return 0;
}

But it receive runtime error. I do know that sort in works, but I want to know Why I can not use qsort. Thanks :)

This question is similar to This Question But there are some differences. In that question, people suggested using sort instead, or using qsort on trivial types. However, my question is I have to use qsort instead of sort, so my question is not addressed in that question, And I do not consider my question as duplicates.

As to why I have to use qsort instead of sort, the answer is "this is the requirement of the assignment", the link is:Here. I translate the original question as follows:

Implement MyString class, which inherits std:string, and the code should compile and run correctly with the following code:

MyString SArray[4] = {"big","me","about","take"};
qsort(SArray,4,sizeof(MyString), CompareString);
for( int i = 0;i < 4;++i )
    cout << SArray[i] << endl;

MyString should be something like:

class MyString:public string{
...
};

This original question requires MyString to pass other tests, which I have passed already. But I still can not pass qsort, So I adapted it and asked my first-version quesion.

From the answers, I can conclude that qsort do not work with non-POD. Since MyString inherits string, and string is non-POD, so MyString is non-POD, therefore MyString can not pass the tests.

Thank you all for answering my question :)

Improve this question
5
  • 1
    sizeof(string) looks suspicious to me. It means that the algorithm will assume that objects are POD (no C++). Turn string into const char * that will probably work. Commented Nov 5, 2016 at 14:32
  • 2
    Undefined behaviour because std::string is not guaranteed to work with qsort. Read the answers to this question: stackoverflow.com/questions/6174955/… Commented Nov 5, 2016 at 14:37
  • 1
    Use std::sort. qsort is nasty old C. <g> Commented Nov 5, 2016 at 14:42
  • Actually I do wish I could use sort, but due to some reasons, I have to use qsort. Commented Nov 5, 2016 at 14:56
  • I wonder why can you use std::string, std::vector and other standard C++ components but not one of the standard algorithmis. Commented Nov 5, 2016 at 15:53

3 Answers 3

Reset to default
2

In order to rearrange and move C++ classes inside an array, the class's copy/move constructors, and/or assignment operators must be used. qsort() is a C library function that knows nothing about a std::string, or any other C++ class, its constructor, or destructor. qsort() cannot be used to sort a vector of non-POD classes.

Use std::sort() to sort your vector, instead.

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

5 Comments

Of course, instead of directly sorting the array of std::strings, one may sort an array of pointers or indices to the first.
I thought qsort knows pointers, and our compareString can compare two strings correctly. So qsort do not need to care about what "string" is. It can just treat it as something like an unknow struct in c. Since we compare using our own-written function compareString, qsort just need to swap two strings using the two pointers, Is that impossible in c?
@Casualet yes, this is impossible in C because std::string must be swapped using its copy or move constructor and assignment operator, and C cannot do this.
Re: "must be swapped using its copy or move constructor and assignment operator": why exactly? Why the swapping cannot be done on a raw bytes of size size?
Because if, for example, an object has a pointer that points to one of its member, blindly copying the raw bytes results in nonsense. By definition, the pointer in the object's new location still points to the old one. Hilarity ensues.
2

C's qsort can't move non-POD objects around. But it can move pointers around. So if you absolutely have to use qsort to sort an array of std::string, you can do it by sorting a corresponding array of pointers:

#include <iostream>
#include <string>           // std::string
#include <vector>           // std::vector
#include <stdlib.h>         // qsort
using namespace std;

auto compare( void const* e1, void const* e2 )
    -> int
{
    string const* const p1 = *reinterpret_cast<string* const*>( e1 );
    string const* const p2 = *reinterpret_cast<string* const*>( e2 );
    return p1->compare( *p2 );
}

template< size_t n >
void sort( string (&a)[n] )
{
    vector<string const*> pointers;
    pointers.reserve( n );
    for( string& item : a ){ pointers.push_back( &item ); }
    qsort( &pointers[0], n, sizeof( pointers[0] ), compare );
    vector<string> result;
    result.reserve( n );
    for( string const* p : pointers ) { result.push_back( move( *p ) ); }
    for( int i = 0; i < int( n ); ++i ) { a[i] = move( result[i] ); }
}

auto main()
    -> int
{
    string strings[4] = { "hehe", "789", "456", "123" };
    sort( strings );
    for( string const& s : strings )
    {
        cout << s << endl;
    }
}
Improve this answer

Comments

1

Your code

string Array[4] = {"hehe","789","456","123"};

produces 4 strings, not 4 pointers to string, the sizeof(std::string) should be 3*sizeof(void *)+some constant if your implementation is using SmallStringOptimization.

Trying my skill at mindreading I would guess your thinking that Array is pointers to strings or string itself is a pointer.

String was originally declared something like this (if you remove all the template stuff).

class string {
  size_t length;
  size_t capacity
  char *buffer;
};

If you had declared your Array 

std::string *Array[4] = {
  new std::string("hehe"),
  new std::string("789"),
  new std::string("456"),
  new std::string("123")
};

It would work.

You can see the whole code here

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.