Olhando para a classe vector STL-como C ++, mas usando armazenamento pilha

votos
44

Antes de eu escrever o meu próprio eu vou pedir a todos vocês.

Estou à procura de uma classe C ++ que é quase exatamente como um vetor STL mas armazenamentos de dados em uma matriz na pilha. Algum tipo de classe alocador STL iria funcionar também, mas eu estou tentando evitar qualquer tipo de pilha, mesmo estáticos alocados montes por thread (embora uma delas é a minha segunda opção). A pilha é apenas mais eficiente.

Ele precisa ser quase uma gota no substituto para o código atual que usa um vetor.

Para o que eu estava prestes a escrever-me que eu estava pensando em algo como isto:

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

Ou a classe pode ter espaço de buffer alocada internamente. Em seguida, ele seria parecido com:

stack_vector<match_item, 256> matches;

Eu estava pensando que iria jogar std :: bad_alloc se ele ficar sem espaço, embora isso não deve acontecer.

Atualizar

Usando stack_container.h de cromo funciona muito bem!

A razão que eu não tinha pensado fazê-lo desta maneira eu mesmo é que eu sempre ignorado o parâmetro alocador de objeto para os construtores de recolha de STL. Eu tenho usado o parâmetro do modelo algumas vezes para fazer piscinas estáticos, mas eu nunca tinha visto código ou escrito qualquer que realmente usou o parâmetro de objeto. Eu aprendi uma coisa nova. Muito legal!

O código é um pouco confuso e por algum motivo GCC me forçado a declarar o alocador como um item real em vez de construí-la no parâmetro alocador do vetor. Ela passou de algo como isto:

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

Para isso:

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

E eu tenho que repetir que sempre que eu declarar um novo. Mas ele funciona exatamente como eu queria.

Notei que stack_container.h tem uma StackVector definido e eu tentei usá-lo. Mas não herda de vector ou definir os mesmos métodos por isso não foi um substituto drop-in. Eu não queria reescrever todo o código utilizando o vector assim que eu dei em cima dele.

Publicado 09/12/2008 em 23:15
fonte usuário
Em outras línguas...                            


10 respostas

votos
38

Você não tem que escrever uma classe completamente nova recipiente. Você pode ficar com seus contêineres STL, mas alterar o segundo parâmetro, por exemplo, std::vectorpara dar-lhe o seu alocador de costume que aloca de uma pilha-tampão. Os autores cromo escreveu um alocador apenas para isso:

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

Ele funciona através da atribuição de um buffer onde você diz o quão grande ele é. Você cria o recipiente e chamada container.reserve(buffer_size);. Se você transbordar desse tamanho, o alocador irá receber automaticamente elementos da pilha (uma vez que é derivado std::allocator, será, nesse caso, basta usar as instalações do alocador padrão). Eu não tentei, mas parece que é do google, então eu acho que vale a pena tentar.

O uso é parecido com isto:

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;
Respondeu 09/12/2008 em 23:27
fonte usuário

votos
15

Parece que boost :: static_vector é o que você está procurando. A partir da documentação:

static_vector é um híbrido entre o vector e de matriz: como vector, que é um recipiente de armazenamento com sequência contígua que pode mudar de tamanho, juntamente com a atribuição estática, baixa sobrecarga, e capacidade fixa de matriz. static_vector é baseado em Adam Wulkiewicz e classe varray de alto desempenho de Andrew Hundt.

O número de elementos em um static_vector pode variar dinamicamente até uma capacidade fixa, pois os elementos são armazenados dentro do próprio objecto semelhante a uma matriz.

Respondeu 16/01/2014 em 14:23
fonte usuário

votos
11

Algumas opções que você pode querer olhar para:

STLSoft por Matthew Wilson (autor de Imperfect C ++) tem uma auto_bufferclasse de modelo que coloca uma matriz padrão na pilha, mas se ela cresce mais do que a alocação de pilha vai agarrar a memória da pilha. Eu gosto desta classe - se você sabe que seus tamanhos de recipientes são geralmente vai ser delimitada por um limite bastante baixo, então você começa a velocidade de um local, empilhar matriz alocada. No entanto, para os casos de canto onde você precisa de mais memória, tudo ainda funciona corretamente.

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

Note-se que a implementação Eu mesmo uso não é STLSoft de, mas uma implementação que empresta muito dele.

"The Lazy programador" fez um post para uma implementação de um recipiente que usa alloca()para o armazenamento. Eu não sou um fã de esta técnica, mas eu vou deixar você decidir por si mesmo se é o que você quer:

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

