std :: vector versus std :: array em C ++

283

Quais são as diferenças entre a std::vectore an std::arrayem C ++? Quando um deve ser preferido em detrimento de outro? Quais são os prós e os contras de cada um? Tudo o que meu livro faz é listar como eles são iguais.

Zud
fonte
1
Estou procurando uma comparação de std::vectorvs. std::arraye como os termos são diferentes.
Zud
Zud, std::arraynão é o mesmo que uma matriz C ++. std::arrayé um invólucro muito fino em torno de matrizes C ++, com o objetivo principal de ocultar o ponteiro do usuário da classe. Vou atualizar minha resposta.
ClosureCowboy
Atualizei o título e o texto da pergunta para refletir seu esclarecimento.
Matteo Italia

Respostas:

318

std::vectoré uma classe de modelo que encapsula uma matriz dinâmica 1 , armazenada na pilha, que cresce e diminui automaticamente se elementos forem adicionados ou removidos. Ele fornece todos os ganchos ( begin(), end()iteradores, etc.) que o fazem funcionar bem com o restante do STL. Ele também possui vários métodos úteis que permitem executar operações que em uma matriz normal seriam complicadas, como, por exemplo, inserir elementos no meio de um vetor (ele lida com todo o trabalho de mover os seguintes elementos nos bastidores).

Como ele armazena os elementos na memória alocada no heap, há alguma sobrecarga em relação às matrizes estáticas.

std::arrayé uma classe de modelo que encapsula uma matriz de tamanho estatístico, armazenada dentro do próprio objeto, o que significa que, se você instanciar a classe na pilha, a própria matriz estará na pilha. Seu tamanho deve ser conhecido no momento da compilação (é passado como parâmetro do modelo) e não pode aumentar ou diminuir.

É mais limitado do que std::vector, mas geralmente é mais eficiente, especialmente para tamanhos pequenos, porque na prática é principalmente um invólucro leve em torno de uma matriz no estilo C. No entanto, é mais seguro, pois a conversão implícita em ponteiro está desabilitada e fornece grande parte da funcionalidade relacionada a STL de std::vectore dos outros contêineres, para que você possa usá-lo facilmente com os algoritmos STL & co. De qualquer forma, para a própria limitação do tamanho fixo, é muito menos flexível que std::vector.

Para uma introdução std::array, dê uma olhada neste artigo ; Para uma rápida introdução std::vectore as operações possíveis, consulte a documentação .


  1. Na verdade, acho que no padrão eles são descritos em termos de complexidade máxima das diferentes operações (por exemplo, acesso aleatório em tempo constante, iteração sobre todos os elementos em tempo linear, adição e remoção de elementos no final em tempo amortizado constante, etc), mas no AFAIK não há outro método para atender a esses requisitos além de usar uma matriz dinâmica. Conforme declarado por @Lucretiel, o padrão realmente exige que os elementos sejam armazenados de forma contígua, portanto , é uma matriz dinâmica, armazenada onde o alocador associado o coloca.
Matteo Italia
fonte
6
Em relação à nota de rodapé: Embora verdadeiro, o padrão também garante que a aritmética do ponteiro funcione nos elementos internos, o que significa que ele precisa ser uma matriz: & vec [9] - & vec [3] == 6 é verdadeiro.
Lucretiel 12/12/12
9
Tenho certeza de que esse vetor não encolhe automaticamente, mas desde C ++ 11 você pode chamar shrink_to_fit.
Dino
Estou totalmente confuso com o termo array estático e não tenho certeza qual é a terminologia correta. Você quer dizer uma matriz de tamanho estático e não uma matriz de variável estática (uma que usa armazenamento estático). stackoverflow.com/questions/2672085/… . Qual é a terminologia correta? Matriz estática é um termo desleixado para uma matriz com tamanho fixo?
Z boson
3
@Zboson: definitivamente não é só você, estática é um termo bastante abusado; a própria staticpalavra - chave em C ++ tem três significados diferentes, e o termo também é usado frequentemente para falar sobre coisas que são corrigidas no tempo de compilação. Espero que "tamanho estatico" seja um pouco mais claro.
Matteo Italia
3
Uma coisa a observar: Para programação em tempo real (onde você não deveria ter nenhuma alocação / desalocação dinâmica após a inicialização), std :: array provavelmente seria preferido em vez de std :: vector.
TED
17

Usando a std::vector<T>classe:

  • ... é tão rápido quanto usar matrizes integradas, supondo que você esteja fazendo apenas o que as matrizes integradas permitem (leitura e gravação em elementos existentes).

  • ... redimensiona automaticamente quando novos elementos são inseridos.

  • ... permite inserir novos elementos no início ou no meio do vetor, "deslocando" automaticamente o restante dos elementos para cima (isso faz sentido?). Ele permite que você remova elementos em qualquer lugar do processo std::vector, deslocando automaticamente o restante dos elementos para baixo.

  • ... permite executar uma leitura de intervalo verificado com o at()método (você sempre pode usar os indexadores []se não quiser que essa verificação seja executada).

