which element will be returned from std::multimap::find, and similarly std::multiset::find?

Question

Most likely this question is a duplicate but I could not find a reference to it.

I'm looking at std::multiset::find & std::multimap::find functions and I was wondering which element will be returned if a specific key was inserted multiple times?

From the description:

Notice that this function returns an iterator to a single element (of the possibly multiple equivalent elements)

Question

Is it guaranteed that the single element is the first one inserted or is it random?

Background

The reason I'm asking is that I'm implementing multipmap like class:

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

I'd like get_item() to work exactly as std::multimap::find. is it possible? if so, how would it be implemented?

Answer 1

The find method may return an arbitrary one if more than one is present, though your STL implementation might indeed just give the first one.

It's safer to use the 'lower_bound' method, and ++ iterate from there (see std::multimap::lower_bound). Do note though that 'lower_bound' returns a ref to another element if what you're looking for isn't present!