C++ -> Fundamentos de Programación: Programando con C++20 (Parte I): Concepts

Artículos de la serie:

Introducción

En este post consideraremos el problema de codificar el bien conocido algoritmo de ordenación por inserción mediante técnicas propias de programación genérica, de manera que éste pueda ser empleado con contenedores diversos. Analizaremos su implementación a la luz de la inclusión de conceptos (concepts), rangos y proyecciones en el estándar del lenguaje C++20 [1-4].

Un concepto es un predicado con nombre, evaluado en tiempo de compilación, que forma parte de la interfaz de una plantilla de clase o de función (template) y restringe el tipo de datos con los que ésta puede operar. La detección temprana de cualquier incumplimiento de tales restricciones, durante los primeros pasos en la generación de una instancia de la plantilla, conducirá por lo general a mensajes de error de fácil comprensión y rastreo. Más que meras ligaduras sintácticas, el objetivo es aquí el de modelar auténticas categorías semánticas que puedan ser reutilizadas por el programador.

Con el fin de codificar los ejemplos de este artículo, resultará necesaria la importación de las siguientes unidades de cabecera estándar (header units):

   import <algorithm>;
   import <concepts>;
   import <functional>;
   import <iterator>;
   import <ranges>;
   import <utility>;
 

Actualmente, los principales compiladores proporcionan un soporte experimental desigual para el sistema de módulos propio de C++20. En nuestra discusión, supondremos el empleo del compilador GCC 10.2 (bajo el flag -std=c++2a), para el que las directivas de importación anteriores deberían ser remplazadas por inclusiones tradicionales #include del precompilador.

Asimismo, emplearemos la biblioteca {fmt}lib para facilitar el formato de texto (véase esta guía de instalación para más detalles). Finalmente, a efectos únicamente de simplificar la lectura de nuestros códigos, introduciremos la cláusula:

   using namespace std;

Ordenación por inserción

Sea R un conjunto cualquiera a ordenar de acuerdo con un determinado predicado binario comp, que deberá establecer un orden débil estricto sobre los operandos que compare. Es decir, asumimos que comp cumple las siguientes propiedades:

Irreflexiva: comp(a,a)es falso para todo a.
Transitiva: comp(a,b) and comp(b,c) implica comp(a,c).
Si definimos equiv(a,b)como !comp(a,b) and !comp(b,a), entonces equiv debe ser también transitiva: equiv(a,b) and equiv(b,c) implica equiv(a,c).

Bajo los supuestos anteriores, equiv constituye una relación de equivalencia y comp induce un orden débil estricto sobre las clases de equivalencia establecidas por equiv.

Consideremos un caso genérico en el que el conjunto R posea al menos dos elementos. El método de inserción deberá ordenar, en su primera iteración, los dos primeros elementos del conjunto R. Es decir, si comp(R[0],R[1]) se evalúa como falso, ambos elementos deberán intercambiarse; en caso contrario, permanecerán en sus posiciones originales. A continuación, insertaremos el tercer elemento R[2] del conjunto (si existe) en la posición correcta dentro del subconjunto ya ordenado {R[0],R[1]}. Los tres primeros elementos del conjunto R quedan, así, ordenados adecuadamente. A continuación, se insertará el cuarto elemento R[3] (si existe) en la posición correcta con respecto al subconjunto ya ordenado {R[0],R[1],R[2]}, y así sucesivamente hasta que el conjunto R quede ordenado en su totalidad.

La figura siguiente muestra, de izquierda a derecha y de arriba abajo, las iteraciones de ordenación de menor a mayor del conjunto de números naturales R = {5,3,1,2}:

Este algoritmo es O(n) en el caso más favorable (conjunto ya ordenado) y O(n²) en los casos medio y menos favorable (conjunto de partida en orden inverso al deseado), siendo n el número de elementos a ordenar [5]. Ciertamente, el interés por la implementación del método de inserción descansa en su relativa facilidad de codificación, recomendándose en general el uso de algoritmos de ordenación más eficientes en código de producción, tales como quick-sort o merge-sort.

