Thread: C++ Map vs. strcmp

  1. #1
    Registered User
    Join Date
    Oct 2005
    Location
    Brasil
    Posts
    220

    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.

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  4. #4
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by King Mir View Post
    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
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Spend your time on the rest of the program, then profile the result before deciding whether to spend extra effort performing micro optimisations.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Salem View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    And whatever you do, use C++ strings.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #11
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by anon View Post
    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."

  12. #12
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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&#37; 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.
    Last edited by VirtualAce; 09-14-2007 at 11:35 PM.

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    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&#37; 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  14. #14
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by QuantumPete View Post
    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.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  15. #15
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Fucntion returns -1, Why?
    By Taper in forum C Programming
    Replies: 16
    Last Post: 12-08-2008, 06:30 PM
  2. help with switch statement
    By agentsmith in forum C Programming
    Replies: 11
    Last Post: 08-26-2008, 04:02 PM
  3. Polynomials and ADT's
    By Emeighty in forum C++ Programming
    Replies: 20
    Last Post: 08-19-2008, 08:32 AM
  4. Creating a map engine.
    By suzakugaiden in forum Game Programming
    Replies: 11
    Last Post: 06-21-2005, 05:06 AM
  5. Searching STL Map Inside STL Map Object :: C++
    By kuphryn in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2002, 09:11 AM