c++ - sencillos - ¿Se pueden abrir sobrecargas para funciones genéricas para otras sobrecargas?

sobrecarga de operadores poo

Question

Quiero implementar algunos algoritmos genéricos y tengo una serie de ideas sobre cómo se podrían implementar los algoritmos especializados en función de ciertos rasgos de las entidades con las que se utiliza el algoritmo. Sin embargo, parece probable que no obtuve todos los rasgos especiales y me gustaría implementar la versión genérica para que puedan trabajar con otra versión especializada.

Por ejemplo, considere la distance(begin, end) (sí, sé que está en la biblioteca estándar; sin embargo, es agradable y simple y se puede usar para demostrar mi problema). Una versión general podría tener este aspecto (estoy usando std::ptrdiff_t lugar de std::iterator_traits<It>::difference_type std::ptrdiff_t como otra simplificación):

template <typename It>
auto distance(It it, It end) -> std::ptrdiff_t {
    std::ptrdiff_t size{};
    while (it != end) {
        ++it;
        ++size;
    }
    return size;
}

Por supuesto, si el tipo de iterador es un iterador de acceso aleatorio, es mucho mejor implementar el algoritmo usando la diferencia entre los dos iteradores. Ingenuamente solo añadiendo

template <typename It>
auto distance(It begin, It end)
     -> typename std::enable_if<is_random_access_v<It>, std::ptrdiff_t>::type {
    return end - begin;
}

no funciona del todo: ambas implementaciones son igualmente buenas coincidencias para los iteradores de acceso aleatorio, es decir, el compilador los considera ambiguos. El enfoque fácil para lidiar con la situación es cambiar la implementación general para que sea aplicable solo para los iteradores de acceso no aleatorio. Es decir, las elecciones de SFINAE se hacen de manera que se excluyan mutuamente al tiempo que cubren todo el espacio.

Desafortunadamente, el conjunto de implementaciones aún está cerrado: sin cambiar la firma de, al menos, una de las implementaciones, no puedo agregar otra implementación en caso de que tenga otra idea para una implementación genérica que aproveche las propiedades especiales. Por ejemplo, si quiero agregar un procesamiento especial para rangos segmentados (idea: cuando la secuencia subyacente consiste en segmentos como están, por ejemplo, el caso de std::deque<...> o std::istreambuf_iterator<cT> , proceso segmentos individualmente) sería necesario cambiar la implementación general para que sea aplicable solo cuando las secuencias no son un acceso aleatorio y no son una secuencia segmentada. Por supuesto, si controlo la implementación que se puede hacer. Un usuario no podría extender el conjunto de implementaciones genéricas.

Soy consciente de que las funciones se pueden sobrecargar para tipos de iteradores especiales. Sin embargo, eso requeriría que cada vez que se agregue un iterador con capacidades especiales, se necesite implementar las funciones respectivas. El objetivo es permitir agregar implementaciones genéricas que sean mejoras en el caso de que las entidades con las que se utilizan expongan instalaciones adicionales. Es similar a las diferentes categorías de iteradores, aunque las propiedades son ortogonales a las categorías de iteradores.

Por lo tanto, mi pregunta es:

• ¿Se pueden implementar algoritmos genéricos de manera que se pueda agregar una nueva idea de mejora sin cambiar las implementaciones existentes y, de ser así, cómo?
• Seguimiento opcional (Estoy interesado principalmente en la pregunta anterior, pero esta también podría ser interesante): Si eso no es posible, ¿esta habilidad se agregaría con conceptos?

Answer 1

Sobrecarga

Primero, echemos un vistazo a solo manejar la función de distance . Usando la biblioteca de Tick , puede implementar rasgos de concepto para recorridos de iteradores en C ++ de la siguiente manera:

TICK_TRAIT(is_incrementable)
{
    template<class T>
    auto requires_(T&& x) -> tick::valid<
        decltype(x++),
        decltype(++x)
    >;
};

TICK_TRAIT(is_decrementable, is_incrementable<_>)
{
    template<class T>
    auto requires_(T&& x) -> tick::valid<
        decltype(x--),
        decltype(--x)
    >;
};

