17

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?

rustyhu
  • 1,912
  • 19
  • 28
idanshmu
  • 5,061
  • 6
  • 46
  • 92

3 Answers3

11

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!

idanshmu
  • 5,061
  • 6
  • 46
  • 92
Carl Colijn
  • 1,423
  • 9
  • 29
4

The C++ standard says that for any associative container a, a.find(k) "returns an iterator pointing to an element with the key equivalent to k, or a.end() if such an element is not found", and it doesn't impose any additional requirements on multimap. Since it doesn't specify which element is returned, the implementation is permitted to return any matching element.

If you're trying to imitate the exact behavior of multimap on the platform where you're running, that's bad news, but if your goal is just to satisfy the same requirements as multimap, it's good news: you can return any matching element that you want to, and in particular it's fine to just always return the first one.

Geoff Romer
  • 2,358
  • 1
  • 18
  • 19
-1

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

Finds an element with key key. If there are several elements with key in the container, the one inserted earlier is selected.

So, an iterator to the first element will be returned.

In general, I find equal_range to be the more useful method, returning a pair of iterators pointing respectively at the first, and after the last, elements matching the key.

small_duck
  • 3,038
  • 20
  • 28
  • 3
    I cannot find anything in the C++ standard to back up the cppreference.com quote. – juanchopanza Jan 14 '14 at 11:29
  • 2
    Indeed, the standard (C++11 table 102) only specifies that it "returns an iterator pointing to an element with the key equivalent to [the key]", with no indication of which one if there's a choice. – Mike Seymour Jan 14 '14 at 11:42
  • 2
    cppreference corrected, thanks to @juanchopanza for bringing it up on the Talk page there. – Cubbi Jan 14 '14 at 13:36
  • In C++98 there is no guarantee that equivalent keys maintain insertion order. C++11 however does guarantee that. However find() still has no guarantee about which one it finds – CashCow Jun 30 '15 at 14:44
  • The reference quoted says `Finds an element with key equivalent to key. If there are several elements with key in the container, any of them may be returned`. The operative word here is *any*. – Bo R Sep 08 '19 at 09:32