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

votos
44

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 pila. Algún tipo de clase de asignador STL también funcionaría, pero estoy tratando de evitar cualquier tipo de pila, incluso acumulaciones estáticas por subproceso (aunque una de esas es mi segunda opción). La pila 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<match_item> matches(buffer, sizeof(buffer));

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

stack_vector<match_item, 256> 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< const char *, const char * > comp_list_item;
typedef std::vector< comp_list_item > 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< const char *, const char * > comp_list_item;
typedef StackAllocator< comp_list_item, comp_list_alloc_size > comp_list_alloc_type;
typedef std::vector< comp_list_item, comp_list_alloc_type > 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.

Publicado el 09/12/2008 a las 23:15
fuente por usuario
En otros idiomas...                            


10 respuestas

votos
38

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::vectorpara darle su asignador personalizado que asigna desde un buffer de pila. 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 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<int, 128> s;
s->push_back(42); // overloaded operator->
s->push_back(43);

// to get the real std::vector. 
StackVector<int, 128>::ContainerType & v = s.container();
std::cout << v[0] << " " << v[1] << std::endl;
Respondida el 09/12/2008 a las 23:27
fuente por usuario

votos
15

Parece que impulso :: static_vector es lo que está buscando. A partir de la documentación:

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

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

Respondida el 16/01/2014 a las 14:23
fuente por usuario

votos
11

Algunas opciones que quizás quiera ver:

STLSoft por Matthew Wilson (autor de Imperfect C ++) tiene una auto_bufferclase de plantilla que coloca una matriz predeterminada en la pila, pero si crece más grande que la asignación de la pila, 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 utiliza 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::arrayque no tiene ninguno de los comportamientos ajuste dinámico del tamaño de los dos primeros, pero le da más de la vectorinterfaz que sólo el uso de punteros como iteradores que se obtiene con matrices incorporadas (es decir, que se obtiene. begin(), end(), size(), Etc.):

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

Respondida el 10/12/2008 a las 02:18
fuente por usuario

votos
4

Si la velocidad importa, veo tiempos de ejecución

  • 4 ns int [10], tamaño fijo en la pila
  • 40 ns <vector>
  • 1300 ns <stlsoft/containers/pod_vector.hpp>

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 <stlsoft/containers/pod_vector.hpp>
#include <stdio.h>
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<int> v;  // 40 ns
    // stlsoft::pod_vector<int> v;  // 1300 ns
    // stlsoft::pod_vector<int, std::allocator<int>, 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 );

}
Respondida el 29/07/2009 a las 12:20
fuente por usuario

votos
4

Puede usar su propio asignador para std :: vector y hacer que asigne trozos de su almacenamiento basado en pila, 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.

Respondida el 09/12/2008 a las 23:18
fuente por usuario

votos
3

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.

Respondida el 09/12/2008 a las 23:39
fuente por usuario

votos
2

Puede darse el caso de que esté utilizando Qt. Entonces es posible que desee ir a QVarLengthArray( docs ). Se asienta básicamente entre std::vectory std::array, la asignación estática de una cierta cantidad y cayendo de nuevo a asignación del montón si es necesario.

Yo prefiero la versión impulso si lo estaba utilizando sin embargo.

Respondida el 13/05/2014 a las 21:00
fuente por usuario

votos
2

¿Por qué quieres ponerlo en la pila 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 arquitecturas, y usted no la corrupción de la pila de riesgos la arruina.

Respondida el 09/12/2008 a las 23:25
fuente por usuario

votos
1

Boost tiene esto. Se llama small_vector

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

small_vector se puede convertir en small_vector_base, un tipo que es independiente del contador de elementos preasignado, permitiendo que el código cliente que no necesita ser con plantilla en ese argumento N. small_vector hereda todas las funciones miembro del vector por lo que es compatible con todas las características estándar como emplazamiento, asignadores con estado, etc.

Respondida el 21/04/2016 a las 05:50
fuente por usuario

votos
0

Si desea asignar en la pila, pero no quieren comprobar la validez de definir un tamaño máximo en tiempo de compilación, puede utilizar StackVector , una pequeña aplicación que puede ser utilizada como esto:

new_stack_vector(Type, name, size)

donde Typees el tipo de elemento en el vector, namees el nombre de la variable del vector, y sizees el número máximo de elementos para permitir en el vector.

sizepuede ser variable y no necesita ser una constante de tiempo de compilación! :RE

Ejemplo:

new_stack_vector(int, vec, 100); //like vector<int> 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!

Exención de responsabilidad: No utilice nunca muy grandes tamaños de matriz en la pila en general. Al igual que usted no debe usar int var[9999999], se debe utilizar de manera similar, no new_stack_vector(int, vec, 9999999)! Utilizar de manera responsable.

Respondida el 07/03/2018 a las 10:27
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more