[Dworza]

hello colleagues,
I want to sort and array of instances of a struct via qsort, but I'm really helpless yet... :-/ For two days I was trying to follow some tutorials, nevertheless I wasn't successful

I would really appritiate, if someone would be so nice and would look at my code and show me, how it shall be coded to work... I want simply sort the personArr by the property name.

PS:I can use only those includes

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;

class CPhoneBook
{

public:
    struct item
    {
        string name;
        string address;
        string phone;
    } ITEM;

    int k;
    item* personArr;
    CPhoneBook (void);
    ~CPhoneBook (void);

    bool Add ( const string & name, const string & address, const string & phone )
    {
        item i ;
        i.name=name;
        i.address=address;
        i.phone=phone;
        personArr[k++]=i;
        sort();
        return true;
    };

    void sort()
    {  
     //here I want to sort personArr
     }

    bool Del ( const string & name, const string & address )
    {
        return true;
    };
    bool Search ( const string & name, const string & address, string  & phone ) const
    {
        return true;
    };
};

CPhoneBook::CPhoneBook ()
{
    personArr = new item[1000];
    k=0;
}

CPhoneBook::~CPhoneBook ()
{
    delete []personArr;
}

int main ()
{
    CPhoneBook rect;
    rect.Add("a1","z2","z3");
    rect.Add("x1","z2","z3");
    rect.Add("0y","2","3");
    rect.Add("z1","z2","z3");
}

The faster, the better....the deadline is close...thanks for any help..

[jimblumberg]

Is there a reason you are using an array of item instead of a vector of items? Is qsort() an actual requirement or can you use std::sort?

Jim

[JackOfAllTrades]

An example of qsort and struct.

[Dworza]

@jimblumberg: As I wrote there, I can't include nothing more than I've already included, thus I can't use vector. I would like to use sort. But do you think, that std::sort is also possible?

@JackOfAllTrades: I've already seen it, I'm really hopeless now, cuz I don't know how to implement it to my code...

[jimblumberg]

If you can't include anything else then no you can't use std::sort. Post the code where you tried to sort your array. Also post the complete error messages exactly as they appear in your development environment.

Jim

[Aphex19]

Are you sure that you've exhausted all possible resources which might help you implement quick sort? Googling "qsort tutorial", I found this tutorial posted on dreamincode.net which may help you. There's so many tutorials, code exampled and more out there though, surely you could come up with something.

[r.stiltskin]

If you want to use qsort to sort your array of structs, the first step is to write a function that can tell qsort how to order your structs. (That type of function is called a comparator function.)

This tutorial uses an array of int as its example, so they wrote a compare function that compares two ints. You have to write a similar compare function that compares two ITEM objects instead.

We can't show you what you did wrong since you haven't shown us what you did, and we won't write it for you.

This post has been edited by r.stiltskin: 24 March 2012 - 03:34 PM

[JackOfAllTrades]

It's rather simple.

qsort is a "generic" function, to sort any kind of data, so it takes as an argument a function capable of comparing two generic datatypes, which takes two const void * arguments. The use of const void * arguments allows any type of data to be passed to the function.

Within the function you "unpack" the passed data into their actual types for comparison. For example, if you wanted to compare two ints, it would look like this:

int fnCompare(const void *l, const void *r)
{
    // Can't dereference a void pointer; it must have a type, 
    // so cast it to an int *, then dereference
    int lhs = *(int *) l;
    int rhs = *(int *) r;
  
    
    return lhs - rhs;
}

You return whether the value on the left is less than the value on the right, equal to it, or greater than it.

When you use a struct, you just have to decide what struct member you're going to use to compare.

[Dworza]

As I've already said - I tried two days to find out, how to implement it, but I wasn't able to fix the errors :-/ I think, that the main problem is not, that I would not understand, how it works, but the main problem is a poor level of my C++ skills... As a longtime java and C# programmer, who just started with C++, I'm really, really confused with this language. :-S

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
class CPhoneBook
{
public:

    struct item
    {
        string name;
        string address;
        string phone;
    };
    int size ;
    item* itemArr;
    int itemCount;

    CPhoneBook (void);
    ~CPhoneBook (void);

    bool Add( const string & name, const string & address, const string & phone );
    bool Del ( const string & name, const string & address );
    bool Search ( const string & name, const string & address, string & phone );
    void resize()
    {
        item* resize_arr = new item[itemCount * 5];
        for(int i = 0; i < itemCount; i++)
            resize_arr[i] = itemArr[i];
        itemCount++;
        itemArr = resize_arr;
        delete[] resize_arr;
    };
    void sort();
    int struct_cmp_by_name(const void *a, const void *B)/>;
};

