If-else-if versus map

c++, dictionary, performance

Solution

Maps (usually) are implemented using red-black trees which gives O(log N) lookups as the tree is constantly kept in balance. Your linear list of if statements will be O(N) worst case. So, yes a map would be significantly faster for lookup.

Many people are recommending using a switch statement, which may not be faster for you, depending on your actual if statements. A compiler can sometimes optimize switch by using a jump table which would be O(1), but this is only possible for values that an undefined criteria; hence this behavior can be somewhat nondeterministic. Though there is a great article with a few tips on optimizing switch statements here Optimizing C and C++ Code.

You technically could even formulate a balanced tree manually, this works best for static data and I happened to just recently create a function to quickly find which bit was set in a byte (This was used in an embedded application on an I/O pin interrupt and had to be quick when 99% of the time only 1 bit would be set in the byte):

unsigned char single_bit_index(unsigned char bit) {
    // Hard-coded balanced tree lookup
    if(bit > 0x08)
        if(bit > 0x20)
            if(bit == 0x40)
                return 6;
            else
                return 7;
        else
            if(bit == 0x10)
                return 4;
            else
                return 5;
    else
        if(bit > 0x02)
            if(bit == 0x04)
                return 2;
            else
                return 3;
        else
            if(bit == 0x01)
                return 0;
            else
                return 1;
}

This gives a constant lookup in 3 steps for any of the 8 values which gives me very deterministic performance, a linear search -- given random data -- would average 4 step lookups, with a best-case of 1 and worst-case of 8 steps.

This is a good example of a range that a compiler would probably not optimize to a jump table since the 8 values I am searching for are so far apart: 1, 2, 4, 8, 16, 32, 64, and 128. It would have to create a very sparse 128 position table with only 8 elements containing a target, which on a PC with a ton of RAM might not be a big deal, but on a microcontroller it'd be killer.

Problem

Original source

Related problems

• Advantage of switch over if-else statement