Joaquin M Lopez Munoz skrev:

...

The situation is characterized by the need to calculate the key after the mapped value (a heavy object) has been placed in the pair. To calculate the key the mapped value needs to be modified (the key is calculated as a side-effect).

I therefore suggest that we add a new function:

typedef ... map; map m; map::node_ptr p = m.get_node_ptr(<like emplace, but only for constructing the mapped value>); p->pair.first = modify( p->pair.second ); m.insert( boost::move(p) );

Thoughts?

Why can't you just do the following?

map::mapped_type x=...; map::key_type k=modify(x); m.emplace(boost::move(k),boost::move(x));

I could, but moving the mapped object is just as expensive as copy-construction, and it is exactly this I want to avoid. -Thorsten

Ion Gaztañaga skrev:

Thorsten Ottosen escribió:

...

Hi Ion and Joaquín,

This issue is related to node-based containers. I think you both have added emplace() to provide efficient in-place construction.

However, I often encounter a situation where emplace() is not sufficient for me.

The situation is characterized by the need to calculate the key after the mapped value (a heavy object) has been placed in the pair. To calculate the key the mapped value needs to be modified (the key is calculated as a side-effect).

I therefore suggest that we add a new function:

typedef ... map; map m; map::node_ptr p = m.get_node_ptr(<like emplace, but only for constructing the mapped value>); p->pair.first = modify( p->pair.second ); m.insert( boost::move(p) );

Is it too expensive to use move insertion from a type with non-const key?

//note that key is non-const! std::pair<key_type, value_type> v(/**/);

m.insert(boost::move(v));

Yes, because the mapped object is not fast to move. The way I code around it currently is to allocate all state in an object on the heap. I then do PriorityMap::iterator i = open_.emplace( &nodes_.back() ); i->second.swap( newData ); since swap is now efficient. But it is still not optimally efficient. -Thorsten

Ion Gaztañaga skrev:

Thorsten Ottosen escribió:

...

...

Is it too expensive to use move insertion from a type with non-const key?

//note that key is non-const! std::pair<key_type, value_type> v(/**/);

m.insert(boost::move(v));

Yes, because the mapped object is not fast to move. The way I code around it currently is to allocate all state in an object on the heap. I then do

PriorityMap::iterator i = open_.emplace( &nodes_.back() ); i->second.swap( newData );

since swap is now efficient. But it is still not optimally efficient.

Ok, I'll think about it. And you can't implement "move" on top of of "swap" to make it efficient (although not optimal, obviously)?

no. See below.

And I'm curious to know why move construction is expensive. Some c-array members, maybe?.

A stack-based adjacency matrix and more stuff, actually. I'm trying to save one heap-allocation here per node, which might not sound like much. But the stuff I work with needs to make an exponential number of nodes. -Thorsten

Thorsten Ottosen escribió:

Thorsten Ottosen skrev:

...

Hi Ion and Joaquín,

This issue is related to node-based containers. I think you both have added emplace() to provide efficient in-place construction.

However, I often encounter a situation where emplace() is not sufficient for me.

I actually got into a situation where I need another member function. The issue arises when I use map/set as a priority_queue and want to limit the size of the queue. In this situation I will be erasing one element and inserting one element again and again. Unless the map/set keeps a free-list of previously erased elements (which I don't think they do normally) we will be deallocating and allocating a new node over and over again.

Therefore I would like to see the follwing member:

iterator modify_key( const_iterator element, const Key& new_key );

This function only needs to rebalance/resort the keys and can completely avoid deallocation/allocation.

Interesting. What about exception safety? We can't assure strong guarantee. It could just erase the element if the change fails? We could also use the assignment operator instead of destroy+construct to reuse some resources. Best, Ion

On Sep 19, 2009, at 4:18 AM, Thorsten Ottosen wrote:

Ion Gaztañaga skrev:

...

Thorsten Ottosen escribió:

...

...

Therefore I would like to see the follwing member:

iterator modify_key( const_iterator element, const Key& new_key );

This function only needs to rebalance/resort the keys and can completely avoid deallocation/allocation.

Interesting. What about exception safety? We can't assure strong guarantee. It could just erase the element if the change fails? We could also use the assignment operator instead of destroy+construct to reuse some resources.

For keys where assignment don't throw, we get the strong guarantee. For the case where assignment could throw, I agree the element should be erase (the user can then reinsert manually if that happens). So maybe we should return

pair<iterator,bool>

to tell the user if the update succeeded?

For cases where the ordering is based merely on a non-throwing part of the Key type, it could be usable with

template< class Key2 > iterator modify_key( const_iterator element, const Key2& new_key );

This function would place the existing node in its right place, but not change the key object which the user then has to do, e.g.

iterator i = modify_key( x, new_object.sub_object ); i->swap( new_object );

I guess there are some additional overloads for movable types.

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: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839 Has been prototyped (using raw pointers) on std::map and lightly tested (just a sanity check). Actual test code below (so you can see how little I tested it, and any details I may have neglected to describe: -Howard #include <iostream> #include <map> #include <new> #include <cstdlib> int outstanding_news = 0; void* operator new(std::size_t s) throw(std::bad_alloc) { ++outstanding_news; return std::malloc(s); } void operator delete(void* p) throw() { if (p) { --outstanding_news; std::free(p); } } template <class C> void display(const char* msg, const C& c) { std::cout << msg << '\n'; for (typename C::const_iterator i = c.begin(), e = c.end(); i != e; ++i) std::cout << '(' << i->first << ", " << i->second << ")\n"; std::cout << '\n'; } int main() { { typedef std::map<int, int> M; typedef M::value_type V; M m1; m1.insert(V(1, 1)); m1.insert(V(2, 1)); m1.insert(V(3, 1)); m1.insert(V(4, 1)); m1.insert(V(5, 1)); m1.insert(V(6, 1)); std::cout << "outstanding_news = " << outstanding_news << '\n'; display("Before remove\nm1 =", m1); // new interface M::node_ptr p = m1.remove(next(m1.cbegin(), 3)); display("After remove\nm1 =", m1); std::cout << "removed node = (" << p->first << ", " << p->second << ")\n"; std::cout << "outstanding_news = " << outstanding_news << '\n'; // new interface p->first = 10; std::cout << "removed node = (" << p->first << ", " << p->second << ")\n"; M m2; // new interface m2.insert(std::move(p)); display("m2 =", m2); std::cout << "outstanding_news = " << outstanding_news << '\n'; } std::cout << "outstanding_news = " << outstanding_news << '\n'; } outstanding_news = 6 Before remove m1 = (1, 1) (2, 1) (3, 1) (4, 1) (5, 1) (6, 1) After remove m1 = (1, 1) (2, 1) (3, 1) (5, 1) (6, 1) removed node = (4, 1) outstanding_news = 6 removed node = (10, 1) m2 = (10, 1) outstanding_news = 6 outstanding_news = 0

Howard Hinnant escribió:

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:

Thanks Howard, very interesting. I'll add it to the to-do list. Ion

On Sep 24, 2009, at 10:02 AM, Thorsten Ottosen wrote:

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 { node_ptr(const node_ptr&); node_ptr& operator=(const node_ptr&); public: typedef pair<Key, T> value_type; node_ptr(); ~node_ptr(); node_ptr(node_ptr&& n); node_ptr& operator=(node_ptr&& n); void reset(); value_type& operator*() const; value_type* operator->() const; };

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 :-)

With what allocator would the node_ptr allocate the node? -Howard

On Sep 24, 2009, at 11:23 AM, Thorsten Ottosen wrote:

Howard Hinnant skrev:

...

On Sep 24, 2009, at 10:02 AM, Thorsten Ottosen wrote:

...

...

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 :-) With what allocator would the node_ptr allocate the node?

