我正在使用std::map（VC++ 实现），通过地图的 find 方法进行查找有点慢。
密钥类型是std::string。
我可以std::map通过地图的自定义键比较覆盖来提高此查找的性能吗？例如，也许< compare在比较数据之前std::string没有考虑简单的比较？string::size()
还有其他加快比较速度的想法吗？
在我的情况下，地图将始终包含 < 15 个元素，但它正在不停地被查询并且性能至关重要。也许有一个更好的数据结构我可以使用它会更快？
更新：地图包含文件路径。
更新2：地图的元素经常变化。
正如Even所说，在 a setis <not中使用的运算符==。
如果您不关心字符串的顺序，set您可以传递set一个自定义比较器，该比较器的性能比常规的less-than更好。
例如，如果您的许多字符串具有相似的前缀（但它们的长度不同），您可以按字符串长度排序（因为string.length速度是恒定的）。
如果您这样做，请注意一个常见错误：
struct comp {
bool operator()(const std::string& lhs, const std::string& rhs)
{
if (lhs.length() < rhs.length())
return true;
return lhs < rhs;
}
};
该运算符不保持严格的弱排序，因为它可以将两个字符串视为一个小于另一个。
string a = "z";
string b = "aa";
按照逻辑，你会看到comp(a, b) == true和comp(b, a) == true。
正确的实现是：
struct comp {
bool operator()(const std::string& lhs, const std::string& rhs)
{
if (lhs.length() != rhs.length())
return lhs.length() < rhs.length();
return lhs < rhs;
}
};
首先，关闭所有 profiling 和 DEBUG 开关。这些可以极大地减慢 STL。
如果不是这样，部分问题可能是您的字符串对于字符串的前 80-90% 是相同的。这对 map 来说当然不错，但它适用于字符串比较。如果是这种情况，您的搜索可能需要更长的时间。
例如，在这段代码中 find() 可能会导致几个字符串比较，但每次都会在比较第一个字符直到 "david" 之后返回，然后将检查前三个字符。因此，每次调用最多检查 5 个字符。
map<string,int> names;
names["larry"] = 1;
names["david"] = 2;
names["juanita"] = 3;
map<string,int>::iterator iter = names.find("daniel");
另一方面，在以下代码中，find() 可能会检查 135+ 个字符：
map<string,int> names;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/wilma"] = 1;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/fred"] = 2;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/barney"] = 3;
map<string,int>::iterator iter = names.find("/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/betty");
这是因为字符串比较必须更深入地搜索才能找到匹配项，因为每个字符串的开头都是相同的。
由于您的数据集非常小，因此在比较中使用 size() 对您没有太大帮助。std::map 保持排序，因此可以使用二进制搜索来搜索其元素。每次对 find 的调用应该导致少于 5 次字符串比较未命中，平均 2 次比较命中。但这确实取决于您的数据。如果您的大多数路径字符串的长度不同，那么像 Motti 描述的大小检查可能会有很大帮助。
考虑替代算法时要考虑的事情是您获得了多少“命中”。您的大多数 find() 调用是返回 end() 还是命中？如果您的大多数 find()s 返回 end()（未命中），那么您每次都在搜索整个地图（比较 2logn 字符串）。
Hash_map 是个好主意；它应该将您的搜索时间减少一半左右；更多的失误。
由于路径字符串的性质，可能需要自定义算法，特别是如果您的数据集具有上述代码中的共同祖先。
要考虑的另一件事是如何获取搜索字符串。如果您正在重用它们，将它们编码成更容易比较的东西可能会有所帮助。如果您使用它们一次并丢弃它们，那么这个编码步骤可能太昂贵了。
我曾经（很久以前）使用过类似 Huffman 编码树的东西来优化字符串搜索。在某些情况下，像这样的二进制字符串搜索树可能更有效，但对于像你这样的小集合来说，它相当昂贵。
最后，研究替代 std::map 实现。我听说过一些关于 VC 的 stl 代码性能的坏消息。尤其是 DEBUG 库在每次调用时检查你是不好的。 StlPort曾经是一个不错的选择，但我已经有几年没有尝试过了。我也一直很喜欢Boost。
如果可能的话，第一件事是尝试使用 hash_map - 你是对的，标准字符串比较不会首先检查大小（因为它是按字典顺序比较的），但是最好避免编写自己的地图代码. 从您的问题看来，您不需要遍历范围；在这种情况下， map 没有 hash_map 没有的任何东西。
它还取决于您在地图中拥有什么样的键。它们通常很长吗？还有“有点慢”是什么意思？如果您还没有对代码进行概要分析，则很可能这是另一个需要时间的部分。
更新：嗯，您程序中的瓶颈是 map::find，但该地图的元素总是少于 15 个。这让我怀疑该配置文件在某种程度上具有误导性，因为在这么小的地图上查找应该不会很慢。事实上，map::find 应该如此之快，只是分析的开销可能超过 find 调用本身。我又要问了，你确定这真的是你程序的瓶颈吗？你说字符串是路径，但你没有在这个循环中做任何类型的操作系统调用、文件系统访问、磁盘访问？其中任何一个都应该比小地图上的 map::find 慢几个数量级。实际上，任何获取字符串的方法都应该比 map::find 慢。
std::map 的比较器不是 std::equal_to 它是 std::less，我不确定短路 a < compare 的最佳方法是什么，以便它比内置的更快。
如果总是有 < 15 个元素，也许您可以使用除 std::string 之外的密钥？
Motti 有一个很好的解决方案。但是，我很确定对于您的 < 15 个元素，映射不是正确的方法，因为它的开销总是大于具有适当散列方案的简单查找表的开销。在您的情况下，仅按长度进行散列甚至可能就足够了，如果仍然会产生冲突，请对所有相同长度的条目进行线性搜索。
为了确定我是否正确，当然需要一个基准，但我很确定它的结果。
您可能会考虑预先计算字符串的哈希值，并将其保存在您的地图中。这样做可以在通过 std::map 树进行搜索期间提供哈希比较而不是字符串比较的优势。
class HashedString
{
unsigned m_hash;
std::string m_string;
public:
HashedString(const std::string& str)
: m_hash(HashString(str))
, m_string(str)
{};
// ... copy constructor and etc...
unsigned GetHash() const {return m_hash;}
const std::string& GetString() const {return m_string;}
};
这样做的好处是在构造时计算一次字符串的哈希。在此之后，您可以实现一个比较功能：
struct comp
{
bool operator()(const HashedString& lhs, const HashedString& rhs)
{
if(lhs.GetHash() < rhs.GetHash()) return true;
if(lhs.GetHash() > rhs.GetHash()) return false;
return lhs.GetString() < rhs.GetString();
}
};
由于哈希现在是在HashedString构造时计算的，因此它们以这种方式存储在 std::map 中，因此比较可以在天文数字的高百分比时间内非常快速地发生（整数比较），当哈希值相等。
也许您可以在将字符串用作地图中的键之前反转字符串？如果每个字符串的前几个字母相同，这可能会有所帮助。
您可以考虑以下几点：
0）你确定这是性能瓶颈所在吗？像 Quantify、Cachegrind、gprof 或类似的结果？因为在这样的 smap 地图上查找应该相当快......
1）您可以覆盖用于比较 std::map<> 中的键的仿函数，还有第二个模板参数可以做到这一点。但是，我怀疑你能比 operator< 做得更好。
2）地图的内容变化很大吗？如果不是，并且鉴于您的地图非常小，也许使用排序向量和二进制搜索可以产生更好的结果（例如，因为您可以更好地利用内存局部性。
3) 这些元素在编译时是否已知？如果是这种情况，您可以使用完美的哈希函数来缩短查找时间。在网上搜索 gperf。
4）您是否有很多查找都找不到任何东西？如果是这样，也许与集合中的第一个和最后一个元素进行比较可能会比每次完全搜索更快地消除许多不匹配。
这些已经被建议，但更详细：
5）由于您的字符串很少，也许您可以使用不同的键。例如，您的钥匙是否都一样大？您可以使用包含固定长度字符数组的类吗？你能把你的字符串转换成数字或一些只有数字的数据结构吗？
根据使用情况，您可以使用其他一些技术。例如，我们有一个应用程序需要跟上超过一百万个不同的文件路径。问题是有成千上万的对象需要保留这些文件路径的小图。
由于向数据集添加新文件路径是一种不常见的操作，因此在向系统添加路径时，会搜索主地图。如果找不到路径，则添加它并返回一个新的有序整数（从 1 开始）。如果路径已经存在，则返回先前分配的整数。然后每个对象维护的每个映射从基于字符串的映射转换为整数映射。这不仅极大地提高了性能，而且通过没有那么多重复的字符串副本减少了内存使用量。
当然，这是一个非常具体的优化。但是当谈到性能改进时，您经常会发现自己必须针对特定问题制定量身定制的解决方案。
而且我讨厌字符串 :) 比较起来不是很慢，但是它们确实可以在高性能软件上浪费您的 CPU 缓存。
试试 std::tr1::unordered_map（在标题 <tr1/unordered_map> 中找到）。这是一个哈希映射，虽然它不维护元素的排序顺序，但可能会比常规映射快得多。
如果您的编译器不支持 TR1，请获取更新的版本。MSVC 和 gcc 都支持 TR1，我相信大多数其他编译器的最新版本也有支持。不幸的是，许多图书馆参考网站尚未更新，因此 TR1 仍然是一项很大程度上未知的技术。
我希望 C++0x 不一样。
编辑：请注意，tr1::unordered_map 的默认散列方法是 tr1::hash，可能需要专门用于 UDT。
如果您有很长的公共子字符串，则 trie 可能是比 map 或 hash_map 更好的数据结构。不过，我说“可能”——hash_map 每次查找只遍历一次键，所以应该相当快。我不会再讨论它，因为其他人已经有了。
如果某些键比其他键更频繁地查找，您也可以考虑使用展开树，但这当然会使最坏情况的查找比平衡树更糟糕，并且查找是变异操作，如果您正在使用这可能对您很重要例如读写锁。
如果您更关心查找的性能而不是修改，那么使用 AVL 树可能会比使用红黑树做得更好，我认为这是 STL 实现通常用于映射的。AVL 树通常具有更好的平衡性，因此每次查找平均需要更少的比较，但差异很小。
找到您满意的这些实现可能是一个问题。在 Boost 主页上的搜索表明他们有一个 splay 和 AVL 树，但没有一个 trie。
您在评论中提到，您从来没有找不到任何东西的查找。所以理论上你可以跳过最后的比较，在 15 < 2^4 个元素的树中，它可以给你带来 20-25% 的加速，而无需做任何其他事情。事实上，可能不止于此，因为相等的字符串是最慢的比较。是否值得为这种优化编写自己的容器是另一个问题。
您也可以考虑参考的局部性——我不知道您是否可以通过从小堆中分配键和节点来避免偶尔的页面丢失。如果您一次只需要大约 15 个条目，那么假设文件名限制低于 256 个字节，您可以确保在查找期间访问的所有内容都适合单个 4k 页面（当然，除了正在查找的键）。与几个页面加载相比，比较字符串可能是微不足道的。但是，如果这是您的瓶颈，则必须进行大量查找，所以我猜一切都相当接近 CPU。值得检查，也许。
另一个想法：如果您在有很多争用的结构上使用悲观锁定（您在评论中说程序是大量多线程的），那么无论分析器告诉您什么（CPU 周期花费在什么代码中） ，通过有效地将您限制为 1 个核心，您的成本可能比您想象的要多。试试读写锁？
hash_map不是标准的，请尝试使用unordered_maptr1 中的可用（如果您的工具链还没有它，则可以在 boost 中使用）。
对于少量字符串，您可能会更好地使用vector，因为map它通常实现为树。
你为什么不使用哈希表呢？boost::unordered_map 可以。或者您可以推出自己的解决方案，并存储字符串的 crc 而不是字符串本身。或者更好的是，将#defines 用于字符串，并使用它们进行查找，例如，
#define "STRING_1" STRING_1