Buscando una clase de vector similar a STL de C ++ pero usando almacenamiento de stack

Antes de escribir el mío, les preguntaré a todos ustedes.

Estoy buscando una clase de C ++ que sea casi exactamente como un vector STL pero almacena datos en una matriz en la stack. Algún tipo de clase de asignador STL también funcionaría, pero estoy tratando de evitar cualquier tipo de stack, incluso acumulaciones estáticas por subproceso (aunque una de esas es mi segunda opción). La stack es simplemente más eficiente.

Tiene que ser casi una gota en reemplazo del código actual que usa un vector.

Por lo que estaba por escribirme, estaba pensando en algo como esto:

char buffer[4096]; stack_vector matches(buffer, sizeof(buffer)); 

O la clase podría tener espacio de búfer asignado internamente. Entonces se vería así:

 stack_vector matches; 

Estaba pensando que arrojaría std :: bad_alloc si se queda sin espacio, aunque eso no debería pasar nunca.

Actualizar

¡Usar stack_container.h de Chromium funciona muy bien!

La razón por la que no había pensado hacerlo de esta manera es que siempre he pasado por alto el parámetro del objeto de asignación para los constructores de la colección STL. He usado el parámetro de la plantilla varias veces para hacer pools estáticos, pero nunca había visto código ni escrito ninguno que realmente utilizara el parámetro del objeto. Aprendí algo nuevo. ¡Muy genial!

El código es un poco desordenado y, por alguna razón, GCC me obligó a declarar el asignador como un elemento real en lugar de construirlo en el parámetro del asignador del vector. Pasó de algo como esto:

 typedef std::pair comp_list_item; typedef std::vector comp_list_type; comp_list_type match_list; match_list.reserve(32); 

A esto:

 static const size_t comp_list_alloc_size = 128; typedef std::pair comp_list_item; typedef StackAllocator comp_list_alloc_type; typedef std::vector comp_list_type; comp_list_alloc_type::Source match_list_buffer; comp_list_alloc_type match_list_alloc( &match_list_buffer ); comp_list_type match_list( match_list_alloc ); match_list.reserve( comp_list_alloc_size ); 

Y tengo que repetir eso cada vez que declaro uno nuevo. Pero funciona como yo quería.

Noté que stack_container.h tiene un StackVector definido e intenté usarlo. Pero no hereda de vector o define los mismos métodos, por lo que no fue un reemplazo inmediato. No quería volver a escribir todo el código usando el vector, así que renuncié a él.

No tiene que escribir una clase de contenedor completamente nueva. Puede seguir con sus contenedores STL, pero cambie el segundo parámetro de, por ejemplo, std::vector para darle su asignador personalizado que asigna desde un buffer de stack. Los autores del cromo escribieron un asignador solo para esto:

https://chromium.googlesource.com/chromium/chromium/+/master/base/stack_container.h

Funciona asignando un búfer donde dices qué tan grande es. Usted crea el contenedor y llama a container.reserve(buffer_size); . Si desborda ese tamaño, el asignador obtendrá automáticamente elementos del montón (ya que se deriva de std::allocator , en ese caso solo usará las instalaciones del asignador estándar). No lo he probado, pero parece que es de Google, así que creo que vale la pena intentarlo.

El uso es así:

 StackVector s; s->push_back(42); // overloaded operator-> s->push_back(43); // to get the real std::vector. StackVector::ContainerType & v = s.container(); std::cout << v[0] << " " << v[1] << std::endl; 

Parece que boost :: static_vector es lo que está buscando. De la documentación:

static_vector es un híbrido entre vector y array: como vector, es un contenedor de secuencia con almacenamiento contiguo que puede cambiar de tamaño, junto con la asignación estática, baja sobrecarga y capacidad fija de la matriz. static_vector se basa en la clase varray de alto rendimiento de Adam Wulkiewicz y Andrew Hundt.

El número de elementos en un static_vector puede variar dinámicamente hasta una capacidad fija porque los elementos se almacenan dentro del objeto de manera similar a una matriz.

Algunas opciones que quizás quiera ver:

STLSoft por Matthew Wilson (autor de Imperfect C ++) tiene una clase de plantilla auto_buffer que coloca una matriz predeterminada en la stack, pero si crece más grande que la asignación de la stack, tomará la memoria del montón. Me gusta esta clase: si sabe que los tamaños de sus contenedores generalmente estarán limitados por un límite bastante bajo, obtendrá la velocidad de una matriz asignada localmente. Sin embargo, para los casos de esquina donde necesita más memoria, todo funciona correctamente.

http://www.stlsoft.org/doc-1.9/classstlsoft_1_1auto__buffer.html

Tenga en cuenta que la implementación que uso no es STLSoft, sino una implementación que toma mucho de él.

“The Lazy Programmer” hizo una publicación para la implementación de un contenedor que usa alloca() para el almacenamiento. No soy partidario de esta técnica, pero te dejaré decidir por ti mismo si es lo que quieres:

