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