Printable View
Hi,
I have a QList which stores objects of type CSignal* ( my own class ). Now wishing I'd used a hashmap for this, but unfortunately didn't, was wondering what is the best way to search through this QList getting the object and seeing if a QString member of the object matches one I'm looking for?
Would I have to just loop through each object in the QList, check the QString and if it matches, then bingo?
Regards,
Steve
Well, the method you describe seems valid to me...but for sure, it would be better to use a QHash or QMap, which are optimized structures for this purpose :)
Yes, in hind sight, I would have used the QHash, but the data structure is used all over the place in the code unfortunately...
Regards,
Steve
The most (and least) efficient way to search for a value in an unsorted list is to just cycle through it, yes.
If you do this very often in your application, you may still want to switch to a hash or tree structure.
Why not just sort the list? If the order of the items in your list is irrelevant but they still have some unique and sortable property, implementing a sorting algorithm on top of the work you've already done might speed things up considerably.
i have a similar problem:
consider a string list. i search for any strings which match a certain pattern,
e.g *abc*. a QHash doesn't help here, sorting doesn't help neither.
how can i find any matching items efficiently?
where can i read about this kind of problem, any good literature?
best regards,
jh
Because at best, sorting is done in O(n log n). Searching for a value in an unsorted list is still only O(n).Quote:
Originally Posted by TheRonin
Perhaps keeping a list sorted at all times by inserting values only in the right location would be different. Then you could use a binary search algorithm, at O(log n). However, inserting a new value would jump from O(1) to O(log n).
Then it seems that keeping the list sorted at all times is the way to go, provided insertions are performed far less frequently than searches.
I think the easiest solution means you're stuck searching linearly through the list. :(Quote:
Originally Posted by jh
The easiest, to be sure. There might be a better way, depending on the pattern you want to search for. If, for example, it's always something like: x* (begins with x) you could still branch on the prefix of the strings. Same thing with *x (ends with x). *x* (contains x), though, would make things a bit more difficult. Except if x is always a fixed distance from the beginning or the end of the string.Quote:
Originally Posted by TheRonin
If you want to search with a variable pattern, you haven't got a hope. :)
I say change the object in the class to a hash and, if it was properly implemented in the first place, you already have a wrapper used to actually access the values in the QList. Now simply rewrite it so that you are utilizing the QHash. Otherwise, write a simple ruby/perl script that goes through all your code and replaces the proper values.
This is the only decent way to approach the problem.
Hi,
I think that a good way to do this is to have the QList sorted by your QString (inserting intems have to be performed manually moving the other items). Then you could try a "dicotomic search" that takes the middle of the QList, compare the values, if the value is minor than the value in the list, you have to get the [0 .. middle-1] QList and do it again until you find th item. If the value is major than the value in the middle of the QList you will take the [middle-1 .. MAX_LIST].
The way to get the QList sorted can be performed by inserting the items sorted when you create them and moving the rest of the objects, or you can perform a sort algoritm like "insertion method", "bubble method", "selection method", ... (I don't know if these are the correct names in english).
I hope it will help you,