This is a C++ blog...
In this blog, I'll quickly discuss what PMR is at a very high level and discuss std::pmr::map's practicality and feasibility in competitive programming.
Containers in the pmr namespace allow you to separate memory allocation from data structure logic, which means you can plug in custom memory resources to control how and where memory is allocated.
This setup usually comes in handy in actual softwares where you want full control of allocated memory, but what about cp?
When can I use it?
If you know a clear and tight upper bound on the number of elements you will insert into your container. This is commonly the case when you use std::map.
How do I use it?
Suppose you are using an std::map<int,int> and you know that you will access at most 10^5 keys. We can use the expression: sizeof(std::_Rb_tree_node<std::pair<const int, int>>) to know the size of a single node in the underlying red-black tree used by std::map.
We need to allocate some memory (on the heap, stack or even statically) with the size of a single node multiplied by the number of nodes your upper bound requires.
static constexpr node_size = sizeof(std::_Rb_tree_node<std::pair<const int, int>>);
std::byte mem[node_size * 100'000];
Finally we need to declare some wrapper to help our containers use this memory, that is std::pmr::monotonic_buffer_resource
std::pmr::monotonic_buffer_resource resource(mem, sizeof(mem));
Now we can declare our std::pmr::map:
std::pmr::map<int,int> is_this_fast(&resource);
Should I use it?
Short answer: No
But... if you are writing a very nasty data structure just for a small speedup, maybe you should try this first.
As you can see, even if std::pmr::map is faster, the difference between std::map and std::pmr::map is very small and since this blog isn't sponsored by pmr I threw in std::unordered_map.
I didn't really test other containers like set or multiset and since we already have std::vector::reserve I felt its not necessary to discuss that.
