c++ - If-else-if 与 map

Question

假设我有这样一个 if/else-if 链:

if( x.GetId() == 1 )
{
}
else if( x.GetId() == 2 )
{
}
// ... 50 more else if statements

我想知道的是，如果我保留一张 map ，它在性能方面会不会更好？ (假设键是整数)

Answer 1

map (通常)是使用红黑树实现的，它提供 O(log N) 查找，因为树始终保持平衡。您的 if 语句线性列表将是 O(N) 最坏的情况。所以，是的， map 的查找速度会快得多。

许多人建议使用 switch 语句，这对您来说可能不会更快，具体取决于您的实际 if 语句。编译器有时可以通过使用 O(1) 的跳转表来优化 switch，但这仅适用于未定义标准的值；因此这种行为可能有些不确定。虽然这里有一篇很棒的文章，其中包含一些关于优化 switch 语句的技巧 Optimizing C and C++ Code .

从技术上讲，您甚至可以手动制定一个平衡树，这最适合静态数据，我最近刚好创建了一个函数来快速找到字节中设置了哪个位(这在 I/上的嵌入式应用程序中使用O pin 中断并且当 99% 的时间只有 1 位会在字节中设置时必须很快):

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;
}

这为 8 个值中的任何一个提供了 3 个步骤的持续查找，这给了我非常确定的性能，线性搜索——给定随机数据——将平均 4 个步骤查找，最好的情况是 1，最坏的情况是8步的情况。

这是编译器可能不会优化为跳转表的范围的一个很好的例子，因为我正在搜索的 8 个值相距甚远:1、2、4、8、16、32、64 和128. 它必须创建一个非常稀疏的 128 位置表，其中只有 8 个元素包含一个目标，这在具有大量 RAM 的 PC 上可能不是什么大问题，但在微 Controller 上它会是 killer 。