Listbox::addItem is O(n*log(n) + n) whilst it should be O(n*log(n))

Issue #452 resolved
Martin Preisler
created an issue

Listbox is using std::vector to manage it's items. This is great for iteration but imagine inserting 100 items into the Listbox at once, the items are unsorted (arbitrary order) and the Listbox is set to sort them. What happens is that std::vector has to keep pushing things around when inserting into the middle, so even though it was meant to be fast and built around insertion sort, this actually makes things crawl when you approach 100+ items. Lots of memmoves (and they repeat themselves again and again, especially if you insert things in reverse sorted order).

Especially noticeable in debug builds.

Reproducibility: always

Additional information: I propose to use std::list (doubly-linked list) to manage Listbox items, iteration is slightly slower but insertion into the middle is very fast.

Comments (2)

  1. Martin Preisler reporter

    Closing as invalid, the O notations are clearly the same, I either missed a bracket or was drunk when writing it or something ;-)

    It is a problem that can be worked around by turning sort off, adding everything and then turning sort on.

  2. Log in to comment