CPhoneBook::CPhoneBook (void)
{
    size=1000;
    itemArr=new item[size];
    itemCount=0;
}

CPhoneBook::~CPhoneBook ()
{
    delete []itemArr;
}

bool CPhoneBook::Add(const string & name, const string & address, const string & phone)
{
    itemArr[itemCount].name = name;
    itemArr[itemCount].address = address;
    itemArr[itemCount].phone = phone;
    itemCount ++;
    sort();
    return true;
}

void CPhoneBook::sort()
{
    size_t structs_len = sizeof(item) / sizeof(itemArr);
    // error:
    // D:\main.cpp|85|error: expected primary-expression before ',' token|
    qsort(item, structs_len, sizeof(itemArr), struct_cmp_by_name);

}

int struct_cmp_by_name(const void *a, const void *B)/>
{
    // error:
    // D:\main.cpp|91|error: forward declaration of 'struct itemArr'|
    struct itemArr *ia = (struct itemArr *)a;
    struct itemArr *ib = (struct itemArr*)b;
    // error:
    // D:\main.cpp|93|error: invalid use of incomplete type 'struct itemArr'|
    return strcmp(ia->name, ib->name);
}

bool CPhoneBook::Del(const string & name, const string & address)
{
    return true;
}

bool CPhoneBook::Search(const string & name, const string & address, string & phone)
{
    return true;
}

};


int main(void)
{
    CPhoneBook rect;
    rect.Add("a1","z2","z3");
    rect.Add("x1","z2","z3");
    rect.Add("0y","2","3");
    rect.Add("z1","z2","z3");
}

This post has been edited by Dworza: 24 March 2012 - 04:09 PM

[r.stiltskin]

In this function

int struct_cmp_by_name(const void *a, const void *B)/>
{
    //...

a and b are going to be two void* pointers pointing to ITEM objects. So you cast them to struct item like this:

struct item ia = *(struct item*)a;

CPhoneBook::item ia = *(CPhoneBook::item*)a;

or, alternatively, just cast the pointers like this

struct item *iap = (struct item*)a;

CPhoneBook::item *ia = (CPhoneBook::item*)a;

edit: For some strange reason I was thinking in C when I wrote that originally. Corrected it.

This post has been edited by r.stiltskin: 24 March 2012 - 07:44 PM

[JackOfAllTrades]

Which is complicated by the fact that struct item is nested within the class. Which means the comparator function needs to be a member (which you actually declared it as), and in addition it must be static, and thus passed to qsort as &CPhoneBook::struct_cmp_by_name

EDIT: And, because itemArr is a pointer, you cannot use sizeof on it; you need to use the itemCount variable.

[#define]

JackOfAllTrades, on 25 March 2012 - 01:35 AM, said:

Which is complicated by the fact that struct item is nested within the class. Which means the comparator function needs to be a member (which you actually declared it as), and in addition it must be static, and thus passed to qsort as &CPhoneBook::struct_cmp_by_name

I was thinking a friend function would work ok, but haven't tried it.

[r.stiltskin]

My post #10 was wrong because I was thinking C when I wrote it -- I wonder why -- maybe because I was looking at "qsort" and "strcmp" at the time... I edited it so it's sane now.

The comparator function can't be a member function of the class because then it won't satisfy the required signature

int (*)(void *, void *)

but it doesn't have to be a friend since item is a public member of CPhoneBook, and item is a struct so all of its members are public as well. But the declarations of the local variables in the comparator need a scope qualifier.

The only other error in struct_cmp_by_name was the attempted use of strcmp to compare two std::strings -- obviously that can't work.

So, take the declaration of struct_cmp_by_name out of the CPhoneBook class definition and place it before the class definition.

Then take this

int struct_cmp_by_name(const void *a, const void *b)
{
// the following are wrong because they are trying to declare a new type "struct itemArr"
//    struct itemArr *ia = (struct itemArr *)a;
//    struct itemArr *ib = (struct itemArr*)b;
// You need to cast the void* to an item*, but item is defined inside CPhoneBook, so...
    CPhoneBook::item *ia = (CPhoneBook::item*)a;
    CPhoneBook::item *ib = (CPhoneBook::item*)b;


// The following is wrong because name is a std::string, not a c_string
    return strcmp(ia->name, ib->name);
}

Fix the last line of that function and you will be "good to go".

Oh, you'll also have to fix the qsort call inside your sort() function which is about 3/4 wrong -- I'll let you ponder that one: read the compiler error message and qsort documentation.

This post has been edited by r.stiltskin: 24 March 2012 - 08:12 PM
Reason for edit:: I keep forgetting to turn off the damn emoticons