What is the searching algorithm used in switch statement in C language?
If the cases are not in order still it searches proper case which means it is not a binary search algorithm, can anybody explain?
-
2Note, you can see what it actually does by decompiling it (often the -S switch in a compiler). For example: goo.gl/aZPl0l (and be sure to change the compiler version in that link to see how different compilers do it).– user40980Dec 12 '14 at 20:07
Add a comment
|
Several options:
the naive method would be an if else cascade (slow)
the compiler can sort the cases behind the scene and then do a binary search (good for disjoint cases)
a jump table; only good for sequential cases but very fast.
For string-based switches there is the option of the prefix Trie, a sorted table that can be binary searched or the strings are hashed and used for the cases of a switch against the hash of the input string with a double check in each case.
answered Dec 12 '14 at 19:26
-
Note that the if/else cascade has some difficulty when you do something like
case 1: foo; case 2: bar; break;that can make some cases a bit more difficult to do.– user40980Dec 12 '14 at 20:00 -
@MichaelT then the compiler would just copy the code of case 2 to after case 1 or make it a if cascade with
goto endSwitch;for each break. Dec 12 '14 at 20:03
Generally, switch statements are implemented as Jump Tables. There is no searching involved.
-
Does this not depend on the compiler, the level of optimization and maybe on the set of switch values? Dec 12 '14 at 19:34
-
@DocBrown - I didn't think it did - especially for a language like C that is more aggressive at restricting its legal swtichable values, though ratchet freak's 2nd point is a good one to indicate that jump tables are maybe less ubiquitous than I was led to believe.– TelastynDec 12 '14 at 19:36