In his defect report, Alan Griffiths <alan@octopull.demon.co.uk> has
done an excellent job of summing up various discussions of the problems
of providing an efficient, specialized swap, and puts forth both a
proposal I made, and one of his own.

But I think that focusing the discussion of these changes on std::swap
is a mistake.  While std::swap best illustrates the need for change,
it brings with it the question of partial specialization of function
templates.  When one considers the use of explicit template arguments
in function calls, it becomes clear that overloading is a poor
substitute for partial specialization.  (And I thank Alan for
bringing this point to my attention.)

As an example, consider swapping two vectors of integers -- the correct
function to call is not std::swap< std::vector<int> >, but rather
std::swap<int>.  Trying to account for this difference within a template
leads one either to avoid explicit template arguments, or to use an
annoying circumlocution:

        template < typename T >
        void myswap( T& left, T& right )
          {
           std::swap( left, right );
          }

In my opinion, the problems with std::swap would be best addressed by
extending the language to allow partial specialization of function
templates, and changing the library to specialize, rather than overload,
std::swap.

Therefore, it may be better to consider a non-template function.
Since it's the canonical example of overloading in 13 [over], consider
std::abs.  Excepting questions of partial specialization, all of the
questions std::swap brings to light apply equally to std::abs.  In short,
is std::abs a name we can uniformly use to denote "absolute value"?
Or must we effectively reserve "abs" in all namespaces by using
this template?

        template < typename T >
        T myabs( const T& arg )
          {
           using std::abs;
           return abs( arg );
          }


Alan quoted a suggestion of mine for an addition to 17.4.3.1
[lib.reserved.names]:
>       "A program may add to namespace std function or function template
>       declarations which overload any standard library function or
>       function template name.  Such declarations result in undefined
>       behavior unless the declaration depends on a user-defined name of
>       external linkage and unless the function or function template
>       meets the standard library requirements for the original function
>       or function template."

And pointed out a problem with that suggestion:
> This has the unfortunate consequence that it allows ambiguities to be
> generated by overloading std templates whose template parameters are not
> deduced. That is, following John Maddock's contribution on boost:
>
>     namespace std {
>         template<typename T>
>         ::arg::example<T> use_facet(const locale&);
>     }
>
>     void foo()
>     {
>        std::use_facet<int>(std::locale());  // ambiguous
>     }

In addition to directing our attention to the use of explicit arguments
to function templates, this objection brings into question the
meaning of the word "depends,"  both in my proposed addition, and in
the current text of paragraph 1 of 17.4.3.1 [lib.reserved.names].
I used that word assuming it was adequately defined in this context,
but I no longer hold that assumption.

I think that a notion of a type or template being dependent on a name
can be formalized -- the rules of 14.6.2 [temp.dep] come close, but don't
quite do the job.  Given such a definition, I would say that a
specialization depends on a name if it specifies a template argument
which depends on that name, and that an overloading function depends
on a name if the type of a function parameter depends on that name.

It may be a good idea to clarify the notion of dependency in
17.4.3.1 [lib.reserved.names].  And in the case of overloading,
this clarification should rule out the example above.

As a further clarification, I note that a careful user will make sure
that the user-defined names in these contexts are fully-qualified,
lest they become standard-defined in a later version of the standard.
I support adding that requirement explicitly to the proposals
in this discussion and to the existing text.


Nevertheless, I think there's a problem with allowing such broad
overloading of the functions in namespace std.  There are contexts
where the name of a non-overloaded function may be used, but
an overloaded name may not.  For example,

   template < class T > int f( T (*g)(T) );

   int x = f( std::abs )         // ambiguous
   int y = f( std::labs )        // not ambiguous: T is long.

Considering this issue, I modified my proposal, limiting it to functions
already overloaded in the standard.  I presume that Alan was not aware of
this change:
>   A program may add to namespace std function or function template
>   declarations which further overload any standard library function
>   or function template name which is overloaded in this standard.
>   Such declarations result in undefined behavior unless the declaration
>   depends on a user-defined name of external linkage and unless the
>   function or function template meets the standard library requirements
>   for the original function or function template.

Since the standard overloads std::swap, this change would allow
a program to provide specialized swap algorithms for its templates.
But if, as I suggested above, std::swap were not overloaded in a
future standard, programs overloading std::swap would be given
undefined (although generally benign) behavior.  This could be avoided
in such a future standard by giving specific, but deprecated, permission
to overload std::swap.


