Fast QList search/access

[tryinghard]

Hi all,

i have a list of custom MyObject objects. MyObject has a property QPoint. I need a quick search in list to retrieve those MyObjects that match given QPoint (more precise - have the same x and y).

What i was thinking is using QHash<QPoint, QList<MyObject*>> ... or perhaps other, faster way exist? (many MyObjects can have same QPoints)

Currently data is not very large- arr ound 50 items, but could grow to ~200.

Thanks!

[SixDegrees]

If there are only a few hundred points, you likely won't notice any difference between a simple linear search and a fast, log(n) algorithm like binary search. There just aren't enough comparisons to worry about.

Code it simply first, then identify where you actually need performance improvements. It's hard to imagine this being such a place.

[tryinghard]

It will not be a single search. Rather a search every few second (user moves map, we do search). But ok, i'll try to code, and check Thanks!

[Lykurg]

If it is so often, then you really may work on that. If so, consider to split QPoint into its x and y parameters. So you can possible avoid some look ups/comparisons: (to be improved!)

QHash<int, QHash<int, MyObject*> > data;

QHash<int, QHash<int, MyObject*> > data;

To copy to clipboard, switch view to plain text mode 

[wysota]

I would consider a structure that retains order in x and y separately. So that once you get hold of an interesting area, you get direct access to its neighbourhood. And of course using BSP (binary space partitioning) is also a great option once the amount of data increases.