Tomemos un rango semiabierto R = [first,last) a ordenar por inserción, donde first es un iterador de tipo I y last es un centinela de tipo S (no necesariamente del mismo tipo que first, como veremos en un ejemplo posterior). Sea proj una proyección a aplicar a los elementos del rango. Ésta puede adoptar la forma, por ejemplo, de un objeto función unario cuyo operador operator() tome una referencia a un elemento constante del rango y retorne una transformación conveniente del mismo. Tales proyecciones permitirán, por ejemplo, ordenar contenedores de agregados de datos en base al orden natural de uno de sus atributos. Denote comp el predicado binario evaluado sobre las proyecciones de los elementos del rango. El rango R quedará ordenado respecto a comp y proj si para cualquier iterador i referenciando a uno de sus elementos se cumple que invoke(comp,invoke(proj,*ranges::next(i,n)),invoke(proj,*i)) es falso para todo entero no-negativo n tal que ranges::next(i,n) siga apuntando a un elemento válido del rango. El empleo de la plantilla de función estándar std::invoke se justifica en este contexto de programación genérica dada la variedad de objetos invocables que pueden representar a comp y proj, incluyendo functors o punteros a funciones.

Introduciremos la siguiente signatura para el algoritmo insertion_sort, explicitando en su interfaz las restricciones impuestas sobre los tipos con los que trabaja:

   template<
      forward_iterator I,
      sentinel_for<I> S,
      typename Comp = ranges::less,
      typename Proj = identity
   >
   requires sortable<I, Comp, Proj>
   // -----------------------------
   constexpr void insertion_sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{})
   {
      // ...
   }

Como podemos observar, hemos especificado una serie de ligaduras tanto dentro de la lista de parámetros de la plantilla (indicada entre llaves angulares) como a través de la palabra clave requires. Por orden de aparición:

El tipo de iterador I debe ser al menos de avance (forward), permitiendo las operaciones habituales de comparación, desreferencia e incremento (++, tanto en sus versiones pre- como post-fijas).

El tipo S debe servir de centinela para I. Ello quiere decir que la comparación first == last debe estar bien definida, así como que si bool(first != last) es cierto, entonces first será desreferenciable y [++first, last) denotará a su vez un rango.

Por su parte, la terna <I,Comp,Proj> debe verificar la ligadura estándar std::sortable [6], definida como conjunción de los conceptos std::permutable y std::indirect_strict_weak_order (véase el código inferior). Éstos requieren, en particular, que los elementos de tipo std::iter_value_t<I> referenciados por los iteradores sean movibles e intercambiables mediante operaciones swap, así como que el tipo de predicado Comp establezca un orden débil estricto sobre los elementos proyectados. En realidad, el compilador sólo podrá comprobar que Comp defina una relación binaria entre ellos: los requerimientos semánticos (irreflexibilidad y transitividad) deberán ser garantizados por el programador.

   namespace std {
      template<typename I, typename Comp, typename Proj>
      concept sortable = permutable<I>
                         and indirect_strict_weak_order<Comp, projected<I, Proj>>;  
   }

Observemos que no requerimos aquí que los objetos de tipo std::iter_value_t<I> sean copiables, una condición más restrictiva que subsumiría el requisito de movilidad anterior. Ello es así pues deseamos poder ordenar, por ejemplo, punteros inteligentes con semántica de propiedad exclusiva std::unique_ptr en base a los datos por ellos referenciados, punto éste que analizaremos posteriormente.

La política de ordenación que hemos adoptado por defecto para el algoritmo insertion_sort es de tipo std::ranges::less, mientras que el proyector por defecto corresponde al tipo de objeto función std::identity, cuyo operador operator() retorna su argumento sin cambio alguno.

