std::map<std::string, aClass*> someMap; vs std::map<int, aClass*> someMap;
谢谢！分析算法的渐进性能是在考虑必须执行的操作以及它们增加到方程式中的成本。为此，您需要首先了解执行的操作，然后评估其成本。
在平衡二叉树（其映射恰好是如此）中搜索关键字需要O(log N)复杂操作。每个操作都意味着比较关键字以查找匹配项，如果关键字不匹配，则跟随适当的指针（子节点）。这意味着总成本与这两个操作的成本成正比，乘以log N。跟随指针是常数时间操作O(1)，而比较关键字取决于关键字。对于整数关键字，比较很快O(1)。但对于两个字符串的比较就不同了，它需要与所涉及字符串的大小成比例的时间O(L)（我故意使用L作为字符串长度参数，而不是更常见的N）。
当您总结所有成本时，您会发现使用整数作为键的总成本为O(log N)*(O(1)+O(1))，即等效于O(log N)。（O(1)被O符号默默隐藏在常数中）。
如果您使用字符串作为键，则总成本为O(log N)*(O(L)+O(1))，其中常数时间操作被更昂贵的线性操作O(L)所隐藏，并且可以转换为O(L*log N)。即，以字符串作为键的映射中定位元素的成本与存储在映射中的元素数量的对数成比例，乘以用作键的字符串的平均长度。
请注意，大O符号最适合用作分析工具，以确定问题规模增长时算法的行为方式，但它隐藏了许多重要的原始性能细节。
作为最简单的例子，如果你将键从通用字符串更改为1000个字符的数组，则可以在符号中省略该成本。比较1000个字符的数组是一个常数操作，但需要相当长的时间。在渐近符号表示法中，这只是一个 O(log N) 操作，就像整数一样。
许多其他隐藏成本也会发生同样的情况，如元素创建成本通常被认为是一个常数时间操作，因为它不依赖于问题的参数（在每个分配中定位内存块的成本不取决于数据集，而是取决于算法分析范围之外的内存碎片化状态；在 malloc 内部获取锁的成本以确保没有两个进程尝试返回相同的内存块取决于锁的争用，该争用又取决于处理器数量、进程数量以及它们执行的内存请求量...再次超出了算法分析的范围)。在阅读大O符号时，必须意识到它真正代表的含义。
首先，我怀疑在实际应用中，使用字符串键或整数键是否会有任何明显的区别。对您的应用程序进行分析将告诉您它是否重要。
如果确实很重要，您可以将键更改为类似于以下内容（未经测试）：
class Key {
public:
unsigned hash;
std::string s;
int cmp(const Key& other) {
int diff = hash - other.hash;
if (diff == 0)
diff = strcmp(s, other.s);
return diff;
}
现在你正在对两个字符串的哈希值进行整数比较。如果哈希值不同，那么这两个字符串肯定不同。如果哈希值相同，你仍然需要比较这两个字符串，因为涉及到鸽巢原理。
成本差异将与比较两个整数与比较两个字符串之间的成本差异相关联。
当比较两个字符串时，您必须取消引用指针以获取第一个字符并进行比较。如果它们相同，则必须比较第二个字符，依此类推。如果您的字符串具有长公共前缀，则可能会稍微减慢该过程。但是，与比较整数相比，这很不可能快。
一个简单的例子，只涉及访问两个具有相同键数的映射中的值 - 一个是整数键，另一个是相同整数值的字符串，使用字符串需要8倍的时间。
O(L)（L：字符串大小），但这仅在整个操作中执行一次：O(L)+O(log N)，将是O(L)或O(log N)中较大的一个。如果键保留为字符串，则在所有节点中执行比较，并且成本为O(L)*O(log N)，即O(L*log N)。 - David Rodríguez - dribeas