TICK_TRAIT(is_advanceable)
{
    template<class T, class Number>
    auto requires_(T&& x, Number n) -> tick::valid<
        decltype(x += n)
    >;
};

Ahora, si escribes las dos sobrecargas podría ser ambiguo. Así que hay un par de maneras de resolver la ambigüedad. Primero, podrías usar el envío de etiquetas:

template <typename It>
auto distance(It it, It end, tick::tag<is_incrementable>) -> std::ptrdiff_t 
{
    std::ptrdiff_t size{};
    while (it != end) {
        ++it;
        ++size;
    }
    return size;
}

template <typename It>
auto distance(It begin, It end, tick::tag<is_advanceable>())
{
    return end - begin;
}

template<typename It, TICK_REQUIRES(is_incrementable<It>())>
auto distance(It begin, It end)
{
    return distance(begin, end, tick::most_refined<is_advanceable<It>());
}

Otra forma es usar la sobrecarga condicional proporcionada por la biblioteca Fit . Esto le permite a su orden las funciones por importancia para evitar ambigüedades. Puede utilizar objetos de función o lambdas. Aquí está cómo hacerlo usando lambdas genéricas:

FIT_STATIC_FUNCTION(distance) = fit::conditional(
    [](auto begin, auto end, TICK_PARAM_REQUIRES(
        tick::trait<is_incrementable>(begin) and 
        tick::trait<is_incrementable>(end)))
    {
        std::ptrdiff_t size{};
        while (it != end) {
            ++it;
            ++size;
        }
        return size;
    },
    [](auto begin, auto end, TICK_PARAM_REQUIRES(
        tick::trait<is_advanceable>(begin) and 
        tick::trait<is_advanceable>(end)))
    {
        return end - begin;
    }
);

Por supuesto, esto lo convierte en un objeto de función, que tendría que envolver en una función real si desea confiar en la búsqueda de ADL.

Puntos de personalización

¿Se pueden implementar algoritmos genéricos de manera que se pueda agregar una nueva idea de mejora sin cambiar las implementaciones existentes y, de ser así, cómo?

Sí pueden, pero necesitas definir puntos de personalización.

Búsqueda de ADL

Una forma es a través de la búsqueda de ADL. Las funciones std::begin y std::end funcionan de esta manera. Así que puedes definir la función de distance en su propio espacio de nombres privado:

namespace detail {
    template<typename It, TICK_REQUIRES(is_incrementable<It>())>
    auto distance(It begin, It end)
    {
        // Implementation of distance
    }
}

Luego, puede definir otra función para que el usuario la use en otro espacio de nombres como este:

namespace my_lib {
template<typename It, TICK_REQUIRES(is_incrementable<It>())>
auto distance(It begin, It end)
{
    using detail::distance;
    distance(begin, end);
}
}

Así que ahora puedes personalizar la función de distance para ciertos tipos.

Especialización de plantillas

Sin embargo, ADL podría ser secuestrado inadvertidamente, y causaría que esto falle algunas veces. Otra forma de proporcionar puntos de personalización es utilizar la especialización de plantillas. Así que podrías definir una plantilla que podría usarse para anular el comportamiento de la distance , como esto:

template<class It, class=void>
struct distance_op;

Entonces, la función de distance podría definirse para preferir el distance_op primero:

 FIT_STATIC_FUNCTION(distance) = fit::conditional(
    [](auto begin, auto end) FIT_RETURNS
    (distance_op<decltype(begin)>::call(begin, end)),
    [](auto begin, auto end, TICK_PARAM_REQUIRES(
        tick::trait<is_incrementable>(begin) and 
        tick::trait<is_incrementable>(end)))
    {
        std::ptrdiff_t size{};
        while (it != end) {
            ++it;
            ++size;
        }
        return size;
    },
    [](auto begin, auto end, TICK_PARAM_REQUIRES(
        tick::trait<is_advanceable>(begin) and 
        tick::trait<is_advanceable>(end)))
    {
        return end - begin;
    }
);

