Index » General » hashed array? (page 2)

November 12, 2012
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
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
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
monarch_dodra:

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

"in" is supported:

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

Bye,
bearophile
November 12, 2012
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
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
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
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
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
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