How to insert a large number of items into a treeview efficiently

re: How to insert a large number of items into a treeview efficiently

JA — Thu, 01 Dec 2011 14:35:15 GMT

And this is why I am burning out on Windows programming, having to know minutia such as this in order to excel is getting old.

re: How to insert a large number of items into a treeview efficiently

.dan.g. — Tue, 29 Nov 2011 22:43:47 GMT

Thanks Raymond, I implemented your suggested solution (requiring changes to 6 lines of code) and whatever the speed benefits are it's got to be better than nothing!

re: How to insert a large number of items into a treeview efficiently

KS — Tue, 29 Nov 2011 15:51:46 GMT

@Raymond: You have only 6 Favorites? Good for you. The average user has a few hundred (not tens of thousands, of course), sometimes organized in several folder levels. Now imagine what happens in a combobox with all that expanded ...

[I have plenty of favorites. But the combo box in question doesn't show all the favorites; only the folders. And I organize my favorites into just 6 folders. If you created hundreds of folders to organize your favorites, then you've basically said "You know what, I like seeing hundreds of things at once - bring it on!" -Raymond]

re: How to insert a large number of items into a treeview efficiently

Adrian — Mon, 28 Nov 2011 21:33:52 GMT

When writing a backwards counting loop, you have to be careful if your loop index is unsigned. As more programmers use STL containers, which use std::size_t for size(), it becomes more common for indexes to be unsigned types. A downward counting loop is a tad safer written as:

for (i = array.Count(); i > 0; ) {

--i;

// loop body here

}

This idiom works whether the index is signed or unsigned.

re: How to insert a large number of items into a treeview efficiently

Kelden — Mon, 28 Nov 2011 15:00:21 GMT

In VB6, you can insert 50k items in about 1 second. But if you try to close the window, it takes about 25 seconds to destroy the window.

re: How to insert a large number of items into a treeview efficiently

Mehrdad — Sun, 27 Nov 2011 19:18:06 GMT

Cool post!

But why is it _slower_ to destroy the window afterward, if you insert things backward?

[The order of insertion should have no effect on destruction performance. The treeview doesn't remember what order you inserted them. -Raymond]

re: How to insert a large number of items into a treeview efficiently

Neil — Sun, 27 Nov 2011 10:29:14 GMT

If you thought a large combobox was bad, then consider the case of a large popup menubutton - you don't have a scrollbar, nor any indication of the current item in the list. (Yes, this was an application badly ported from the Mac.)

re: How to insert a large number of items into a treeview efficiently

Phaeron — Fri, 25 Nov 2011 21:19:44 GMT

Having run into this problem before, the counterpoints I would make are that:

1) You can see this performance issue with about a thousand nodes, which isn't that bad to browse if the tree view is full screen height.

2) You don't always have enough control over the data that you receive.

3) In my view, it's sub-optimal design for a UI control to have O(N^2) insertion performance when populated in natural order.

The danger with having an O(N^2) situation like this is that it doesn't just make the program slow as N grows large but instead it makes the program unusable. Since a tree view is often used for the top-level view of data, the alternatives for shortening the node list aren't great -- both chunking into intermediate nodes and "display more" links seem more awkward to me from a usability standpoint.

I did notice that this performance issue is now documented in MSDN, though, which is good.

re: How to insert a large number of items into a treeview efficiently

CarlD — Fri, 25 Nov 2011 20:51:46 GMT

"You'll probably want to consider a better way of presenting the information than in a tree view that goes on for hundreds of screens."

Or a combo box that tries to cram 10,000 items into a scrollable, non-searchable drop-down!

Unfortuantely, sometimes you have no choice: e.g. a query-based parameter in SSRS allows for one UI representation: a combo box, regardless of how many items might be presented. It is truly a horrible UI experience.

re: How to insert a large number of items into a treeview efficiently

acq — Fri, 25 Nov 2011 20:03:37 GMT

"Given that a treeview is, well, a tree structure, it's not clear what "after" means when applied to a tree as a whole"

I agree. For me it was also unclear that hInsertAfter can even be "TVI_ROOT: Add the item as a root item." Why that?