Title: C++ Standards - The "swap" Problem

The C++ Language Standard was approved in 1998 and is likely to remain unchanged for some years. So why does the standards committee still meet? Well, the obvious reason is that in any work of this size there are both bugs and features that do not work properly. While those on the committee did their best to desk check it was published before any compiler or library implementation was completely in step with it (Indeed, at the time of writing there is still no conforming implementation publicly available - although I expect this to change soon.)

This article explores one such problem - a feature that does not quite work in an acceptable manner. It has cropped up in a number of forms, and in a number of places - I know of discussions on accu-general, comp.lang.c++.moderated and boost.org. My name got associated with it because I submitted a defect report on the subject, the function "swap" became associated with it because it provides an easy to understand example.

Consider a user-defined class:

class client {
public:
  . . . 
  void swap(client& that);
private:
  typedef std::vector<int> lookup_table;
  std::string name;
  lookup_table xref;
  int id;
};

and a possible implementation of client::swap()...

void client::swap(client& that) {
using std::swap;
swap(name, that.name);
swap(xref, that.xref);
swap(id, that.id);
}

This is clear, exception safe (if you want to be technical it meets the "no-throw guarantee"), and efficient. It would be difficult to justify to most developers that it is poor style and fragile. However, as we shall see, that is indeed the consequence of the standard.

Suppose during the course of maintenance a developer decided to change the above typedef to...

typedef arg::vector<int> lookup_table;

For the sake of argument suppose the author of arg::vector intends it to be a "drop in" replacement for std::vector. In practice the change compiles and the functionality is unchanged.

A large part of the C++ standard library is made up of a supposedly extensible range of containers and algorithms (this part of the library is often known by its earlier name of STL). The whole philosophy behind the STL is that new containers and algorithms can be introduced and work seamlessly.

Consequently, it is not unreasonable to expect that the above code change should work. However, when the author of arg::vector tries to achieve that, she discovers that it is not quite possible within the standard.

It goes wrong because the above code uses std::swap< arg::vector<int> > - this template is defined in such a way as to create a temporary copy and exchange values by a series of assignment. The result is that the client code ceases to be efficient and gives a far weaker exception safety guarantee (probably the basic guarantee).

The std::swap template behaves differently for the standard containers because it is overloaded in such a way that std::swap< std::vector<int> > calls std::vector<int>::swap() and this gives the no-throw guarantee.

Now the author of the arg::vector template probably realised that a similar non-throwing swap function was required - let us assume she has provided arg::swap for this purpose. Those of you that have heard of "Koenig Lookup" may wonder at this point why this version of swap isn't called. The relevant passage is from 3.4.2 - Argument-dependent name lookup paragraph 2: "If the ordinary unqualified lookup of the name finds the declaration of a class member function, the associated namespaces and classes are not considered."

This last clause is the reason we needed the using std::swap statement in the original code fragment - if the class did not have a swap method it would work without. (Do not write and tell me that it does not "work without" on your compiler - Visual C++ does not support "Koenig Lookup" correctly.)

In that case you might ask "why not overload the std::swap template?" Because of another passage in the standard 17.4.3.1 - Reserved names paragraph 1 "It is undefined for a C++ program to add declarations or definitions to namespace std or namespaces within namespace std unless otherwise specified."

The same paragraph appears to allow some hope, because it continues: "A program may add template specializations for any standard library template to namespace std. Such a specialization (complete or partial) of a standard library template results in undefined behavior unless the declaration depends on a user-defined name of external linkage and unless the specialization meets the standard library requirements for the original template." This means that she could, in fact, provide an explicit complete specialization of std::swap for arg::vector<int>. (Consequently, so long as the library author or the user does this for every type on which arg::vector<int> is instantiated the problem is "solved".)

What about "partial specialization" which was mentioned in the above passage? Sorry, that only exists for class templates.

Like many bugs there are ways to work around the problem:

These, however, are not general solutions:

This last approach does justify the argument that the problem is with unskilled use of the language. In practice, many users of C++ lack the skill to realise when this indirect approach to using std functions is necessary.

NONE of these work-arounds meet the need of a library author to be able to produce containers that work correctly with the standard algorithms. (E.g. since std::sort calls std::swap versions of both algorithms must be supplied.) Nor does it make it easy to write algorithms that work with third party containers.

I strongly dislike relying on undefined behaviour but I do not trust users of my code to implement the work-arounds described in the last section. Consequently I have reluctantly adopted the approach of overloading template functions in namespace std. This works on all implementations I have encountered and has also been adopted by other library authors (no, I will not name the guilty).

There are two basic approaches to fixing this problem being discussed within the committee. One (which brings other significant benefits) is to introduce "partial specialization" of function templates into the core language. The other is to relax the restriction on overloading standard template functions. Neither of these changes is likely to be in the forthcoming "Technical Corrigenda".