Ventana corredera genérica -- ++ campo con algorithm campo con c++14 campo con template-meta-programming camp codereview Relacionados El problema

Generic sliding window


4
vote

problema

Español

El código implementa una ventana deslizante totalmente genérica con complejidad lineal. Por lo general, debe emparejarse con el iterador transformador para alcanzar el máximo potencial.

La ventana deslizante es una agrupación de elementos mediante la longitud exactamente de la ventana deslizante, luego "deslizando" la ventana por un elemento en cada iteración.

Ejemplo: Dado a = [0, 1, 2, 3], L = 3, hay 2 ventanas: [0, 1, 2], [1, 2, 3].

Pero en lugar de trabajar solo en números, el código funciona en cualquier cosa, dado que el usuario suministra su propia operación Agregar (agrega un elemento a la ventana) y elimina la operación (elimina el elemento de la ventana).

  #ifndef SUNRISE_SLIDING_WINDOW_HPP #define SUNRISE_SLIDING_WINDOW_HPP  #include <functional> #include <stdexcept> #include <iterator>  namespace shino {     template<typename BidirIt,              typename OutputIt,              typename T = typename std::iterator_traits<BidirIt>::value_type,              typename BinaryDoOp = std::plus<>,              typename BinaryUndoOp = std::minus<>>     std::pair<BidirIt, OutputIt> sliding_window(BidirIt first,                         BidirIt last,                         OutputIt d_first,                         typename std::iterator_traits<BidirIt>::difference_type length,                         T init = {},                         BinaryDoOp add_op = {},                         BinaryUndoOp remove_op = {})     {         if (first == last || length == 0)         {             return std::make_pair(first, d_first);         }          BidirIt milestone(std::next(first, length)); //try to default construct         auto tail = first;          while (first != last && first != milestone)         {             init = add_op(init, *first);             ++first;         }          if (first != milestone)         {             throw std::invalid_argument("Iterator range is smaller than length of the window");         }          *d_first = init;         ++d_first;          if (first == last)         {             return std::make_pair(first, d_first);         }          while (first != last)         {             init = remove_op(init, *tail);             init = add_op(init, *first);             *d_first = init;             ++tail;             ++first;             ++d_first;         }          return std::make_pair(first, d_first);     } }  #endif //SUNRISE_SLIDING_WINDOW_HPP   

SO AIM es hacer una versión genérica de este código , proporcionando Algunos valores predeterminados para que sea fácil de usar. Aunque la mejor manera de usar el algoritmo deslizante genérico es escribir más especializados, por el bien de la claridad y reduciendo los vectores de errores. Además, usando 9988776655544331 , es posible obtener potencia completa sobre la manipulación agrupada .