Finally, Alan has proposed using the partial ordering of function
templates to limit the ability to overload:
>     "A program may add to namespace std function or function template
>     declarations which overload any standard library function or
>     function template name.  Such declarations result in undefined
>     behaviour unless the declaration depends on a user-defined name of
>     external linkage and unless the function or function template meets
>     the standard library requirements for the original function or
>     function template.  Further, such declarations result in undefined
>     behaviour unless the standard library function or function template
>     and that supplied by the program are in distinct equivalence groups
>     according to the rules in 14.5.5.2."

I think that this does not adequately address the problems of overloading
non-template functions.  But in the case of function templates, I think
this wording may serve to limit the notion of dependency to the types of
function parameters, albeit in a roundabout way.


To sum up, here is the clearest wording I've found for my proposal,
replacing the last two sentences of 17.4.3.1 [lib.reserved.names],
paragraph 1:

   A program may add to namespace std specializations for any
   standard library template. Such a specialization (complete
   or partial) of a standard library template results in undefined
   behavior unless at least one template argument depends on a
   fully-qualified user-defined name of external linkage and unless
   the specialization meets the standard library requirements for
   the original template.

   A program may add to namespace std function or function template
   declarations which further overload any standard library function
   or function template name which is overloaded in this standard.
   Such declarations result in undefined behavior unless the type of
   at least one parameter of the declared function or function
   template depends on a fully-qualified user-defined name of external
   linkage and unless the function or function template meets the
   standard library requirements for the original function or function
   template.

                                                --Lisa Lippincott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In message <1256449208-77815153@mail.bigfix.com>, Lisa Lippincott
<lisa_lippincott@bigfix.com> writes
...
>
>But I think that focusing the discussion of these changes on std::swap
>is a mistake.  While std::swap best illustrates the need for change,

That is, of course, the reason for choosing it. <g>

It is the motivating example.

>it brings with it the question of partial specialization of function
>templates.  When one considers the use of explicit template arguments
>in function calls, it becomes clear that overloading is a poor
>substitute for partial specialization.  (And I thank Alan for
>bringing this point to my attention.)
...
>
>In my opinion, the problems with std::swap would be best addressed by
>extending the language to allow partial specialization of function
>templates, and changing the library to specialize, rather than overload,
>std::swap.

Maybe, but that is a change with far reaching implications for language
and/or standard library implementors.

>Therefore, it may be better to consider a non-template function.
>Since it's the canonical example of overloading in 13 [over], consider
>std::abs.  Excepting questions of partial specialization, all of the
>questions std::swap brings to light apply equally to std::abs.  In short,
>is std::abs a name we can uniformly use to denote "absolute value"?
>Or must we effectively reserve "abs" in all namespaces by using
>this template?
>
>        template < typename T >
>        T myabs( const T& arg )
>          {
>           using std::abs;
>           return abs( arg );
>          }

In the light of the following I think there is another example that
should also be considered.  That of a non-overloaded standard algorithm.

I suggest the first one I found: for_each.

I can imagine a hypothetical implementation/library on a system
permitting multiple threads of execution that wishes to provide a
tailored version of this algorithm to operate concurrently.

The argument from a hypothetical example is not as solid as with swap -
but as I stated in the defect report I do think there is an issue with
all the standard algorithms.  (The extension to other free functions -
such as abs - is, I feel weaker.)

...
>
>I think that a notion of a type or template being dependent on a name
>can be formalized -- the rules of 14.6.2 [temp.dep] come close, but don't
>quite do the job.  Given such a definition, I would say that a
>specialization depends on a name if it specifies a template argument
>which depends on that name, and that an overloading function depends
>on a name if the type of a function parameter depends on that name.
>
>It may be a good idea to clarify the notion of dependency in
>17.4.3.1 [lib.reserved.names].  And in the case of overloading,
>this clarification should rule out the example above.
>
>As a further clarification, I note that a careful user will make sure
>that the user-defined names in these contexts are fully-qualified,
>lest they become standard-defined in a later version of the standard.
>I support adding that requirement explicitly to the proposals
>in this discussion and to the existing text.
>
>
>Nevertheless, I think there's a problem with allowing such broad
>overloading of the functions in namespace std.  There are contexts
>where the name of a non-overloaded function may be used, but
>an overloaded name may not.  For example,
>
>   template < class T > int f( T (*g)(T) );
>
>   int x = f( std::abs )         // ambiguous
>   int y = f( std::labs )        // not ambiguous: T is long.

And this objection applies equally to for_each.

