If ladder or hash and switch-case for strings?

[Impacatus]

Let's say I'm accepting text commands. I need to figure out exactly which of many commands was entered. What's the most efficient way to do this? Thank you in advance.

[Disch]

depends on how many strings there are, how long they are, and how likely they are to share common text at the beginning.

- if/else ladders are fine if you only have a few commands
- binary search trees (ie: std::map) is good if you have lots of commands but few/none of them start with similar text
- hash tables are good if you have lots of commands and many of them start with similar text. Well, they're actually good most of the time unless your strings are excessively long.
- switch is not an option as it is not possible with strings.


binary search vs. hash:

Binary search is very quick as long as the text can be compared quickly. If every command starts with a unique letter, then comparing two strings can be as fast as comparing only a single character, and is thus very fast.

If you have a bunch of strings that all start the same:

"command 1"
"command 5"
"commandos"
"command and conquer"
"commander"

Then comparing two strings requires you check multiple characters and it gets slower, so a binary search wouldn't be ideal.

Hash tables are pretty much always fast unless your strings are excessively long.

[Impacatus]

Huh, ok.. Actually what I meant was switch-case using the hashed values of the strings, but I'll have to read about these hash tables, and look into binary searches as well. Thanks.

[Impacatus]

Alright, so I think I understand how to write a hash function to turn the string into an integer, but then what? Should I use a switch-case to determine how to react to the command?

I'm thinking of a structure like this. Would it work, and be efficient?

switch (hash(input)) {
	case hash("command1"):
	if (input =="command1"){
		//do something
		break;
	}
	case hash("command2"):
	if (input =="command2"){
		//do something
		break;
	}
}

The if statements are a precaution against collision.

[Impacatus]

Or would it be better to make an array of a class that contains a function pointer to the correct action, as well as a pointer to the next command at the same position? I'm thinking something like this:

struct hashfield {
	std::string key;
	hashfield * next;
	void (*command)(float, char, char) = NULL;  //I don't really know how to make a function pointer

	void add (std::string cKey,function * cCommand);//if the fields are undefined, add them, if not make a new hashfield
	bool execut(std::string tKey,std::string input);//if tKey matches key, execute command, otherwise onto the next
}

Some of the syntax might be wrong, but do I at least have the right idea? I'd like to know before I continue so it gets done right.

[PanGalactic]

That looks a lot like std::map<string, functor> to me...

[Impacatus]

Meaning... what? Please tell me what I should do.