Depois, há boost::arrayque não tem nada do comportamento de dimensionamento dinâmico dos dois primeiros, mas dá-lhe mais do vectorInterface do que apenas usando ponteiros como iteradores que você começa com matrizes internos (ou seja, você começa. begin(), end(), size(), Etc.):

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

Respondeu 10/12/2008 em 02:18
fonte usuário

votos
4

Se a velocidade é importante, eu vejo tempos de execução

  • 4 ns int [10], de tamanho fixo na pilha
  • 40 ns <vector>
  • 1300 ns <stlsoft/containers/pod_vector.hpp>

para um teste de burro abaixo - apenas dois impulso, v [0] v [1], 2 pop, em uma plataforma, ppc mac, gcc-4.2 -O3 única. (Eu não tenho idéia se a Apple tem otimizado seu STL).

Não aceite nenhum horários você não ter falsificado a si mesmo. E, claro, cada padrão de uso é diferente. No entanto Factores> 2 surpresa me.

(Se MEMS, acessos à memória, são o fator dominante em tempos de execução, quais são todos os MEMS extras nas várias implementações?)

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

}
Respondeu 29/07/2009 em 12:20
fonte usuário

votos
4

Você pode usar seu próprio alocador para std :: vector e tê-lo alocar pedaços de seu armazenamento baseado em pilha, semelhante ao seu exemplo. A classe alocador é a segunda parte do modelo.

Edit: Eu nunca tentei isso, e olhando para a documentação me leva ainda mais para acreditar que você não pode escrever seu próprio alocador. Eu ainda estou olhando para ele.

Respondeu 09/12/2008 em 23:18
fonte usuário

votos
3

tr1 :: matriz corresponde parcialmente sua descrição. Falta-lhe coisas como impulso ___ back (), etc., mas pode valer a pena dar uma olhada em como ponto de partida. Envolvê-lo e adicionar um índice para a "volta" para apoiar push_back (), etc. deve ser bastante fácil.

Respondeu 09/12/2008 em 23:39
fonte usuário

votos
2

Pode ser o caso que você está usando Qt. Em seguida, você pode querer ir para QVarLengthArray( docs ). Senta-se, basicamente, entre std::vectore std::array, alocando estaticamente por um determinado período e caindo de volta para alocação de pilha, se necessário.

Eu prefiro a versão impulso se eu estava usando-o embora.

Respondeu 13/05/2014 em 21:00
fonte usuário

votos
2

Por que você deseja colocá-lo na pilha particularmente? Se você tem uma implementação de alloca (), você poderia buld um alocador de classe usando que em vez de malloc (), mas a sua idéia de usar uma matriz alocada estaticamente é ainda melhor: é tão rápido na maioria das arquiteturas, e você não faz corrupção de pilha risco de você fracassar.

Respondeu 09/12/2008 em 23:25
fonte usuário

votos
1

Impulso ter isso. Seu chamado small_vector

small_vector é um recipiente vector semelhante optimizado para o caso em que ele contém poucos elementos. Ele contém alguns elementos pré-alocados no local, o que lhe permite evitar o uso de alocação de armazenamento dinâmico quando o número real de elementos é inferior ao limiar pré-alocados. small_vector é inspirada por recipiente SmallVector do LLVM. Ao contrário static_vector, a capacidade do small_vector pode crescer além da capacidade preallocated inicial.

small_vector é conversível para small_vector_base, um tipo que é independente da contagem de elementos pré-alocados, permitindo que o código do cliente que não precisam ser modeladas em que o argumento N. small_vector herda as funções de membro todos do vetor para que ele suporta todas as características padrão, como colocação, alocadores stateful, etc.

Respondeu 21/04/2016 em 08:50
fonte usuário

votos
0

Se você gostaria de alocar na pilha, mas não quero pré-definir um tamanho máximo em tempo de compilação, você pode usar StackVector , uma pequena aplicação que pode ser usado como este:

new_stack_vector(Type, name, size)

onde Typeé do tipo de elemento no vector, nameé o nome da variável do vector, e sizeé o número máximo de elementos para permitir no vector.

sizepode ser variável e não precisa ser uma constante em tempo de compilação! : D

Exemplo:

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

...e isso é tudo!

Disclaimer: Nunca use tamanhos muito grandes de matriz na pilha em geral. Como você não deve usar int var[9999999], você também não deve usar new_stack_vector(int, vec, 9999999)! Use com responsabilidade.

Respondeu 07/03/2018 em 13:27
fonte usuário

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