http://tlzprgmr.wordpress.com/2008/04/02/c-how-to-create-variable-length-arrays-on-the-stack/

Luego está boost::array que no tiene el comportamiento de tamaño dynamic de los dos primeros, pero te da más de la interfaz de vector que simplemente usar punteros como iteradores que obtienes con matrices incorporadas (es decir, obtienes begin() , end() , size() , etc.):

http://www.boost.org/doc/libs/1_37_0/doc/html/boost/array.html

Puede usar su propio asignador para std :: vector y hacer que asigne trozos de su almacenamiento basado en stack, similar a su ejemplo. La clase de asignador es la segunda parte de la plantilla.

Editar: nunca he intentado esto, y al mirar la documentación aún más, me hace creer que no puedes escribir tu propio asignador. Todavía estoy investigando.

Si la velocidad importa, veo tiempos de ejecución

  • 4 ns int [10], tamaño fijo en la stack
  • 40 ns
  • 1300 ns

para una estúpida prueba a continuación: solo 2 push, v [0] v [1], 2 pop, en una plataforma, mac ppc, gcc-4.2 -O3 solamente. (No tengo idea si Apple ha optimizado su stl)

No aceptes ningún horario que no hayas falsificado tú mismo. Y, por supuesto, cada patrón de uso es diferente. No obstante, los factores> 2 me sorprenden.

(Si los mems, los accesos a la memoria, son el factor dominante en los tiempos de ejecución, ¿cuáles son todos los mems adicionales en las diversas implementaciones?)

 #include  #include  using namespace std; int main( int argc, char* argv[] ) { // times for 2 push, v[0] v[1], 2 pop, mac g4 ppc gcc-4.2 -O3 -- // Vecint10 v; // stack int[10]: 4 ns vector v; // 40 ns // stlsoft::pod_vector v; // 1300 ns // stlsoft::pod_vector, 64> v; int n = (argv[1] ? atoi( argv[1] ) : 10) * 1000000; int sum = 0; while( --n >= 0 ){ v.push_back( n ); v.push_back( n ); sum += v[0] + v[1]; v.pop_back(); v.pop_back(); } printf( "sum: %d\n", sum ); } 

tr1 :: array parcialmente coincide con su descripción. Carece de elementos como push ___ back (), etc., pero podría valer la pena echarle un vistazo como punto de partida. Envolverlo y agregar un índice al “respaldo” para apoyar push_back (), etc. debería ser bastante fácil.

¿Por qué quieres ponerlo en la stack particularmente? Si tiene una implementación de alloca (), puede agregar un asignador de clase utilizando ese en lugar de malloc (), pero su idea de usar una matriz estáticamente asignada es aún mejor: es igual de rápida en la mayoría de las architectures, y usted no la corrupción de la stack de riesgos la arruina.

Puede ser el caso de que estés usando Qt. Entonces es posible que desee ir a QVarLengthArray ( documentos ). Se ubica básicamente entre std::vector y std::array , asignando estáticamente una cierta cantidad y volviendo a la asignación de montón si es necesario.

Preferiría la versión de refuerzo si la estuviera usando.

Boost tiene esto. Se llama small_vector

small_vector es un contenedor tipo vector optimizado para el caso cuando contiene pocos elementos. Contiene algunos elementos preasignados in situ, lo que le permite evitar el uso de la asignación dinámica de almacenamiento cuando el número real de elementos está por debajo de ese umbral preasignado. small_vector está inspirado en el contenedor SmallVector de LLVM. A diferencia de static_vector, la capacidad de small_vector puede crecer más allá de la capacidad inicial preasignada.

small_vector es convertible a small_vector_base, un tipo que es independiente del recuento de elementos preasignados, lo que permite el código del cliente que no necesita ser modelado en ese argumento N. small_vector hereda todas las funciones de miembros del vector, por lo que admite todas las características estándar, como emplazamientos, asignadores con estado, etc.

Si desea asignar en la stack, pero no desea predefinir un tamaño máximo en tiempo de comstackción, puede usar StackVector , una implementación pequeña que se puede usar así:

 new_stack_vector(Type, name, size) 

donde Type es el tipo de elemento en el vector, el name es el nombre de la variable del vector, y el size es la cantidad máxima de elementos para permitir en el vector.

size puede ser variable y no necesita ser una constante en tiempo de comstackción :RE

Ejemplo:

 new_stack_vector(int, vec, 100); //like vector vec; vec.reserve(100); but on the stack :) vec.push_back(10); //added "10" as the first item in the vector 

…¡y eso es todo!

Descargo de responsabilidad: nunca utilice tamaños de matriz muy grandes en la stack en general. Como no debería usar int var[9999999] , tampoco debería usar new_stack_vector(int, vec, 9999999) ! Úselo de manera responsable.