FIT_RETURNS restringirá la lambda a cuando distance_op<decltype(begin)>::call(begin, end) es válido. Entonces, si quisieras personalizar la distance para std::queue , podrías escribir:

template<>
struct distance_op<queue<int>::iterator>
{
    static void call(queue<int>::iterator begin, queue<int>::iterator end)
    {
        // Do queue-based distance
    }
};

Además, el segundo parámetro está allí para que pueda especializarse según los tipos que coincidan con ciertas restricciones, por lo que podríamos implementarlo para cada iteratar donde is_queue_iterator es verdadero, como esto:

template<Iterator>
struct distance_op<Iterator, TICK_CLASS_REQUIRES(is_queue_iterator<Iterator>())>
{
    static void call(queue<int>::iterator begin, queue<int>::iterator end)
    {
        // Do queue-based distance
    }
};

Mapas conceptuales

Seguimiento opcional (Estoy interesado principalmente en la pregunta anterior, pero esta también podría ser interesante): Si eso no es posible, ¿esta habilidad se agregaría con conceptos?

Sí, utilizando mapas conceptuales , podría ampliar fácilmente estas operaciones. Así que podrías crear un concept distancia como este:

template<class Iterator>
concept Distance
{
    ptrdiff_t distance(Iterator begin, Iterator end);
}

Luego hacemos un concept_map para cuando es un Incrementable y cuando es Advanceable :

template<Incrementable Iterator>
concept_map Distance<Iterator>
{
    ptrdiff_t distance(Iterator begin, Iterator end)
    {
        std::ptrdiff_t size{};
        while (it != end) {
            ++it;
            ++size;
        }
        return size;
    }
};

template<Advanceable Iterator>
concept_map Distance<Iterator>
{
    ptrdiff_t distance(Iterator begin, Iterator end)
    {
        return end - begin;
    }
};

Y luego, más adelante, el usuario podría especializar el concept_map de concept_map para nuevos tipos también:

template<class T>
concept_map Distance<queue<T>::iterator>
{
    ptrdiff_t distance(Iterator begin, Iterator end)
    {
        return end - begin;
    }
};

Answer 2

Tenga en cuenta que puede "emular" conceptos en C ++ 11 utilizando el truco void_t Walter Brown (consulte void_t "¿se pueden implementar conceptos"? ).

A continuación, puede proporcionar una implementación base como una plantilla de clase

template <typename It, class=void>
struct dist_impl {
auto operator()(It it, It end) -> std::size_t {
    std::size_t size{};
    while (it != end) {
        ++it;
        ++size;
    }
    cout << "base distance/n";
    return size;
}
};

y realice una especialización parcial con void_t para permitir que el compilador elija la coincidencia más especializada

template <typename It>
struct dist_impl<It, void_t<typename std::enable_if<is_random_access<It>::value>::type>> {
auto operator()(It begin, It end) -> std::size_t {
    cout << "random distance/n";
    return end - begin;
}
};

Se aplican las mismas consideraciones de "ortogonalidad".

Aquí hay un ejemplo completo: http://coliru.stacked-crooked.com/a/e4fd8d6860119d42

Answer 3

Un enfoque es un mecanismo de sobrecarga basado en la clasificación. Asigne a cada sobrecarga un rango y deje que la resolución de sobrecarga haga el resto.
Estos son los rasgos auxiliares:

template <unsigned i> struct rank : rank<i - 1> {};

template <> struct rank<0> {};

using call_ranked = rank<256>;

Y este es un ejemplo de uso:

template <typename It>
auto distance_ranked(rank<0>, It it, It end) -> std::size_t {
    std::size_t size{};
    while (it != end) {
        ++it;
        ++size;
    }
    return size;
}

template <typename It>
auto distance_ranked(rank<1>, It begin, It end)
     -> typename std::enable_if<is_random_access_v<It>, std::size_t>::type {
    return end - begin;
}

