12

I would like to know if the STL map in c++ has contiguous memory - or is the memory assigned to the heap?

Blood
  • 4,126
  • 3
  • 27
  • 37
Master Oogway
  • 461
  • 2
  • 5
  • 10
  • 1
    What has the question to do with "alignment"? – Kerrek SB Jul 17 '12 at 18:54
  • You can't use "stack" memory for `map`; it's impossible. – user541686 Jul 17 '12 at 19:12
  • 6
    @Mehrdad: My custom `stack_allocator` would like a word with you. :P – Xeo Jul 17 '12 at 19:13
  • @Xeo: I don't think we're thinking of the same meaning for the word "stack". :P I'm talking about the CPU stack, not just anything that looks like a stack. But actually, I've been thinking of making something that allocates in a stack-like fashion. Is the purpose of your allocator to provide efficient allocation when they occur in a stack-like fashion? If so, would you mind sharing it? :D Writing allocators is a pain... – user541686 Jul 17 '12 at 19:16
  • 3
    Is there some specific reason you care. Maybe we can help more if you explain why you want to know. – Martin York Jul 17 '12 at 19:23
  • @Mehrdad: I was thinking of `char mem[N]; stack_allocator> alloc(mem); map<...> m(alloc);`, where the memory is *indeed* on the stack – Xeo Jul 17 '12 at 20:05
  • @Xeo: Oh, but then it's not really dynamically sized... – user541686 Jul 17 '12 at 20:49

2 Answers2

13

Since map is a dynamic container, the memory for its elements is dynamically allocated (whatever that means (it depends on a configurable allocator)!).

Moreover, map is a node-based container, so each element goes into a distinct, separate allocation (so as to permit maximal iterator and reference non-invalidation). Elements are almost certainly not contiguous in memory, and probably scattered about in a way that reflects how you added them.

Practically, a map will be implemented as some type of balanced tree in order to achieve logarithmic lookup, insertion and deletion times.

(If you want a data structure with contiguous storage and logarithmic lookup time, consider a sorted vector.)

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • All true, unless of course you use an allocator that goes out of its way to make the items contiguous in memory, or you get very lucky. :) – abarnert Jul 17 '12 at 19:57
  • @abarnert: They may easily be contiguous with a `stack_allocator` that takes a memory buffer as input to allocate from, but they may not be in sort order inside the memory. – Xeo Jul 17 '12 at 20:06
  • 1
    @Xeo: There's probably some node overhead in each node, meaning that the actual data is probably *never* contiguous. – Kerrek SB Jul 17 '12 at 20:21
  • @Kerrek: True that, the links between the nodes for iteration. – Xeo Jul 17 '12 at 20:23
1

It is more than likely implementation-specific, and you can certainly change the allocator of any STL container, but this is not for the faint of heart and you would need to look at the documentation for the standard library you are using.

At any rate, map is usually implemented as a red-black tree and tree nodes are on the heap.

(Tree nodes, if I understand correctly, contain instances of value_type, which are key/value pairs of your map).

Note that stack is a bad storage idea for any container as stack should be considered a scarce resource.

Community
  • 1
  • 1