Что такое векторная структура данных

Слово «вектор» применительно к информатике/программированию заимствовано из математики, что может запутать его использование (даже ваш вопрос может относиться к нескольким предметам).

Простейшим примером векторов в математике является числовая линия, используемая для обучения элементарной математике (особенно для визуализации отрицательных чисел, вычитания отрицательных чисел, сложения отрицательных чисел и т. д.).

Вектор - это расстояние и направление от точки. Вот почему это может запутать обсуждение, потому что структура векторных данных МОЖЕТ быть тремя точками, X, Y, Z, в структуре, используемой в 3D-графических движках, или 2D-точкой (только X, Y). В этом контексте вычитание двух таких точек приводит к вектору - вектор описывает, как далеко и в каком направлении нужно пройти от одного из исходных операндов к другому.

Это относится к хранилищу, такому как векторы stl или векторы Java, в котором хранилище представлено как расстояние от адреса (где адрес памяти подобен точке в пространстве или на числовой прямой).

Эта концепция связана с массивами, потому что массивы могут быть хранилищем, выделенным для вектора, но я утверждаю, что вектор — это более широкое понятие, чем массив. Вектор должен включать понятие расстояния от начальной точки, и если вы думаете о начале массива как о начальной точке, расстояние до конца массива — это его размер.

Таким образом, структура данных, представляющая вектор, должна включать размер, в то время как у массива нет памяти для включения размера, это предполагается способом его распределения. То есть, если вы динамически выделяете массив, нет структуры данных, хранящей размер этого массива, программист должен предположить, что знает этот размер, или сохранить его в каком-то целом или длинном.

Структура векторных данных (скажем, дизайн векторного класса) ДОЛЖНА хранить размер, поэтому, как минимум, будет начальная точка (база массива или некоторый адрес в памяти) и расстояние от этого точка, указывающая размер.

Однако в описании это действительно ориентировано на «ОЗУ», потому что есть еще один не описанный момент, который должен быть частью данных, описывающих вектор, - понятие размера элемента. Если вектор представляет байты, а объем памяти обычно измеряется в байтах, то адрес и расстояние (или размер) будут представлять собой вектор байтов, но ничего больше — и это очень машинный уровень мышления. Высшая мысль, мысль какой-то структуры, имеет свой размер — скажем, размер float или double, или структуры или класса в C++. Каким бы ни был размер элемента, память, необходимая для хранения N из них, требует, чтобы структура векторных данных имела некоторое представление о том, ЧТО она хранит и насколько она велика. Вот почему вы думаете о «векторе строк» ​​или «векторе точек». Вектор также должен хранить размер элемента.

Итак, базовая структура векторных данных должна иметь:

Адрес (отправная точка)

Размер элемента (каждая вещь, которую он хранит, имеет длину X байтов)

Количество сохраненных элементов (сколько элементов, умноженное на размер элемента, является «минимальным» размером хранилища).

Одно важное «предположение», сделанное в этом простом списке из трех элементов в структуре векторных данных, заключается в том, что адрес представляет собой выделенную память, которая должна быть освобождена в какой-то момент и должна быть защищена от доступа за пределами конца вектора.

Значит чего-то не хватает. Чтобы векторный класс работал, существует распознаваемая разница между количеством ПУНКТОВ, хранящихся в векторе, и объемом памяти, ВЫДЕЛЕННОЙ для этого хранилища. Как правило, как вы могли понять из использования вектора из STL, он может «знать», что у него есть место для хранения 10 элементов, но в настоящее время их только 2.

Таким образом, рабочий векторный класс ТАКЖЕ должен хранить объем выделенной памяти. Таким образом он мог бы динамически расширяться — теперь у него было бы достаточно информации для автоматического расширения хранилища.

Продумывая, как заставить работать векторный класс, вы получите структуру данных, необходимую для работы с векторным классом.

Это массив с динамически выделяемым пространством, каждый раз, когда вы превышаете это пространство, выделяется новое место в памяти, а старый массив копируется в новый. Тогда старый освобождается.

Кроме того, вектор обычно выделяет больше памяти, чем нужно, поэтому ему не нужно копировать все данные при добавлении нового элемента.

Может показаться, что списки тогда намного лучше, но это не обязательно так. Если вы не меняете свой вектор часто (с точки зрения размера), то кэш-память компьютера работает с векторами намного лучше, чем со списками, потому что они непрерывны в пространстве памяти. Недостатком является то, что у вас большой вектор, который вам нужно расширить. Затем вы должны согласиться скопировать большой объем данных в другое место в памяти.

Более того. Вы можете добавить новые данные в конец и в начало вектора. Поскольку векторы похожи на массивы, каждый раз, когда вы хотите добавить элемент в начало вектора, весь массив должен быть скопирован. Добавление элементов в конец вектора гораздо эффективнее. Со связанными списками такой проблемы нет.

Вектор предоставляет произвольный доступ к своим внутренним данным, а списки, очереди и стеки — нет.

1. Векторы аналогичны динамическим массивам с возможностью автоматического изменения размера при вставке или удалении элемента.

2. Векторные элементы размещаются в непрерывной памяти, чтобы к ним можно было обращаться и перемещаться с помощью итераторов.

3. В векторах данные вставляются в конце.