Prev: Good books about STL and template
Next: An insert_iterator for forward_list
From: Alberto Ganesh Barbati on 31 Mar 2008 20:18
Niels Dekker - no return address ha scritto:
> Alberto Ganesh Barbati wrote:
>
>> On this topic, the very recent paper n2590
>> (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2590.pdf)
>> proposes to introduce a new concept MemberSwappable, that would help
>> avoid the need for the three overloads.
>
> Thank you for the pointer as well! Still I think it would make sense to
> add generic std::swap overloads as well, to support swapping an rvalue.
> Those overloads could be implemented by simply doing an unqualified swap
> function call:
>
> namespace std
> {
> // Supporting an rvalue at the left hand side.
> template<class T> void swap(T&& a, T& b)
> {
> swap(a, b);
> }
>
> // Supporting an rvalue at the right hand side.
> template<class T> void swap(T& a, T&& b)
> {
> swap(a, b);
> }
> }
>
> Note that 'a' and 'b' would no longer be rvalues within the body of
> those functions, so there would't be an infinite recursion! Instead,
> argument dependent lookup (ADL) could be applied to find the most
> appropriate swap.
>
> I think such std::swap overloads would be useful, for the sake of
> generic programming. What do you think?
>

I think that your idea gives me the basis for a broader approach to the
swappable mess^H^H^H^Hissue. ADL is both a blessing and a curse to whole
concept of swapping. Consider a generic algorithm that needs to swap two
variables:

template <class T>
void my_clever_algorithm(T x, T y)
{
// ... do something clever
// (*) swap x and y
// ... do something else clever
}

how do you write step (*)?

If you write swap(x, y) you may reach a user-provided swap() through ADL
but if you don't find it the code won't compile even if T is
MoveConstructible and MoveAssignable (for example if T is a basic type!).

If you write std::swap(x, y) instead, the code will probably work with
all suitable types, but it will miss the possibility to use an optimized
swap() that would be reachable through ADL.

Someone suggested this idiom:

template <class T>
void my_clever_algorithm(T x, T y)
{
// ... do something clever
using std::swap;
swap(x, y);
// ... do something else
}

which does the right thing in all cases, but, frankly... it sucks!

What if the user could write std::swap() and do the right thing in every
cases? I admit that I haven't digested concepts fully, so the feedback
of some concept Guru is mostly welcome, but I think I found a way to get
such feature. Consider this code (for the sake of brevity, I follow the
approach of allowing rvalue-rvalue swaps, the code could easily be
modified to disallow that case):

namespace std
{
template <ClassType T>
auto concept AdlSwappable {
void swap(T&, T&); // notice, no need for && here
};

template <ClassType T>
auto concept MemberSwappable {
void T::swap(T&); // no need for && here too
};

template <class T>
requires !MemberSwappable<T>
&& !AdlSwappable<T>
&& MoveConstructible<T>
&& MoveAssignable<T>
void swap(T&& a, T&& b)
{
T x(std::move(a));
a = std::move(b);
b = std::move(x);
}

template <class T>
requires !MemberSwappable<T> && AdlSwappable<T>
void swap(T&& a, T&& b)
{
swap(a, b);
}

template <class T>
requires MemberSwappable<T>
void swap(T&& a, T&& b)
{
a.swap(b);
}

// and finally:
template <ClassType T>
requires MemberSwappable<T> || AdlSwappable<T>
|| (MoveConstructible<T> && MoveAssignable<T>)
auto concept Swappable {
};
}

Now a user-defined type T could provide "swappability" in three
different ways, in order of preference:

1) by T having a member function swap()
2) by having a free function swap in an namespace associated with T
3) by T being MoveConstructible and MoveAssignable

In any case and even if T only provides 1) or 2) with the "legacy"
signature bearing T& and not T&&, the following code:

template <class T>
void my_clever_algorithm(T x, T y)
{
// ... do something clever
std::swap(x, T()); // notice, rvalue used here!
// ... do something else
}

will compile and will always do the right thing! In fact the definition
of concept Swappable would be different from the one currently proposed
in paper N2502: now Swappable means that you can truly apply
std::swap(), regardless of how such algorithm is implemented, the N2502
concept of Swappable being replaced with AdlSwappable which is just one
possible ingredient of the Swappable soup.

Apart from the possible mistakes I may have inserted in the concept
code, does it make sense?

