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