哪个元素将从 std::multimap::find 返回，同样，std::multiset::find

Question

这个问题很可能是重复的，但我找不到对它的引用。

我正在查看 std：：multiset：：find & std：：multimap：：find 函数，我想知道如果多次插入特定键，将返回哪个元素？

从描述：

请注意，此函数将迭代器返回到单个元素 （可能有多个等效元素）

问题

是保证单个元素是第一个插入的元素还是随机的？

背景

我

问的原因是我正在实现类似类的 multipmap：

typedef std::vector<Item> Item_vector;
class Item
{
  string m_name;
};
class MyItemMultiMap
{
public:
   
  // forgive me for not checking if key exist in the map. it is just an example.
  void add_item( const Item& v ) { m_map[v.m_name].push_back(v); }
  
  // is returning the first item in the vector mimic std::multimap::find behavior?
  Item& get_item( const string& v ) { return m_map[v][0]; } 
private:
  std::map<string,Item_vector> m_map;
};

我希望get_item()完全按照std::multimap::find工作。 可能吗？ 如果是这样，它将如何实施？

Answer 1

如果存在多个 find，则 find 方法可能会返回任意一个，尽管您的 STL 实现可能确实只提供第一个。

使用"lower_bound"方法更安全，++从那里迭代（参见std：：multimap：：lower_bound）。 请注意，如果您正在寻找的内容不存在，"lower_bound"会返回另一个元素的 ref！

Answer 2

C++ 标准说，对于任何关联容器a，a.find(k) "返回一个迭代器，指向一个元素，其键等同于 k ，如果没有找到这样的元素，则返回a.end()"，并且它不会对multimap施加任何额外的要求。由于它不指定返回哪个元素，因此允许实现返回任何匹配的元素。

如果你试图在你运行的平台上模仿multimap的确切行为，那是个坏消息，但如果你的目标只是满足与multimap相同的要求，这是个好消息：你可以返回任何你想要的匹配元素，特别是总是返回第一个元素是可以的。

Answer 3

http://en.cppreference.com/w/cpp/container/multimap/find

查找具有键键的元素。如果有几个元素与键 在容器中，选择之前插入的容器。

因此，将返回第一个元素的迭代器。

一般来说，我发现equal_range是更有用的方法，返回一对迭代器，分别指向第一个，在最后一个之后，与键匹配的元素。