Ganesh

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Yechezkel Mett on 1 Apr 2008 05:57
On Apr 1, 2:18 pm, Alberto Ganesh Barbati <AlbertoBarb...(a)libero.it>
wrote:
> I think that your idea gives me the basis for a broader approach to the
> swappable mess^H^H^H^Hissue. ADL is both a blessing and a curse to whole
> concept of swapping. Consider a generic algorithm that needs to swap two
> variables:
>
> template <class T>
> void my_clever_algorithm(T x, T y)
> {
> // ... do something clever
> // (*) swap x and y
> // ... do something else clever
> }
>
> how do you write step (*)?
>
> If you write swap(x, y) you may reach a user-provided swap() through ADL
> but if you don't find it the code won't compile even if T is
> MoveConstructible and MoveAssignable (for example if T is a basic type!).
>
> If you write std::swap(x, y) instead, the code will probably work with
> all suitable types, but it will miss the possibility to use an optimized
> swap() that would be reachable through ADL.
....
>
> What if the user could write std::swap() and do the right thing in every
> cases? I admit that I haven't digested concepts fully, so the feedback
> of some concept Guru is mostly welcome, but I think I found a way to get
> such feature. Consider this code (for the sake of brevity, I follow the
> approach of allowing rvalue-rvalue swaps, the code could easily be
> modified to disallow that case):
>
> namespace std
> {
> template <ClassType T>
> auto concept AdlSwappable {
> void swap(T&, T&); // notice, no need for && here
> };
>
> template <ClassType T>
> auto concept MemberSwappable {
> void T::swap(T&); // no need for && here too
> };
>
> template <class T>
> requires !MemberSwappable<T>
> && !AdlSwappable<T>
> && MoveConstructible<T>
> && MoveAssignable<T>
> void swap(T&& a, T&& b)
> {
> T x(std::move(a));
> a = std::move(b);
> b = std::move(x);
> }
>
> template <class T>
> requires !MemberSwappable<T> && AdlSwappable<T>
> void swap(T&& a, T&& b)
> {
> swap(a, b);
> }
>
> template <class T>
> requires MemberSwappable<T>
> void swap(T&& a, T&& b)
> {
> a.swap(b);
> }
>
> // and finally:
> template <ClassType T>
> requires MemberSwappable<T> || AdlSwappable<T>
> || (MoveConstructible<T> && MoveAssignable<T>)
> auto concept Swappable {
> };
>
> }
>
> Now a user-defined type T could provide "swappability" in three
> different ways, in order of preference:
>
> 1) by T having a member function swap()
> 2) by having a free function swap in an namespace associated with T
> 3) by T being MoveConstructible and MoveAssignable

Perhaps the following would be better (assuming it works!)

namespace std
{
auto concept Swappable<typename T> {
void swap(T&, T&)
{
T x(std::move(a));
a = std::move(b);
b = std::move(x);
}
};

auto concept MemberSwappable<typename T> : Swappable<T> {
void T::swap(T&);
void swap(T& lhs, T& rhs) { lhs.swap(rhs); }
};

template <Swappable T>
void swap(T&& a, T&& b)
{
Swappable<T>::swap(a, b);
}
}

Yechezkel Mett


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Alberto Ganesh Barbati on 1 Apr 2008 20:09
Yechezkel Mett ha scritto:
>
> Perhaps the following would be better (assuming it works!)
>
> namespace std
> {
> auto concept Swappable<typename T> {
> void swap(T&, T&)
> {
> T x(std::move(a));
> a = std::move(b);
> b = std::move(x);
> }
> };
>
> auto concept MemberSwappable<typename T> : Swappable<T> {
> void T::swap(T&);
> void swap(T& lhs, T& rhs) { lhs.swap(rhs); }
> };
>
> template <Swappable T>
> void swap(T&& a, T&& b)
> {
> Swappable<T>::swap(a, b);
> }
> }
>

I see... very nice. I'm starting to like concepts ;) and possibly I'm
also starting to learn how to use them effectively, thanks!

Please correct me if I'm wrong, but in this case swappability would be
achieved by:

1) by providing a explicit concept map for Swappable<T>
2) by T having a member function swap()
3) by having a free function swap in a namespace associated with T
4) by T being MoveConstructible and MoveAssignable

so we would provide the user a third "customization point" over the
basic algorithm: that would be great! (and we don't even need the
AdlSwappable concept around!)

I hope Alisdair Meredith (the author of paper N2591) is reading this
thread, as I'd love to hear feedback from him.

Cheers,

