c++ - Cómo sobrecargar std:: swap()

performance optimization

Question

std::swap() es utilizado por muchos contenedores estándar (tales como std::list y std::vector ) durante la clasificación e incluso la asignación.

Pero la implementación estándar de swap() es muy generalizada y bastante ineficiente para los tipos personalizados.

Por lo tanto, la eficiencia se puede obtener al sobrecargar std::swap() con una implementación específica de tipo personalizado. Pero, ¿cómo se puede implementar para que los contenedores estándar lo utilicen?

Answer 1

La manera correcta de sobrecargar el intercambio es escribirlo en el mismo espacio de nombres que lo que está intercambiando, para que se pueda encontrar a través de la búsqueda dependiente de argumentos (ADL). Una cosa particularmente fácil de hacer es:

class X
{
// ...
friend void swap(X& a, X& b)
{
using std::swap; // bring in swap for built-in types
swap(a.base1, b.base1);
swap(a.base2, b.base2);
// ...
swap(a.member1, b.member1);
swap(a.member2, b.member2);
// ...
}
};

Answer 2

No está permitido (según el estándar de C ++) sobrecargar std :: swap, sin embargo, está específicamente permitido agregar especializaciones de plantilla para sus propios tipos al espacio de nombres std. P.ej

namespace std
{
template<>
void swap(my_type& lhs, my_type& rhs)
{
// ... blah
}
}

entonces los usos en los contenedores estándar (y en cualquier otro lugar) elegirán su especialización en lugar de la general.

También tenga en cuenta que proporcionar una implementación de clase base de swap no es lo suficientemente buena para sus tipos derivados. Ej. Si tienes

class Base
{
// ... stuff ...
}
class Derived : public Base
{
// ... stuff ...
}
namespace std
{
template<>
void swap(Base& lha, Base& rhs)
{
// ...
}
}

esto funcionará para las clases base, pero si intenta intercambiar dos objetos derivados usará la versión genérica de std porque el swap con plantilla es una coincidencia exacta (y evita el problema de solo intercambiar las partes ''base'' de sus objetos derivados) )

NOTA: He actualizado esto para eliminar los bits incorrectos de mi última respuesta. D''oh! (gracias puetzk y j_random_hacker por señalarlo)

Answer 3

Si bien es cierto que uno generalmente no debe agregar cosas al espacio de nombres std ::, se permite específicamente agregar especializaciones de plantilla para los tipos definidos por el usuario. La sobrecarga de las funciones no lo es. Esta es una diferencia sutil :-)

17.4.3.1/1 No está definido para un programa C ++ agregar declaraciones o definiciones al espacio de nombres std o espacios de nombres con el espacio de nombres std a menos que se especifique lo contrario. Un programa puede agregar especializaciones de plantilla para cualquier plantilla de biblioteca estándar al espacio de nombres std. Tal especialización (completa o parcial) de una biblioteca estándar da como resultado un comportamiento indefinido a menos que la declaración dependa de un nombre de vinculación externa definido por el usuario y a menos que la especialización de la plantilla cumpla con los requisitos estándar de la biblioteca para la plantilla original.

Una especialización de std :: swap se vería así:

namespace std
{
template<>
void swap(myspace::mytype& a, myspace::mytype& b) { ... }
}

Sin la plantilla <>, sería una sobrecarga indefinida, en lugar de una especialización, lo que está permitido. El enfoque de @ Wilka de cambiar el espacio de nombres predeterminado puede funcionar con el código de usuario (debido a que Koenig prefiere la versión sin espacio de nombres) pero no está garantizado, y de hecho no se supone que deba hacerlo (la implementación de STL debe usar completamente -cualificado std :: swap).

Hay un hilo en comp.lang.c ++ moderado con una larga discusión del tema. Sin embargo, la mayoría es sobre especialización parcial (que actualmente no hay una buena forma de hacerlo).

Answer 4

Atención Mozza314

Aquí hay una simulación de los efectos de un std::algorithm std::swap genérico que llama a std::swap , y que el usuario proporcione su intercambio en el espacio de nombres std. Como se trata de un experimento, esta simulación utiliza el namespace exp lugar del namespace std de namespace std .

// simulate <algorithm>
#include <cstdio>
namespace exp
{
template <class T>
void
swap(T& x, T& y)
{
printf("generic exp::swap/n");
T tmp = x;
x = y;
y = tmp;
}
template <class T>
void algorithm(T* begin, T* end)
{
if (end-begin >= 2)
exp::swap(begin[0], begin[1]);
}
}
// simulate user code which includes <algorithm>
struct A
{
};
namespace exp
{
void swap(A&, A&)
{
printf("exp::swap(A, A)/n");
}
}
// exercise simulation
int main()
{
A a[2];
exp::algorithm(a, a+2);
}

Para mí esto se imprime:

generic exp::swap

Si su compilador imprime algo diferente, entonces no está implementando correctamente la "búsqueda en dos fases" para las plantillas.

Si su compilador está conforme (con cualquiera de C ++ 98/03/11), dará el mismo resultado que muestro. Y en ese caso exactamente sucede lo que temes que suceda. Y poner su swap en el espacio de nombres std ( exp ) no impidió que sucediera.

Dave y yo somos miembros del comité y hemos estado trabajando en esta área del estándar durante una década (y no siempre de común acuerdo). Pero este problema se resolvió durante mucho tiempo, y ambos estamos de acuerdo en cómo se ha resuelto. Ignore la opinión / respuesta experta de Dave en esta área bajo su propio riesgo.

Este problema salió a la luz luego de la publicación de C ++ 98. Comenzando alrededor de 2001, Dave y yo comenzamos a trabajar en esta área . Y esta es la solución moderna:

// simulate <algorithm>
#include <cstdio>
namespace exp
{
template <class T>
void
swap(T& x, T& y)
{
printf("generic exp::swap/n");
T tmp = x;
x = y;
y = tmp;
}
template <class T>
void algorithm(T* begin, T* end)
{
if (end-begin >= 2)
swap(begin[0], begin[1]);
}
}
// simulate user code which includes <algorithm>
struct A
{
};
void swap(A&, A&)
{
printf("swap(A, A)/n");
}
// exercise simulation
int main()
{
A a[2];
exp::algorithm(a, a+2);
}

La salida es:

swap(A, A)

Actualizar

Una observación ha sido hecha que:

namespace exp
{
template <>
void swap(A&, A&)
{
printf("exp::swap(A, A)/n");
}
}

¡trabajos! Entonces, ¿por qué no usar eso?

Considere el caso de que su A es una plantilla de clase:

// simulate user code which includes <algorithm>
template <class T>
struct A
{
};
namespace exp
{
template <class T>
void swap(A<T>&, A<T>&)
{
printf("exp::swap(A, A)/n");
}
}
// exercise simulation
int main()
{
A<int> a[2];
exp::algorithm(a, a+2);
}

Ahora no funciona de nuevo. :-(

Entonces podrías poner swap en namespace std y hacer que funcione. Pero deberá recordar colocar el espacio de nombres de A para el caso cuando tenga una plantilla: A<T> . Y dado que ambos casos funcionarán si coloca el swap en el espacio de nombres de A, es más fácil recordar (y enseñar a otros) que solo lo haga de una manera.