|
Document number: |
J16/01-0003 = WG21 N1289 |
|
Date: |
March 15, 2001 |
|
Author: |
Howard Hinnant, Metrowerks |
This document concerns lib issue 225 and the proposed resolution:
Unless otherwise specified, no global or non-member function in the standard library shall use a function from another namespace which is found through argument-dependent name lookup (3.4.2 [basic.lookup.koenig]).
Although I generally agree with the resolution, the basic intent of this document is to clearly outline where and why "Unless otherwise specified" should appear. This document also applies to lib issue 229 (which is very closely related).
The bulk of this document concerns only one method: swap. But there are a few other methods involved as well. To begin, I would like to define the term swappable so that I may easily refer to this definition later in the paper.
This concept is modeled after similar concepts in the standard. Namely:
swappable requirements:
In the table t and u are non-const values of a type T.
|
expression |
return type |
post-condition |
|
swap(t, u) |
void |
t has the value originally held by u, and u has the value originally held by t |
For a type T, being swappable does not require (or imply) copyconstructible nor assignable. But if a type is both copyconstructible and assignable, then it is also swappable. For example:
class Swappable
{
public:
Swappable(int size) : size_(size), data_(new int[size]) {}
~Swappable() {delete [] data_;}
friend void swap(Swappable& x, Swappable& y);
private:
int size_;
int* data_;
Swappable(const Swappable&); // not defined
Swappable& operator=(const Swappable&); // not defined
};
void
swap(Swappable& x, Swappable& y)
{
std::swap(x.size_, y.size_);
std::swap(x.data_, y.data_);
}Swappable is swappable, but not copyconstructible nor assignable.
Non-const scalars such as int and int* are swappable because they are copyconstructible and assignable. They can be swapped with std::swap.
A typical client-level class may have one or several methods, both at class scope and at namespace scope that are used by the standard library. Indeed, most (but not all) of these methods are neatly written up in various "requirements" sections in the standard. Examples include default constructible, copy constructible and assignable. These three requirements refer to member methods of an object.
The equality and less-than comparison requirements can refer to methods either at class scope, or at namespace scope. Although not specifically mentioned, the equality and less-than comparison requirements appear to require that if the method is defined at namespace scope, then it must be in the same namespace as the class definition. There are two reasons for this implied requirement:
This implied requirement does not come as a surprise to the general C++ programmer. Indeed, it is considered good programming practice to group namespace scope functions of a class within the same namespace as the class, whether or not the std::lib is involved (Items 31-34, Exceptional C++, Herb Sutter).
Another example of primitive requirements in the standard is in sections 24.5.1 and 24.5.2. These are the istream_iterator and ostream_iterator sections. The standard says that these use operator >> and operator << respectively. No mention is made of namespaces. Nor is there a reference to "readable" or "writeable" requirements. Here it is implied that an unqualified call to operator>>(std::istream&, your_object&) will be made. You had better set up your operator>> so that it will work! (i.e. put it in the same namespace as your class).
Had Jerry chosen read(istream&, MyClass&) instead of operator>>, would we today be questioning what namespace "read" was supposed to go in? I'm grateful to Jerry that this is not an issue we have to wrestle with. Since "read" was implemented as an operator, we currently accept without question that koenig lookup should find the correct method in the namespace of MyClass.
I believe swap is a primitive. More a part of a class's intrinsic interface, than a std::lib method. Similar to:
istream& operator >>(istream&, MyClass&); ostream& operator <<(ostream&, const MyClass&); bool operator ==(const MyClass&, const MyClass&); bool operator <(const MyClass&, const MyClass&); MyClass operator +(const MyClass&, const MyClass&);
Indeed, if C/C++ had a built-in operator that meant swap, I don't believe we would be having this conversation.
So I think swap is a primitive. What else do I think is a primitive? Where do we draw the line? Are we expecting another visit from Pandora so soon?
I'm afraid I don't have a good definition of primitive. My dictionary defines primitive (in part) as:
primitive adj not derived, original, primary, assumed as a basis, ...
This is a concept not unlike pornography. I have difficulty with a precise definition, but I know it when I see it. Perhaps other members of the committee can help me with this. In short, a primitive is something that has more to do with a type, than it has to do with an algorithm in the std::lib. Perhaps primitive is not the right adjective to be describing this concept.
The bad news is: more than one.
The good news is: not that many.
For the moment I would like to define anything implemented as an operator (either built-in or overloaded) as a primitive. It would be very convenient if we could just stop there: methods implemented as operators are primitive and belong in the client's namespace, and methods not implemented as operators are not primitive and belong in namespace std. But I believe that this rough cut based on syntax and history alone is not in the best interest of the C++ community.
In addition to those methods implemented as operators, I propose the following list of primitives. Note that only one of them (swap) is outside of Section 26 (Numerics):
And I think the following identifiers should be reserved as possible future primitives:
swap is used a fair amount in <algorithm>. This should really come as no surprise. After all, it is a primitive! :-) There are actually two distinctions I would like to make though. There are currently several methods that specifically mention swap, either in their effects clause, or in their complexity clause. In my opinion, these must call swap (not std::swap, nor a series of assignments). In addition there are several methods that commonly call swap as part of their implementation, but no mention is made of this possibility in the standard. I would like to allow for this possibility with "may call swap". That is, it is implementation defined if such a method calls std::swap, swap, or neither.
iter_swap (1) swap_ranges reverse random_shuffle partition next_permutation prev_permutationThese methods are currently missing any requirements statement except that their use of forward or better iterator implies that the value_type is assignable. Since the (proposed) implementation must call swap, the minimum needed requirement on the value_type is that it is swappable.
Footnote (1): Implementations are allowed to specialize iter_swap. If such specializations do not call swap, they are forbidden from assuming copy constructibility or assignability of the iterator's value_type, despite the container's requirements.
rotate pop_heap sort_heap sort partial_sort partial_sort_copy nth_elementThese methods are currently missing any requirements statement except that their use of forward or better iterator implies that the value_type is assignable. Since the (proposed) implementation may call swap, then the value_type must be both swappable and assignable.
stable_partition inplace_merge stable_sortThese methods are currently missing any requirements statement except that their use of forward or better iterator implies that the value_type is assignable. The description of these methods includes the possibility of using a temporary buffer. This implies that the value_type is also copy constructible. Thus swappable is already implied, clearing the way for the possibility that these methods may call swap.
The rest of the proposed primitives are called by member methods of the same name within the valarray template (26.3.3.3).
So how big of a change is this? What does it mean to implementors? And more importantly, what does it mean to clients of the std::lib?
I believe that in terms of effected code, this is a minuscule change. From a practical standpoint I do not think a single line of non-std::lib code will be broken. Up until very recently (mid 2000?), all std::lib implementations made most or all calls to other std::methods with the unqualified syntax. Issue 225 is mandating that this is incorrect and several (two?) vendors have already modified their libs accordingly. Thus I see little or no possibility that any client code exists which would be surprised by a std::lib calling a swap method in their own namespace. Indeed, I'm sure there is much more code that would be surprised by this not happening.
The change to std::lib vendors who have not yet swept through their libs and qualified internal calls is significant but not overwhelming. I converted the Metrowerks std::lib to qualified calls in about 8 hours. For those vendors who have already done this job, they would have to undo qualification on swap and the rest of the primitives defined herein. I estimate that job to take less than an hour.
Acceptance of this proposal will undercut much (all?) of the motivation for relaxing 17.4.3.1/1 to allow client code to put definitions into namespace std.
I believe that this is the path that will produce the least surprise to C++ programmers, and at the same time, provide them with the highest quality tools.
Respectfully,
Howard Hinnant
Senior Library and Performance Engineer Metrowerks hinnant@metrowerks.com