This paper reviews the three possibilities in issue 431 and makes a recommendation based on that review.
Section 20.1.5, paragraph 5 gives the definition of operator== for two allocators of the same type:
Given a1 and a2 are both some type of allocator, the expression
a1 == a2
returns true if a1 can deallocate memory allocated by a2 and vice-versa.
Two allocators may for example hold a private pool of memory from which they allocate. Such allocators (having separate private pools) would probably not react well when trying to deallocate a pointer that was not allocated from their own private pool.
This operation is illegal. Perhaps we could say that an implementation is required to check and to throw an exception, or perhaps we could say it's undefined behavior.
This is an easy option to implement. However it is not a good option for clients of containers. It turns an operation with what could be well-defined and reasonable semantics into a run time error. There is no easy way to check for such an error in source code except to ban the use of unequal allocators in your code.
The operation performs a slow swap (i.e. using three invocations of operator=, leaving each allocator with its original container. This would be an O(N) operation.
Of all of the options, this one is the most dangerous of all. An O(N) swap has fundamentally, but subtly different semantics than an O(1) swap. The O(1) swap is a no-throw operation. The O(N) swap can not be no-throw. This means that clients could make a change in one part of a program (say in an allocator definition), and a far-removed call to swap between two containers of identical type could turn into a throwing operation instead of a no-throw operation:
// generic assignment with commit-or-rollback semantics
template <class T>
inline
T&
strong_assign(T& x, T y)
{
x.swap(y);
return x;
}Such a change could completely and silently invalidate carefully laid out designs.
In addition to the altered semantics with respect to exception safety, an O(N) swap also has altered semantics with respect to iterator, pointer and reference invalidation.
#include <vector>
#include <cassert>
int main()
{
int i1[] = {1, 2, 3};
int i2[] = {4, 5, 6};
std::vector<int> v1(i1, i1+sizeof(i1)/sizeof(i1[0]));
std::vector<int> v2(i2, i2+sizeof(i2)/sizeof(i2[0]));
std::vector<int>::iterator i = v1.begin();
std::vector<int>::iterator j = v2.begin();
assert(*i == i1[0]);
assert(*j == i2[0]);
v1.swap(v2);
assert(*i == i1[0]);
assert(*j == i2[0]);
}Currently the standard says that the above code should always run (without asserting). However if the swap were to become O(N), then the above code becomes undefined behavior because both i and j get invalidated. The code could assert. The code could crash.
In summary, changing from an O(1) swap to an O(N) swap is not just a performance issue, it is also a subtle change in semantics. Clients of containers using unequal allocators would have to carefully scrutinize code to see if such changes altered the correctness of their programs.
The operation swaps both the vectors' contents and their allocators. This would be an O(1) operation.
Another way of looking at this option is:
Whenever an allocator is asked to allocate a pointer, the pointer and the allocator become an inseparable unit until the allocator deallocates the pointer. If ownership of the pointer is transferred to another container, then the allocator must follow the pointer so that the pointer's new owner knows how to deallocate the pointer.
This option maintains the semantics of the containers with respect to swap:
It does introduce an additional requirement on allocators. The expression:
swap(a1, a2);
must compile and have the expected semantics. This might use the generic swap algorithm, and thus also introduce an assignability requirement on the allocator (currently allocators are not required to be assignable). Or a custom swap function (in the allocator's namespace) could be found which need not require assignability. std::allocator is currently swappable. In general, it is anticipated that for unequal allocators, a swappability requirement will be trivial to implement whereas an assignability requirement may not be.
Option 3 has been implemented by Metrowerks CodeWarrior since 1999 with no reported problems. An implementation detail introduced in 2000 removes the call to swap allocators if the type is "empty".
Although issue 431 does not explicitly mention list::splice, it is a closely related issue. The splice member functions can transfer ownership of allocated pointers from one list to another. In two of the splice overloads, a list may result in owning pointers that were allocated from two different (unequal) allocators. This is clearly an intolerable situation. Rather than resort to an O(N) splice (with the resulting change in semantics discussed under option 2), the Metrowerks implementation throws a run time_error.
Option 3 is the only option that retains the existing container/swap semantics. Option 1 produces well defined semantics, but unnecessarily restricts the functionality of unequal allocators. Option 2 will likely silently introduce subtle bugs into working programs. For the case of list::splice, we need to fall back on option 1 at least for cases that would end up with a list owning pointers from two different unequal allocators.