Año nuevo

Bueno, este año fue poco productivo en este blog. El próximo no prometo mucho más, pero espero mejorar. Dejo un par de links que agregué en la sidebar:

• Pre-defined C/C++ Compiler Macros: Si alguna vez tenemos que detectar la versión de un compilador o en qué plataformas estamos, estas macros pueden ayudarnos a escribir código portable.
• C++ Reference Wiki: Una wiki con referencia sobre C++ y C++11

Los próximos años pueden llegar a ser los mejores años de C++. Con clang avanzando sobre gcc, es probable que aparezcan herramientas muy importantes para ayudar a programar en C++. Aquí les dejo un video:

¡Feliz año nuevo!

Código C++ moderno

Una excelente charla de Herb Sutter (en inglés) introduciendo algunas de las novedades del nuevo estándar C++11 y sobre cómo escribir código en C++ aprovechando todo el conocimiento acumulado en estos años (si nunca leíste C++ Coding Standards de Herb Sutter y Andrei Alexandrescu, compralo):

http://channel9.msdn.com/Events/BUILD/BUILD2011/TOOL-835T

Los puntos tratados que no podes dejar pasar por alto:

• El nuevo significado de la palabra auto para inferir tipos automáticamente.
• La nueva sintaxis de lambdas para definir functors en línea y usarlos en algoritmos estándares (ej: for_each()).
• Exception safety y heap lifetime con smart pointers, los cuales ya tenemos varios posts en este mismo blog sobre el concepto de smart pointers y RAII.
• Nuevos contenedores de tipo hash table.
• Move semantics que evita la creación y destrucción de objetos temporales innecesarias (ej: al retornar por valor).
• Varios pequeños nuevos coding standards de C++11: funciones begin()/end(), override explícito, idioma pimpl con unique_ptr<>, etc.

En futuros posts voy a dedicar algo de tiempo en introducir estos temas y explicar por qué nacieron cada una de estas modificaciones en el nuevo estándar de C++.

Cola de prioridades (STL priority_queue)

La cola de prioridades es una estructura de datos que se puede visualizar como una bolsa, donde podemos ir metiendo elementos uno atrás del otro, pero sólo los podemos retirar según un criterio de prioridad. Por ejemplo, en el caso de un ladrón obsesivo-compulsivo, podría robar un banco cargando bolsas de dinero sin ningún criterio, y al vaciarla podría retirar los billetes según su valor (primero los de $100, luego los de $50, etc.).

Otro ejemplo, imaginemos que tenemos un barco:

#include <queue>
#include <list>

using namespace std;

class Barco {
public:
  void subirPasajero(const Pasajero& pasajero);
  void abandonarBarco(list<Pasajero>& pasajerosEnOrden);

private:
  priority_queue<Pasajero> pasajeros_;
};

La función subirPasajero() debe agregar un pasajero al barco, y abandonarBarco() debe sacar todos los pasajeros del barco y colocarlos (por orden de prioridad) en la lista que se recibe como argumento:

void Barco::subirPasajero(const Pasajero& pasajero)
{
  pasajeros_.push(pasajero);
}

void Barco::abandonarBarco(list<Pasajero>& pasajerosEnOrden)
{
  while (!pasajeros_.empty()) {
    pasajerosEnOrden.push_back(pasajeros_.top());
    pasajeros_.pop();
  }
}

Tenga en cuenta que la función miembro pop() de las colas en C++ (queue, priority_queue, etc.) no retornan el valor extraído. Esto es así para evitar crear copias de los objetos dentro de la cola. De este modo la función top() devuelve una referencia al elemento mismo que se encuentra en la cola, y pop() lo remueve sin devolver nada. Así nos evitamos de crear copias temporales de la instancia removida.

Para poder usar la priority_queue sobre un tipo de dato propio (como Pasajero), debemos ofrecer una implementación del operator<() para comparar distintas instancias de nuestro tipo de dato (este operador se utiliza para saber qué elemento debe salir último de la cola, es decir, el menor elemento tiene menor prioridad):

enum Prioridad { Capitan, Hombre, Mujer, Ninio };

class Pasajero {
public:
  Pasajero(Prioridad p) : prioridad_(p) { }

  bool operator<(const Pasajero& otro) const {
    return prioridad_ < otro.prioridad_;
  }

  Prioridad prioridad() const { return prioridad_; }

private:
  Prioridad prioridad_;
};

De este modo, el capitán tiene prioridad 0 y es tomado en cuenta como el de menor prioridad para abandonar el barco. Los pasajeros que mayor prioridad tienen de abandonar el barco son las mujeres y los niños. En este caso podrían tener igual prioridad, no tendría mucho sentido salvar a todos los niños sin sus respectivas madres.

Ahora podemos crear un ejemplo:

#include <iostream>

using namespace std;

int main()
{
  Barco titanic;
  titanic.subirPasajero(Pasajero(Capitan));
  titanic.subirPasajero(Pasajero(Mujer));
  titanic.subirPasajero(Pasajero(Hombre));
  titanic.subirPasajero(Pasajero(Mujer));
  titanic.subirPasajero(Pasajero(Ninio));
  titanic.subirPasajero(Pasajero(Hombre));
  titanic.subirPasajero(Pasajero(Ninio));
  // ...

  list<Pasajero> pasajeros;
  titanic.abandonarBarco(pasajeros);
  
  for (list<Pasajero>::iterator it = pasajeros.begin(),
         end = pasajeros.end(); it != end; ++it) {
    cout << it->prioridad() << "\n";
  }
  
  return 0;
}

El anterior ejemplo imprime:

3
3
2
2
1
1
0

Lo que significa que, sin importar el orden en el cual agregamos los pasajeros, primero extraemos los niños, luego las mujeres, los hombres, y finalmente el capitán.

Más información:
http://www.cplusplus.com/reference/stl/priority_queue/
http://en.wikipedia.org/wiki/Priority_queue