O que é a estrutura de dados vetoriais

A Palavra "vector" aplicada à ciência da computação/programação é emprestada da matemática, o que pode tornar o uso confuso (até a sua pergunta pode ser sobre vários assuntos).

O exemplo mais simples de vetores em matemática é a linha de números, usada para ensinar matemática elementar (especialmente para ajudar a visualizar números negativos, subtração de números negativos, adição de números negativos, etc).

O vector é uma distância e direcção de um ponto. É por isso que pode confundir o discussão, porque uma estrutura de dados vetoriais pode ser de três pontos, X, Y, Z, em uma estrutura usada em motores gráficos 3D,ou um ponto 2D (apenas X, Y). Nesse contexto, a subtração de dois desses pontos resulta em um vetor - o vetor descreve a distância e em que direção viajar de um dos operandos da fonte para o outro.

Isto aplica-se ao armazenamento, como vectores stl ou Vectores Java, no qual o armazenamento é representado como uma distância de um endereço (onde um endereço de memória é semelhante a um ponto no espaço, ou em uma linha de números).

O conceito está relacionado com arrays, porque arrays podem ser o armazenamento alocado para um vetor, mas eu submeto que o vetor é um conceito maior do que o array. Um vetor deve incluir o conceito de distância de um ponto de partida, e se você pensar no início de um array como o ponto de partida, a distância ao fim do array é o seu tamanho.

Assim, a estrutura de dados que representa um vector deve incluir o tamanho, enquanto que uma matriz não tem armazenamento para incluir o tamanho, é assumido pela forma como é alocado. Isto é, se você dinamicamente alocar um array, não há estrutura de dados armazenando o tamanho desse array, o programador deve assumir saber esse tamanho, ou armazená-lo em um número inteiro ou longo.

A estrutura de dados vetoriais (digamos, o design de uma classe vetorial) precisa armazenar o tamanho, então no mínimo, haveria um ponto de partida (a base de uma matriz, ou algum endereço na memória) e uma distância a partir desse ponto indicando o tamanho.

Isso é realmente" RAM " orientado, embora, na descrição, porque há mais um ponto ainda não descrito que deve ser parte dos dados que descrevem o vetor - a noção de tamanho do elemento. Se um vetor representa bytes, e o armazenamento de memória é normalmente medido em bytes, um endereço e uma distância (ou tamanho) representariam um vetor de bytes, mas nada mais - e isso é um pensamento de nível de máquina. Um pensamento superior, o de alguma estrutura, tem o seu próprio tamanho-digamos, o tamanho de um flutuador ou duplo, ou de uma estrutura ou classe em C++. Qualquer que seja o tamanho do elemento, a memória necessária para armazenar N deles requer que a estrutura de dados vetoriais tenha algum conhecimento do que está armazenando, e quão grande essa coisa é. É por isso que você pensaria em termos de "um vetor de strings" ou "um vetor de pontos". Um vetor também deve armazenar um tamanho de elemento.

Então, uma estrutura básica de dados vetoriais deve ter:

Um endereço (Ponto de partida)

Tamanho do elemento (cada coisa que armazena é X bytes de comprimento)

Um número de elementos armazenados (quantos elementos vezes o tamanho do elemento é o tamanho mínimo de armazenamento).

Uma importante "suposição" feita nesta simples lista de 3 itens na estrutura de dados vetoriais é que o endereço é memória alocada, que deve ser liberado em algum ponto, e deve ser guardado contra o acesso além do fim do vetor.

Isso significa que falta alguma coisa. A fim de fazer um trabalho de classe vetorial, há uma diferença reconhecível entre o número de itens armazenados no vetor, e a quantidade de memória alocada para esse armazenamento. Tipicamente, como você pode perceber a partir do uso do vetor a partir do STL, ele pode "saber" que tem espaço para armazenar 10 itens, mas atualmente apenas tem 2 deles. Então, uma classe de vetores de trabalho também teria que armazenar a quantidade de alocação de memória. Seria assim que ele poderia se estender dinamicamente - ele agora teria informações suficientes para expandir o armazenamento automaticamente.

Pensar em como você faria uma classe vetorial operar dá - Lhe a estrutura de dados necessários para operar uma classe vetorial.

É um array com espaço dinamicamente alocado, toda vez que você exceder este espaço novo lugar na memória é alocado e antiga array é copiado para o novo. Então o velho está livre.

Além disso, o vetor geralmente aloca mais memória do que precisa, de modo que não tem que copiar todos os dados, quando novo elemento é adicionado.

Pode parecer que as listas são muito melhores, mas não é necessariamente assim. Se você não mudar seu vetor frequentemente (em termos de tamanho), então a memória de cache do computador funciona muito melhor com vetores, do que listas, porque eles são continuus no espaço de memória. Desvantagem é quando você tem um vetor grande, que você precisa expandir. Então você tem que concordar em copiar grande quantidade de dados para outro espaço na memória. Além disso. Você pode adicionar novos dados para o final e para a frente do vetor. Porque vetoriais são array-like, então toda vez que você quer adicionar elemento ao início do vetor todos os array têm que ser copiados. Alar elementos para o fim do vetor é muito mais eficiente. Não existe tal problema com listas ligadas.

O Vector dá acesso aleatório aos seus dados internos mantidos, enquanto as listas,filas,pilhas não dão.