O(1) "popAny" for associative array?
Steven Schveighoffer via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Thu Dec 11 11:14:42 PST 2014
On 12/11/14 1:41 PM, H. S. Teoh via Digitalmars-d-learn wrote:
> On Thu, Dec 11, 2014 at 10:36:02AM -0800, H. S. Teoh via Digitalmars-d-learn wrote:
> [...]
>> auto mykey = myarray.byKey().front;
>> myarray.remove(mykey);
> [...]
>
> Ah, I forgot that you need to check .empty on the range returned by
> byKey before accessing .front. Thanks to Ali for pointing that out. :-)
> In this case, though, you *could* just check myarray.empty directly
> instead.
Just want to say that until recently, byKey was NOT O(1). A recent
optimization caches the first used bucket, which makes it O(1).
I would recommend checking for array.empty, because that allows you to
avoid keeping the byKey range in a variable.
-Steve
More information about the Digitalmars-d-learn
mailing list