10 Dec, 2007, Guest wrote in the 1st comment:
Votes: 0
Just wondering, since it seems likely enough to exist, is there a C++ equivalent to doing what the command_hash does? If you take a look at add_command, find_command, and unlink_command it should be clear what I'm after duplicating.
10 Dec, 2007, David Haley wrote in the 2nd comment:
Votes: 0
The quick 'n dirty (and, frankly, dumb) answer to your question is:
The STL standard does not include a hash table, so no.


The longer and more interesting answer is:

The hashing algorithm the command table code uses is… well… very bad. It hashes by sticking commands into buckets according to their first letter. So all commands that start with 'c' will be in one long linked list. As a result, the hash table buckets will be very unbalanced unless the commands happen to be naturally balanced across the alphabet. This defeats the whole purpose of using a hash table in the first place.

Basically, the current hash table is just an array of linked lists where the subscript is the first letter of the command. (So the table is in fact even worse, because it has a good deal of buckets that will always be empty!)

Since the hashing algorithm is basically useless, you'd be better off with a std::map which is typically implemented as a binary tree. You would get much better performance than the terrible hashing algorithm in use now.
10 Dec, 2007, Guest wrote in the 3rd comment:
Votes: 0
Well the reason I asked is because I do have it setup as a std::map now, but in doing so I've lost the ability to "prioritize" where commands are placed. So instead of "look" coming up when you type "L" you end up with "landmarks" instead because that's where it ended up in the table. So I was hoping to get back the ability to use cedit to raise and lower the placement of commands in the table, but using something C++ to accomplish it.

On a related note, since there's only 26 letters in the alphabet, why does the command_hash have 125 buckets?
10 Dec, 2007, David Haley wrote in the 4th comment:
Votes: 0
Oh. Well, you could just have a vector of vectors, where the first vector is indexed by the first character of the command, and the second is an ordered list of the commands. This would be implementing the same indexing as the current version, so you wouldn't be losing performance. To prioritize commands would be to change their position in the sub-vector. You would use a vector and not a linked list because you don't care about insert/remove cost, so there's no need to pay the overhead of a linked list.

I imagine they have 126 buckets because commands can start with non-letters, and it's easier to just use the first 126 characters than to figure out which buckets are needed. As a result, buckets with control characters (most below 32 for example) will be empty.
11 Dec, 2007, Omega wrote in the 5th comment:
Votes: 0
stl hash_map perhaps ?
12 Dec, 2007, David Haley wrote in the 6th comment:
Votes: 0
That exists but it isn't part of the standard, but most implementations have it anyhow.

Nonetheless it's not directly solving the problem, which is wanting to order the buckets, not just implement the commands using a hash table.
13 Dec, 2007, Guest wrote in the 7th comment:
Votes: 0
Ok. So. This vector of vectors. I'm having a brain fart or something but how would you go about declaring that?

vector<vector> ?
vector<vector<string>> ?

And can you in fact use v_member["a"] to refer to the vector containing all of the commands that start with "a" ?

( we'll note I should work on getting more sleep during the week )
13 Dec, 2007, David Haley wrote in the 8th comment:
Votes: 0
You'd do a vector where you index by character, not by string. Then you'd do:

vector< vector<cmd_data> >

you index the first vector by character value; then you traverse the second list of command data looking for the string you want.
13 Dec, 2007, Davion wrote in the 9th comment:
Votes: 0
Might also be possible to use std::map's third template parameter (the compare functor) to affect weighting of choices. Probably going to slow down the comparison a bit though, heh.
13 Dec, 2007, David Haley wrote in the 10th comment:
Votes: 0
It would be complicated to do it that way, because you would need to associate with each command a priority. The comparison functor itself would be fairly easy: sort on priority first, then alphabetically. It's just that you would have to add the field to all commands, and you would no longer be able to manipulate them with simple cedit_raise; you'd need to specify a number. (Either that, or not specify the number in cedit, and have it figure out the number for you…)

Come to think of it, though, that sort function wouldn't work because lookups become "interesting"… to find the command, you would have to know not only its name but its priority, too. But that defeats the point of looking something up by prefix.

Speaking of which, a std::map wouldn't work by prefix, anyhow, at least not without a lot of extra finagling.
13 Dec, 2007, Guest wrote in the 11th comment:
Votes: 0
Alright. I'm not at home right now so I can't test this, but… would this work? I'm not sure if I'm going about accessing the vector of vectors right to do this.

vector< vector<cmd_type*> > command_table;

cmd_type *find_command( const string& command )
{
vector<cmd_type*> cmd_list;
vector<cmd_type*>::iterator icmd;
char c = command[0];

cmd_list = command_table[c];

for( icmd = cmd_list.begin(); icmd != cmd_list.end(); ++icmd )
{
cmd_type *cmd = *icmd;

if( !str_cmp( cmd->name, command ) )
return cmd;
}
return NULL;
}
14 Dec, 2007, David Haley wrote in the 12th comment:
Votes: 0
That looks reasonable just by reading through the code. I don't know if you need str_cmp or str_prefix or whatever. But you're copying the whole vector of commands, which isn't necessary. Instead, do this:

vector<cmd_type*>::const_iterator icmd;
char c = command[0];

const vector<cmd_type*> & cmd_list = command_table[c];

The const is not necessary but is good practice.

The reference declaration avoids the need to copy the whole vector, which is a Good Thing.
14 Dec, 2007, Guest wrote in the 13th comment:
Votes: 0
Yeah, this whole "you're making a copy of it" thing is going to take a lot of getting used to. It's not normal for me to think of it behaving that way. Why is a const_iterator preferred over a regular one?
14 Dec, 2007, David Haley wrote in the 14th comment:
Votes: 0
If you have a const reference, you need the const iterator. As for why const is preferred, it's because if you don't need to change anything, having it const forces you to not make that change. Not only does it make the code safer (you can't accidentally assign something) but also it forces everybody who uses that code (or people who you call) to not modify the data either. By making something const, you are stating the important intent of not ever changing that thing.

A recent example on the FUSS forums where that is very important was that socials bug where it was modifying a string it shouldn't have been. (I think the forum thread was lost with the crash, unfortunately.)

Using const is the kind of thing that won't make or break your code or save you every time you use it, but is a good practice in general and can avoid problems later on.
0.0/14