[std][ptr_container][multi_index] proposal about std algorithms based on iter_swap
Hello, although this is more of a std issue than a Boost one, I think it has some nice implications for some Boost libraries, so please allow me to post it here (also, my original proposal at comp.std.c++, http://tinyurl.com/7wjyl, got almost zero response.) The proposed resolution N1523 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1523.htm aims at settling down the issue of whether some std algorithms are required/allowed to call user-provided overloads of swap(): by requiring that internall calls to swap are unqualified, a whole range of algorithms (swap_ranges, reverse, rotate, etc.) are automatically extended to cover types modeling the "swappable" concept: this includes assignable types but also non-assignable types for which a suitable swap() overload is provided. Now, my proposal tries to extend the applicability of these algorithms by adding an extra level of indirection: instead of requiring that swap() is unqualifiedly called, let us mandate that swapping be performed by an unqualified call to iter_swap(). Also, make the definition of std::iter_swap() unqualifiyingly call swap(). What does this buy us? In the general case, the situation is exactly the same as proposed in N1523, but the extra level of indirection allows us to overload iter_swap() in cases where the pointed-to types are not even swappable. A paradigmatic case of use is Boost.PtrContainer: the types held in this kind of containers are in general not swappable, but an iter_swap() overload than simply exchanges the internal pointers makes a lot of sense: the overall result is that rotate, reverse, etc. will work as expected, save the minor detail that this "extended swap" concept does not work as usual with raw pointers to the ext-swapped elements --only iterators to the elements get their pointed-to elements interchanged. What do you think of this? IMHO this can solve the problem of making std swapping algorithms work with ptr_containers, a problem for which (if I'm not wrong) no satisfying solution has been designed. My selfish interest in this proposal stems from the fact that a vector-like type of indices I'm designing for Boost.MultiIndex would also benefit from this. If the idea is well accepted, maybe we can provide Boost implementations of these algorithms taking proper care of unqualifyingly call iter_swap(). Ideas, comments etc. are most welcome. Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Hi Joaquin,
even swappable. A paradigmatic case of use is Boost.PtrContainer: the types held in this kind of containers are in general not swappable, but an iter_swap() overload than simply exchanges the internal pointers makes a lot of sense: the overall result is that rotate, reverse, etc. will work as expected, save the minor detail that this "extended swap" concept does not work as usual with raw pointers to the ext-swapped elements --only iterators to the elements get their pointed-to elements interchanged.
What do you think of this? IMHO this can solve the problem of making std swapping algorithms work with ptr_containers, a problem for which (if I'm not wrong) no satisfying solution has been designed.
you're right that no satisfiable solution has been reached. http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1771.html explains a different way to fix standard algorithms by mandating moving is used if available. my understanding of this, based on discussion with Howard, is that we can actually make an iterator with a proxy-reference for pointer containers that works. hence I don't feel a great need to do anything about it right now. -Thorsten
Thorsten Ottosen ha escrito:
What do you think of this? IMHO this can solve the problem of making std swapping algorithms work with ptr_containers, a problem for which (if I'm not wrong) no satisfying solution has been designed.
you're right that no satisfiable solution has been reached.
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1771.html
explains a different way to fix standard algorithms by mandating moving is used if available.
my understanding of this, based on discussion with Howard, is that we can actually make an iterator with a proxy-reference for pointer containers that works.
Could you elaborate on this? I'm interested on how to apply this tecnhique for my own purposes. Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Thorsten Ottosen ha escrito:
What do you think of this? IMHO this can solve the problem of making std swapping algorithms work with ptr_containers, a problem for which (if I'm not wrong) no satisfying solution has been designed.
you're right that no satisfiable solution has been reached.
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1771.html
explains a different way to fix standard algorithms by mandating moving is used if available.
my understanding of this, based on discussion with Howard, is that we can actually make an iterator with a proxy-reference for pointer containers that works.
Could you elaborate on this? I'm interested on how to apply this tecnhique for my own purposes. Thank you,
>>>
well, first of all, it requires the algorithm to move elements around if it can (so nothing will work until C++0x). secondly, your reference-type of the iterator is a proxy that can be moved where moving it actually moves the pointer underneith. maybe there is more to it, but Howard assured my that the algorithms in question would never do a lvalue to rvalue conversion (from the iterators reference to its value type) -Thorsten
On May 5, 2005, at 8:46 AM, Thorsten Ottosen wrote:
Thorsten Ottosen ha escrito:
What do you think of this? IMHO this can solve the problem of making std swapping algorithms work with ptr_containers, a problem for which (if I'm not wrong) no satisfying solution has been designed.
you're right that no satisfiable solution has been reached.
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1771.html
explains a different way to fix standard algorithms by mandating moving is used if available.
my understanding of this, based on discussion with Howard, is that we can actually make an iterator with a proxy-reference for pointer containers that works.
Could you elaborate on this? I'm interested on how to apply this tecnhique for my own purposes. Thank you,
>>>>
well, first of all, it requires the algorithm to move elements around if it can (so nothing will work until C++0x).
secondly, your reference-type of the iterator is a proxy that can be moved where moving it actually moves the pointer underneith.
maybe there is more to it, but Howard assured my that the algorithms in question would never do a lvalue to rvalue conversion (from the iterators reference to its value type)
Clarification: I'm not positive of the definition of "algorithms in question", so I'll try to supply one. I believe you're referring to algorithms only allowed to use Swappable, and not MoveConstructible or MoveAssignable. N1771 lists those algorithms as: swap_ranges iter_swap reverse random_shuffle partition next_permutation prev_permutation Notably absent from this list is rotate, specifically mentioned in Joaquín's proposal. This algorithm, along with several others, requires Swappable, MoveConstructible and MoveAssignable. Such an algorithm may call unqualified swap, but is also allowed to move construct and move assign not only from one iterator reference to another, but to and from the iterator's value_type (typically a local temporary). For example from the insertion_sort example in N1771:
value_type tmp(std::move(*j)); // move construct to temporary for (BidirectionalIterator k = i; k != first && tmp < *--k; --j) *j = std::move(*k); // move assign from reference to reference *j = std::move(tmp); // move assign from temporary to reference
Such capability is considered critical for the typical "gcd" implementations of rotate. If you would like to rig up a self contained test case for me to try out on a full implementation of N1770/N1771 I would be happy to do so and report back with the results. -Howard
participants (2)
-
Howard Hinnant -
JOAQUIN LOPEZ MU?Z -
Joaquín Mª López Muñoz
-
Thorsten Ottosen