¿Cuál es la diferencia entre SGI slist y C++ 11 forward_list?

Question

Tanto SGI slist como C++ 11 std::forward_list parecen idénticos a mí a menos que me haya perdido algo; ambos implementan una lista de enlace único.

Supongo que hay una diferencia, ya que el C++ Standard Commitee no adoptó el nombre slist y en su lugar eligió un nuevo nombre, forward_list, cuando agregaron el contenedor a la biblioteca estándar para C++ 0x.

Answer 1

Una diferencia importante es que std::forward_list carece de una función de miembro size(), donde no es así como sgi::slist. La motivación para esto es que un O (N) size() ha sido problemático. N2543 tiene más detalles sobre las decisiones de diseño para forward_list.

Actualización:

recientemente he tenido una buena excusa para mirar más de cerca a este tema. slist también tiene otras funciones miembro que uno estaría tentado a pensar que son O (1), pero en realidad son O (N). Estos incluyen:

iterator previous(iterator pos); 
const_iterator previous(const_iterator pos) const; 
iterator insert(iterator pos, const value_type& x); 
iterator erase(iterator pos); 
void splice(iterator position, slist& x); 
void splice(iterator position, slist& x, iterator i); 

En resumen, si no estás muy cuidado, usted puede terminar con problemas de rendimiento significativas mediante el uso de slist. El uso de std::forward_list en su lugar asegura que obtendrá el rendimiento de O (1) esperado de su lista vinculada individualmente.

Answer 2

Así que, simplemente, sgi :: slist y forward_list son muy similares.

Las diferencias radican en que forward_list carece de una función miembro de size() que se incluye en sgi :: slist y forward_list incluye una función de miembro emplace_after que no está incluida en sgi :: slist. Además, forward_list no proporciona funciones de insertar y borrar miembros como lo hace sgi :: slist.

Si conoce alguna otra diferencia, no dude en mencionarla.

Answer 3

Recientemente he encontrado otra diferencia. El método splice_after tiene una interfaz diferente y un comportamiento diferente.

1) forward_list es necesario que indique el envase se está moviendo desde como segundo argumento:

void splice_after(const_iterator pos, forward_list& other, 
        const_iterator first, const_iterator last); 

slist:

void splice_after(iterator pos, iterator before_first, iterator before_last) 

Esto es similar a las sobrecargas.

2) Específico para la sobrecarga mencionada anteriormente: el último iterador se interpreta de manera diferente. Donde slist mueve el rango [before_first + 1, before_last + 1>, forward_list mueve el rango < primero, último>. Entonces, al convertir el código (ya que slist está en desuso en GCC, por ejemplo), asegúrese de usar: last = before_last + 1.