I'm curious, how is the associative array type implemented? is it merely a dynamic array with two sets of data per element, or is it implemented as a linked list, or bst or something?

I looked through the D documentation and couldn't find an answer, so I figured I'd ask here.

Thanks,
--Nick

OK, I asked prematurely.  I realized soon after posting this question that the source was right in front of my nose.  Granted it looks rather confusing to my tired eyes, but it looks like a bst, no?  Is it balanced or anything funky like that?  Yeah I'll probably figure that out on my own in a minute, so sorry to bother you guys with these posts!

--Nick


In article <b3a2vd$2u5b$1@digitaldaemon.com>, lesnin@rpi.edu says...
>
>I'm curious, how is the associative array type implemented? is it merely a dynamic array with two sets of data per element, or is it implemented as a linked list, or bst or something?
>
>I looked through the D documentation and couldn't find an answer, so I figured I'd ask here.
>
>Thanks,
>--Nick
>
>

"Nick Lesniewsk-Laas" <lesnin@rpi.edu> wrote in message news:b3a5ne$30au$1@digitaldaemon.com...
> OK, I asked prematurely.  I realized soon after posting this question that
the
> source was right in front of my nose.  Granted it looks rather confusing
to my
> tired eyes, but it looks like a bst, no?  Is it balanced or anything funky
like
> that?  Yeah I'll probably figure that out on my own in a minute, so sorry
to
> bother you guys with these posts!

It's a hashed array of binary trees. Such is a simple data structure, but I've found with years of experience that it is as efficient as about anything else. The reason this isn't mentioned in the D spec is because the underlying algorithm is left up to the implementor, leaving them plenty of room to come up with a better scheme.

how do I change the underlying impl of assoc arrays ?
for instance to allow
typedef int delegate ( int, Object ) mydp;
mydp[char[]] foo;

which I can't do at present;

or within my win32 lib I use a assoc array for message handler lookup, I wnat to try some cacheing algorythms in the assoc array (keep the last message, and keep track of the order x is usually followed by y etc)



"Walter" <walter@digitalmars.com> wrote in message news:b3bacm$tng$2@digitaldaemon.com...
>
> "Nick Lesniewsk-Laas" <lesnin@rpi.edu> wrote in message news:b3a5ne$30au$1@digitaldaemon.com...
> > OK, I asked prematurely.  I realized soon after posting this question
that
> the
> > source was right in front of my nose.  Granted it looks rather confusing
> to my
> > tired eyes, but it looks like a bst, no?  Is it balanced or anything
funky
> like
> > that?  Yeah I'll probably figure that out on my own in a minute, so
sorry
> to
> > bother you guys with these posts!
>
> It's a hashed array of binary trees. Such is a simple data structure, but I've found with years of experience that it is as efficient as about anything else. The reason this isn't mentioned in the D spec is because
the
> underlying algorithm is left up to the implementor, leaving them plenty of room to come up with a better scheme.
>
>

"Mike Wynn" <mike.wynn@l8night.co.uk> wrote in message news:b3dh66$2r71$1@digitaldaemon.com...
> how do I change the underlying impl of assoc arrays ?
> for instance to allow
> typedef int delegate ( int, Object ) mydp;
> mydp[char[]] foo;
>
> which I can't do at present;
>
> or within my win32 lib I use a assoc array for message handler lookup, I wnat to try some cacheing algorythms in the assoc array (keep the last message, and keep track of the order x is usually followed by y etc)

That should work.

it does as does

alias char[] str;
str[whatever] foo;

and I'm 100% sure that never worked b4.

back to the orginal question ... how do I change the underlying impl ?

"Walter" <walter@digitalmars.com> wrote in message news:b3ets5$cah$1@digitaldaemon.com...
>
> "Mike Wynn" <mike.wynn@l8night.co.uk> wrote in message news:b3dh66$2r71$1@digitaldaemon.com...
> > how do I change the underlying impl of assoc arrays ?
> > for instance to allow
> > typedef int delegate ( int, Object ) mydp;
> > mydp[char[]] foo;
> >
> > which I can't do at present;
> >
> > or within my win32 lib I use a assoc array for message handler lookup, I wnat to try some cacheing algorythms in the assoc array (keep the last message, and keep track of the order x is usually followed by y etc)
>
> That should work.
>
>

"Walter" <walter@digitalmars.com> schrieb im Newsbeitrag news:b3bacm$tng$2@digitaldaemon.com...

> It's a hashed array of binary trees. Such is a simple data structure, but I've found with years of experience that it is as efficient as about anything else.

Hi, any chance that we can see a feature in D to serialize these to disk and be able to read them in again? IMO this would give a simple (KISS) embedded database functionality to D that will be OK for some 50%+ of data-storing problems. Robert

"Mike Wynn" <mike.wynn@l8night.co.uk> wrote in message news:b3eu93$cgd$1@digitaldaemon.com...
> back to the orginal question ... how do I change the underlying impl ?

Modify the library code in \dmd\src\phobos

"Robert M. Münch" <robert.muench@robertmuench.de> wrote in message news:b3hqs1$22n0$1@digitaldaemon.com...
> "Walter" <walter@digitalmars.com> schrieb im Newsbeitrag news:b3bacm$tng$2@digitaldaemon.com...
> > It's a hashed array of binary trees. Such is a simple data structure,
but
> > I've found with years of experience that it is as efficient as about anything else.
> Hi, any chance that we can see a feature in D to serialize these to disk
and
> be able to read them in again? IMO this would give a simple (KISS)
embedded
> database functionality to D that will be OK for some 50%+ of data-storing problems. Robert

That was in my original plan for D, but I've made no progress towards it.

"Walter" <walter@digitalmars.com> schrieb im Newsbeitrag news:b45jmi$25b8$2@digitaldaemon.com...

> Hi, any chance that we can see a feature in D to serialize these to disk and be able to read them in again?
>
> That was in my original plan for D, but I've made no progress towards it.

Hi, I don't know how hard it would be. But IMO only being able to serialize associative arrays don't help a lot, we would need a serialization method for objects as well... Robert