C++ -> Fundamentos de Programación: mayo 2016

GCC en sistemas MS Windows

MinGW-w64 (mingw-w64.org) es una implementación para entornos MS Windows de la familia de compiladores GCC (GNU Compiler Collection), de uso muy extendido en los sistemas Unix, Linux y BSD. MinGW-w64 incluye un subconjunto de la API de Windows, lo que permite el desarrollo de aplicaciones nativas para dicha plataforma, tanto de 64 bits (x86-64) como de 32 bits (x86).

Una de las funcionalidades más destacadas de esta solución integrada es, sin duda, Winpthreads, una biblioteca POSIX Thread que da soporte a la programación concurrente de acuerdo a las especificaciones del estándar C++11. Puede encontrarse un instalador que permite seleccionar la versión del compilador con la que trabajar (desde 4.8.1 hasta 5.3.0) en la distribución de nombre MinGW-Builds (sourceforge.net/projects/mingw-w64).

Otra distribución a señalar es la proveída en el portal Nuwen.net (nuwen.net/mingw.html). Si bien no cuenta con soporte para programación concurrente estándar mediante Winpthreads, al utilizar Win32 como modelo de threading, sí contiene la versión más actual del compilador, G++ 6.1.0 (cuyas características fueron analizadas en un post anterior), así como la versión 1.61.0 de las bibliotecas Boost (boost.org).

Guía rápida de creación de listas (II)

Artículos de la serie:

Una vez definidos los algoritmos de inserción, eliminación e intercambio de nodos en la lista mediante la estructura detail::Node_base (véase el primer post de esta serie), procederemos a implementar la lista doblemente enlazada como una plantilla uniparamétrica de clase List<>, donde el parámetro indique el tipo de variable almacenada.

Los elementos almacenados en la lista (nodos) constarán de tres campos, a saber: los punteros prev y next a los nodos inmediatamente anterior y posterior, respectivamente, así como el área de datos. Emplearemos la herencia como mecanismo básico para añadir la información contenida en la estructura detail::Node_base (es decir, los punteros de posicionamiento) a una nueva estructura privada List<>::Node que contenga, esta vez sí, el área de datos:

   template<typename T>
   class List {
      struct Node : detail::Node_base { // herencia pública
         T dat; // dato almacenado
         Node(T const& d) : dat{d} { };
      };
      detail::Node_base dnb_; // nodo centinela
   public:
      struct List_iterator; // ver definición más abajo
      struct List_const_iterator;

      // resto de la interfaz pública...
   };

Observemos que una lista contiene un subobjeto detail::Node_base, de nombre dnb_, que actuará como nodo centinela. Éste no almacenará, por supuesto, ningún dato: tan sólo proporcionará un indicador natural para finalizar las iteraciones a lo largo de la estructura. Asimismo, y con el fin de facilitar la implementación de los métodos de la clase, enlazaremos la lista circularmente a través de dicho nodo centinela, tal y como se muestra en la figura inferior. De esta manera, será posible acceder al inicio o al fondo de la lista partiendo del nodo centinela con una sola operación de avance o retroceso, respectivamente (dnb_.next en el primer caso y dnb_.prev en el segundo).

Guía rápida de creación de listas (I)

Última actualización de la serie: Noviembre de 2019.

Artículos de la serie:

En este post analizaremos los aspectos básicos del diseño de una lista lineal doblemente enlazada, inspirándonos en las implementaciones de estructuras dinámicas de datos estándar de este tipo facilitadas por compiladores profesionales, muy especialmente GCC [1]. Como es habitual, nuestra motivación aquí es puramente educativa, de manera que algunas de las elecciones en la implementación de la lista serán ciertamente discutibles y mejorables, pero no restarán valor pedagógico al conjunto.

En contraste con un vector, donde los objetos ocupan posiciones adyacentes, los elementos contenidos en una lista (a los que nos referiremos desde ahora bajo el nombre de nodos) se encuentran generalmente desperdigados en memoria (ver la imagen superior), siendo necesario que cada uno de ellos almacene la posición del elemento inmediatamente posterior (resultando una lista simplemente enlazada) así como, opcionalmente, del elemento inmediatamente anterior (lista doblemente enlazada). Centraremos nuestra atención en este segundo caso (doble enlace), al ser el más general.