Re: Use vectors rather than lists for skylines. (issue 583750043 by address@hidden)

[dak]

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/