How to add element in std::map doing allocation oneself?

Question

The purpose behind my question is to use std::map (ie insertion, deletion, access) with guarantee that no exception will throw from std::map implementation.

Deletion is not a problem, neither access if one use things carefully (no at without check for example).

But insertion is another problem. In this code:

#include <map>

struct foo{};

int main()
{
  std::map<int, foo> my_map;

  my_map.insert(std::pair<int, foo>(42, foo{}));
}

my_map do some allocation and throw if there is no more memory.

Now, what I want is a way to do this:

#include <map>

struct foo{};

int main()
{
  std::map<int, foo> my_map;
  auto my_new_pair{ new std::pair<int, foo>(42, foo{}) };

  if (my_new_pair) // ok, we could build the node
  {
    my_map.insert(my_new_pair); // no allocation, my_map only takes the "ownership" of my_new_pair
  }
}

but there is no such overload of insert.

Do you guys have a solution?

Give the map a custom allocator. You can then make that allocator unexceptional ;). You will have to work out what you want to have happen if you run out of memory though. — NathanOliver, Jan 25 '17 at 14:50

Kerrek SB · Answer 1 · 2017-01-25T15:45:58.627

2

Use node extraction and transplanation:

{
    std::map<int, foo> staging_map;
    staging_map.emplace(42, foo{});

    real_map.insert(staging_map.extract(42));  // cannot throw
}

You're not quite doing the allocation "yourself", but you basically can get hold of a pre-allocated map node with this approach that you can use to your own ends until you're ready to insert it into the map, e.g.:

auto nh = staging_map.extract(42);
// Done initializing.

// use nh freely

real_map.insert(std::move(nh));  // guaranteed to work

edited Jan 25 '17 at 15:45

answered Jan 25 '17 at 14:54

Kerrek SB

464,522
92
875
1,084

1

Note that it is from C++17. – Jarod42 Jan 25 '17 at 15:10
Can't `staging_map.emplace(42, foo{});` still throw an exception? – NathanOliver Jan 25 '17 at 15:42
@NathanOliver yes, so I think that does not solve the problem. – Boiethios Jan 25 '17 at 15:43
@NathanOliver: Yes, sure, there's always *some* part where you allocate something and that can fail. The upshot is that we can move that point arbitrarily far away from the final insertion with an approach like this. – Kerrek SB Jan 25 '17 at 15:44
Okay. Just wanted to check. It will be nice when we can actually move the nodes. – NathanOliver Jan 25 '17 at 15:45
@KerrekSB Sure il could fit for some cases, but in my case we do not have too much memory, and whatever the place, we do not want exceptions. – Boiethios Jan 25 '17 at 15:47
@Boiethios: Hm, your question shows use of `new` as an design goal. How does that square with not wanting exceptions? – Kerrek SB Jan 25 '17 at 16:00

score 2 · Accepted Answer · edited May 23 '17 at 11:45

The purpose behind my question is to use std::map (ie insertion, deletion, access) with guarantee that no exception will throw from std::map implementation.

If you leave the default std::allocator in place when instantiating a

std::map<Key, T, Com=std::less<Key>, Allocator=std::allocator<...>>;

then you cannot make any exception guarantees. in inserts or emplace.

23.2.1/8: Unless otherwise specified, all containers defined in this clause obtain memory using an allocator

I don't see how its possible to do inserts without memory allocation in most STL implementations because they mostly make use of Red Black Trees with heap allocated nodes. You may want to use a custom allocator that allocates from an existing memory pool, with noexcept guarantees. Or write your own container.

Your answer seems the closest of my need. In the custom allocator I test the return of `new` and abort the program if `nullptr`. — Boiethios, Jan 30 '17 at 18:25

How to add element in std::map doing allocation oneself?

2 Answers2