View mode: basic / threaded / horizontal-split · Log in · Help
November 12, 2012
Re: hashed array?
On Monday, 12 November 2012 at 15:32:24 UTC, Joseph Rushton 
Wakeling wrote:
> On 11/12/2012 03:53 PM, Andrej Mitrovic wrote:
>> You probably mean a Set? I think we could really use some 
>> syntax
>> support for sets. Otherwise people use workarounds like "alias
>> void[0][string] StringSet"
>
> Can you give a bit more explanation of how that workaround 
> would work?  I can't see how you would insert entries in that 
> case ...
>
>     StringSet s;
>
>     s["one"] = .... ?

The set interface would mean you use "add" or "insert", so you 
would write it like this:

Set!string s;
s.add("one");

As for the implementation, this seems to work:


StringSet(T)
{
    private void[0][T] _data;
    void add(T value)
    {
        _data.get(value, cast(void[0]) null);
    }
}
November 12, 2012
Re: hashed array?
On Monday, 12 November 2012 at 15:22:00 UTC, bearophile wrote:
> The situation is not fully symmetrical: associative arrays 
> fully defined in Phobos have bad literals.
>
> Bye,
> bearophile

Related: what is the hook for implementing "in"?
November 12, 2012
Re: hashed array?
On Monday, 12 November 2012 at 15:36:29 UTC, monarch_dodra wrote:
> As for the implementation, this seems to work:
>
>
> StringSet(T)
> {
>     private void[0][T] _data;
>     void add(T value)
>     {
>         _data.get(value, cast(void[0]) null);
>     }
> }

Wait. That doesn't work actually. This does.
    auto add(T value)
    {
        return _data[value] = cast(void[0]) null;
    }
November 12, 2012
Re: hashed array?
monarch_dodra:

> Related: what is the hook for implementing "in"?

"in" is supported:

http://dlang.org/operatoroverloading.html#Binary

Bye,
bearophile
November 12, 2012
Re: hashed array?
On 11/12/2012 04:49 PM, monarch_dodra wrote:
> Wait. That doesn't work actually. This does.
>      auto add(T value)
>      {
>          return _data[value] = cast(void[0]) null;
>      }

Only with DMD.  GDC and LDC both reject this formulation -- it seems better to 
use byte instead of void[0].

The problem is this workaround version blows up massively with number of entries 
-- disproportionately to how much memory it would take to simply store all the 
key values. :-(
November 12, 2012
Re: hashed array?
On 11/12/12, Joseph Rushton Wakeling <joseph.wakeling@webdrake.net> wrote:
> Can you give a bit more explanation of how that workaround would work?  I
> can't
> see how you would insert entries in that case ...
>
>      StringSet s;
>
>      s["one"] = .... ?
>

s["one"] = [];
November 12, 2012
Re: hashed array?
On Mon, Nov 12, 2012 at 03:43:57PM +0100, monarch_dodra wrote:
> D has a built in hashed associative container, which is great.
> 
> I've noticed though it has no built-in "hashed container" for when
> you just need to store unique elements, but without any specific
> data associated (lists of names, for example).
> 
> Has anybody requested this before? Would there be any plans for it?

Well, I haven't *requested* this before, but I've certainly encountered
the need for it.

It's not too hard to implement, actually, you can basically just use the
same code as the current AA implementation, minus the parts that deal
with values. Then modify the lookup functions to return false when no
key is found (instead of a[b] throwing an exception when b isn't in a,
or returning a null value with the 'in' operator), and you're good to
go.


T

-- 
"You are a very disagreeable person." "NO."
November 12, 2012
Re: hashed array?
On Mon, Nov 12, 2012 at 04:38:59PM +0100, monarch_dodra wrote:
> On Monday, 12 November 2012 at 15:22:00 UTC, bearophile wrote:
> >The situation is not fully symmetrical: associative arrays fully
> >defined in Phobos have bad literals.
> >
> >Bye,
> >bearophile
> 
> Related: what is the hook for implementing "in"?

auto opBinaryRight(string op)(KeyType k) if (op=="in") { ... }


T

-- 
The early bird gets the worm. Moral: ewww...
November 12, 2012
Re: hashed array?
11/12/2012 6:43 PM, monarch_dodra пишет:
> D has a built in hashed associative container, which is great.
>


No. The literals are nice though.

> I've noticed though it has no built-in "hashed container" for when you
> just need to store unique elements, but without any specific data
> associated (lists of names, for example).

There is no need for built-in containers. If anything there is plan to 
move hash out of built-ins. The fact that it utterly failed to happen 
doesn't prove anything as it still has to be the library type.

>
> Has anybody requested this before? Would there be any plans for it?
>

> ----
> The current "workaround" is to just dummy it.
> alias bool Dummy;
> Dummy[string] names;
> names["Paul"] = true; //Ew.

Make a wrapper?

>
> But it is not very obvious what is going on. I also tried "void"ing it, eg:
> void[string] names;
> But that doesn't work either: Error: can't have associative array of void.
>
> ----
> What would you think of introducing a built-in hashed container, that
> contains only keys?

Infinitely awful.

>
> We could call them "HA" for Hashed Array, and declare them with this
> simple syntax:
>

Or rather call them sets and have them in the library.


-- 
Dmitry Olshansky
November 12, 2012
Re: hashed array?
On Monday, 12 November 2012 at 16:27:58 UTC, Dmitry Olshansky 
wrote:
> 11/12/2012 6:43 PM, monarch_dodra пишет:
> [SNIP]

Yeah... I'm implementing my lightweight wrapper now.
1 2 3 4
Top | Discussion index | About this forum | D home