// Delegating function template:
template <typename... Args>
auto distance(Args&&... args)
    -> decltype(distance_ranked(call_ranked(), std::forward<Args>(args)...)) {
    return      distance_ranked(call_ranked(), std::forward<Args>(args)...);
}

Demo
Un rango con un número más alto tiene más prioridad que uno con un número más bajo. El rank<1> hace que la segunda sobrecarga se seleccione sobre el primero ( rank<0> ) si las coincidencias serían idénticas.

Si desea agregar una implementación basada en segmentos, enable_if como la condición para enable_if . Los rangos presumiblemente segmentados y los rangos de acceso aleatorio serían mutuamente excluyentes, pero si no lo son, asigne una prioridad más alta al acceso aleatorio. La pauta general podría ser: cuanto más eficiente sea una implementación, mayor será su rango.
Usando este método, otras implementaciones no deberían verse afectadas cuando se introduce una nueva. Sin embargo, uno debe asegurarse de que cualquiera de las dos categorías con intersecciones no vacías (que no están cubiertas por una categoría con un rango más alto) tenga un rango diferente, lo que constituye una desventaja notable.

Answer 4

Usaría una clase de utilidad para eso, porque en ese caso es fácil darle un algoritmo predeterminado (para el caso genérico) manteniendo la posibilidad de anularlo para usos específicos. Más o menos lo que hacen las clases de STL con Allocator:

template < class T, class Alloc = allocator<T> > class list;

De forma predeterminada, obtiene un allocator<T> pero puede proporcionar su propia implementación.

template <class T, class Dist = dist<T> >
class dist_measurer {
public:
    static auto distance(T begin, T end) {
        return Dist.distance(begin, end);
    }
}

Luego crea el dist<T> genérico y, opcionalmente, otras implementaciones específicas con una sola distancia de método estático.

Cuando quieras usar el método genérico en la clase X:

dist_measurer<X>.distance(x, y); // x and y objects of class X

Si ha implementado otro algoritmo en dist2, lo usa con:

dist_measurer<X, dist2<X> >.distance(x, y);

Answer 5

Concepts prefieren una sobrecarga más restringida sobre una sobrecarga menos restringida, por lo que no es necesario excluir el dominio de una implementación restringida del dominio de una implementación no restringida como lo haría con SFINAE. Su implementación básica podría escribirse como:

template <typename It>
std::size_t distance(It it, It end) {
    std::size_t size{};
    while (it != end) {
        ++it;
        ++size;
    }
    return size;
}

template <typename It>
requires is_random_access_v<It>
std::size_t distance(It begin, It end) {
    return end - begin;
}

no es necesario excluir los iteradores de acceso aleatorio (el dominio de la sobrecarga restringida) del dominio de la sobrecarga no restringida.

Si todos los iteradores segmentados son aleatorios o todos los iteradores aleatorios están segmentados, nuevamente, Concepts preferirá la sobrecarga más restringida y todo está bien. Simplemente agregue la nueva sobrecarga restringida:

template <typename It>
requires SegmentedIterator<It>
std::size_t distance(It begin, It end) {
    // ...
}

Si tiene sobrecargas restringidas con rangos superpuestos pero ninguno de los dos incluye las restricciones de la otra, la resolución de sobrecarga es ambigua, igual que con SFINAE. Sin embargo, romper la ambigüedad es un poco más sencillo, ya que solo es necesario agregar una nueva sobrecarga para especificar el comportamiento en la región de superposición:

template <typename It>
requires SegmentedIterator<It> && is_random_access_v<It>
std::size_t distance(It begin, It end) {
    // ...
}

SFINAE requeriría que excluyas adicionalmente la superposición del dominio de las otras sobrecargas, pero Concepts preferirá esta sobrecarga más restringida sin requerir cambios en las sobrecargas para is_random_access_v y is_random_access_v .

Concepts le permite a un usuario extender fácilmente su implementación genérica con sobrecargas ortogonales. Las sobrecargas no ortogonales requieren más esfuerzo para especificar el comportamiento en la "superposición", pero no requieren cambios en el código original como lo haría SFINAE.