On 2020/04/23 16:01:20, dak wrote: > On 2020/04/22 07:43:17, hanwenn wrote:
> > * The linked list has an overhead of 2 pointers, on a 4x Real > > datastructure, ie. 50% overhead. By the way: C++11 has Forward_list which would be another plugin container type with less overhead. I actually have some sort routine for that lying around here that I offered several times on the libc++ list without pickup. Someone benchmarked it to be about 30% faster than what's in there, on average (and, as its a merge sort, with a worst case hardly worse) but I gave up trying to forcefeed it to them after a few tries. Did not take any extra memory apart from an O(lg n) stack maintained manually rather than recursively. Now what would probably work reasonably well is to just collect buildings without bothering to look at them, clean up via a priority queue when one has gathered enough material and merge ultimately. Priority queues can be well done with vectors. All of those more order-ignorant methods will want arithmetic that is largely order-independent. https://codereview.appspot.com/583750043/