CODEWITHSUNDEEP
c++
Michael Anderson
Michael Anderson

Reputation: 73480

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

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?

Upvotes: 6

Views: 936

Answers (3)

Matthieu M.
Matthieu M.

Reputation: 299810

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.

Upvotes: 2

Kerrek SB
Kerrek SB

Reputation: 477040

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

Upvotes: 2

Xeo
Xeo

Reputation: 131789

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.

Upvotes: 2

Related Questions