In theory, it should be possible to do a "popFront" equivalent for a hash that has O(1) average complexity, so long as you don't care about order.  I.e., "give me any key from the hash, I don't care which one, and then delete it from the hash".  Is that correct?

If it is correct, is there any way to do it in D?

Do I assume correctly that "myarray.keys[0]" would not meet the O(1) requirement?

Thanks.

Andrew

On 12/11/2014 10:27 AM, Andrew Klaassen wrote:

> If it is correct, is there any way to do it in D?
>
> Do I assume correctly that "myarray.keys[0]" would not meet the O(1)
> requirement?

Correct. keys() is eager. For O(1) you want byKey(), which returns a lazy range but the code is less than pretty:

import std.stdio;

void main()
{
    auto aa = [ 1 : "one", 2 : "two" ];

    while (true) {
        auto keys = aa.byKey;

        if (keys.empty) {
            break;
        }

        aa.remove(keys.front);
    }
}

Ali

On Thu, Dec 11, 2014 at 06:27:06PM +0000, Andrew Klaassen via Digitalmars-d-learn wrote:
> In theory, it should be possible to do a "popFront" equivalent for a hash that has O(1) average complexity, so long as you don't care about order.  I.e., "give me any key from the hash, I don't care which one, and then delete it from the hash".  Is that correct?
> 
> If it is correct, is there any way to do it in D?
> 
> Do I assume correctly that "myarray.keys[0]" would not meet the O(1)
> requirement?
[...]

AA.keys will walk the entire hash table and return an array of keys. That's totally wasteful of what you want, and is definitely not O(1).

On the other hand, AA.byKey() will return a *lazy* sequence of keys
(i.e., it won't actually walk the AA unless you want it to), so doing
this ought to be O(1):

	auto mykey = myarray.byKey().front;
	myarray.remove(mykey);

Be careful that you do not attempt to continue using the lazy sequence returned by byKey() once you have invoked .remove, though, because modifying a container while iterating over it almost always leads to counterintuitive (and sometimes outright buggy) behaviour. Repeatedly retrieving the first key and then removing it, as above, is OK, since you're starting over with a new sequence of keys each time.


T

-- 
Computers aren't intelligent; they only think they are.

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.


T

-- 
Why are you blatanly misspelling "blatant"? -- Branden Robinson

H. S. Teoh:

> On the other hand, AA.byKey() will return a *lazy* sequence of keys
> (i.e., it won't actually walk the AA unless you want it to), so doing
> this ought to be O(1):
>
> 	auto mykey = myarray.byKey().front;
> 	myarray.remove(mykey);

In general the associative array table can have many empty slots, so byKey.front is not always O(1). But AAs were recently improved, now byKey.front is much faster.

Bye,
bearophile

Thanks everyone!

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