Al generar una versión específica de la plantilla de función, el compilador comprobará que los parámetros verifiquen las restricciones establecidas, emitiendo un mensaje de error comprensible en caso contrario. Con nuestra versión del algoritmo, seremos capaces de operar con iteradores forward, incluyendo aquéllos de una lista unidireccional std::forward_list, una lista bidireccional std::list o un array de acceso aleatorio como std::vector. La siguiente aserción estática así lo atestigua:

   static_assert(forward_iterator<vector<int>::iterator>
                 and forward_iterator<list<int>::iterator>
                 and forward_iterator<forward_list<int>::iterator>); // ok

A continuación, implementaremos el cuerpo de insertion_sort como combinación de algoritmos estándar bien conocidos [7, 8]:

   template<
      forward_iterator I,
      sentinel_for<I> S,
      typename Comp = ranges::less,
      typename Proj = identity
   >
   requires sortable<I, Comp, Proj>
   // -----------------------------
   constexpr void insertion_sort(I first, S last, Comp comp = Comp{}, Proj proj = Proj{})
   {
      // retornamos directamente si la longitud del rango es <= 1:
      if constexpr (sized_sentinel_for<S, I>) {
         if (last - first <= 1) return;                             // (A)
      } else {
         if (first == last or ranges::next(first) == last) return;  // (B)
      }

      for (I const i : views::iota(ranges::next(first), last)) {
         I const j = ranges::upper_bound(first, i, invoke(proj, *i), comp, proj);  // (C)
         ranges::rotate(j, i, ranges::next(i));                                    // (D)
      }   
   }

A modo de optimización, hemos tenido en cuenta que si el rango a ordenar [first,last) estuviese vacío o poseyese sólo un elemento, el algoritmo debería acabar directamente. El compilador insertará la sentencia de control (A) si la distancia entre first y last puede calcularse en tiempo constante, es decir, si el concepto sized_sentinel_for<S,I> se evalúa como true en tiempo de compilación (tal es el caso, por ejemplo, de una pareja de iteradores de acceso aleatorio). En caso contrario (por ejemplo, dada una pareja de iteradores uni- o bi-direccionales), se ejecutará la sentencia (B).

El bucle for anterior deja el subrango [first,i] ordenado en cada iteración, dando por supuesto que el subrango con un único elemento [first,next(first)) se encuentra ya ordenado. El algoritmo std::ranges::upper_bound (C) encuentra, mediante búsqueda binaria, el iterador j más alejado en [first,i] tal que para todo iterador k en [first,j) se cumple que !bool(invoke(comp, invoke(proj,*i),invoke(proj,*k))) es true. El método std::ranges::rotate (D) se encarga entonces de colocar al elemento apuntado por i en la posición j mediante una permutación cíclica.

Observemos, muy en particular, cómo todas las operaciones realizadas en el cuerpo de la función se ajustan exactamente a las restricciones establecidas sobre sus argumentos. Asimismo, hagamos notar que el comparador y el proyector son capturados por valor en consonancia con la especificación estándar de este tipo de algoritmos (véase este post anterior para más detalles).

Procederemos también a definir una sobrecarga del algoritmo que opere directamente con un rango, en sustitución de la pareja iterador-centinela de la primera versión:

   template<
      ranges::forward_range R,
      typename Comp = ranges::less,
      typename Proj = identity
   >
   requires sortable<ranges::iterator_t<R>, Comp, Proj>
   // -------------------------------------------------
   constexpr void insertion_sort(R&& r, Comp comp = Comp{}, Proj proj = Proj{})
   {
      insertion_sort(ranges::begin(r), ranges::end(r), move(comp), move(proj));
   }

