我正在使用map<MyStruct, I*> map1;。显然，我总应用时间的9％用于那里。特别是我的一个主要职能的一行。地图不是很大（<1k几乎总是，<20是常见的）。
是否有我可能想要使用的替代实现？我想我不应该写自己的，但如果我认为这是一个好主意我可以。
附加信息：我总是在添加元素之前检查。如果存在密钥，我需要报告问题。在一点之后，我将大量使用地图进行查找，并且不会再添加任何元素。
首先，您需要了解地图是什么以及您正在执行的操作代表什么。 std::map是一个平衡的二叉树，查找将采用O( log N )操作，每个操作都是键的比较加上一些额外的，你可以在大多数情况下忽略（指针管理）。插入大致需要大致相同的时间来定位插入点，加上新节点的分配，实际插入树和重新平衡。虽然隐藏的常数更高，但复杂性仍然是O( log N )。
当您尝试在插入之前确定某个键是否在地图中时，会产生查找成本，如果不成功，则定位插入点的成本相同。你可以通过使用std::map::insert来避免额外的成本，它返回一个带有迭代器和bool的对，告诉你插入是否实际发生了或元素是否已经存在。
除此之外，您需要了解比较键的成本是多少，这不符合问题所示（MyStruct只能容纳一个int或其中的一千个），这是您需要考虑的事情。
最后，可能是因为map不是满足您需求的最有效的数据结构，您可能需要考虑使用具有预期的恒定时间插入的std::unordered_map（哈希表）（如果哈希函数不是很糟糕）或者对于小型数据集，甚至是一个普通的有序数组（或std::vector），您可以使用二进制搜索来定位元素（这将减少分配数量，但代价是更昂贵的插入，但如果保持的类型足够小它可能是值得的）
与性能一样，测量然后尝试了解花费的时间。另请注意，在特定功能或数据结构中花费的时间的10％可能很多或几乎没有，具体取决于您的应用程序。例如，如果您的应用程序只是在数据集中执行查找和插入，并且只占CPU的10％，那么您可以在其他任何地方进行优化！
如果钥匙已经存在，那么只是做一个insert并检查pair.second是否是false会更快吗？
像这样
if ( myMap.insert( make_pair( MyStruct, I* ) ).second == false)
{
//report error
}
else
// inserted new value
而不是每次都做一次find电话？
你可以尝试使用散列键而不是树来查找元素的map，而不是unordered_map。 This answer给出了一些暗示什么时候更喜欢unordered_map而不是map。
这可能是一个长镜头，但对于小型收藏，有时最关键的因素是cache表现。
由于std::map实现了一个红黑树，这是[AFAIK]不是非常高效缓存 - 可能实现地图作为std::vector<pair<MyStruct,I*>>将是一个好主意，并使用二进制搜索[而不是地图查找]，在非常至少它应该是有效的，一旦你开始只查找[停止插入元素]，因为std::vector更可能适合缓存而不是map。
这个因子[cpu-cache]通常在大O表示法中被忽略并隐藏为常量，但对于大型集合，它可能会产生重大影响。
您使用地图的方式是，您正在基于MyStruct实例进行查找，并且根据您的特定实现，所需的比较可能成本也可能不高。
是否有我可能想要使用的替代实现？我想我不应该写自己的，但如果我认为这是一个好主意我可以。
如果您能够很好地理解这个问题，那么您应该详细说明您的实施将如何更好。
map是正确的结构吗？如果是这样，那么您的标准库的实现可能质量很好（经过优化）。
可以简化MyStruct比较吗？
问题出在哪里 - 调整大小？抬头？
您是否最小化了复制并为结构分配成本？
正如评论中所述，如果没有适当的代码，几乎没有通用的答案可以给你。但是，如果MyStruct非常庞大，堆栈复制可能会很昂贵。也许将指针存储到MyStruct并实现自己的比较机制是有意义的：
template <typename T> struct deref_cmp {
bool operator()(std::shared_ptr<T> lhs, std::shared_ptr<T> rhs) const {
return *lhs < *rhs;
}
};
std::map<std::shared_ptr<MyStruct>, I*, deref_cmp<MyStruct>> mymap;
但是，这是您必须要分析的内容。它可能会加快速度。
你会查找这样的元素
template <typename T> struct NullDeleter {
void operator()(T const*) const {}
};
// needle being a MyStruct
mymap.find(std::shared_ptr<MyStruct>(&needle,NullDeleter()));
毋庸置疑，优化的潜力更大。