Ok, I guess that is why I originally spoke about the following interface:

typedef ... map; map m; map::node_ptr p = m.get_node_ptr(<like emplace, but only for constructing the mapped value>); p->pair.first = modify( p->pair.second ); m.insert( boost::move(p) );

So get_node_ptr( ... ) with two overloads would be needed.

first ::new (&p->first) key_type(modify( p->second )); // tell node_ptr that it is now responsible for p->first

This is effectively the same thing as: typedef ... map; map m; map::node_ptr p = m.remove(m.emplace_hint(m.begin(), my_special_cheap_key_value, mv1, mv2)); p->first = modify( p->second ); m.insert( boost::move(p) ); The main differences are: 1. map never exposes a partially constructed pair to the client. 2. the onus is on the client to figure out how to cheaply and temporarily construct a key (when he needs to). 3. exception safety handling is much simplified. It is a tradeoff that I think is good. Having an interface that exposes a partially constructed object to everyone would be bad (for almost everyone). Having an interface that makes it more difficult for a few clients to extract a little more performance, isn't good, but it is better than exposing partially constructed objects. These partially constructed objects would need more complicated exception safety protection, which could only be partially encapsulated by the node_ptr: typedef ... map; map m; map::node_ptr p = m.get_node_ptr(<like emplace, but only for constructing the mapped value>); // p->first not constructed here // if construction fails, ~node_ptr() only destructs p->second, not p- p.first_constructed(true); m.insert( boost::move(p) ); -Howard

Howard Hinnant escribió:

This is effectively the same thing as:

typedef ... map; map m; map::node_ptr p = m.remove(m.emplace_hint(m.begin(), my_special_cheap_key_value, mv1, mv2)); p->first = modify( p->second ); m.insert( boost::move(p) );

Removing something just after inserting it seems a bit useless. Even if we insert in the first position we need to do a comparison to make sure the hint is correct.Why not: map::node_ptr p = m.create_node(my_special_cheap_key_value, mv1, mv2); //We would need to unconst-cast... const_cast<Key&>(p->first) = modify( p->second ); m.insert( boost::move(p) ); Best, Ion

Howard Hinnant skrev:

On Sep 24, 2009, at 4:26 PM, Ion Gaztañaga wrote:

...

Howard Hinnant escribió:

...

This is effectively the same thing as: typedef ... map; map m; map::node_ptr p = m.remove(m.emplace_hint(m.begin(), my_special_cheap_key_value, mv1, mv2)); p->first = modify( p->second ); m.insert( boost::move(p) );

Removing something just after inserting it seems a bit useless. Even if we insert in the first position we need to do a comparison to make sure the hint is correct.Why not:

map::node_ptr p = m.create_node(my_special_cheap_key_value, mv1, mv2); //We would need to unconst-cast... const_cast<Key&>(p->first) = modify( p->second ); m.insert( boost::move(p) );

FWIW, I like this. My only worry is about the const_cast: is it not undefined behavior to do that here (since the .first member is constructed as a const object)?

One could do that but the node allocation and construction is typically the expensive part of the insertion. Once you've got that done, and if especially if your hint is correct, the insertion is very fast. So it seems to me like m.create_node would be interface aimed at a very rare use case and for an optimization that is going to be quite minor (percent-wise), perhaps not even measurable.

In my case it is not possible to provide a hint fot the new node. But you are right, that emplace/remove and create_node might not be that different in performace. I find create_node slightly more to the point. -Thorsten