Entonces, aquí es ejemplo: el promedio deslizante usando la ventana corredera genérica:

  template <typename InputIt, typename OutputIt> std::pair<InputIt, OutputIt> sliding_average(InputIt first, InputIt last,                     const typename std::iterator_traits<InputIt>::difference_type window_length,                     OutputIt d_first) {     using value_type = typename std::iterator_traits<InputIt>::value_type;     auto divide = [&window_length](const value_type& value)     {         return value / window_length;     };      auto iterator = shino::transformer(divide, d_first); //transform_iterator<Functor, Iterator>      auto result = shino::sliding_window(first, last, iterator, window_length);      return std::make_pair(result.first, result.second.internal_iterator()); }   

El algoritmo también advierte si el tipo de entrada es int3 , y el tipo de salida es 9988777665544334 , por ejemplo, El compilador advirtirá si se realizan las conversiones de reducción.

Original en ingles

The code implements fully generic sliding window with linear complexity. It should usually be paired with transforming iterator to reach full potential.

Sliding window is a grouping of elements by exactly length of sliding window, then "sliding" the window by one element on each iteration.

Example: Given A = [0, 1, 2, 3], L=3, there are 2 windows: [0, 1, 2], [1, 2, 3].

But instead of working only on numbers, the code works on anything, given that user supplies their own add operation (adds an element into the window), and remove operation (removes the element from the window).

#ifndef SUNRISE_SLIDING_WINDOW_HPP #define SUNRISE_SLIDING_WINDOW_HPP  #include <functional> #include <stdexcept> #include <iterator>  namespace shino {     template<typename BidirIt,              typename OutputIt,              typename T = typename std::iterator_traits<BidirIt>::value_type,              typename BinaryDoOp = std::plus<>,              typename BinaryUndoOp = std::minus<>>     std::pair<BidirIt, OutputIt> sliding_window(BidirIt first,                         BidirIt last,                         OutputIt d_first,                         typename std::iterator_traits<BidirIt>::difference_type length,                         T init = {},                         BinaryDoOp add_op = {},                         BinaryUndoOp remove_op = {})     {         if (first == last || length == 0)         {             return std::make_pair(first, d_first);         }          BidirIt milestone(std::next(first, length)); //try to default construct         auto tail = first;          while (first != last && first != milestone)         {             init = add_op(init, *first);             ++first;         }          if (first != milestone)         {             throw std::invalid_argument("Iterator range is smaller than length of the window");         }          *d_first = init;         ++d_first;          if (first == last)         {             return std::make_pair(first, d_first);         }          while (first != last)         {             init = remove_op(init, *tail);             init = add_op(init, *first);             *d_first = init;             ++tail;             ++first;             ++d_first;         }          return std::make_pair(first, d_first);     } }  #endif //SUNRISE_SLIDING_WINDOW_HPP 

So aim is to make a generic version of this code, providing some defaults to make it easy to use. Though the best way of using the generic sliding algorithm is to write more specialized ones, for the sake of clarity and narrowing down the error vectors. Also, using transform_iterator, it is possible to get full power over grouped manipulation.

So, here is example: the sliding average using generic sliding window:

template <typename InputIt, typename OutputIt> std::pair<InputIt, OutputIt> sliding_average(InputIt first, InputIt last,                     const typename std::iterator_traits<InputIt>::difference_type window_length,                     OutputIt d_first) {     using value_type = typename std::iterator_traits<InputIt>::value_type;     auto divide = [&window_length](const value_type& value)     {         return value / window_length;     };      auto iterator = shino::transformer(divide, d_first); //transform_iterator<Functor, Iterator>      auto result = shino::sliding_window(first, last, iterator, window_length);      return std::make_pair(result.first, result.second.internal_iterator()); } 

The algorithm also warns if input type is int, and output type is double, e.g. compiler will warn if narrowing conversions are performed.

           

Lista de respuestas


Relacionados problema

13  ID de tipo único en C ++  ( Unique type id in c ) 
Necesito tener una identificación única para cualquier tipo en C ++ para un tipo de variante. ¿Este código es confiable para obtener la identificación? No me ...

11  Selección Clasificación de una lista de tipos (Tiempo de compilación)  ( Selection sorting a type list compile time ) 
Esta pregunta tiene la plantilla 998877666554433665544336 que ordena la plantilla variada de una tupla usando un comparador (cualquier plantilla que toma do...

3  ¿Podría este esquema de ejecución diferido ser más simple?  ( Could this deferred execution scheme be any simpler ) 
He creado este esquema para preservar las llamadas de la función hasta que estén disponibles todos los argumentos. La stub_op8 Las clases se reemplazarán co...

11  Clon de variante de impulso  ( Clone of boost variant ) 
Como parte del aprendizaje C ++, con especial énfasis en C ++ 11, quería implementar el equivalente a la variante de Boost (ubicada AQUÍ ). Mi código está di...

2  C ++ Socket Part-2 A (Utilidades)  ( C socket part 2 a utilities ) 
Este es el código que utilizo para construir dinámicamente los mensajes de error. Utilidad.H #ifndef THORSANVIL_SOCKET_UTILITY_H #define THORSANVIL_SOCKE...

5  C ++ Elija entre funciones de implementación de tiempo de ejecución y tiempo de compilación  ( C choose between runtime and compile time implementation functions ) 
Escribí una pequeña función de envoltura para elegir entre Tiempo de ejecución (STD) 99887766555443318 y una versión de ConsexPR, como continuación de la cl...

6  Clase de matriz multidimensional simple en C ++ 11  ( Simple multi dimensional array class in c11 ) 
La nueva versión del código se puede revisar en Clase de matriz multidimensional simple en C ++ 11 - Seguimiento . El siguiente código implementa una clas...

20  Construyendo una buena biblioteca de plantillas C ++ 11 - Tiempo compilado enumeró la matriz enumulada [cerrada]  ( Building a good c11 template library compile time checked enum array ) 
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas. ¿Quieres ...

16  Implementación muy básica de la tupla  ( Very basic tuple implementation ) 
Me han metido la metaprogramación y las plantillas variadas en C ++, y me fui con esta implementación muy primitiva de una tupla: activityKey4 siendo la...

6  Biblioteca de listas de metaprogramas de pequeña plantilla  ( Small template metaprogramming list library ) 
Entonces, tiempo para explorar las profundidades de asustadizo de la metaprogramación de plantillas (bueno, aterrador para mí, de todos modos). Esta bibliot...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos