On 15 Aug 2014 at 19:02, Ion Gaztañaga wrote:
El 15/08/2014 18:30, Niall Douglas escribió:
On 15 Aug 2014 at 0:28, Vinícius dos Santos Oliveira wrote:
Currently, flat_multimap mirrors C++98's multimap concept.
I'd like to propose an update to flat_multimap fulfil the C++11's multimap concept.
Can I persuade you to also implement the N3645 (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3645.pdf) extensions?
Sure. Open a trac ticket so it's not forgotten. No promise for Boost 1.57, though.
Let me finish my concurrent_unordered_map which implements that superset of N3645 first.
If you're interested, they have become enhanced since, and I can tell you those enhancements on request. However, the essence of the extensions remains the same - they make maps much faster and lower latency by letting you do node allocation outside of any mutex locks.
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: * node_ptr_type gains the get(), release() and reset() member functions so it now looks identical to a std::unique_ptr. * 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. 2. template<class U> node_ptr_type rebind_node_ptr(typename U::node_ptr_type &&p); This rebinds, with potential reallocation, a foreign node_ptr_type to this container's allocator. If the allocators are identical and the type is an rvalue ref, a simple move rebind of the pointer occurs, if they are not the same allocator or the type is not a rvalue ref, a new allocation and forward is performed. This lets one move node_ptr_type instances between maps as efficiently as possible without needing to hold any mutexs. 3. template<class InputIterator> std::vector<node_ptr_type> make_node_ptrs(InputIterator start, InputIterator finish, value_type **to_use=nullptr); This is an interesting one. This manufactures many node_ptr_types from the input iterator range, optionally using an externally supplied list of already allocated storage. This optionally lets you use batch/burst allocation to very substantially reduce amortised memory allocation overheads. * The proposed insert_return_t insert(node_ptr_type v) becomes std::pair<iterator, bool> insert(node_ptr_type &&v) instead. We dispense with the insert_return_t type and the input rvalue ref is the same as on entry if the operation fails. * A new std::pair<iterator, bool> insert_ct(node_ptr_type &&v) inserts only if no new memory would be allocated. This is highly valuable for low latency use. * merge() is now of two forms: 1. template<class U> void merge(U &o) where U is any map providing a node_ptr_type. This is surprisingly trivial to implement actually thanks to rebind_node_ptr() above e.g. template<class U> void merge(U &o) { for(typename U::iterator it=o.begin(); it!=o.end(); it=o.begin()) { typename U::node_ptr_type e=o.extract(it); insert(rebind_node_ptr(e)); } } 2. template<class _Hash, class _Pred, class _Alloc> void merge(concurrent_unordered_map<Key, T, _Hash, _Pred, _Alloc> &o) is an optional local map container specialisation. It may offer stronger guarantees and performance than the generic template<class U> void merge(U &o). I think that is more or less it. Obviously this is for code not fully tested yet, so gotchas and surprises may yet present. Comments are welcome. My extensions may be poorly thought through. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/