CListCtrl Item Search Efficiency :: MFC

[kuphryn]

Hello.

I would to know how efficient is an assorted CListCtrl's search feature. In other words, is CListCtrl's find feature efficient when finding random item in a list that is assort? Is it faster than O(n)?

Thanks,
Kuphryn

[Oliver Twesten]

hi kuphryn

I do not know, but since MS obviously tends to use very simple sorting algorithms, it does not seem to be improbable that they also use very simple search algos (=linear search O(n))...

If you fill your list with many items, it would probably be a better approach to use callback items instead of letting the control store the item information (although I've never done it myself).
If you use a STL container for example, you'd have access to the STL find (and sort) algorithms instead of sorting the list itself. I'd be curious if the implementation works flawlessly...

Oliver.

[gstercken]

One solution is FindItem().



Now seriously, CListCtrl::FindItem() doesn't use a search algorithm based on the sorting order. There are various reasons for that:

• You can't only search for an item text, but also for the item's lParam value, a partial text, a position given by x/y coordinates, and combinations of the above. A binary search algorithm taking into account the current sorting would only work for very few of those cases, or have to use multiple internal indexes which would have to be constantly uopdated.
• Sorting is not necessarily done based on the item text, but can also take a user-provided comparision function. In this case, sorting would again not help to optimize the search.
• The item number where searching performance would be a concern is so high that the list control becomes unmanageable anyway. Just try adding 1,000,000 items to a list control - you will see that inserting them will take fairly long (a minute or two), your app will need around 100 MB of memory, but finding an item takes less than a second, regardless of whether the list is sorted or not.

In other words, implementing a binary search (or some other kind of optimized search based on the sorting order)wouldn't have been worth the trouble. However, I suspect they use something like a redundant hash table internally to speed up the search - but in any case, it's independent from sorting.

[kuphryn]

Okay. Thanks.

Kuphryn