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@xxxxxxxxx> 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;
