std::map 插入还是 std::map 查找？

StackOverflow https://stackoverflow.com/questions/97050

  •  01-07-2019
  •  | 
  •  

题

假设您想要保留现有条目的地图。20% 的情况下，您插入的条目是新数据。使用返回的迭代器执行 std::map::find 然后 std::map::insert 是否有优势？或者尝试插入然后根据迭代器是否指示记录已插入或未插入来采取行动是否更快？

有帮助吗？

解决方案

答案是你两者都不做。相反，您想要执行第 24 项建议的操作 有效的STL 经过 斯科特·迈耶斯:

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.second->second = v;
  }
}

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

但是，对 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;
  }
}

为了调用“插入”，我们需要支付昂贵的调用来构造我们的值类型 - 从您在问题中所说的来看，您 20% 的时间不会使用这个新值。在上述情况下，如果无法更改映射值类型，那么首先执行“查找”来检查是否需要构造元素会更有效。

或者，可以更改映射的值类型，以使用您最喜欢的智能指针类型存储数据的句柄。对 insert 的调用使用空指针（构造起来非常便宜），并且仅在必要时才构造新的数据类型。

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

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

我认为如果您先查找然后插入，额外的成本将是当您找不到密钥并在之后执行插入时。这有点像按字母顺序翻阅书籍，但找不到该书，然后再次翻阅书籍以了解将其插入的位置。这归结为您将如何处理按键以及它们是否不断变化。现在有一些灵活性，如果你没有找到它，你可以记录，异常，做任何你想做的事......

我对最上面的答案迷失了。

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

慢两倍

map.insert

对于地图中尚未存在的任何元素，因为它必须搜索两次。一次看看它是否在那里，再次寻找放置新东西的地方。

如果您担心效率，您可能需要查看 哈希映射<>.

通常，map<> 被实现为二叉树。根据您的需要，hash_map 可能更有效。

我似乎没有足够的点来发表评论，但勾选的答案对我来说似乎很冗长 - 当你认为 insert 无论如何都会返回迭代器时，为什么要搜索 lower_bound ，当你可以只使用返回的迭代器时。奇怪的。

关于效率的任何答案都取决于 STL 的具体实现。唯一确定的方法是对这两种方式进行基准测试。我猜差异不太可能很大，所以根据您喜欢的风格来决定。

map[ key ] - 让 stl 来解决它。这是最有效地传达您的意图。

是的，很公平。

如果您执行查找然后插入，则当您未命中时，您将执行 2 x O(log N)，因为查找只会让您知道是否需要插入，而不是插入应该去的位置（lower_bound 可能会帮助您） 。我的做法就是直接插入然后检查结果。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top