How should std::map be used with a value that does not have a default constructor?

Question

I've got a value type that I want put into a map. It has a nice default copy constructor, but does not have a default constructor.

I believe that so long as I stay away from using operator[] that everything will be OK.

However I end up with pretty ugly constructs like this to actually insert an object. (I think insert just fails if there is already a value for that key).

// equivalent to m[5]=x but without default construction

std::map<int,X>::iterator it = m.find(5);
if( it != m.end() )
{
   m->second = x;
}
else
{
  m->insert( std::make_pair(5,x) );
}

Which I believe will scan the map twice, and also looks pretty ugly.

Is there a neater / more efficient way to do this?

existing answer here http://stackoverflow.com/questions/1409454/c-map-find-to-possibly-insert-how-to-optimize-operations — miaout17, Dec 01 '11 at 06:38
@miaout17, yep that existing answer will solve it. However the question that is solves is a different issue IMO. — Michael Anderson, Dec 01 '11 at 06:44
@miaout17, actually that doesn't quite solve it. That is the case where you don't store a new value into the map if one already exists. But dont over write it with a new value. The functions ned to be tweaked slightly to do that ... Someone posted a solution that did that correctly and then deleted their answer :( — Michael Anderson, Dec 01 '11 at 06:48

score 2 · Answer 1 · answered Dec 01 '11 at 06:46

2

You could first get the position to insert the pair with lower_bound, then check if it's already there, and if not, insert it, providing the iterator where to insert. Something along those lines.

answered Dec 01 '11 at 06:46

Xeo

129,499
52
291
397

Kerrek SB · Accepted Answer · 2011-12-01T07:08:57.793

2

You can simply "insert-or-overwrite" with the standard insert function:

auto p = mymap.insert(std::make_pair(key, new_value));

if (!p.second) p.first->second = new_value;  // overwrite value if key already exists

If you want to pass the elements by rerference, make the pair explicit:

insert(std::pair<K&, V&>(key, value));

If you have a typedef for the map like map_t, you can say std::pair<map_t::key_type &, map_t::mapped_type &>, or any suitable variation on this theme.

Maybe this is best wrapped up into a helper:

template <typename Map>
void insert_forcefully(Map & m,
                       typename Map::key_type const & key,
                       typename Map::mapped_type const & value)
{
  std::pair<typename Map::iterator, bool> p = m.insert(std::pair<typename Map::key_type const &, typename Map::mapped_type const &>(key, value));
  if (!p.second) { p.first->second = value; }
}

edited Dec 01 '11 at 07:08

answered Dec 01 '11 at 06:51

Kerrek SB

464,522
92
875
1,084

The only issue I have with this is that constructing a pair from `key` or `new_value` may be expensive, or in the case of C++11 impossible (`new_value` could be move-only). I've ran into this issue in my code. :( – GManNickG Dec 01 '11 at 06:56
@GMan: Why not use a pair of references? Actually, does `make_pair` deduce a reference type? Otherwise use `std::tie`. – Kerrek SB Dec 01 '11 at 06:57
Both of those won't work because `insert` requires a `pair_type`. It's really just a short-coming of the container. – GManNickG Dec 01 '11 at 07:00
@GMan: Yes, true, `tie` makes tuples, not `pairs`. Meh, you can make the pair-of-references explicit; I added that. – Kerrek SB Dec 01 '11 at 07:01
1

Wouldn't it still copy, since the `insert()` itself takes a reference to `map::value_type`, which is a `pair` and not a pair of references? – Dave S Dec 01 '11 at 07:05
@DaveS: I think it's fine. It doesn't make any more copies than necessary. – Kerrek SB Dec 01 '11 at 07:07
@KerrekSB Is'n't there should be: if (!p.second) p->second = new_value; // overwrite value if key already exists ? – Ghita Dec 01 '11 at 07:10

score 2 · Answer 3 · answered Dec 01 '11 at 07:31

There are two things you missed in the interface of map (and the like):

insert(value_type) returns a std::pair<iterator, bool>, the .first member points to the element with the key you tried to insert and the .second member indicates whether it is actually the element you tried to insert or another that previously was in the container.
insert(iterator, value_type) allows you to give a hint as to where insert

The latter is not necessarily useful in your situation though.

typedef std::map<int,X> Map;

// insert and check
std::pair<Map::iterator, bool> const result =
  map.insert(std::make_pair(5, x));            // O(log N)

if (not result.second)
{
  result->first.second = x;                    // O(1)
  // OR
  using std::swap;
  swap(result->first.second, x);
}

If you type does not support assignment and there is no swap, however, you need to bite the bullet:

// locate and insert
Map::iterator position = map.lower_bound(5);         // O(log N)
if (position != map.end() and position->first == 5) 
{
  position = map.erase(position);                    // O(1)
}
map.insert(position, std::make_pair(5, x));          // O(log N) if rebalancing

In C++11, the insert methods are doubled:

insert(value_type const&) // insertion by copy
insert(P&&) // insertion by move

and with perfect forwarding we get the new emplace method. Similar to insert, but which construct the element in place by forwarding the arguments to its constructor. How it differentiate arguments for the key and value is a mystery to me though.

How should std::map be used with a value that does not have a default constructor?

3 Answers3

Linked