Re: [boost] [Container] Provide more guarantees for flat_multimap

Subject: Re: [boost] [Container] Provide more guarantees for flat_multimap
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2014-08-16 11:39:35

On 15 Aug 2014 at 21:38, Ion Gaztañaga wrote:

> >> In which sense they have become enhanced?
> >
> > I stress the following is still in flux, but it's getting close to
> > final. The following changes were mostly agreed with Howard and
> > Jonathan, and none of the other authors of N3645 objected:
> 
> I think we should implement the minimal functions in order to improve 
> the proposal and add it to the standard when possible. Even in the 
> original proposal, "node_ptr extract(const key_type& x);" seems redundant.

Why?

> > * node_ptr_type gains the get(), release() and reset() member
> > functions so it now looks identical to a std::unique_ptr.
> 
> So why not call it unique_ptr ;-) The deleter type can be something like 
> allocator_deleter<A>, which calls a.destroy() + a.deallocate() via 
> allocator_traits. There are issues with allocator_traits::propagate_xxxx 
> but maybe solvable. A new type with nearly the same interface and 
> semantics as unique_ptr is something that sounds avoidable.

Allocators :(

I personally choose to have no opinion on this, or rather I defer to 
the opinion of others more expert in this, but I can see where you're 
coming from. I would say though that a full unique_ptr lets external 
code do stuff like reset(newptr) which may or may not be wise.

I also think that if you do go down this route, I am no longer sure 
if node_ptr_type should be a member type of each map class. Perhaps 
now a std::map_node_ptr<> used by all map STL containers makes more 
sense.

> node_ptr_type is also a bit confusing, because it holds also an 
> allocator. node_ptr_type sounds a a pointer (raw or smart) to the 
> internal node type used by the container. Maybe node_holder is a bit 
> more accurate.

My original implementation which duplicated the essence of N3645 
before I knew about N3645 used "value_type_ptr". I still think that 
the best name - after all, we're not pointing to a node, it's 
actually a smart pointer to an allocated value_type not currently 
owned nor managed by a map.

> > * The following three new node_ptr_type factory functions are added:
> >
> > 1. template<class... Args> node_ptr_type make_node_ptr(Args&&...
> > args);
> >
> > This allocates a node_ptr_type using the container allocator.
> 
> Thanks for the explanations, still don't see the need for too many 
> operations, but I will start with basic operations and start thinking 
> about your proposed extensions.

Most of my extensions are driven by the needs of a reliable latency 
concurrent_unordered_map. They are probably slightly overkill for 
something not as latency sensitive, equally they also do no harm. I 
do quite like the way that in the future one can convert a std::map 
into a std::unordered_map with very little overhead.

BTW I personally have found my extensions let you collapse a lot of 
implementation into single reusable routines. For example, 
insert/emplace are simply a make_node_ptr followed by insert, and 
insert is simply an insert_ct followed by a storage expanding insert 
if it fails. It probably isn't ideal for performance, but it sure 
makes debugging and maintenance much easier.

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ 
http://ie.linkedin.com/in/nialldouglas/