Thread: C++ Map vs. strcmp

Algorithmically, the map solution is actually faster than the if...else solution.

Of course, algorithmic performance doesn't matter if there are only 10 different options to choose from, but still I doubt using a map would noticeably slow anything down.

Be careful with operator[] on maps. If a subscripted index does not exist, it will create it for you, which may not be what you want.

But I would advise using a map.

Originally Posted by King Mir

Be careful with operator[] on maps. If a subscripted index does not exist, it will create it for you, which may not be what you want.

But I would advise using a map.

Exactly, you should use map.find() and copare to map.end() to see whether the item exists.
Also a map will definitly be faster, since it is a Red-Black tree and will find a key in O(log n) time, whereas your if/else will take O(n/2) on average.

QuantumPete

It is probably slower, but how much is hard to say - why not write a little benchmark that compares the two solutions.

You could always have a construction like this:

Code:

struct table {
   char *cmd;
   int      value;
};

table t[] = { { "AUTH", AUTH },
                    { "QUERY", QUERY },
                     ... };

   for(int i =0; i < sizeof(t) / sizeof(t[0]); i++) {
        if (strcmp(t[i].cmd, command) == 0) {
            return t[i].value;
         }
   }

--
Mats

Spend your time on the rest of the program, then profile the result before deciding whether to spend extra effort performing micro optimisations.

Originally Posted by Salem

Spend your time on the rest of the program, then profile the result before deciding whether to spend extra effort performing micro optimisations.

Very good point - unless you KNOW already that this is a large portion of your execution, in which case you should benchmark it to see if it's faster, slower or the same.

--
Mats

If there's going to be many strings, using a map to begin with would be no more a micro-optimization than choosing quicksort over bubble-sort.

For just a couple of strings that wouldn't make much of a difference (but map might be more versatile).

Speaking of optimizing, may-be you could write a function that is able to determine what the string begins with without making an extra copy (boost might have something for that).

And from general code quality point of view, may-be you could use std::string or at least a single point of exit so you won't need to delete the temporary buffer under every case label.

And whatever you do, use C++ strings.

I agree with Salem in that there are probably bigger fish to fry. But also agree with others in that you probably ought to decide whether or not you are going to use the STL map because it will change you code significantly.

I recommend using the map container because it has been tested, proven, and removes the burden of creating your own identical container from scratch. As well you can derive classes from the STL map or create template classes that operate on STL maps and end up with an extremely powerful library of code to do just what you want.

And whatever you do, use C++ strings.

100% agreed. Use all the tools that C++ offers you because it will greatly simplify your code as well as make it much more robust and safe.

You could spend weeks faffing about trying to work out the most optimal one, and still not get it right.
- You start with strcmp() and an if / else if ladder with just a couple of commands.
- You then add more commands, and the code becomes too bulky, so you opt for a std::map.
- When the program is done and profiled, and you find that say "QUERY" accounts for 95% of the look ups, you might consider a hybrid approach.

But if the next thing after QUERY is a bunch of say MySQL calls, then what you do here won't matter at all. Look at the bigger picture of what happens overall.

If you've made anything like a half decent job of separating the interface and the implementation, it will be an easy job to update the code as better information arrives.

Otherwise every 5 minute job becomes a week-long discussion, and your potential users have decided to shop elsewhere.

Originally Posted by QuantumPete

Also a map will definitly be faster, since it is a Red-Black tree and will find a key in O(log n) time, whereas your if/else will take O(n/2) on average.

O(n/2) is the same thing as O(n) and I don't see why people bother using big O notation if they're going to throw in spurious constants.

And the cost of walking down a few if-then-elses isn't that bad, considering that strcmp itself will have to walk through the whole string when the comparison succeeds.

You can do brutal if-then-elsing in logarithmic time anyway, if you simply put your if-then-else structures in a balanced tree shape instead of chaining them out like a linked list.

Or you can use a hash map. Or you can use a sorted array. (O(log n) lookup with less space overhead than the tree.) The possibilities are there. It's all a matter of exact use case and profiling.