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

Ответ 1

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

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

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

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

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

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

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

Это действительно "ОЗУ", ориентированное, однако, в описании, потому что еще нет еще одной точки, которая должна быть частью данных, описывающих вектор, - понятие размера элемента. Если вектор представляет байты, а память обычно измеряется в байтах, адрес и расстояние (или размер) будут представлять собой вектор байтов, но ничего другого - и это очень машинный уровень мышления. Высшая мысль, какая-то структура, имеет собственный размер - скажем, размер поплавка или двойника, или структуры или класса в С++. Независимо от размера элемента, память, необходимая для хранения N из них, требует, чтобы структура векторных данных обладала некоторыми знаниями о том, что она хранит, и насколько велика эта вещь. Вот почему вы думаете в терминах "вектора строк" ​​или "вектора точек". Вектор также должен хранить размер элемента.

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

Адрес (начальная точка)

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

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

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

Это означает, что чего-то не хватает. Чтобы сделать работу векторного класса, существует заметная разница между количеством ITEMS, хранящимся в векторе, и количеством памяти, РАСПРОСТРАНЕННЫМ для этого хранилища. Как правило, как вы можете понять из использования вектора из STL, он может "знать", что у него есть место для хранения 10 элементов, но в настоящее время только 2 из них.

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

Размышляя о том, как вы создадите операцию векторного класса, вы получите структуру данных, необходимых для управления векторным классом.

Ответ 2

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

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

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

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

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