Vector
Реализация одной из разновидностей динамического типа данных.
В С++ его
нарекли Vector . По сути напоминает динамическй массив с небольшими , но надо
сказать удобными плюшками, например присвоение одного вектора другому,
обмен значениями , начальная инициализация значениями, вставка элемента или
диапазона элементов в любое место, удаление любого элемента или диапазона
элементов, и при этом сохраняется быстрота доступа к элементам как у массива.
Вектор автоматически регулирует свою внутреннюю размерность, выделяя память с
небольшим запасом. Создать полную функциональность std::vector крайне
сложно из-за фундаментальных различий в синтаксисе языков.
Внимание: вектор не выделяет память для динамических типов данных (например строк или пользовательских типов ) , все это ложится на плечи программиста!!! Именно поэтому для строк надо выделять память отдельно , а в vector отправлять указатель на строку.
Использование:
Объявить макрос T_VECTOR_... с именем и типом нового вектора. Макрос может иметь до 5 параметров:
T_VECTOR_0 (имя вектора, имя типа для макроса, реальное имя типа)
T_VECTOR_1 (имя вектора, имя типа для макроса, реальное имя типа , размер)
T_VECTOR_2 (имя вектора, имя типа для макроса, реальное имя типа , размер , данные)
имя вектора - по сути это будет указатель на
вектор
имя типа для макроса - идентифицируещее
имя для данного вектора , может быть такое же как реальное имя типа , но не
может иметь пробелов. Именно из-за таких типов, как например long ptr , byte ptr ptr , пришлось
вводить в конструкцию макроса третий параметр.
реальное имя типа - здесь указывается тип вектора , как он есть
размер - начальный размер вектора (память для ячеек выделяется при создании)
данные - начальные данные, которыми будут заполнены ячейки вектора при создании
Пример создания макросов:
T_VECTOR_0 (pS , String , String Ptr) ' создать нулевой вектор с типом "STRING PTR" T_VECTOR_1 (pF , Single , Single , 10) ' создать вектор с типом "SINGLE" на 10 ячеек T_VECTOR_2 (pB , Byte , Byte , 20 , 32) ' создать вектор с типом "BYTE" на 20 ячеек и присвоить ячейкам символ пробела
Функции, используемые с вектором:
- size - Возвращает количество элементов в векторе
- back - Доступ к последнему элементу (только чтение)
- front - Доступ к первому элементу (только чтение)
- empty - Возвращает true, если вектор пуст
- capacity - Возвращает количество элементов, которое может содержать вектор до того, как ему потребуется выделить больше места.
- clear - Удаляет все элементы вектора
- insert - Вставка отдельного элемента в вектор, или элементов из массива, или диапазона элементов массива (перегруженная функция)
- erase - Удаляет указанный элемент или диапазон элементов вектора (перегруженная функция)
- push_back - Вставка элемента в конец вектора
- pop_back - Удалить последний элемент вектора, возвращает значение удаляемого элемента перед удалением
- resize - Изменяет размер вектора на заданную величину (перегруженная функция)
- assign - Заменяет содержимое контейнера вектора , может заменять значения в диапазоне (перегруженная функция)
- swapV - Обменивает значения векторов
- shrink_to_fit - Уменьшает количество используемой памяти за счёт освобождения неиспользованной
- at - Доступ к ячейкам с проверкой диапазона
- [] - Доступ к ячейкам без проверки диапазона
Сама реализация вектора:
#MACRO T_VECTOR_INT (vector_ptr , vector_type , vector_realname_type) #IFNDEF tVectorType##vector_type Type tVectorType##vector_type As vector_realname_type #ENDIF #IFNDEF VECTOR##vector_type Type VECTOR##vector_type vData As tVectorType##vector_type Ptr iSize As Long iRealMemSize As Long Declare Constructor() Declare Constructor ( Byref rhs As VECTOR##vector_type) Declare Constructor(iSize As Long) Declare Constructor(iSize As Long , vData As tVectorType##vector_type) Declare Destructor() Declare Function size() As Long ' Возвращает количество элементов в векторе Declare Function back() As tVectorType##vector_type ' Доступ к последнему элементу Declare Function front() As tVectorType##vector_type ' Доступ к первому элементу Declare Function empty() As BOOLEAN ' Возвращает true, если вектор пуст Declare Function capacity() As Long ' Возвращает количество элементов, которое может содержать вектор до того, как ему потребуется выделить больше места. Declare Function Clear() As BOOLEAN ' Удаляет все элементы вектора Declare Function insert Overload(iPos As Long , vData As tVectorType##vector_type) As BOOLEAN ' Вставка элементов в вектор перед iPos Declare Function insert Overload(iPos As Long , vData() As tVectorType##vector_type) As BOOLEAN ' Вставка элементов в вектор перед iPos из массива Declare Function insert Overload(iPos As Long , vData() As tVectorType##vector_type , iStartPos As Long, iEndPos As Long) As BOOLEAN ' Вставка элементов из массива c диапазоном в вектор перед iPos Declare Function Erase Overload(iPos As Long) As BOOLEAN ' Удаляет указанный элемент вектора Declare Function Erase Overload(iStartPos As Long , iEndPos As Long) As BOOLEAN ' Удаляет диапазон указанных элементов вектора Declare Function push_back(vData As tVectorType##vector_type) As BOOLEAN ' Вставка элемента в конец вектора Declare Function pop_back() As tVectorType##vector_type ' Удалить последний элемент вектора Declare Function resize Overload(iCount As Long ) As BOOLEAN ' Изменяет размер вектора на заданную величину Declare Function resize Overload(iCount As Long , vData As tVectorType##vector_type) As BOOLEAN ' Изменяет размер вектора на заданную величину Declare Function assign Overload(iCount As Long , vData As tVectorType##vector_type) As BOOLEAN ' Заменяет содержимое контейнера вектора Declare Function assign Overload(iStartPos As Long , iEndPos As Long , vData As tVectorType##vector_type) As BOOLEAN ' Заменяет содержимое контейнера вектора в диапазоне Declare Function swapV(v As VECTOR##vector_type) As BOOLEAN ' Обменивает значения векторов Declare Function shrink_to_fit() As BOOLEAN ' Уменьшает количество используемой памяти за счёт освобождения неиспользованной Declare Property at(iIndex As Long) As tVectorType##vector_type ' доступ к ячейкам с проверкой диапазона (получение) Declare Property at(iIndex As Long , vData As tVectorType##vector_type) ' доступ к ячейкам с проверкой диапазона (установка) Declare Function realloc() As BOOLEAN ' перераспределение памяти Declare Operator [] (Byref iIndex As Long) Byref As tVectorType##vector_type ' обычный доступ к ячейкам Declare Operator Let (Byref v2 As VECTOR##vector_type) ' копирование одного вектора в другой Declare Operator Let (Byref v As tVectorType##vector_type) ' присваивание значения в вектор End Type Constructor VECTOR##vector_type() this.iSize = 0 this.iRealMemSize = 0 End Constructor Constructor VECTOR##vector_type(iSize As Long) this.vData = Callocate(iSize , Sizeof(tVectorType##vector_type)) If this.vData Then this.iSize = iSize this.iRealMemSize = iSize Endif End Constructor Constructor VECTOR##vector_type(iSize As Long , vData As tVectorType##vector_type) this.vData = Callocate(iSize , Sizeof(tVectorType##vector_type)) If this.vData Then this.iSize = iSize this.iRealMemSize = iSize For i As Long = 0 To iSize-1 (this.vData)[i] = vData Next Endif End Constructor Destructor VECTOR##vector_type() If this.vData Then Deallocate(this.vData) this.vData = 0 this.iSize = 0 this.iRealMemSize = 0 End Destructor ' Возвращает количество элементов в векторе Function VECTOR##vector_type.size() As Long Return iSize End Function ' Доступ к последнему элементу Function VECTOR##vector_type.back() As tVectorType##vector_type If this.vData andalso this.iSize Then Return (this.vData)[this.iSize-1] Endif End Function ' Доступ к первому элементу Function VECTOR##vector_type.front() As tVectorType##vector_type If this.vData andalso this.iSize Then Return (this.vData)[0] Endif End Function ' Возвращает true, если вектор пуст Function VECTOR##vector_type.empty() As BOOLEAN If this.vData andalso this.iSize Then Return FALSE Else Return TRUE Endif End Function ' Возвращает количество элементов, которое может содержать вектор до того, как ему потребуется выделить больше места. Function VECTOR##vector_type.capacity() As Long Return this.iRealMemSize End Function ' Удаляет все элементы вектора Function VECTOR##vector_type.clear() As BOOLEAN If this.vData andalso this.iSize Then Deallocate(this.vData) this.vData = 0 this.iSize = 0 this.iRealMemSize = 0 Return true Else Return false Endif End Function ' Вставка элементов в вектор перед iPos Function VECTOR##vector_type.insert Overload(iPos As Long , vData As tVectorType##vector_type) As BOOLEAN If iPos >=0 Then If this.iSize >= this.iRealMemSize Then this.iRealMemSize += 10 this.vData = Reallocate(this.vData , (this.iRealMemSize)* Sizeof(tVectorType##vector_type)) If this.vData = 0 Then Return FALSE Endif Endif If iPos >= iSize Then (this.vData)[iSize] = vData Else For i As Long = iSize To 0 Step -1 If i > iPos Then (this.vData)[i] = (this.vData)[i-1] Else (this.vData)[i] = vData Exit For Endif Next Endif iSize +=1 Return TRUE Else Return FALSE Endif End Function ' Вставка элементов из массива в вектор перед iPos Function VECTOR##vector_type.insert Overload(iPos As Long , vData() As tVectorType##vector_type) As BOOLEAN If iPos >=0 Then If this.iSize + Ubound(vData) >= this.iRealMemSize Then this.iRealMemSize = this.iSize + Ubound(vData) + 10 this.vData = Reallocate(this.vData , (this.iRealMemSize)* Sizeof(tVectorType##vector_type)) If this.vData = 0 Then Return FALSE Endif Endif If iPos >= iSize Then For i As Long = iSize To iSize + Ubound(vData) (this.vData)[i] = vData(i-iSize) Next Else Dim As Long iIndex = Ubound(vData) For i As Long = iSize+ubound(vData) To 0 Step -1 If i > iPos+ubound(vData) Then (this.vData)[i] = (this.vData)[i-ubound(vData)-1] Else (this.vData)[i] = vData(iIndex) iIndex-=1 If iIndex < 0 Then Exit For Endif Next Endif iSize += Ubound(vData)+1 Return TRUE Else Return FALSE Endif End Function ' Вставка элементов из массива c диапазоном в вектор перед iPos Function VECTOR##vector_type.insert Overload(iPos As Long , vData() As tVectorType##vector_type , iStartPos As Long, iEndPos As Long) As BOOLEAN If iPos >=0 andalso iStartPos>=0 andalso iEndPos >= iStartPos Then Dim As Long iEndMinusStart = (iEndPos - iStartPos) If this.iSize + iEndMinusStart >= this.iRealMemSize Then this.iRealMemSize = this.iSize + iEndMinusStart + 10 this.vData = Reallocate(this.vData , (this.iRealMemSize)* Sizeof(tVectorType##vector_type)) If this.vData = 0 Then Return FALSE Endif Endif If iPos >= iSize Then For i As Long = iSize To iSize + iEndMinusStart (this.vData)[i] = vData(i - iSize + iStartPos) Next Else Dim As Long iIndex = iEndPos For i As Long = iSize+iEndMinusStart To 0 Step -1 If i > iPos+iEndMinusStart Then (this.vData)[i] = (this.vData)[i-iEndMinusStart-1] Else (this.vData)[i] = vData(iIndex) iIndex-=1 If iIndex < iStartPos Then Exit For Endif Next Endif iSize += iEndMinusStart+1 Return TRUE Else Return FALSE Endif End Function ' Удаляет указанный элемент вектора Function VECTOR##vector_type.erase Overload(iPos As Long) As BOOLEAN If this.vData andalso this.iSize _ andalso iPos >=0 andalso iPos < iSize Then If iPos = iSize-1 Then (this.vData)[iSize-1] = 0 Else For i As Long = 0 To iSize-2 If i >= iPos Then (this.vData)[i] = (this.vData)[i+1] Endif Next Endif this.iSize -=1 Return this.realloc() Else Return false Endif End Function ' Удаляет диапазон указанных элементов вектора Function VECTOR##vector_type.erase Overload(iStartPos As Long , iEndPos As Long) As BOOLEAN If iStartPos = iEndPos Then Return Erase(iStartPos) Endif If this.vData andalso this.iSize _ andalso iStartPos < iEndPos _ andalso iStartPos >= 0 andalso iEndPos < this.iSize Then If iEndPos = iSize-1 Then For i As Long = iStartPos To iEndPos (this.vData)[i] = 0 Next Else Dim As Long iStartIndex = iStartPos For i As Long = 0 To iSize-2 If i >= iEndPos Then (this.vData)[iStartIndex] = (this.vData)[i+1] iStartIndex+=1 Endif Next Endif this.iSize = this.iSize - (iEndPos - iStartPos + 1) Return this.realloc() Else Return false Endif End Function ' Вставка элемента в конец вектора Function VECTOR##vector_type.push_back(vData As tVectorType##vector_type) As BOOLEAN If this.iSize >= this.iRealMemSize Then this.iRealMemSize += 10 this.vData = Reallocate(this.vData , (this.iRealMemSize)* Sizeof(tVectorType##vector_type)) If this.vData = 0 Then Return FALSE Endif Endif (this.vData)[iSize] = vData iSize +=1 Return TRUE End Function ' Удалить последний элемент вектора Function VECTOR##vector_type.pop_back() As tVectorType##vector_type If this.vData andalso this.iSize Then this.iSize -=1 Function = (this.vData)[this.iSize] (this.vData)[this.iSize] = 0 this.realloc() Endif End Function ' Изменяет размер вектора на заданную величину Function VECTOR##vector_type.resize Overload(iCount As Long ) As BOOLEAN If this.iSize > iCount Then this.iSize = iCount Return this.realloc() Elseif this.iSize < iCount Then If iCount >= this.iRealMemSize Then this.iRealMemSize = iCount + 10 this.vData = Reallocate(this.vData , (this.iRealMemSize)* Sizeof(tVectorType##vector_type)) If this.vData = 0 Then Return FALSE Endif this.iSize = iCount Return TRUE Else Return FALSE Endif End Function ' Изменяет размер вектора на заданную величину Function VECTOR##vector_type.resize Overload(iCount As Long , vData As tVectorType##vector_type) As BOOLEAN If this.iSize > iCount Then this.iSize = iCount Return this.realloc() Elseif this.iSize < iCount Then If iCount >= this.iRealMemSize Then this.iRealMemSize = iCount + 10 this.vData = Reallocate(this.vData , (this.iRealMemSize)* Sizeof(tVectorType##vector_type)) If this.vData = 0 Then Return FALSE Endif Dim As Long iOld = this.iSize this.iSize = iCount For i As Long = iOld To iCount - 1 (this.vData)[i] = vData Next Return TRUE Else Return FALSE Endif End Function ' Заменяет содержимое контейнера вектора Function VECTOR##vector_type.assign Overload(iCount As Long , vData As tVectorType##vector_type) As BOOLEAN If this.iSize < iCount andalso iCount >= this.iRealMemSize Then this.iRealMemSize = iCount + 10 this.vData = Reallocate(this.vData , (this.iRealMemSize)* Sizeof(tVectorType##vector_type)) If this.vData = 0 Then Return FALSE this.iSize = iCount Endif For i As Long = 0 To iCount - 1 (this.vData)[i] = vData Next Return TRUE End Function ' Заменяет содержимое контейнера вектора в диапазоне Function VECTOR##vector_type.assign Overload(iStartPos As Long , iEndPos As Long , vData As tVectorType##vector_type) As BOOLEAN If iStartPos >= 0 Then If this.iSize <= iEndPos andalso iEndPos > 0 andalso (iEndPos-1) >= this.iRealMemSize Then this.iRealMemSize = iEndPos + 10 this.vData = Reallocate(this.vData , (this.iRealMemSize)* Sizeof(tVectorType##vector_type)) If this.vData = 0 Then Return FALSE this.iSize = iEndPos + 1 Endif For i As Long = iStartPos To iEndPos (this.vData)[i] = vData Next Return TRUE Else Return FALSE Endif End Function ' Обменивает значения векторов Function VECTOR##vector_type.swapV(v As VECTOR##vector_type) As BOOLEAN If this.vData andalso v.vData andalso _ this.iSize andalso v.iSize andalso _ this.iRealMemSize andalso v.iRealMemSize Then Dim As tVectorType##vector_type Ptr pTemp = this.vData this.vData = v.vData v.vData = pTemp Dim As Long iTemp = this.iSize this.iSize = v.iSize v.iSize = iTemp iTemp = this.iRealMemSize this.iRealMemSize = v.iRealMemSize v.iRealMemSize = iTemp Return true Else Return False Endif End Function ' Уменьшает количество используемой памяти за счёт освобождения неиспользованной Function VECTOR##vector_type.shrink_to_fit() As BOOLEAN If this.vData Then If this.iSize < this.iRealMemSize Then this.vData = Reallocate(this.vData , (this.iSize) * Sizeof(tVectorType##vector_type)) If this.vData Then this.iRealMemSize = this.iSize Return true Else Return false Endif Endif Else Return false Endif End Function ' доступ к ячейкам с проверкой диапазона (получение) Property VECTOR##vector_type.at(iIndex As Long) As tVectorType##vector_type If iIndex < 0 orelse iIndex > this.iSize-1 Then Print "out of range!" Else Return (this.vData)[iIndex] Endif End Property ' доступ к ячейкам с проверкой диапазона (установка) Property VECTOR##vector_type.at(iIndex As Long , vData As tVectorType##vector_type) If iIndex < 0 orelse iIndex > this.iSize-1 Then Print "out of range!" Else (this.vData)[iIndex] = vData Endif End Property ' перераспределение памяти Function VECTOR##vector_type.realloc() As BOOLEAN If this.iSize+20 < this.iRealMemSize Then this.iRealMemSize = this.iSize + 10 this.vData = Reallocate(this.vData , (this.iRealMemSize)* Sizeof(tVectorType##vector_type)) If this.vData Then Return TRUE Else Return FALSE Endif Endif End Function ' обычный доступ к ячейкам Operator VECTOR##vector_type.[] (Byref iIndex As Long) Byref As tVectorType##vector_type Return (this.vData)[iIndex] End Operator ' копирование одного вектора в другой Operator VECTOR##vector_type.let (Byref v2 As VECTOR##vector_type) If v2.vData andalso v2.iRealMemSize Then If this.vData Then Deallocate(this.vData) Endif this.vData = Callocate(v2.iRealMemSize , Sizeof(tVectorType##vector_type) ) If this.vData Then this.iRealMemSize = v2.iRealMemSize this.iSize = v2.iSize For i As Long = 0 To v2.iSize -1 this.vData[i] = v2.vData[i] Next Endif Endif End Operator ' проверка на равенство Operator = ( v1 As VECTOR##vector_type , v2 As VECTOR##vector_type) As BOOLEAN If v1.vData andalso v2.vData _ andalso v1.iSize = v2.iSize Then If v1.iSize Then For i As Long = 0 To v1.iSize-1 If (v1.vData)[i] <> (v2.vData)[i] Then Return False Endif Next Endif Return TRUE Else Return FALSE Endif End Operator #ENDIF #endmacro #MACRO T_VECTOR_0 (vector_ptr , vector_type , vector_realname_type ) T_VECTOR_INT (vector_ptr , vector_type , vector_realname_type) Dim As VECTOR##vector_type Ptr vector_ptr = New VECTOR##vector_type #EndMacro #MACRO T_VECTOR_1 (vector_ptr , vector_type , vector_realname_type , size ) T_VECTOR_INT (vector_ptr , vector_type , vector_realname_type ) Dim As VECTOR##vector_type Ptr vector_ptr = New VECTOR##vector_type (size) #EndMacro #MACRO T_VECTOR_2 (vector_ptr , vector_type , vector_realname_type , size , filldata) T_VECTOR_INT (vector_ptr , vector_type , vector_realname_type ) Dim As VECTOR##vector_type Ptr vector_ptr = New VECTOR##vector_type (size , filldata) #EndMacro
А это пример работы всех его функций (вроде ничего не забыл):
T_VECTOR_1 (pB , Byte , Byte , 20) T_VECTOR_0 (pB2 , Byte , Byte) ' создадим еще один вектор (пустой) ' передаем вектор в процедуру , обратите внимание на имя типа , 'оно складывается из слов VECTOR и второго параметра макроса Sub printVector(p As VECTORbyte , sRem As String = "") ' выводим значения ? "Output " & sRem & ":" For i As Long = 0 To p.size - 1 ? "index " & i & "=" ,p[i] Next End Sub ' Давайте создадим сразу символические ссылки , чтобы использование векторов было максимально удобно: Dim Byref V1 As VECTORbyte = *pB Dim Byref V2 As VECTORbyte = *pB2 If V1.empty Then ? "Vector empty!" Else ? "Vector not empty, count = " ; V1.size Endif ? ? "pushback x2" ? ' добавляем 2 ячейки в конец вектора и того станет 22 V1.push_back(10) V1.push_back(20) ' выводим значения printVector(V1, "V1") ? ' выводим значения из 1 и последней ячейки ? "first=" ; V1.front ? "last=" ; V1.back ' показываем размерность и реальную вместимость на данный момент ? "size="; V1.size, "capacity" ; V1.capacity ? ' уджаляем последнюю ячейку ? "Delete last element" V1.pop_back ? ' выводим значения с использованием функции "at" ? "Output V1 using AT:" For i As Long = 0 To V1.size - 1 ? V1.at(i) Next ? ' вставка одного элемента в начало и одного элемента на 5 позицию ? "Insert" V1.insert(0, 66) V1.insert(5, 55) 'вставка всех элементов из массива на 11 позицию Dim As Byte b(8) = {1,2,3,4,5,6,7,8,9} V1.insert(11, b()) 'вставка 3 элементов из массива в диапазоне (4-6) на 23 позицию , то есть будут вставлены числа 5 ,6 ,7 V1.insert(23, b() , 4,6) ? printVector(V1, "V1") ? ? "ERASE" ' удалить 1 элемент V1.erase(0) ' удалить все ячейки в диапазоне от 20 до последней V1.erase(20 ,V1.size-1) ? printVector(V1, "V1") ? ' присвоим один вектор другому (если помните, V2 был пустой) ' значения V2 и V1 выведем в конце примера ? "let V2 = V1" V2 = V1 ? ? "clear vector" ' очистить весь вектор V1.clear ? ' показываем размерность и реальную вместимость на данный момент ? "size="; V1.size, "capacity" ; V1.capacity ? ? "resize vector" ' изменяем размер вектора , данные вектора не инициализируются (содержат мусор) V1.resize(5) ' показываем размерность и реальную вместимость на данный момент ? "size="; V1.size, "capacity" ; V1.capacity ? "resize vector with data" ' изменяем размер вектора с инициализацией добавляемых ячеек V1.resize(10 , 44) ' показываем размерность и реальную вместимость на данный момент ? "size="; V1.size, "capacity" ; V1.capacity ? ? "shrink..." V1.shrink_to_fit ' показываем размерность и реальную вместимость на данный момент ? "size="; V1.size, "capacity" ; V1.capacity ? printVector(V1, "V1") ? ? "assign" ' заменяем содержимое первых 3 ячеек V1.assign(3, 99) ' заменяем содержимое ячеек в диапазоне 7-9 V1.assign(7, 9, 100) ? printVector(V1, "V1") ' выводим значения второго вектора ? printVector(V2, "V2") ' обменяем значения векторов V1.swapV(V2) ? ? "after swap" ? ? printVector(V1, "V1") ' выводим значения второго вектора ? printVector(V2, "V2") ' удалим векторы Delete pB Delete pB2 Sleep
Так же опробовать код вектора вы можете на алгоритме поиска Ахо-Корасик