C++ std::map 插入还是 std::map 查找？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/97050/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
std::map insert or std::map find?
提问by Superpolock
Assuming a map where you want to preserve existing entries. 20% of the time, the entry you are inserting is new data. Is there an advantage to doing std::map::find then std::map::insert using that returned iterator? Or is it quicker to attempt the insert and then act based on whether or not the iterator indicates the record was or was not inserted?
假设您要保留现有条目的地图。20% 的情况下，您插入的条目是新数据。使用返回的迭代器执行 std::map::find 然后执行 std::map::insert 是否有优势？或者尝试插入然后根据迭代器是否指示记录是否插入会更快？
回答by luke
The answer is you do neither. Instead you want to do something suggested by Item 24 of Effective STLby Scott Meyers:
答案是你两者都不做。相反，您想要做Scott Meyers的Effective STL的第 24 条建议的事情：
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
}
回答by Richard Corden
The answer to this question also depends on how expensive it is to create the value type you're storing in the map:
这个问题的答案还取决于创建存储在地图中的值类型的成本：
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.second->second = v;
}
}
For a value type such as an int, the above will more efficient than a find followed by an insert (in the absence of compiler optimizations). As stated above, this is because the search through the map only takes place once.
对于诸如 int 之类的值类型，上述方法比 find 后跟插入（在没有编译器优化的情况下）更有效。如上所述，这是因为通过地图的搜索只发生一次。
However, the call to insert requires that you already have the new "value" constructed:
但是，调用 insert 要求您已经构建了新的“值”：
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.second->second = v;
}
}
In order to call 'insert' we are paying for the expensive call to construct our value type - and from what you said in the question you won't use this new value 20% of the time. In the above case, if changing the map value type is not an option then it is more efficient to first perform the 'find' to check if we need to construct the element.
为了调用“插入”，我们为构建我们的值类型的昂贵调用付出了代价——从你在问题中所说的来看，你不会在 20% 的情况下使用这个新值。在上述情况下，如果更改地图值类型不是一个选项，那么首先执行“查找”以检查我们是否需要构造元素会更有效。
Alternatively, the value type of the map can be changed to store handles to the data using your favourite smart pointer type. The call to insert uses a null pointer (very cheap to construct) and only if necessary is the new data type constructed.
或者，可以更改映射的值类型以使用您最喜欢的智能指针类型存储数据句柄。对 insert 的调用使用空指针（构造起来非常便宜），并且仅在必要时才构造新的数据类型。
回答by gbjbaanb
There will be barely any difference in speed between the 2, find will return an iterator, insert does the same and will search the map anyway to determine if the entry already exists.
两者之间的速度几乎没有任何差异， find 将返回一个迭代器， insert 执行相同的操作并且无论如何都会搜索地图以确定条目是否已经存在。
So.. its down to personal preference. I always try insert and then update if necessary, but some people don't like handling the pair that is returned.
所以..这取决于个人喜好。我总是尝试插入然后在必要时更新，但有些人不喜欢处理返回的对。
回答by PiNoYBoY82
I would think if you do a find then insert, the extra cost would be when you don't find the key and performing the insert after. It's sort of like looking through books in alphabetical order and not finding the book, then looking through the books again to see where to insert it. It boils down to how you will be handling the keys and if they are constantly changing. Now there is some flexibility in that if you don't find it, you can log, exception, do whatever you want...
我认为如果你先查找然后插入，额外的成本将是当你没有找到键并在之后执行插入时。这有点像按字母顺序浏览书籍并没有找到这本书，然后再次浏览书籍以查看将其插入的位置。这归结为您将如何处理密钥以及它们是否不断变化。现在有一些灵活性，如果你没有找到它，你可以记录，异常，做任何你想做的......
回答by gman
I'm lost on the top answer.
我迷失在最佳答案上。
Find returns map.end() if it doesn't find anything which means if you are adding new things then
Find 返回 map.end() 如果它没有找到任何东西，这意味着如果你正在添加新的东西然后
iter = map.find();
if (iter == map.end()) {
map.insert(..) or map[key] = value
} else {
// do nothing. You said you did not want to effect existing stuff.
}
is twice as slow as
是慢的两倍
map.insert
for any element not already in the map since it will have to search twice. Once to see if it's there, again to find the place to put the new thing.
对于地图中尚未存在的任何元素，因为它必须搜索两次。一次看看它是否在那里，再次找到放置新东西的地方。
回答by Stonky
I don't seem to have enough points to leave a comment, but the ticked answer seems to be long winded to me - when you consider that insert returns the iterator anyway, why go searching lower_bound, when you can just use the iterator returned. Strange.
我似乎没有足够的分数来发表评论，但打勾的答案似乎对我来说是冗长的 - 当您认为 insert 无论如何都会返回迭代器时，为什么要搜索lower_bound，当您可以只使用返回的迭代器时。奇怪的。
回答by Adam Tegen
If you are concerned about efficiency, you may want to check out hash_map<>.
如果您担心效率，您可能需要查看hash_map<>。
Typically map<> is implemented as a binary tree. Depending on your needs, a hash_map may be more efficient.
通常 map<> 被实现为二叉树。根据您的需要， hash_map 可能更有效。
回答by Mark Ransom
Any answers about efficiency will depend on the exact implementation of your STL. The only way to know for sure is to benchmark it both ways. I'd guess that the difference is unlikely to be significant, so decide based on the style you prefer.
任何有关效率的答案都取决于您的 STL 的确切实现。确定知道的唯一方法是对它进行两种方式的基准测试。我猜想差异不大，所以根据你喜欢的风格来决定。
回答by Mark Ransom
map[ key ] - let stl sort it out. That's communicating your intention most effectively.
map[ key ] - 让 stl 整理一下。这是最有效地传达您的意图。
Yeah, fair enough.
是的，够公平。
If you do a find and then an insert you're performing 2 x O(log N) when you get a miss as the find only lets you know if you need to insert not where the insert should go (lower_bound might help you there). Just a straight insert and then examining the result is the way that I'd go.
如果您先查找然后插入，当您错过时，您将执行 2 x O(log N)，因为查找只会让您知道是否需要插入而不是插入应该去的位置（lower_bound 可能会在那里帮助您） . 只是直接插入然后检查结果是我要走的方式。
