101

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

4

8 回答 8

154

答案是你都不做。相反，您想做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
}
于 2008-09-19T13:52:25.413 回答
13

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

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 之类的值类型，上述方法将比 find 后跟 insert 更有效（在没有编译器优化的情况下）。如上所述，这是因为通过地图的搜索只发生一次。

但是，对 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.first->second = v;
  }
}

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

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

于 2008-09-19T11:09:50.743 回答
8

2 之间的速度几乎没有任何差异，find 将返回一个迭代器， insert 做同样的事情，并且无论如何都会搜索地图以确定条目是否已经存在。

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

于 2008-09-18T21:17:26.610 回答
5

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

于 2008-09-18T21:24:42.227 回答
1

如果您关心效率，您可能需要查看hash_map<>。

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

于 2008-09-18T21:26:30.957 回答
1

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

于 2011-07-28T06:47:05.877 回答
-1

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

于 2008-09-18T21:21:27.287 回答
-2

map[ key ] - 让 stl 整理出来。那是最有效地传达你的意图。

是的，很公平。

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

于 2008-09-18T21:19:43.563 回答