>
>Considering this issue, I modified my proposal, limiting it to functions
>already overloaded in the standard.  I presume that Alan was not aware of
>this change:

I must apologise - I did see this at the time, but hadn't fully
appreciated the reasoning and had forgotten it when I wrote the defect
report.

>>   A program may add to namespace std function or function template
>>   declarations which further overload any standard library function
>>   or function template name which is overloaded in this standard.
>>   Such declarations result in undefined behavior unless the declaration
>>   depends on a user-defined name of external linkage and unless the
>>   function or function template meets the standard library requirements
>>   for the original function or function template.
>
>Since the standard overloads std::swap, this change would allow
>a program to provide specialized swap algorithms for its templates.

And therefore addresses the motivating example.  Yes.

...
>
>Finally, Alan has proposed using the partial ordering of function
>templates to limit the ability to overload:
>>     "A program may add to namespace std function or function template
>>     declarations which overload any standard library function or
>>     function template name.  Such declarations result in undefined
>>     behaviour unless the declaration depends on a user-defined name of
>>     external linkage and unless the function or function template meets
>>     the standard library requirements for the original function or
>>     function template.  Further, such declarations result in undefined
>>     behaviour unless the standard library function or function template
>>     and that supplied by the program are in distinct equivalence groups
>>     according to the rules in 14.5.5.2."
>
>I think that this does not adequately address the problems of overloading
>non-template functions.  But in the case of function templates, I think
>this wording may serve to limit the notion of dependency to the types of
>function parameters, albeit in a roundabout way.
>
>
>To sum up, here is the clearest wording I've found for my proposal,
>replacing the last two sentences of 17.4.3.1 [lib.reserved.names],
>paragraph 1:
>
>   A program may add to namespace std specializations for any
>   standard library template. Such a specialization (complete
>   or partial) of a standard library template results in undefined
>   behavior unless at least one template argument depends on a
>   fully-qualified user-defined name of external linkage and unless
>   the specialization meets the standard library requirements for
>   the original template.
>
>   A program may add to namespace std function or function template
>   declarations which further overload any standard library function
>   or function template name which is overloaded in this standard.
>   Such declarations result in undefined behavior unless the type of
>   at least one parameter of the declared function or function
>   template depends on a fully-qualified user-defined name of external
>   linkage and unless the function or function template meets the
>   standard library requirements for the original function or function
>   template.

I accept Lisa's issues with my proposed resolution. (But I would have
preferred a resolution that covered all the algorithms.)

However, in the above proposal I find it hard to justify the phrase
"depends on a fully-qualified user-defined name" as the way the name is
denoted at the point of use isn't part of the name.  But the intent
clearly addresses the main issues.

--
Alan Griffiths  (alan@octopull.demon.co.uk)  http://www.octopull.demon.co.uk/
ACCU Chairman   (chair@accu.org)             http://www.accu.org/

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

[ moderator's note: forwarded to C++ committee. -sdc ]

Apologies that this is long, but the problem arises as a result
of the interaction of several areas of the standard and with some
expectations of C++ users that are not justified by the standard.

I am attempting to summarise the results of a number of discussions
- on the ACCU-general mailing list, on the boost mailing list and
on comp.lang.c++.moderated.

In the following discussion I concentrate on the standard algorithm
"swap" because the problem here is particularly acute.  This is
because use of an efficient, non-throwing swap is key to a number
of common idioms.  As a result the desirability of providing a
tailored version of this particular algorithm is clear.

The problem clearly generalises to other algorithms and can be
extended to the vast majority of functions in namespace std.


Problem statement

/1/ As an author of a C++ template library I find that in order
    to conform to the reasonable expectations of some of my
    users many functions that I declare in my namespace whose
    names match functions in the std namespace must conform
    to the behaviour of the corresponding std function.

/2/ Further, I find that I must rely on this constraint being
    applies to any libraries that users combine with mine.

    This is true even if it the name in question belongs to a
    future version of the standard.

/3/ In addition I find myself unable to resolve the conflicting
    goals of using constructions that are justified by the
    language standard and meeting other expectations of my users.

    In particular, they wish to apply "standard" algorithms
    and transparently invoke one optimised for my types.  As
    we shall see the code that they need to write to achieve
    this is not "transparent".


Elaboration

Let me first give an example where there is no problem so as
to set the background, the following example will highlight
the difficulties...

    // In my namespace I define a (silly) class
    namespace arg
    {
        class example
        {
        public:
            example(int xx, int yy) : x(xx), y(yy) {}

            // Note: I need "using std::swap;" because of example::swap
            void reverse() { using std::swap; swap(x, y); }

            void swap(example& rhs)
                { using std::swap; swap(x, rhs.x); swap(y, rhs.y); ... }
            . . .
        private:
            int x;
            int y;
            . . .
        };
    }

    // In namespace std I provided an explicit specialisation of swap()
    namespace std
    {
        template<> inline
        void swap<::arg::example>(
            ::arg::example& lhs,
            ::arg::example& rhs)
        { lhs->swap(rhs); }
    }

I don't believe there is anything contentious about this approach - it
appears in a number of places (e.g. Herb Sutters answer to GOTW 68)


    // And the end user can happily type:
    namespace user
    {
        class example
        {
             ::arg::example a;
             ::arg::example b;
            int x;
            int y;

            . . .

             void swap(example& rhs)
             {
                 using std::swap;
                 swap(x, rhs.x);
                 swap(y, rhs.y);
                 swap(a, rhs.a);
                 swap(b, rhs.b);
             }
        };
    }

So far, everyone is happy.  But suppose both I and the user
decide to parameterise the example classes...

    // In my namespace:
    namespace arg
    {
        template<typename T>
        class example
        {
        public:
            example(T xx, T yy) : x(xx), y(yy) {}

            // Note: I need "using std::swap;" because of example::swap
            // But will always invoke std::swap - I come back to this.
            void reverse() { using std::swap; swap(x, y); }

            void swap(example& rhs)
                { using std::swap; swap(x, rhs.x); swap(y, rhs.y); ... }
            . . .
        private:
            int T;
            int T;
            . . .
        };
    }

    // In namespace std I provided an explicit specialisation of swap()
    namespace std
    {
        template<> inline
        void swap<::arg::example<int> >(
            ::arg::example<int>& lhs,
            ::arg::example<int>& rhs)
        { lhs->swap(rhs); }

    // BUT I can't overload it
    #ifdef UNDEFINED_BEHAVIOUR
        template<typename T> inline
        void swap<::arg::example<T> >(
            ::arg::example<T>& lhs,
            ::arg::example<T>& rhs)
        { lhs->swap(rhs); }
    #endif
    }

So back to namespace arg & rely on argument dependent name lookup

    namespace arg
    {
        template<typename T> inline
        void swap<::arg::example<T> >(
            ::arg::example<T>& lhs,
            ::arg::example<T>& rhs)
        { lhs->swap(rhs); }
    }


    // Meanwhile the end user has
    namespace user
    {
        template<typename T>
        class example
        {
             T a;
             T b;
            int x;
            int y;

            . . .

             void swap(example& rhs)
             {
                 using std::swap;
                 swap(x, rhs.x);
                 swap(y, rhs.y);
                 swap(a, rhs.a);
                 swap(b, rhs.b);
             }
        };

        . . .

        example<int> ok;                  // Everything is fine
        example<std::vector<int> > ok;    // Everything is fine
        example<arg::example<int> > ok;   // Everything is fine
        example<arg::example<long> > nok; // Compiles BUT NOT fine
    }

Now I could go back and add an explicit specialisation for
std::swap<::arg::example<long> > - but that way lies madness.

I have to convince the user that their code is wrong.  This
is hard since:

   /1/ It compiles - and has the right semantics, and

   /2/ In the simpler example above it worked fine.

   /3/ It conforms to a reasonable (but unjustified) expectation
       that the standard is defined in such a way that std::swap
       is the name for the swap algorithm.

After some discussion the user rewrites their code...

    namespace user
    {
        template<typename Y>
        void myswap(Y& lhs, Y& rhs)
        {
            using std::swap;
            swap(lhs, rhs);
        }

        template<typename T>
        class example
        {
             T a;
             T b;
            int x;
            int y;

            . . .

             void swap(example& rhs)
             {
                 myswap(x, rhs.x);
                 myswap(y, rhs.y);
                 myswap(a, rhs.a);
                 myswap(b, rhs.b);
             }
        };

        . . .

        example<int> ok;                  // Everything is fine
        example<std::vector<int> > ok;    // Everything is fine
        example<arg::example<int> > ok;   // Everything is fine
        example<arg::example<long> > nok; // Everything is fine
    }


And I correct the mistake I noted earlier so as to work with
libraries that have a compatable swap function in their own
namespace.

    namespace arg
    {
        template<typename Y>
        void myswap(Y& lhs, Y& rhs)
        {
            using std::swap;
            swap(lhs, rhs);
        }

        template<typename T>
        class example
        {
        public:
            example(T xx, T yy) : x(xx), y(yy) {}

            void reverse() { ::arg::myswap(x, y); }

            void swap(example& rhs)
                { ::arg::myswap(x, rhs.x); ::arg::myswap(y, rhs.y);... }
            . . .
        private:
            int T;
            int T;
            . . .
        };

        template<typename T> inline
        void swap<::arg::example<T> >(
            ::arg::example<T>& lhs,
            ::arg::example<T>& rhs)
        { lhs->swap(rhs); }
    }

This a fragile solution - incorrect user code compiles and it
also requires a "gentleman's agreement" about the semantics of
"swap" in every namespace reached by Koenig lookup.

Even if the standard were to dictated that "swap" in every
namespace meets the standard library requirements for the std
function it is unreasonable to expect every library and user
to write "myswap" (or its analogue) when they wish to invoke a
standard algorithm.


Options

A number of strategies have been suggested (on boost and C.L.C++.M)

/1/ Do nothing, everyone understands the situation and the
    gentleman's agreement is all that is required.

    I don't think many understand the situation and more
    support for such an agreement is needed from the standard.

    Nor do I believe it the intent for std:: functions to
    cast shadows across other namespaces in this way.

/2/ Change the argument dependent name lookup rules so that
    the correct "swap" is found.

    I cannot imagine that this can be done without both
    imposing requirements on "swap" in every namespace and
    also breaking existing code.

/3/ Add "explicit partial template specialisation" for functions.
    And allow then within std with the same restrictions that
    apply to explicit full template specialisations.

    The discussion on C.L.C++.M does suggest that this could work.

    OTOH Changing the core language at this point is a bad idea.

/4/ Redefine the standard library swap (etc) to call std_swap (say)
    and let std_swap be overloaded in developer namespaces.

    A global change to library like this is probably a bad idea.
    And would be incompatible with prior art.

This leaves my least unfavourite and therefore proposed option:

/5/ Allow overloading in namespace std - with a "suitable" set of
    restrictions on the allowed overloads.

    Because overloading can cause ambiguities beyond the issues
    addressed by the restrictions on explicit specialisations
    additional or different restrictions would be required.


Proposed resolution

Two suggestions for changes to support option /5/ have been made - both
add a paragraph to 17.4.3.1 [lib.reserved.names]:

      "A program may add to namespace std function or function template
      declarations which overload any standard library function or
      function template name.  Such declarations result in undefined
      behavior unless the declaration depends on a user-defined name of
      external linkage and unless the function or function template
      meets the standard library requirements for the original function
      or function template."
                                                --Lisa Lippincott

This has the unfortunate consequence that it allows ambiguities to be
generated by overloading std templates whose template parameters are not
deduced. That is, following John Maddock's contribution on boost:

    namespace std {
        template<typename T>
        ::arg::example<T> use_facet(const locale&);
    }

    void foo()
    {
       std::use_facet<int>(std::locale());  // ambiguous
    }

In view of this I think an additional requirement to avoid ambiguity is
also needed:

    "A program may add to namespace std function or function template
    declarations which overload any standard library function or
    function template name.  Such declarations result in undefined
    behaviour unless the declaration depends on a user-defined name of
    external linkage and unless the function or function template meets
    the standard library requirements for the original function or
    function template.  Further, such declarations result in undefined
    behaviour unless the standard library function or function template
    and that supplied by the program are in distinct equivalence groups
    according to the rules in 14.5.5.2."
--
Alan Griffiths  (alan@octopull.demon.co.uk)  http://www.octopull.demon.co.uk/
ACCU Chairman   (chair@accu.org)             http://www.accu.org/


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Alan Griffiths <alan@octopull.demon.co.uk> wrote in message
news:v60g6NA2oO94EwXB@octopull.demon.co.uk...
[snip]

I'm very glad Alan went all the way to synthesize and formalize the
discussion about traits. I highly appreciate this effort.

His conclusion - as is mine and many others' - is that the most reasonable
solution is to allow overloading of free functions in std for template
classes. He also concludes - and I couldn't agree more - that it's terribly
unreasonable to rely on Koeing lookup for standard algorithms.

I guess this post will be rejected, as it falls in the "me too" category.
But, you never know :o).


Andrei

P.S. Blow-my-own-trumpet-section: there's an article on traits at
http://creport.com/html/from_pages/column.cfm. Don't shoot the pianist :o).




---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]