Question Qu'est-ce que la structure de données vectorielles?


Je connais le vecteur en C ++ et Java, c'est comme le tableau dynamique, mais je ne trouve aucune définition générale de la structure des données vectorielles. Alors, qu'est ce que Vector? Est-ce que Vector est une structure de données générale (comme arrray, stack, queue, tree, ...) ou simplement un type de données en fonction de la langue?


11
2017-09-12 16:38


origine


Réponses:


Le mot "vecteur" appliqué à l'informatique / à la programmation est emprunté aux mathématiques, ce qui peut rendre l'utilisation confuse (même votre question pourrait concerner plusieurs sujets).

L'exemple le plus simple de vecteurs en mathématiques est la droite numérique utilisée pour enseigner les mathématiques élémentaires (en particulier pour aider à visualiser les nombres négatifs, la soustraction de nombres négatifs, l'addition de nombres négatifs, etc.).

Le vecteur est une distance et une direction à partir d'un point. C'est pourquoi il peut confondre la discussion, car une structure de données vectorielles POURRAIT être trois points, X, Y, Z, dans une structure utilisée dans les moteurs graphiques 3D, ou un point 2D (juste X, Y). Dans ce contexte, la soustraction de deux de ces points aboutit à un vecteur - le vecteur décrit à quelle distance et dans quelle direction il faut se déplacer d’un opérande source à l’autre.

Cela s'applique au stockage, comme les vecteurs stl ou les vecteurs Java, dans lequel le stockage est représenté comme une distance par rapport à une adresse (où une adresse mémoire est similaire à un point dans l'espace ou sur une ligne numérique).

Le concept est lié aux tableaux, car les tableaux peuvent être le stockage alloué à un vecteur, mais je pense que le vecteur est un concept plus grand que le tableau. Un vecteur doit inclure le concept de distance à partir d'un point de départ, et si vous considérez le début d'un tableau comme le point de départ, la distance à la fin du tableau correspond à sa taille.

Ainsi, la structure de données représentant un vecteur doit inclure la taille, tandis qu'un tableau n'a pas de stockage pour inclure la taille, il est supposé par la manière dont il est alloué. C'est-à-dire que si vous allouez dynamiquement un tableau, il n'y a pas de structure de données stockant la taille de ce tableau, le programmeur doit supposer avoir cette taille, ou la stocker dans un certain nombre d'entiers ou long.

La structure de données vectorielles (par exemple, la conception d'une classe de vecteur) DOIT stocker la taille, il y aurait donc au minimum un point de départ (la base d'un tableau ou une adresse en mémoire) et une distance par rapport à celle-ci. point indiquant la taille.

C'est vraiment "RAM" orienté, cependant, dans la description, car il y a encore un point non encore décrit qui doit faire partie des données décrivant le vecteur - la notion de taille de l'élément. Si un vecteur représente des octets et que le stockage en mémoire est généralement mesuré en octets, une adresse et une distance (ou une taille) représenteraient un vecteur d'octets, mais rien d'autre. Une pensée supérieure, celle d'une structure, a sa propre taille - disons la taille d'un float ou d'un double, ou d'une structure ou d'une classe en C ++. Quelle que soit la taille de l'élément, la mémoire nécessaire pour stocker N d'entre elles nécessite que la structure de données vectorielles ait une connaissance de ce qu'elle stocke et de sa taille. C'est pourquoi vous pensez en termes de "vecteur de chaînes" ou "vecteur de points". Un vecteur doit également stocker une taille d'élément.

Ainsi, une structure de données vectorielles de base doit avoir:

Une adresse (le point de départ)

Une taille d'élément (chaque objet stocké est long de X octets)

Un nombre d'éléments stockés (combien d'éléments fois la taille de l'élément est la taille de stockage 'minimum').

Une "hypothèse" importante faite dans cette liste simple de 3 éléments d'entrées dans la structure de données vectorielles est que l'adresse est affectée à la mémoire, qui doit être libérée à un moment donné, et doit être protégée au-delà de la fin du vecteur.

Cela signifie qu'il manque quelque chose. Pour faire fonctionner une classe de vecteur, il existe une différence reconnaissable entre le nombre d'ITEMS stockés dans le vecteur et la quantité de mémoire allouée pour ce stockage. Typiquement, comme vous pouvez vous en rendre compte avec l'utilisation du vecteur de la STL, il peut "savoir" qu'il peut stocker 10 éléments, mais n'en a actuellement que 2.

Ainsi, une classe de vecteur de travail devrait également stocker la quantité d'allocation de mémoire. Il s’agirait de la manière dont il pourrait s’étendre de manière dynamique - il aurait désormais suffisamment d’informations pour étendre automatiquement le stockage.

En réfléchissant à la manière dont vous voulez faire fonctionner une classe de vecteurs, vous obtenez la structure des données requises pour faire fonctionner une classe de vecteurs.


13
2017-09-12 18:18



C'est un tableau avec un espace alloué dynamiquement, chaque fois que vous dépassez cet espace, un nouvel emplacement en mémoire est alloué et l'ancien tableau est copié sur le nouveau. L'ancien est libéré alors.

De plus, vector alloue généralement plus de mémoire qu'il n'est nécessaire, de sorte qu'il n'est pas nécessaire de copier toutes les données, lorsqu'un nouvel élément est ajouté.

Il peut sembler que les listes sont beaucoup mieux, mais ce n’est pas nécessairement le cas. Si vous ne changez pas souvent votre vecteur (en termes de taille), la mémoire cache de l'ordinateur fonctionne beaucoup mieux avec les vecteurs, qu'avec les listes, car elles sont continues dans l'espace mémoire. Le désavantage est que lorsque vous avez un grand vecteur, que vous devez développer. Ensuite, vous devez accepter de copier une grande quantité de données dans un autre espace en mémoire.

Quoi de plus. Vous pouvez ajouter de nouvelles données à la fin et au début du vecteur. Comme les vecteurs sont de type tableau, chaque fois que vous voulez ajouter un élément au début du vecteur, tout le tableau doit être copié. L'ajout d'éléments à la fin du vecteur est beaucoup plus efficace. Il n'y a pas un tel problème avec les listes liées.

Vector donne un accès aléatoire à ses données internes conservées, contrairement aux listes, aux files d'attente et aux piles.


4
2017-09-12 16:45