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.