Ganesh

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Yechezkel Mett on 3 Apr 2008 02:13
On Apr 2, 2:09 pm, Alberto Ganesh Barbati <AlbertoBarb...(a)libero.it>
wrote:
> Yechezkel Mett ha scritto:
> > Perhaps the following would be better (assuming it works!)
>
> > namespace std
> > {
> > auto concept Swappable<typename T> {
> > void swap(T&, T&)
> > {
> > T x(std::move(a));
> > a = std::move(b);
> > b = std::move(x);
> > }
> > };
>
> > auto concept MemberSwappable<typename T> : Swappable<T> {
> > void T::swap(T&);
> > void swap(T& lhs, T& rhs) { lhs.swap(rhs); }
> > };
>
> > template <Swappable T>
> > void swap(T&& a, T&& b)
> > {
> > Swappable<T>::swap(a, b);
> > }
> > }
>
> I see... very nice. I'm starting to like concepts ;) and possibly I'm
> also starting to learn how to use them effectively, thanks!
>
> Please correct me if I'm wrong, but in this case swappability would be
> achieved by:
>
> 1) by providing a explicit concept map for Swappable<T>
> 2) by T having a member function swap()
> 3) by having a free function swap in a namespace associated with T
> 4) by T being MoveConstructible and MoveAssignable

That was the idea, but after working my way through bits of N2501 I
don't think it'll work. Worse yet, sometimes it will and sometimes it
won't depending on instantiation order. If I've understood it
correctly :-) and depending on the precise meaning of the word "need".

I think the following should do the trick:

namespace std
{
auto concept Swappable<typename T> {
void swap(T& lhs, T& rhs)
{
T x(std::move(lhs));
lhs = std::move(rhs);
rhs = std::move(x);
}
};

auto concept MemberSwappable<typename T> {
void T::swap(T&);
};

template<MemberSwappable T>
concept_map Swappable<T> {
swap(T& lhs, T& rhs)
{
lhs.swap(rhs);
}
};

template <Swappable T>
void swap(T&& a, T&& b)
{
Swappable<T>::swap(a, b);
}
}

Yechezkel Mett


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Alberto Ganesh Barbati on 3 Apr 2008 22:36
Yechezkel Mett ha scritto:
>
> I think the following should do the trick:
>
> namespace std
> {
> auto concept Swappable<typename T> {
> void swap(T& lhs, T& rhs)
> {
> T x(std::move(lhs));
> lhs = std::move(rhs);
> rhs = std::move(x);
> }
> };
>
> auto concept MemberSwappable<typename T> {
> void T::swap(T&);
> };
>
> template<MemberSwappable T>
> concept_map Swappable<T> {
> swap(T& lhs, T& rhs)
> {
> lhs.swap(rhs);
> }
> };
>
> template <Swappable T>
> void swap(T&& a, T&& b)
> {
> Swappable<T>::swap(a, b);
> }
> }
>

Sounds good to me (which isn't very much as I'm not a concepts expert
;). The only thing that may be missing is the improved diagnostic that
concepts should bring in case you try to apply std::swap() to a type
that is neither explicitly Swappable, nor MemberSwappable nor
MoveConstructible/MoveAssignable. I guess the compiler would just
stumble parsing the default implementation of Swappable<T>::swap() with
a possibly difficult-to-read error message about a missing constructor
or assignment operator.

Anyway, I believe we agree about the following approach, which is
substantially different from the current proposals N2572/N2573 as well
as the revised proposal N2590:

1) the default implementation requiring MoveConstructible and
MoveAssignable is put in some concept or concept_map, rather than in
some template (or specialization or overload) of std::swap() itself

2) std::swap() just acts as a selector among the different possible
implementations of swapping

That would bring us:

1) std::swap() (to *always* be qualified with std::!) would become the
true universal swapping algorithm, valid for every type T, provided that T:

a) has a explicit concept_map for Swappable, or
b) is MemberSwappable, or
c) there is an ADL-reachable swap() free function, or
d) is MoveConstructible and MoveAssignable

This will once and for all solve the "to ADL or not to ADL" dilemma
about swapping and clarify the "extension points" of the algorithm.

2) as every library class or class template which is supposed to be
Swappable is or can be made MemberSwappable, we could safely remove all
swap() free member functions and function templates from the whole
library (achieving the same goal as N2590).

Ganesh

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 | 
Pages: 1
Prev: Good books about STL and template
Next: An insert_iterator for forward_list