Existem duas advertências principais no uso std::vector<T>:

  1. Você não tem acesso confiável ao ponteiro subjacente, o que pode ser um problema se você estiver lidando com funções de terceiros que exigem o endereço de uma matriz.

  2. A std::vector<bool>turma é boba. É implementado como um campo de bits condensado, não como uma matriz. Evite se você quiser uma variedade de bools!

  3. Durante o uso, std::vector<T>s será um pouco maior que uma matriz C ++ com o mesmo número de elementos. Isso ocorre porque eles precisam acompanhar uma pequena quantidade de outras informações, como o tamanho atual e, sempre que std::vector<T>redimensionadas, reservam mais espaço do que precisam. Isso evita que eles sejam redimensionados toda vez que um novo elemento é inserido. Esse comportamento pode ser alterado fornecendo um costume allocator, mas nunca senti a necessidade de fazer isso!


Edit: Depois de ler a resposta de Zud à pergunta, achei que deveria adicionar isso:

A std::array<T>classe não é a mesma que uma matriz C ++. std::array<T>é um invólucro muito fino em torno de matrizes C ++, com o objetivo principal de ocultar o ponteiro do usuário da classe (em C ++, matrizes são implicitamente convertidas em ponteiros, geralmente com efeito desanimador). A std::array<T>classe também armazena seu tamanho (comprimento), o que pode ser muito útil.

Encerramento
fonte
5
É "tão rápido" quanto usar um array interno alocado dinamicamente. Por outro lado, o uso de um array automático pode ter um desempenho consideravelmente diferente (e não apenas durante a alocação, devido aos efeitos da localidade).
Ben Voigt
4
Para vetores não-booleanos no C ++ 11 e posterior, você pode chamar data()a std::vector<T>para obter o ponteiro subjacente. Você também pode usar o endereço do elemento 0 (garantido que funcione com C ++ 11, provavelmente funcionará com versões anteriores).
Matt
16

Para enfatizar um argumento do @MatteoItalia, a diferença de eficiência é onde os dados são armazenados. A memória heap (requerida com vector) requer uma chamada ao sistema para alocar memória e isso pode ser caro se você estiver contando ciclos. A memória da pilha (possível para array) é virtualmente "zero-overhead" em termos de tempo, porque a memória é alocada apenas ajustando o ponteiro da pilha e isso é feito apenas uma vez na entrada de uma função. A pilha também evita a fragmentação da memória. Para ter certeza, std::arraynem sempre estará na pilha; depende de onde você o alocará, mas ainda envolverá uma alocação a menos de memória do heap em comparação ao vetor. Se você tem um

  • pequena "matriz" (digamos menos de 100 elementos) - (uma pilha típica tem cerca de 8 MB, portanto, não aloque mais do que alguns KB na pilha ou menos se o seu código for recursivo)
  • o tamanho será fixo
  • a vida útil está no escopo da função (ou é um valor de membro com a mesma vida útil da classe pai)
  • você está contando ciclos,

definitivamente use um std::arrayover de um vetor. Se algum desses requisitos não for verdadeiro, use a std::vector.

Mark Lakata
fonte
3
Boa resposta. "Para ter certeza, o std :: array nem sempre estará na pilha; depende de onde você o aloca" Então, como eu poderia criar um std :: array que não está na pilha com um grande número de elementos?
precisa saber é o seguinte
4
O @Trilarion usa new std::arrayou o torna membro de uma classe que você usa 'novo' para alocar.
precisa saber é o seguinte
Portanto, isso significa que new std::arrayainda espera saber seu tamanho em tempo de compilação e não pode alterar seu tamanho, mas ainda vive na pilha?
Trilarion
Sim. Não há uma vantagem significativa para usando new std::arrayvs new std::vector.
precisa saber é
12

Se você está pensando em usar matrizes multidimensionais, há uma diferença adicional entre std :: array e std :: vector. Um std :: array multidimensional terá os elementos compactados na memória em todas as dimensões, assim como o array no estilo ac. Um std :: vector multidimensional não será compactado em todas as dimensões.

Dadas as seguintes declarações:

int cConc[3][5];
std::array<std::array<int, 5>, 3> aConc;
int **ptrConc;      // initialized to [3][5] via new and destructed via delete
std::vector<std::vector<int>> vConc;    // initialized to [3][5]

Um ponteiro para o primeiro elemento na matriz de estilo c (cConc) ou std :: array (aConc) pode ser iterado por toda a matriz adicionando 1 a cada elemento anterior. Eles estão bem embalados.

Um ponteiro para o primeiro elemento na matriz de vetores (vConc) ou na matriz de ponteiros (ptrConc) só pode ser iterado pelos 5 primeiros elementos (nesse caso) e, em seguida, existem 12 bytes (no meu sistema) de sobrecarga para o próximo vetor.

Isso significa que uma matriz std :: vector> inicializada como uma matriz [3] [1000] será muito menor na memória do que uma inicializada como uma matriz [1000] [3] e ambas serão maiores na memória que uma std: matriz alocada de qualquer maneira.

Isso também significa que você não pode simplesmente passar um vetor multidimensional (ou ponteiro) para, digamos, openGL sem levar em conta a sobrecarga de memória, mas você pode ingenuamente passar um std :: array multidimensional para openGL e fazê-lo funcionar.

psimpson
fonte
-17

Um vetor é uma classe de contêiner enquanto uma matriz é uma memória alocada.

Saif al Harthi
fonte
23
Sua resposta parece abordar std::vector<T>versus T[], mas a pergunta é sobre std::vector<T>versus std::array<T>.
Keith Pinson