c++ - una - vectores en c

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

Question

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.

Answer 1

¿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.

Answer 2

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 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 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 dinámico 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

Answer 3

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.

Answer 4

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 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<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 5

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.

Answer 6

Puede ser el caso de que estés usando Qt. Entonces es posible que desee ir a QVarLengthArray ( docs ). 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.

Answer 7

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.

Answer 8

Si desea asignar en la pila, pero no desea predefinir un tamaño máximo en tiempo de compilació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 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!

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

Answer 9

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 );

}

Answer 10

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.