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

Question

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

Answer 1

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

Answer 2

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

是的，很公平。

如果你先查找然后插入，那么当你错过时，你将执行 2 x O(log N)，因为查找只会让你知道是否需要插入，而不是插入应该去的地方（lower_bound 可能会帮助你） 。 我的做法就是直接插入然后检查结果。

Answer 3

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

Answer 7

答案是你两者都不做。 相反，您想要执行 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
}

Answer 8

这个问题的答案还取决于创建要存储在映射中的值类型的成本有多大：

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

但是，对 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 的调用使用空指针（构造起来非常便宜），并且仅在必要时才构造新的数据类型。