CODEWITHSUNDEEP
c++dictionary
Boiethios
Boiethios

Reputation: 42759

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

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?

Upvotes: 1

Views: 698

Answers (2)

Kerrek SB
Kerrek SB

Reputation: 477040

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

Upvotes: 2

WhiZTiM
WhiZTiM

Reputation: 21576

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.

Upvotes: 2

Related Questions