Buscando clase vector C++ STL-like pero usando almacenamiento de pila

Question

Antes de escribir la mía, 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 iba a escribir, yo 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. A continuación, se vería como:

stack_vector<match_item, 256> matches; 

Yo estaba pensando que sería tirar std :: bad_alloc si se queda sin espacio, aunque eso no debería ocurrir nunca.

actualización

Usando stack_container.h de cromo funciona muy bien!

La razón por la que no había pensado hacerlo de esta manera es porque 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 complicado 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. Se 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 que cada vez que declaro una nueva. Pero funciona como yo quería.

Me di cuenta de 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.

Answer 1

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 pila. Los autores escribieron un asignador de cromo sólo para esto:

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

Funciona mediante la asignación de un búfer en el que dice lo grande que es. Usted crea el contenedor y llama al 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 la siguiente:

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; 

Answer 2

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 mirando la documentación aún más me hace creer que no puede escribir su propio asignador. Todavía estoy investigando.

Answer 3

¿Por qué quiere ponerlo en la pila en particular, la pila? 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.

Answer 4

TR1 :: matriz coincide parcialmente 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.

Answer 5

Algunas opciones que puede tener que mirar:

STLSoft por Matthew Wilson (autor de Imperfect C++) tiene una clase auto_buffer plantilla que pone una matriz por defecto en la pila, pero si crece más grande que la asignación Stack agarra 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 yo mismo uso no es de STLSoft, pero una implementación que inspira en gran medida de ella.

"The Lazy Programmer" realizó una publicación para la implementación de un contenedor que usa alloca() para el almacenamiento. No soy un fan de esta técnica, pero voy a dejar que decida por sí mismo si es lo que quiere:

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

Luego está boost::array que no tiene ninguno de los comportamientos ajuste dinámico del tamaño de los dos primeros, pero le da más de la interfaz vector que sólo el uso de punteros como iteradores que se obtiene con matrices incorporadas (es decir, se obtiene begin(), end(), size(), etc.):

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

Answer 6

Si la velocidad es importante , YO ver correr veces

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

para a continuación una prueba estúpida - sólo 2 de empuje, 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 acepte ninguna temporización que no haya falsificado usted mismo. Y, por supuesto, cada patrón de uso es diferente. No obstante, los factores> 2 me sorprenden.

(Si accede MEMS, la memoria, son el factor dominante en los tiempos de ejecución, lo son todos los MEMS supletorias 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); 

} 

Answer 7

Parece que boost::static_vector es lo que está buscando. 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 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.

Answer 8

Puede ser que esté utilizando Qt. Entonces es posible que desee ir a QVarLengthArray (docs). Se encuentra básicamente entre std::vector y std::array, asignando estáticamente una cierta cantidad y volviendo a la asignación del montón si es necesario.

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

Answer 9

Boost tiene esto. Su llamado small_vector

small_vector es un contenedor vector-como optimizado para el caso cuando se contiene pocos elementos. Contiene algunos elementos preasignados in situ, lo que le permite evitar el uso de la asignación de almacenamiento dinámico cuando la cantidad 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 se puede convertir en small_vector_base, un tipo que es independiente de la preasignado contador de elementos , permitiendo que el código cliente que no necesita ser con plantilla en ese argumento N. small_vector hereda funciones miembro todo de vector por lo que soporta todas las características estándar como emplazamiento, asignadores con estado, etc.

Answer 10

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

new_stack_vector(Type, name, size) 

donde Type es el tipo de elemento en el vector, name es el nombre de la variable del vector, y es el máximo size número de elementos a todos bajo en el vector.

size puede ser variable y no necesita ser una constante de tiempo de compilación!: D

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!

Descargo de responsabilidad: Nunca utilice tamaños de matriz muy grandes en la pila en general. Al igual que no debería usar int var[9999999], tampoco debe usar new_stack_vector(int, vec, 9999999). Úselo de manera responsable.