new std.variant (was Re: The Right Approach to Exceptions)
sandford at jhu.edu
Wed Feb 22 17:10:35 PST 2012
On Wed, 22 Feb 2012 18:51:27 -0600, Jonathan M Davis <jmdavisProg at gmx.com> wrote:
> On Thursday, February 23, 2012 01:38:05 Juan Manuel Cabo wrote:
>> (And not talking about some cheesy insertion sort!!)
>> If you build an array once and for all, and all you want
>> is to do binary search on it later, it doesn't make sense to
>> allocate that big contiguous .data. I'd rather leave it
>> as an appender.
>> On Wednesday, 22 February 2012 at 23:22:35 UTC, Juan Manuel Cabo
>> >> No, because the array doesn't actually exist until appender
>> >> makes copy.
>> > Will one be able to use the sort!()() algorithm directly on
>> > your appender,
>> > that is, without accessing/creating the underlying array?
> If appender ends up with multiple arrays in it, then random access is no
> longer O(1) and is therefore unacceptable. As such, most sort algorithms
> wouldn't work with it.
> Also, your bit about using appender to pass an array around wouldn't work
> either, because it wouldn't simply be wrapper around an array anymore.
> - Jonathan M Davis
> P.S. Please don't top post. Replies should go _after_ the preceding message.
Well, a VList (which is a list of arrays) is has O(1) amortized indexing. Actual performance of my implementation would be O(N / (4080/T.sizeof)), which isn't so bad. And anything under a page of ram would be O(1).
More information about the Digitalmars-d