En este caso, garantizamos que el tipo R cumpla el concepto de rango unidireccional std::ranges::forward_range, para posteriormente requerir que los tipos de iterador del rango std::ranges::iterator_t<R>, comparador Comp y proyector Proj cumplan el concepto std::sortable. La operación ranges::end(r), en particular, retornará un objeto que cumpla el concepto std::sentinel_for<ranges::iterator_t<R>>.

Ejemplo 1: Elementos movibles pero no copiables

El código siguiente muestra cómo, en base al algoritmo anterior, es posible ordenar un array de elementos movibles pero no copiables, en este caso punteros inteligentes std::unique_ptr<int> de propiedad exclusiva. El comparador, definido a través de una expresión lambda, toma dos de dichos punteros y los desreferencia para establecer el orden natural de los enteros apuntados:

   auto ptrs = array{
      make_unique<int>(5),
      make_unique<int>(1),
      make_unique<int>(7),
      make_unique<int>(-2)
   };

   insertion_sort(ptrs, [](auto const& p1, auto const& p2){ return *p1 < *p2; });

   for (auto const& p : ptrs)
      fmt::print("{} ", *p);  // output: -2 1 5 7
 

La disposición en memoria del array del ejemplo seguiría, antes y después de la ordenación, un esquema como el siguiente (transfiriendo las propiedades de los enteros cuando sea necesario):

De forma alternativa, la ordenación del array podría realizarse con un proyector que desreferencie los punteros:

   insertion_sort(ptrs, ranges::less{}, &unique_ptr<int>::operator*);

Ejemplo 2: Proyecciones

Como hemos podido comprobar, las proyecciones hacen posible que el algoritmo de ordenación aplique transformaciones sobre los elementos del rango antes de compararlos. A modo de ejemplo adicional, el siguiente código sencillo ordena un vector de libros de tipo Book en base a uno de sus atributos públicos (el precio), siguiendo una política de ordenación de mayor a menor ranges::greater:

   struct Book {
      string title;
      double price;
   };

   auto books = vector<Book>{
      {.title = "Romeo and Juliet",             .price =  8.95},
      {         "The Count of Monte Cristo",             12.89},
      {         "War and Peace",                          7.59},
      {         "Chronicle of a Death Foretold",         10.59},
      {         "A Study in Scarlet",                     9.89}
   };
   
   insertion_sort(books, ranges::greater{}, &Book::price);
   
   for (Book const& b : books)
      fmt::print("title: {:<30} | price: {}\n", b.title, b.price);

   /* output:
      title: The Count of Monte Cristo      | price: 12.89
      title: Chronicle of a Death Foretold  | price: 10.59
      title: A Study in Scarlet             | price: 9.89
      title: Romeo and Juliet               | price: 8.95
      title: War and Peace                  | price: 7.59   
   */

Ejemplo 3: Centinelas

El siguiente código de ejemplo, consistente en la ordenación de una cadena de caracteres con terminación nula característica del lenguaje C (zero-terminated string), muestra una situación en la que el tipo de iterador I (un char const*) y el tipo de centinela S (denominado Zstr_sentinel) son diferentes:

   struct Zstr_sentinel{ };
   auto operator==(char const* p, Zstr_sentinel /* no-name */) { return *p == '\0'; }
   

   char spell[] = "expelliarmus!";
   insertion_sort(spell, Zstr_sentinel{});

   for (char const c : ranges::subrange{spell, Zstr_sentinel{}})
      fmt::print("{}", c);    // output: !aeeillmprsux

Puede consultarse una explicación más detallada del tipo Zstr_sentinel en la referencia [9].

Ejemplo 4: Ordenación en tiempo de compilación

Cerraremos este artículo poniendo a prueba una vez más las capacidades de metaprogramación del lenguaje C++. Sin duda no habrá escapado a la atención del lector que las sobrecargas del algoritmo de ordenación insertion_sort hayan sido declaradas con el especificador constexpr. Ello permite su ejecución en tiempo de compilación siempre que su llamada constituya una expresión constante [10].

