A LWG subgroup met in Curaçao concerning these issues. Two action items emerged, as noted in the issues list:
[Curaçao: An LWG-subgroup spent an afternoon working on issues 225, 226, and 229. Their conclusion was that the issues should be separated into an LWG portion (Howard will write a proposal), and a EWG portion (Dave will write a proposal). The LWG and EWG had (separate) discussions of this plan the next day.]
This paper is the LWG portion which will atempt to resolve these issues within the current language.
The problem can be summarized:
Given namespace N containing template functions f and g, with f calling g with arguments of parameterized type, and with the intent that client code should be able to replace g, how should the call be made?
namespace N
{
template <typename T>
void g(T);
template <typename T>
void
f(T t)
{
g(t); // or N::g(t) or something else?
}
}This is an issue for the standard library in several places. For example consider:
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
{
for (; first1 != last1; ++first1, ++first2)
swap(*first1, *first2); // or std::swap(*first1, *first2);
return first2;
}In several places, an implementation of the standard library may have one function template call another function template with no intention of the secondary function template being replaceable by client code. The called function is purely an implementation detail. Issue 225 gives this example:
template <class _ForwardIter>
_ForwardIter
unique(_ForwardIter __first, _ForwardIter __last)
{
__first = adjacent_find(__first, __last);
return unique_copy(__first, __last, __first);
}Here adjacent_find and unique_copy are implementation details, (hopefully) clearly, std::adjacent_find and std::unique_copy are intended. So this should be coded with explicit qualification to disable Koenig lookup:
template <class _ForwardIter>
_ForwardIter
unique(_ForwardIter __first, _ForwardIter __last)
{
__first = std::adjacent_find(__first, __last);
return std::unique_copy(__first, __last, __first);
}I believe that this much is not controversial. It is only when the called function is not intended to be an implementation detail, but a "point of customization" for the algorithm that opinions differ. Of course opinions also vary on which functions should have what points of customization.
For purposes of discussion, temporarily assume that std::swap_ranges intends that the fact that it calls swap be part of its public interface, and a point of customization. When the ranges contain scalars, clearly std::swap must be called. When the ranges contain user-defined types, it is desirable that if the type has a customized (overloaded) swap function, that it be called instead of the general std::swap. The reason it is desirable is because of efficiency. A heavy weight class may be able to "swap" much faster than performing a series of copy construction and copy assignments on the entire object.
Consider a user-defined class N::A. And to make it interesting, this user-defined class is actually a template class:
namespace N {
template <typename T> class A {/* ... */};
}This class A is a "heavy" class that could benefit from an overloaded swap function (just as the std::containers do). And client code wants to call swap_ranges on a container of A:
template <typename T>
void f()
{
N::A<T> v1[5], v2[5];
...
std::swap_ranges(v1, v1+5, v2);
}Now there are two closely related questions to ask:
This paper proposes that the answer to the above two questions be:
1. The author of A<T> writes swap within A's namespace (N) in accordance to what Herb Sutter has termed the "Interface Principle"
namespace N { template <typename T> class A {/* ... */}; template <typename T> void swap(A<T>& x, A<T>& y) {x.swap(y);} } // N2. std::swap_ranges calls swap unqualifed so as to enable Koenig lookup. If argument dependent lookup does not find a better overload, the general std::swap is used.
Having the author of A<T> put the overloaded swap into namespace std is not currently an option as 17.4.3.1 forbids it. Section 17.4.3.1 could be modified to allow overloaded definitions, but further complicatons arise. Consider:
namespace std
{
template <class T>
void
swap(T& a, T& b)
{
T tmp(a);
a = b;
b = tmp;
}
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
{
for (; first1 != last1; ++first1, ++first2)
std::swap(*first1, *first2);
return first2;
}
} // std
namespace N
{
template <typename T> class A {/* ... */};
} // N
namespace std
{
template <typename T>
void swap(N::A<T>& x, N::A<T>& y)
{x.swap(y);}
} // stdIn this example, swap_ranges will use the general purpose std::swap, not the overloaded swap for A<T>. Qualified calls are bound at template definition time. This code could work as intended if A and swap(A,A) appeared before std::swap_ranges in the translation unit, but this dependence on ordering is fragile at best.
If templated code is going to allow Koenig lookup on an internal call, that fact becomes part of the template's interface. It must be clearly and unambiguously documented. The current standard is defective in this respect. In this section I attempt a list of all such places in the standard:
25.2.2/7: iter_swap
-7- Effects: Calls swap (unqualified) with the values pointed to by the two iterators a and b.
25.2.2/3: swap_ranges
-3- Effects: For each non-negative integer n < (last1 - first1) performs: (unqualified) swap(*(first1 + n), *(first2 + n)).
25.2.9/1: reverse
-1- Effects: For each non-negative integer i <= (last - first)/2, applies (unqualified) swap to all pairs of the values referenced by the iterators first + i, (last - i) - 1.
25.2.10/4: rotate
-4- Complexity: At most last - first unqualified calls to swap.
25.2.11/2: random_shuffle
-2- Complexity: Exactly (last - first) - 1 unqualified calls to swap.
25.2.12/3: partition
-3- Complexity: At most (last - first)/2 unqualifed calls to swap. Exactly last - first applications of the predicate are done.
25.2.12/6: stable_partition
-6- Complexity: At most (last - first) * log(last - first) unqualified calls to swap, but only linear number of swaps if there is enough extra memory. Exactly last - first applications of the predicate.
26.3.3.3/1: valarray transcendentals
-1- Each of these functions may only be instantiated for a type T to which a unique function with the indicated name can be applied (unqualified). This function shall return a value which is of type T or which can be unambiguously converted to type T .