c++11 - library - stack c++ stl

C++ STL-¿Por qué el método forward_list no size()?

Question

He estado usando forward_list C ++ 11 como un contenedor para inserciones rápidas, sin mucha sobrecarga de memoria, ya que es una lista vinculada individualmente.

Después de darme cuenta de que forward_list no tiene el método size() , estoy un poco confundido sobre el razonamiento detrás de eso. ¿No podría simplemente mantener un campo privado manteniendo un registro de los nodos insertados y eliminados, por lo tanto, implementando una operación O (1) size ()?

Answer 1

N2543 es la propuesta, y tiene una discusión detallada sobre el size() .

La elección entre la Opción 3 [que no proporciona el size() ] y la Opción 2 [que proporciona un size() O (1) size() ] es más una cuestión de criterio. Elegí la opción 3 por la misma razón por la que elegí insertar-después en lugar de insertar-antes: la opción 3 es más consistente con el objetivo de cero sobrecarga en comparación con una lista vinculada estilo C escrita a mano. Mantener un conteo duplica el tamaño de un objeto forward_list (una palabra para el encabezado de la lista y otra para el recuento), y ralentiza cada operación que cambia la cantidad de nodos. En la mayoría de los casos, esto no es un cambio en la complejidad asintótica (el único cambio en la complejidad asintótica está en una de las formas de splice ), pero es una sobrecarga no nula. Es un costo que todos los usuarios tendrían que pagar, ya sea que necesiten esta función o no, y, para los usuarios que se preocupan por mantener un conteo, es igual de fácil mantenerla fuera de la lista, incrementando el conteo con cada inserción y disminuyéndolo con cada borrado, como lo es mantener el recuento dentro de la lista.

Answer 2

Los contenedores STL han eliminado tradicionalmente / inteligentemente las características de las estructuras de datos que no funcionan bien en términos de tiempo y espacio.

Agregar presupuesto de "Biblioteca estándar de C ++: un tutorial y una referencia"

Una std::forward_list no proporciona una función de miembro de size() . Esto es consecuencia de la omisión de características que crean una sobrecarga de tiempo o espacio en relación con una lista manuscrita individualmente vinculada.

Answer 3

Me pregunto si el comité estándar consideró una mezcla como parámetros de plantilla que pueden agregar el mantenimiento de un miembro de tamaño opcional a las clases de la lista. Esto hubiera permitido que la clase tuviera un conteo de elementos opcional, sin pérdida de generalidad.

Me gusta esto

class HasSize
{ 
public:
   HasSize() : size_(0) { } 

   void addSize(size_t add) { size_ += add; }

   bool has_size() { return true; }

   size_t size() { return size_; }

   size_t size_;
};

class NoSize
{ 
public:
   void addSize(size_t add) { }

   bool has_size() { return false; }

   size_t size() { return 0; }
};

template<type T, type Allocator, type Sz = HasSize>
class forward_list
{

    void push_back( T &arg )
    {
         ...
         opt_.addSize( 1 );
    }

    size_t size()
    {
       if (opt_.has_size())
          return opt_.size();
       else
          return std::distance(begin(), end()); 
    }

    Sz opt_;
};

/ esta pregunta se marcó como duplicada, por lo que se agrega aquí /