假设有一个地图，您想要保留现有条目。20%的情况下，您要插入的条目是新数据。使用std :: map :: find然后使用返回的迭代器进行std :: map :: insert是否有优势？还是尝试插入，然后根据迭代器指示记录是否已插入而采取行动更快？
假设您想要在保留现有条目的情况下向地图中插入新数据。在这种情况下，使用std :: map :: find来查找该数据是否已经存在于地图中可以减少不必要的插入尝试并节省时间。如果数据不存在，则需要使用std :: map :: insert将其插入地图中。但是，如果数据已经存在，则不需要进行插入操作。
typedef map<int, int> MapType; // Your map type may vary, just change the typedef
MapType mymap;
// Add elements to map here
int k = 4; // assume we're searching for keys equal to 4
int v = 0; // assume we want the value 0 associated with the key of 4
MapType::iterator lb = mymap.lower_bound(k);
if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
// key already exists
// update lb->second if you care to
}
else
{
// the key does not exist in the map
// add it to the map
mymap.insert(lb, MapType::value_type(k, v)); // Use lb as a hint to insert,
// so it can avoid another lookup
}
这个问题的答案还取决于在地图中存储的值类型的创建成本有多高：
typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;
void foo (MapOfInts & m, int k, int v) {
IResult ir = m.insert (std::make_pair (k, v));
if (ir.second) {
// insertion took place (ie. new entry)
}
else if ( replaceEntry ( ir.first->first ) ) {
ir.first->second = v;
}
}
对于像int这样的值类型，上述方法比查找和插入的组合更有效（在没有编译器优化的情况下）。如上所述，这是因为对映射的搜索只发生一次。
然而，调用插入需要你已经构造了新的“value”：
class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;
void foo (MapOfLargeDataType & m, int k) {
// This call is more expensive than a find through the map:
LargeDataType const & v = VeryExpensiveCall ( /* ... */ );
IResult ir = m.insert (std::make_pair (k, v));
if (ir.second) {
// insertion took place (ie. new entry)
}
else if ( replaceEntry ( ir.first->first ) ) {
ir.first->second = v;
}
}
在速度方面，这两者几乎没有什么区别，find将返回一个迭代器，而insert也会查找map以确定条目是否已存在。
所以，这取决于个人喜好。我通常尝试插入然后再根据需要更新，但有些人不喜欢处理返回的pair。
我认为，如果你进行查找然后插入的话，当你没有找到键并且在之后执行插入操作时，额外的成本会增加。这有点像按字母顺序查找书籍，没找到书，然后再次查找书籍以确定应将其插入到哪里。这归结于如何处理密钥以及它们是否经常更改。现在有一些灵活性，如果你找不到它，你可以记录、抛出异常或者采取任何你想要的操作...
map::lower_bound代替map::find，但是更加繁琐。 - Justme0如果您关心效率，您可能需要查看hash_map<>。
通常，map<>实现为二叉树。根据您的需求，使用hash_map可能更有效。
我似乎没有足够的积分来发表评论，但是被选中的答案对我来说似乎有点冗长——考虑到插入操作会返回迭代器，为什么要去搜索 lower_bound 呢？直接使用返回的迭代器不就可以了吗？很奇怪。
关于效率的任何回答都取决于您的STL的确切实现方式。唯一确定的方法是两种方式都进行基准测试。我猜差别不太可能显著，因此请根据您喜欢的风格做出决定。
insert没有使用从lower_bound调用提供的提示来避免第二个O(log n)搜索，那么这是一个相当糟糕的质量缺陷。没有理由让find、lower_bound或insert使用根本不同的算法，因此通过避免第二次查找来将两个O(log n)查找减少为一个应该会提供有意义的好处。 - ShadowRangermap[key] - 让STL自行排序，这是最有效地传达你的意图。
是啊，说得没错。
如果你进行查找然后插入，那么在出现未命中时，你要执行2 x O(log N)操作，因为查找只让你知道是否需要插入而不是插入的位置（使用lower_bound可能会有所帮助）。我会选择直接插入，然后检查结果。