C++ Map vs. strcmp

Hi, i have some code that compares a string like ten times and accordinly to that string a type is returned:

Code:

---

Server::MessageTypes Server::getMessageType(const char* message)
{
        int  index  = strcspn(message, " ");
        char* command = new char[index + 1];

        strncpy(command, message, index);
        command[index] = '\0';

        if (strcmp(command, "AUTH") == 0)
        {
                delete [] command;

                return AUTH;
        }
        else if (strcmp(command, "QUERY") == 0)
        {
                delete [] command;

                return QUERY;
        }
        else
        {
                delete [] command;

                return INVALID;
        }
}

---

But i wanted to make this code more flexible by using C++ maps. For example: a person adds a key like: "APPVER" in the map and the value will be a int APPVER (defined in a enum). So i came up with the following code:

Code:

---

void Server::addCommand(const char* command, int id)
{
      map[command] = id;
}

Server::MessageTypes  Server::getMessageType(const char* message)
{
        int  index  = strcspn(message, " ");
        char* command = new char[index + 1];

        strncpy(command, message, index);
        command[index] = '\0';

        int value = map[command];

        delete [] command;

      return value;
}

---

But i was a litlle afraid, since this function is called many times, of this map solution decreasing my performance. I wanted a suggestion...

Thank you.

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.

Quote:

---

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.

Quote:

---

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

The map solution has MANY things going for it. You don't have to hard-code the strings to be searched, so you can add new ones at runtime if necessary. It looks better. And it is much, MUCH faster if you have lots of strings to compare with.

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.

Quote:

---

Originally Posted by anon

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.

---

I wouldn't look at it as an optimization at all. It's just "the right thing to do." He wants to MAP strings to integers. That's what a MAP is for :-)

The rule is, "Don't optimize prematurely," not "Pick the slowest available method."

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.

Quote:

---

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.

Quote:

---

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.

Ok, i will now start to use std::string class, and i will implement the std::map way. But one question, how do std::map work on it´s internals? Thank you all.

Quote:

---

But one question, how do std::map work on it´s internals?

---

That is implementation dependent, but due to the complexity requirements the underlying data structure would be some kind of balanced binary tree.