|
Hi folks,
Need some serious help here. May i know how i can perform a qsort on a list of class objects I created using CList ?
I've been refering to Dr. Newcomer article on Sorting for assistance..but guess i'm pretty amateur to really understand the full concept.
Suppose I create a linked list of data type matchData called ResultList...
class matchData {
public:
matchData(CString ="", double = 0, double =0, double =0, int=0); //constructor
//set functions
void setMatchData(CString, double,double,double,int);
CString getModelName();
double getNum1();
double getNum2();
~matchData(); //destructor
private:
CString modelName;
double num1;
double num2;
int x;
};
typedef CList<matchdata*,matchdata*> matchList;
matchList Result;
how can i proceed on to qsort my Result list (assuming the list is not empty) based on num1 followed by num2? Do I have to create another class say Finalresult and put in a private data matchList inside the class ?
Please help...
Thanks alot!
|
|
|
|
|
do not know why i can't modify my message abv..
just a further clarification
My Result (list) is declared as below.
typedef CList<matchData*,matchData*> matchList;
matchList Result;
Thanks.
|
|
|
|
|
You need to provide a function for qsort to use that will compare the required fields of the objects that you want to sort by, ie, if you want to sort by num1 then the compare function would be comparing those fields and returning the result
HTH
btw the CList will be storing pointers to your objects so the compare function will be receiving 2 pointers in
|
|
|
|
|
The problem is that CList (or any linked list for that matter) doesn't lend itself well to the C runtime library's qsort() routine. qsort basically sorts an array in place, swapping entire array entries if necessary. So you first have to guarantee that all items to be sorted are in one contiguous memory block. The CList class doesn't make this guarantee.
Secondly, qsort doesn't care about the links to neighboring items. It'll just move them around blindly as it moves the object (and doesn't notify you when it does so). If qsort() moves an item referenced by another item's neighbor link, then that link is no longer valid, since it doesn't point to the original neighbor anymore. qsort doesn't care about maintaining these links...it just swaps objects blindly.
So qsort() is basically a crappy choice for linked lists.
If you're determined to use qsort(), then you'll most likely have to abandon CList as your container type in favor of something that provides a reliable array that qsort can operate on. This means that you must be sure that all elements of the array occupy one contiguous memory block. I don't think even CArray guarantees that (if you're also determined to use an MFC collection type).
So here are some things to think about if you *must* use qsort:
- If you know the maximum size the list will reach, then you can simply create a single array of that size and populate it as your program runs. You'll have to make sure to clean up "holes" when items are removed (by sliding later elements backward to fill the vacancy). This will guarantee that all sortable items will be in one contiguous block. New items get added to the end, and the list is sorted as new items are added.
- If you don't know the list's maximum size, then you'll need to develop your own resizable array class that guarantees that all items are in one contiguous memory block. The array should be able to grow (and shrink) when needed, but must always guarantee congiguous memory for qsort.
If qsort() isn't a requirement, though, then you can consider some other means of sorting the list. Linked lists, though, don't sort too well, since you can really only sort them sequentially.
However, if you're application is using num1 and num2 (and maybe x) to reference some unique CString (modelName), then you may want to consider using the CMap class instead. CMap is basically a hash table, which lends itself well to this sort of application (mapping some key value or values to a unique item). If you can provide a means to provide a unique "key" value by combining num1 and num2, you can use that key value as an index into the CMap to select the string (or entire matchData object).
For example, if you know that num1 and num2 will never exceed 10,000, then you can define your "key" value for the CMap as follows:
<br />
double CalculateKey(double num1, double num2) <br />
{ <br />
return( num1 * 10000 + num2 );<br />
}<br />
Define your CMap as follows:
<br />
typedef CMap<double, double, matchData *, const matchData *> matchList;<br />
matchList Result;<br />
Then adding a new matchData item to the list is simple:
<br />
matchData *pdataToAdd;<br />
...<br />
...<br />
double key = CalculateKey(pdataToAdd->GetNum1(), pdataToAdd->GetNum2());<br />
Result[key] = pDataToAdd;<br />
Locating an item is also simple:
<br />
double num1ToFind, num2ToFind;<br />
matchData * pfoundData;<br />
...<br />
...<br />
double key = CalculateKey(num1ToFind, num2ToFind);<br />
BOOL bFound = Result.Lookup(key, pfoundData);<br />
if( bFound )<br />
{<br />
}<br />
else<br />
{<br />
}<br />
Note that you can't use the [] operator when searching for an item. Check out the documentation for CMap over at the MSDN site. Here's the documentation for CMap
I sure hope all this helped, and good luck!!
Bob Ciora
|
|
|
|
|
Hi thanks for the replies so far. I'm aware of qsort requirement and about pointers for the comparison function.
Basically the list maximum size is not determined, but with a minimum of over hundred of matchData nodes. My intention is basically to hold matching data for an input against many models. However,the number of models may differ differently based on my experimental conditions.
My ultimate aim is to perform a multi-level sort on a linked list of matching results based on each node value, say on num1 followed by num2 if they are e same. I'm hoping to improve the overall speed by using quick sort. Thus frm the best result(top of list), i would retrieve what is the model file (my modelname).
I have looked into CMap, but I don't see the need for a hashvalue lookup cos my matchresult will differ for each model against different inputs.
Thus qsort is not a must, but apparently seems that itz one of e few choices that i can do. And also perphaps after studying e Sorting Article http://www.flounder.com/sorting.htm[^] with gives me e notion for it.
I'm still in e process of writting the codes. So not too sure if the end result will turn out fine..
What i'm current doing is i did another abstraction called Class SortedList where i've e sort function in it,which basically copies e content to a CArray and qsorts it.
I'm not too sure if i understand correctly but seems that the pointers are being sorted so in actual fact my original list node remains..
Or is there any better suggestion for my approach? Tks alot!
|
|
|
|
|
If you use the STL std::list container instead of CList, you can use the built-in sort() function.
|
|
|
|
|
The std::list container doesn't seem to have a way to locate an item in the list
Bob Ciora
|
|
|
|
|
Use the STL algorithm find() , it works on all STL containers.
|
|
|
|
|
Maybe a further clarification of the problem is in order. It sounds sort of like an axis sort, but I'm not sure...
- In what way do you specify uniqueness of the objects? For example, is modelName unique for each entry in the list or can multiple objects have the same modelName ?
- If modelName is unique across all entries in the list, can multiple objects exist at the same (num1,num2) position? Or is this the condition you're trying to prevent?
Bob Ciora
|
|
|
|
|
Is it possible to get the address of a character array and assign it to an int?
The following code doesn't compile because testptr should be "char * testptr".
#include "stdafx.h"
int main(int argc, char* argv[])
{
char test[10] = "hello";
int testptr=0;
testptr = &test;
return 0;
}
|
|
|
|
|
You can get the raw value of a pointer by casting it to an unsigned integral type that is the same size as a pointer. In MSVC this is unsigned , although in Windows code you should use DWORD_PTR instead for Win32/64 compatibility.
--Mike--
LINKS~! Ericahist | 1ClickPicGrabber | CP SearchBar v2.0.2 | C++ Forum FAQ | You Are Dumb
Magnae clunes mihi placent, nec possum de hac re mentiri.
Strange things are afoot at the U+004B U+20DD
|
|
|
|
|
Thanks for the tip, I'm actually using ILE C on an AS/400.
But I was testing this concept using vc++.
I didn't even think about the fact that int is signed.
Now the bad news, works great in vc++, didn't work on the 400. It compiles and runs, but the value isn't correct.
I might experiment with casting it into some other types and see what happens.
Thanks,
Erik
|
|
|
|
|
You can't assume that a pointer fits in an int or even unsigned int . You must find out which integral type in your C implementation is large enough to hold a pointer. Try printing the value of sizeof(void *) .
|
|
|
|
|
i want to create a MFC app. which can use ms-dos commands
i have to use which functions,etc..?
and sorry about my english
|
|
|
|
|
|
thanks!!
|
|
|
|
|
Didn't there used to be a link to that faq on the forum somewhere?
Or is it still there, and i'm blind...
Shog9
I'm not the Jack of Diamonds... I'm not the six of spades.
I don't know what you thought; I'm not your astronaut...
|
|
|
|
|
|
THere used to be a link at the top of the page when you were viewing the VC forum, but it hasn't been there for a while. I keep a link to it in my .sig though.
--Mike--
LINKS~! Ericahist | 1ClickPicGrabber | CP SearchBar v2.0.2 | C++ Forum FAQ | You Are Dumb
Magnae clunes mihi placent, nec possum de hac re mentiri.
Strange things are afoot at the U+004B U+20DD
|
|
|
|
|
Well, that's one thing i haven't hallucinated today at least. Any idea why it was removed?
Shog9
I'm not the Jack of Diamonds... I'm not the six of spades.
I don't know what you thought; I'm not your astronaut...
|
|
|
|
|
|
|
In my app there is an assumption that
After selecting a folder , i need to grab the one and only .xml file and parse it .
With the help of u code gurus I was able to get the folder path for the file .
Now I will not know the name of the .xml file(contained within that folder) to parse
What is the best way to
1) Make sure that there is only one file of that extension in the folder
Something like : "where count of *.xml files equals 1 "
2) Be able to get the name of the file .
|
|
|
|
|
try something like this:
WIN32_FIND_DATA FileData;
HANDLE hFind = NULL;
if (hFind = FindFirstFile("c:\\temp\\*.xml", &FileData))
{
CString filename = FileData.cFileName;
etc
FindClose(hFind);
}
Image Toolkits | Image Processing | Cleek
|
|
|
|
|
hi
In mfc way
CFileFind fFind;
BOOL bMoreFile;
bMoreFile = fFind.FindFile("C:\\YourFolder\\*.xml");
if ( bMoreFile == FALSE )
{
// no files
}
else
{
fMore = fFind.FindNextFile();
if ( fMore == FALSE )
{
// means there is only one file.
CString sFilename = fFind.GetFileName();
}
else
// can be more files
}
Hope this helps
Jetli
conclusion means Coming to wrong Decision with confidence
|
|
|
|