Re: [boost] [interprocess][multi_index] emplace() is not sufficient for maps

24 Sep 2009

      Howard Hinnant skrev:
...
On Sep 19, 2009, at 4:18 AM, Thorsten Ottosen wrote:
...
Ion Gaztañaga skrev:
...
Thorsten Ottosen escribió:
...
Suggestion:
Using std::map as an example as I am not familiar with 
[interprocess][multi_index].  Also using C++0X notation (to be emulated 
in C++03).
Add to the container:
template <class Key, class T, class Compare, class Allocator>
class map
{
public:
    ...
    typedef /details/ node_ptr;
node_ptr remove(const_iterator p);
    pair<iterator, bool> insert(node_ptr&& nd);
    iterator             insert(const_iterator p, node_ptr&& nd);
    ...
};
map::node_ptr is a move-only smart pointer which holds an Allocator* and 
a map::node* (or equivalent smart pointer as interprocess may need?).  
node_ptr roughly looks like:
template <class Key, class T, class Allocator>
class node_ptr
{
    typedef typename Allocator::value_type node;
node*        node_;
    Allocator*   alloc_;
node_ptr(const node_ptr&);
    node_ptr& operator=(const node_ptr&);
public:
    typedef pair<Key, T> value_type;
node_ptr() : node_(), alloc_() {}
    ~node_ptr() {reset();}
node_ptr(node_ptr&& n)
        : node_(n.node_),
          alloc_(n.alloc_)
        {
            n.node_ = nullptr;
            n.alloc_ = nullptr;
        }
node_ptr& operator=(node_ptr&& n)
        {
            reset();
            node_ = n.node_;
            alloc_ = n.alloc_;
            n.node_ = nullptr;
            n.alloc_ = nullptr;
            return *this;
        }
void reset()
    {
        if (node_ != nullptr)
        {
            node_->__value_.~pair<const Key, T>();
            alloc_->deallocate(node_, 1);
        }
    }
value_type& operator*() const
    {
        return *(value_type*)addressof(node_->__value_);
    }
    value_type* operator->() const
    {
        return (value_type*)addressof(node_->__value_);
    }
private:
    node_ptr(node* n, Allocator* a) : node_(n), alloc_(a) {}
node* release()
    {
        node* r = node_;
        node_ = 0;
        alloc_ = 0;
        return r;
    }
template <class, class, class, class> friend class map;
};
The client can default construct a node_ptr, or get one from 
map::remove().  He can extract a node, get const-free access to the 
node's value field (as if node_ptr pointed straight at the value field), 
and insert the node back into any map that has an equal allocator:
M::node_ptr p = m1.remove(next(m1.cbegin(), 3));
    p->first = 10;
    m2.insert(std::move(p));
The remove() is nothrow.
The client manipulates the node's value outside of the container.  If 
that manipulation throws, or is abandoned, node_ptr cleans up.
insert() can only throw if the Compare operation throws, and if that 
happens, node_ptr continues to own the node.  Thus the client can catch 
exceptions if desired outside the insert without loosing ownership of 
the node (which is why insert doesn't take node_ptr by value).
Constraints:
A node_ptr returned from m.remove() must not outlive m, unless it is 
reset/move-assigned first.
Notes:
This solution addresses both Thorsten's use case and Alan's:
I'm fine with this interface, and it seems less complicated compared to 
Joaquin's modify_key().

It doesn't quite address my first issue though, namely that I need to 
construct the mapped value in the node, and then compute the key from 
this mapped value (after some modification).

I think if the node_ptr class had

  a) a forwarding (Key,Value) constructor

  b) an emplacing constructor that
  constructed the pair with (Key,...)

then I could do exactly what I needed :-)

-Thorsten