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

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.

std::vectoré uma classe de modelo que encapsula uma matriz dinâmica ¹ , 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.

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.

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.

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.

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