Say I have a method that needs to pull 8 values from a map with 100 elements in it. Which do you think would be preferable:
Walk in a for loop from begin to end once, pulling the elements out by switching on the key?
Or using find 8 times to get those values?
Walking the list will take you O(n) time to find a random element.
Map is a balanced binary tree, so doing a find is O(log n).
Thus doing 8 finds results in 8*log2(n) and walking the list is (n). The larger the list, the larger the gains, but in all random cases doing finds will be faster than doing iterations.
In non-random cases if there is reason to thing the items you want are near each other in the tree, or near the "begining" (left side) then walking/iterating would be faster. But that seems unlikey.
虽然我会选择这个find选项，但人们对渐近性能施加了太多压力。
事实是，渐近性能对于可以接收相当大的输入的算法来说是一个方便的指南，但即便如此它也不是万无一失的。对于任何合理的输入，渐近性能比另一个算法更差的算法很有可能更快。
然后有时您的输入大小会相当小（甚至是固定的）。在这种情况下，渐近性能几乎没有意义。
I would use find 8 times. It will be less (and more obvious) code.
You should try not make performance judgements based on small numbers since (a) it isn't likely to be a performance bottleneck either way at this size and (b) the numbers may change in the future -- choose the algorithm with the best asymptotic performance.
Note: you mention 'switching' on the key ... that may apply in your case, but in general you can't switch on the key value in a map. Allowing for this would make the code to searching for M items in a map by iteration even more complex.
正如其他人所指出的，我可能只会在地图上使用 find() 八次并完成它。但是根据您的需要，可以考虑另一种选择。如果地图中的项目在地图构建后不会发生太大变化，或者您不需要将插入与查找交错，您可以尝试将键/值对保留在排序向量中。如果这样做，则可以使用 lower_bound() 函数在对数时间内进行二进制搜索。这样做的好处是，如果您要查找的键可以排序（并且您知道它们将始终存在），那么您可以使用从前一个查找返回的迭代器作为下一个查找的下限。例如，
矢量::迭代器 a = my_map.lower_bound(my_map.begin(), my_map.end(), "a"); 矢量::迭代器 b = my_map.lower_bound(a + 1, my_map.end(), "b"); 向量::迭代器 c = my_map.lower_bound( b + 1, my_map.end(), "c" ); // ...
两种方法都有对数查找，但这有助于在一定程度上减少常数。
8个finds最好，因为代码更简单明了。
不过，考虑性能更有趣，所以我也会这样做。
正如 Artelius 在我写这个答案时所说，忽略复杂性。这无关紧要，因为您知道 n=100。例如，插入排序的算法复杂度比快速排序更差（至少在平均情况下），但在几乎所有实现中，对于小的 n，插入排序都比快速排序快，因此快速排序在接近尾声时突破为插入排序。您的 n 也很小，因此 n -> infinity 的限制并不重要。
由于这两个选项的代码都很容易编写，我建议对其进行分析。这将 (a) 告诉你哪个更快，并且 (b) 证明两者都非常快，以至于你做什么都没有关系（除非它是你的程序唯一做的事情，而且它做了很多事情）。尤其是当您谈论打开密钥时-如果密钥是整数类型，则限制因素更有可能是内存缓存问题，而不是任何实际处理。
然而，如果做不到这一点，通常比较搜索算法的方法是计算比较，假设它们比遍历结构要慢得多。如果不出意外，每次比较都会访问内存并且是一个不可预测的分支，这是 CPU 通常最不擅长的两件事。
如果您在开始之前对 8 个元素进行排序（大约需要 24 次比较）而不是您建议的开关，那么由于地图也已排序，您只需在遍历的每个节点上进行一次比较，以及每个项目进行一次比较您正在搜索（比较每个“边”的一个节点。如果它们匹配，则两边都增加。如果它们不匹配，则用较小的元素增加边）。所以在最坏的情况下是 8+100，或者如果你在结束之前找到所有 8 个，则更少。但是 8 个中最后一个的平均位置，如果它们随机位于地图中，仍然是大约 8/9 的位置。所以称它为 8+88+24 = 120 次比较，最坏的情况是 132 次。最好的情况是 8（如果您要搜索的东西都在开头）+24（用于初始排序）= 32 次比较，
红黑树（通常是映射）中节点的平均深度略高于 log2(n)。在这种情况下称它为 7，因为 2^7 是 128。所以找到 8 个元素应该进行 56 次比较。IIRC 红黑树的平衡特性是最深节点不超过最浅节点深度的两倍。所以最坏的情况深度是 floor(2*log2(n))，称之为 15，总共 120，最好的是 ceil(1/2 log2(n))，即 4。这又是 32 次比较。
因此，假设比较是唯一影响速度的因素，那么 8 次发现的速度将是线性遍历的 4 倍和 4 倍之间，平均要好 2 倍。
但是，线性遍历可能会触及更多内存，因此可能会更慢。但最终对于 n=100 你说的是毫秒时间，所以只要做最简单的代码（可能是 8 个发现）。我有没有提到如果你真的想知道你无法预测的速度，你只需要分析它吗？
如果这很关键，我会同时实施并基准测试性能。
理论上是不是
8 * lg(100) >?< 100
其他考虑因素是这些数字中的任何一个是否会改变——它是否会超过 100 个元素？你会做超过 8 次搜索吗？
下面是对它们的时间复杂度的分析（n 是地图中的项目数），它保证以对数或更好的时间复杂度对 find 进行查找：
8 * log2 n 8 次查找 n 用于遍历所有
对于较小的数字，第一个较大（例如，n=2 时为 8），但在 43 左右，第一个将变得比第二个更好并保持不变。所以，你会想要使用第一种方法，因为它也更方便编码。
您应该使用 find 8 次。
将切换方法视为获取每个节点并将其比较 8 次。那是 800 次比较，你完全失去了被键控的地图的所有好处，它也可能是一个列表。
通过 find 方法，您可以利用地图的优势遍历列表。我相信 std::maps 是作为二叉树实现的，这意味着搜索键只需将您的键与树的深度进行比较，对于 100 个元素的二叉树，深度为 8~。现在，您只需 8*8 次比较或 64 次比较即可找到所有 8 个元素。
让我们假设当它找到密钥时“find”保释。
让我们进一步假设您对“开关”进行了明智的编码，并且在找到匹配项后退出检查。一旦找到所有 8 个，我们还将假设您不必费心编写代码以在整个过程中保释（编写代码可能会很痛苦）。
“8 find”方法可以预期（iow：平均而言）执行 50 * 8 = 400 次比较。
“切换”方法可以预期（iow：平均而言）执行 (8 * 100) - 28 = 772 次比较。
因此，在比较方面，8 finds 方法更好。但是，比较的数量足够少，您最好选择更容易理解的选项。不过，这也可能是 8 find 方法。