Dictionary / Hashtable / Associative Array ?

#1 B I N G O

www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=4711

#2 Hmm... I hadn't actually seen that resource before, maybe I'll look into it.

The way I solved this problem was to make a console object wrapper for std::map. I submitted the resource for it yesterday so I'm just waiting for Garage Games to approve it and I'll post a link (with demo). Hopefully it will be available fairly soon and it will give you some ideas if you're interested in going the STL route.

The main advantage to STL is: A) we know it works and B) most C++ programmers know how to use it so its fairly easy to create a wrapper for it. If you don't like my wrapper, you can always create your own.

If the resource you found gets the job done, great :)

#3 @Matthew, is there a place where it can be downloaded? Sometimes it takes a long time for them to approve resources.

#4 Sent you an e-mail...

#5 I still haven't used Matthew's resource - compiling the STL is kind of daunting for me.

I have been happily using "Script Array Upgrade" that I linked to above. However I stupidly just realized it's not an actual hashtable: the getIndexFromKey() function does a key by key scan of the whole array :-(

Can anyone comment about the pros and cons of

1. Torquescripts built-in arrays (which seem to be able to double as hashtables) just use a string as an index instead of an integer like $myHash[ "fu" ] =3.14;

2. Matthew Kee's wrapper for std::map hashtable

3. Googles Sparse Hashtable classes code.google.com/projects.html

I am writing some torquescript code that depends on having the best possible hashtable implementation.

Thanks

#6 I believed that STL::map wasn't hash tables exactly, sometime I read it was based in trees
and hash tables and dictionaries are part of the TSR 1.1 or something like that...

#7 Yeah, apparently it usually uses red-black trees. A red-black tree is a binary search tree that guarantees to be nearly-balanced. So it does search, insert, delete in O(lgn) whereas a BST does it in O(n) worst case. So, not as fast as hash tables (average case) but still probably fast enough.. there is also std::hash_map

I just finished a midterm for a data structures course a few hours ago, so I have lots of great facts and algorithms fresh in mind.. ;-) .. what's the amortized cost of deleting a node in a Fibonacci Heap?

#8 Do you guys happen to know if torque's arrays are real hashtables or if they are an array that also can use strings as indices? Not sure where to look in the C++ source exactly.

#9 Sorry, I don't know much about TorqueScript data structures, and I'm not sure where to get details aside from going into the source code (or where to go in the source code).

I'm actually very curious about that though. I have a feeling that each variable in an array is actually just treated as an individual variable.. So they aren't even stored sequentially. They are just a way of making variable names that you can iterate through. Take the array name, append the index to it, and that is your variable name. This would explain all my experience with them. That would also exlain why you can use strings as indices.

So, if anyone knows the REAL answer, I'm interested too.

Also, is there a way to pass arrays as parameters?

#10 @James: I think you're right. An array is simply a variable with the array "index" tacked on, like...

%myarray[4] == %myarray4;
%myarray["McSpazatron"] == %myarrayMcSpazatron;

That's my understanding of it.
Edit: It may get an underscore if you use 2 dimensions.

%myarray[4, 5] == %myarray4_5;

#11 Of course, in the end that probably means that it does use a hash table because TorqueScript has to somehow look up variable names (at least that's how most compilers do it).

#12 Have you dug in the core code?
I found a custom template [tVector.h]
at first look seems this class is a weight light version of the STL standar
Am I wrong?
And I found a dictionary data class TagDictionary in [tagDictionary.h]

I even found a linked list that nobody uses [llist.h]
of course nobody is going to use your code if you put something lke this on it ^_^

// WARNING - this template has not been thoroughly tested so there may be bugs in it!

#13 Is anyone interested in Lua? I have Lua talking to TorqueScript and vice versa... Lua has dictionaries. In fact, "tables in Lua are not a data structure; they are the data structure" of the language, and tables == dictionaries. The code is messy and can use more error checking, but most things work and I plan to make it a resource once it's more finished.

#14 @of course I am interested, LUA is something
I must try definetively...