O(1) dictionaries

Robert Fraser fraserofthenight at gmail.com
Wed Nov 14 19:36:07 PST 2007


Jari-Matti Mäkelä Wrote:

> mandel wrote:
> 
> > Tim Keating Wrote:
> > 
> >> mandel wrote:
> >> > Hi,
> >> > 
> >> > I have made a dictionary that way:
> >> > enum Word { Hello, Bye };
> >> > char[][Word] dict;
> >> > 
> >> > static this()
> >> > {
> >> >    dict = [
> >> >      Word.Hello : "Hello",
> >> >      Word.Bye : "Bye"
> >> >    ];
> >> > }
> >> > 
> >> > Now there are two problems I have with this:
> >> > 
> >> > - the dict is an AA, but an array would be much faster,
> >> >   but it is not possible to assign it via an array literal
> >> >   with a mixed order and supplied keys.
> >> > char[][Word.max] dict = [Word.Hello : "Hello", ...]
> >> 
> >> Why does the array literal have to be in mixed order? You can just do
> >> the enum and the array in the same order:
> >> 
> >> enum Word { Hello, Bye };
> >> char[] dict = [ "Hello", "Bye" ];
> >> 
> >> The only complication there is that for a dictionary of any meaningful
> >> length, it won't line up quite as nicely. Ensuring each enum value
> >> matches its correct word will be a real pain. In this situation, I might
> >> use code generation.
> > You named the reason, it won't line up.
> > The dict may also change order when words are added and quite possibly
> > regrouped. The entire alignment will be hard to maintain.
> 
> That's no good excuse to not use templates :P :
> 
> template _E(T...) {
>   static if (T.length>1)
>     const _E = T[0] ~ "," ~ _E!(T[1..$]);
>   else
>     const _E = T[0] ~ "};";
> }
> 
> template _A(T...) {
>   static if (T.length>1)
>     const _A = `"` ~ T[0] ~ `"[],` ~ _A!(T[1..$]);
>   else
>     const _A = `"` ~ T[0] ~ `"[]];`;
> }
> 
> template RealEnum(char[] aName, char[] eName, T...) {
>   const RealEnum = "enum " ~ eName ~ "{" ~ _E!(T) ~
>                    "char[][] " ~ aName ~ "=[" ~ _A!(T);
> }
> 
> mixin(RealEnum!("Word", "dict", "Hello", "Bye"));
> 
> CTFE would produce smaller binaries though.

IMHO, CTFE produces cleaner code, too, and there are no worries about symbol length.



More information about the Digitalmars-d mailing list