关于c ++：std :: map插入还是std :: map查找？

std::map insert or std::map find?

假设要在其中保留现有条目的地图。 20％的时间，您要插入的条目是新数据。使用返回的迭代器执行std :: map :: find然后进行std :: map :: insert有好处吗？还是尝试插入然后根据迭代器是否指示记录已插入而采取行动来更快？

答案是你什么都不做。相反，您想要执行Scott Meyers的《有效STL的第24条》建议的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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
}

这个问题的答案还取决于创建要存储在地图中的值类型的成本：

1
2
3
4
5
6
7
8
9
10
11
12

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;
}
}

对于诸如int的值类型，上面的方法将比在插入后进行查找(在没有编译器优化的情况下)更有效。如上所述，这是因为通过地图的搜索仅发生一次。

但是，插入调用要求您已经构造了新的"值"：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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;
}
}

为了调用"插入"，我们为构建值类型的昂贵调用付出了代价-根据您在问题中所说的，您不会在20％的时间内使用此新值。在上述情况下，如果不选择更改地图值类型，则首先执行"查找"以检查是否需要构造元素会更有效。

另外，可以使用您喜欢的智能指针类型来更改映射的值类型以存储数据的句柄。插入调用使用空指针(构造起来非常便宜)，并且仅在必要时构造新的数据类型。

2之间的速度几乎没有任何区别，find将返回一个迭代器，insert进行相同的操作，并且无论如何都会搜索该映射以确定该条目是否已经存在。

所以..其取决于个人喜好。我总是尝试插入，然后在必要时进行更新，但是有些人不喜欢处理返回的对。

我认为如果您先查找然后插入，那么额外的费用将是您找不到密钥并在之后执行插入操作。这有点像按字母顺序浏览书籍，而不是查找书籍，然后再次浏览书籍以查看将其插入到哪里。归结为您将如何处理按键以及它们是否不断变化。现在有了一些灵活性，如果您找不到它，则可以记录日志，进行异常，执行任何您想做的事情...

我迷失了最佳答案。

如果找不到任何内容，则Find返回map.end()，这意味着如果要添加新内容，则

1
2
3
4
5
6

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.
}

慢两倍