stl_map Implementation Details for Development of Custom Allocator

[Umara Dissanayake]

So sorry Jonathan I actually had the issue in stl_map.h

129     typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
130                        key_compare, _Pair_alloc_type> _Rep_type;

I can't see where _Rb_tree is defined? stl_tree.h is not included by
stl_map? What am I missing?

On Thu, Aug 29, 2013 at 5:20 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> On 29 August 2013 12:19, Umara Dissanayake wrote:
>> Hi Jonathan,
>>
>> Thanks for your reply.
>>
>> "To avoid the copy done by get_allocator() the container would have to
>> store two allocator objects, which would increase the size of some
>> maps.  The design of the STL assumes copying allocators is relatively
>> cheap"
>>
>> This is what I needed to know, exactly WHY this design decision was made.
>
> Traditionally allocators are lightweight and stateless, so copying
> them is cheap.  Storing two separate objects is not necessary if
> copying them is cheap. That's a decision made 15 years ago during
> standardization of C++ 1998, partly because specifying the semantics
> of stateful allocators was too complicated to get right at the time.
>
>
>> I was proposing to have two pointers pointing to objects of
>> Alloc<_Rb_tree_node> and Alloc<value_type>. Forgive my incorrect
>> terminology I've only been programming in C++ for six months.
>
> You don't need pointers to objects, you need the objects themselves.
>
>>
>>
>> If you could indulge me for one more question.
>>
>> In the code for stl_tree, the member variable _M_impl is used in quite
>> a number of places, though I cannot seem to be able to find its
>> initial definition. Has this been defined in some other way than being
>> included in header files?
>
> It's defined in _Rb_tree, maybe you missed it:
>
>       _Rb_tree_impl<_Compare> _M_impl;