A modo de ejemplo, definamos la siguiente plantilla de clase Sorted_array<T,N>, que hereda públicamente de std::array<T,N>. Dado un array arbitrario, un comparador y un proyector, el constructor de la clase se encargará de almacenar y ordenar los datos mediante una llamada a insertion_sort:

   template<movable T, size_t N, typename Comp = ranges::less, typename Proj = identity>
   struct Sorted_array : array<T, N> {
      using Data = array<T, N>;
      constexpr explicit Sorted_array(Data&& entries, Comp comp = Comp{}, Proj proj = Proj{})
         : Data{move(entries)}
      {
         insertion_sort(*this, move(comp), move(proj));
      }
   };
 

Consideremos el siguiente programa sencillo:

   constexpr auto entries = Sorted_array{array{5, 12, 7, -3, 1}, ranges::greater{}};
  
   auto main() -> int
   {
      for (int const i : entries)
         printf("%d\n", i);
   }

Su código ensamblador x86-64 (compilado con el nivel -O3 del optimizador y -DNDEBUG) demuestra que el array global de enteros entries (con duración de almacenamiento estático y contenido en el data segment) es construido y ordenado de mayor a menor en tiempo de compilación:

.LC0:
.string "%d\n"
main:
push rbx
xor ebx, ebx
.L2:
mov esi, DWORD PTR entries[rbx]
mov edi, OFFSET FLAT:.LC0
xor eax, eax
add rbx, 4
call printf
cmp rbx, 20
jne .L2
xor eax, eax
pop rbx
ret
entries:
.long 12
.long 7
.long 5
.long 1
.long -3

No puede dejar de sorprender que el código de nuestro artículo se limite en este caso a un conjunto tan reducido de instrucciones.

Curiosamente, el compilador Clang 10.0.1 es capaz de desenroscar el bucle for de impresión y producir una serie de llamadas a printf [11]. Se trata de una optimización que puede mejorar la velocidad de ejecución de nuestro programa a costa de un aumento en el tamaño del ejecutable. Eso sí, para comprobar este punto nuestro código debe ser adaptado dada la ausencia de las bibliotecas <concepts> y <ranges> en este compilador:

main: # @main
push rax
mov edi, offset .L.str
mov esi, 12
xor eax, eax
call printf
mov edi, offset .L.str
mov esi, 7
xor eax, eax
call printf
mov edi, offset .L.str
mov esi, 5
xor eax, eax
call printf
mov edi, offset .L.str
mov esi, 1
xor eax, eax
call printf
mov edi, offset .L.str
mov esi, -3
xor eax, eax
call printf
xor eax, eax
pop rcx
ret
.L.str:
.asciz "%d\n"

Seguiremos investigando la expresividad y eficiencia del nuevo estándar C++20 en próximos posts de esta serie.

Referencias bibliográficas

Cppreference - Constraints and concepts: https://en.cppreference.com/w/cpp/language/constraints
Cppreference - Concepts library: https://en.cppreference.com/w/cpp/concepts
Cppreference - Iterator library: https://en.cppreference.com/w/cpp/iterator
Cppreference - Rages library: https://en.cppreference.com/w/cpp/ranges
Cormen T. H., et al., Introduction to Algorithms. 3rd Edition, MIT Press (2009).
Cppreference - std::sortable: https://en.cppreference.com/w/cpp/iterator/sortable
Cppreference - std::rotate - https://en.cppreference.com/w/cpp/algorithm/rotate
Stack Overflow - https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c
foonathan::blog() - C++20’s Iterator Sentinels: https://foonathan.net/2020/03/iterator-sentinel/
Cppreference - Constant expression: https://en.cppreference.com/w/c/language/constant_expression
Eric Niebler - https://twitter.com/ericniebler/status/1270832838754004992

C++ -> Fundamentos de Programación

Programando con C++20 (Parte I): Concepts

No hay comentarios:

Publicar un comentario