2

If I have a std::map with default allocator that initialises to no element, will memory be allocated when it is defined to provide some capacity? Is there a way I can prevent the memory allocation until the first time an insertion is performed? I would like this behaviour because I need to frequently create a map, but it is often not used at all and thus no element is inserted. I would like to pay the cost of memory allocation only when an element is inserted.

i.e.

std::map<string, double> foo{}; // Is there memory allocation here?
RelativisticPenguin
  • 185
  • 8
  • The answer depends on which STL you're using. – Botje Jul 28 '21 at 13:38
  • are you sure an empty map allocates anything? Which compiler? – Marek R Jul 28 '21 at 13:41
  • I've never tried it, but your question made me wonder: How would I find out the answer ? I think I would try to subclass `std::allocator` by defining only `allocate` _(which should 'hide' the base implementation)_, so that I would be able to probe **when** it is effectively called... _(the definition of `allocate` only has to route the call to the base implementation)_. To use it, pass it as the 4th argument of `std::map` _(and set the 3rd to `std::less`)_. Then you should be able to answer the question by yourself... ;) – Tenphase Jul 28 '21 at 13:48
  • @Tenphase Maybe the simplest way is to redefine `operator new`; live demo: https://godbolt.org/z/zK3Eoh3WK. With my MSVC, it outputs 40, which supports the Artyer's answer. – Daniel Langr Jul 28 '21 at 13:56
  • @DanielLangr Yes, but your solution would be hard to use within already written code. Except if you subclass `std::map`, which would even be more complicated... By _hiding_ `allocate` on a single user-defined `allocator`, you would have the ability to probe any particular instance of any _STL_ container. Hence the idea/proposition... ;) – Tenphase Jul 28 '21 at 14:02
  • @Tenphase That's generally true, but I don't think OP would need to track allocations in the existing code. They just need to know whether their implementation actually does or does not allocate in map's default constructor, which can be done with a simple test program. For a complex existing code, I would use some heap profilers such as Heaptrack. – Daniel Langr Jul 28 '21 at 14:04
  • @Tenphase Daniel has exactly hit the point. I would like only to find out if my current implementation allocates memory, or if the C++ standard says anything about it. – RelativisticPenguin Jul 29 '21 at 08:40
  • @DanielLangr & RelativisticPenguin that makes sense. I just took the habit to develop my own diagnostic tools, and usually let them active in debug. This is because, like everyone has certainly experienced once _(the answer of Artyer demonstrates it somehow)_, there's often differences between what a thing should be _(how it is supposed to behave)_ and its actual implementation here and there... At my last job, I had to rewrite and maintain alone a code base of ~470,000 LoC in 4 languages. I had to find strategies for the code to tell me what's wrong before having to find it by myself... – Tenphase Jul 30 '21 at 04:15

1 Answers1

3

A more detailed answer to a similar question can be found here: https://stackoverflow.com/a/57299732/5754656

What an empty / default constructed map is isn't mandated by the standard. Most have their internal pointers point to some "end node". In libc++ and libstdc++, this end node is not heap allocated, and the default constructor is marked noexcept (and there is no allocation, as you want). In Microsoft's standard library, the end node is on the heap and there would be memory allocation.

The only way to prevent memory allocation if not used is to not call the default constructor. This could mean using alternative map implementations or using a std::optional<std::map> or something else

Artyer
  • 31,034
  • 3
  • 47
  • 75
  • OT: This has also interesting consequences. When map's default constructor allocates in Microsoft STL, this basically means that its move constructor is not `noexcept` as well (needs to get a map into an empty = default-constructed state). Then, once one has a vector of maps, these maps are _copied_ when the vector reallocates. This is not only inefficient, but it disallows having a non-copyable objects in maps that are contained in a vector (such as `std::vector>>`). Several question have already been posted here about this problem. – Daniel Langr Jul 29 '21 at 12:59