0 - General
The code is based on data structure C + + language version by Mr. Deng Junhui, with appropriate changes.
It feels like this is basically a simplified STL.
Follow the book and review the basics of C + + language.
1 - interface declaration
The vector class is implemented here. In order to distinguish it from the vector in the standard library, the beginning character is capitalized.
In consideration of reusability, the template class is adopted here, and it is assumed that the instance of the class supports comparison operations and judgment operations, or the class has overloaded the comparison operators <, > and judgment operators = =.
In addition, in order to make the idea clearer, some robustness considerations are sacrificed. For example, the legitimacy of the incoming parameter rank r is not checked, which may cause the array to cross the boundary.
#ifndef _VECTOR_H_
#define _VECTOR_H_
#define DEFAULT_CAPACITY 3
typedef int Rank;
//As a sort parameter, it is used to call different sorting algorithms
enum SortMethod {
BUBBLE_SORT,
INSERTION_SORT,
SHELL_SORT,
SELECTION_SORT,
HEAP_SORT,
MERGE_SORT_ITERATIVELY,
MERGE_SORT_RECURSIVELY,
QUICK_SORT,
COUNTING_SORT,
RADIX_SORT
};
//As a parameter of search, it is used to call different search algorithms
enum SearchMethod {
BIN_SEARCH,
FIB_SEARCH
};
template <typename T>
class Vector {
public:
//Default constructor: the capacity is c, the size is s, and all are initialized to v
Vector(int c = DEFAULT_CAPACITY, int s = 0, T v = 0);
//Use array global construction
Vector(T const* A, Rank n);
//Using array interval construction
Vector(T const* A, Rank lo, Rank hi);
//Using vector global copy construction
Vector(Vector<T> const& V);
//Using vector interval construction
Vector(Vector<T> const& V, Rank lo, Rank hi);
~Vector();
/****Read only access interface****/
//Return scale
Rank size() const;
//Air judgment
bool empty() const;
//Returns the number of adjacent pairs in reverse order
int disordered() const;
//Global search of unordered vectors
Rank find(T const& e) const;
//Unordered vector interval search
Rank find(T const& e, Rank lo, Rank hi) const;
//Ordered vector global search
Rank search(T const& e, SearchMethod m = BIN_SEARCH) const;
//Ordered vector interval search
Rank search(T const& e, Rank lo, Rank hi, SearchMethod m = BIN_SEARCH) const;
//Overloaded subscript operator []
T& operator[](Rank r) const;
//Overloaded assignment operator =, which is convenient for direct copy, and returned reference is convenient for chained assignment
Vector<T>& operator=(Vector<T> const& V);
//Delete elements with rank r
T remove(Rank r);
//Delete elements with rank between [lo,hi)
int remove(Rank lo, Rank hi);
//Insert element
Rank insert(Rank r, T const& e);
//Insert as end by default
Rank insert(T const& e);
//Interval sorting
void sort(Rank lo, Rank hi, SortMethod m = BUBBLE_SORT);
//Overall sorting
void sort(SortMethod m = BUBBLE_SORT);
//Interval scrambling
void unsort(Rank lo, Rank hi);
//Overall scrambling
void unsort();
//Disordered vector de duplication
int deduplicate();
//Ordered vector de duplication
int uniquify();
//Traversal using function pointers
void traverse(void (*)(T&));
//Traversal using a functor (function object)
template <typename VST>
void traverse(VST&);
protected:
Rank _size;
int _capacity;
T* _elem;
//Copy array
void copyFrom(T const* A, Rank lo, Rank hi);
//Capacity expansion
void expand();
//shrink
void shrink();
//Bubble sorting
void bubbleSort(Rank lo, Rank hi);
//Insert sort
void insertionSort(Rank lo, Rank hi);
//Shell Sort
void shellSort(Rank lo, Rank hi);
//Pick maximum
Rank max(Rank lo, Rank hi);
//Select sort
void selectionSort(Rank lo, Rank hi);
//Heap sort
void heapSort(Rank lo, Rank hi);
//Merge sort iterative version
void mergeSort_iteratively(Rank lo, Rank hi);
//Ordered subsequence merging
void merge(Rank lo, Rank mi, Rank hi);
//Merge sort recursive version
void mergeSort_recursively(Rank lo, Rank hi);
//Pivot point structure
Rank partition(Rank lo, Rank hi);
//Quick sort
void quickSort(Rank lo, Rank hi);
//Count sort
void countingSort(Rank lo, Rank hi);
//Cardinality sort
void radixSort(Rank lo, Rank hi);
}; //Vector
#endif
2 - Interface Implementation
2.1 - constructors and destructors
There are five versions of constructors and a destructor with access rights of public.
The default constructor will request #define default_ Capability is an array space of size 3 and initializes the contents to 0. There is a problem here. If T is a non numeric user-defined class, it should be wrong to pass T v=0 as the default parameter of the function, unless the user passes in an instance of this class to replace the default parameter T v=0.
The remaining four overloaded versions of constructors are used for
- Copy elements as a whole from an array
- Copy elements from an array
- Copy elements as a whole from vector < T >
- Copy elements between partitions from vector < T >
These four overloaded versions are implemented based on the copyFrom() function (see 2.2).
The final destructor will member variables_ The array object pointed to by elem is delete d [] and the pointer is set to null.
template <typename T>
Vector<T>::Vector(int c, int s, T v) {
_elem = new T[_capacity = c];
for (_size = 0; _size < s; ++_size) {
_elem[_size] = v;
}
}
template <typename T>
Vector<T>::Vector(T const* A, Rank n) {
copyFrom(A, 0, n);
}
template <typename T>
Vector<T>::Vector(T const* A, Rank lo, Rank hi) {
copyFrom(A, lo, hi);
}
template <typename T>
Vector<T>::Vector(Vector<T> const& V) {
copyFrom(V._elem, 0, V._size);
}
template <typename T>
Vector<T>::Vector(Vector<T> const& V, Rank lo, Rank hi) {
copyFrom(V._elem, lo, hi);
}
template <typename T>
Vector<T>::~Vector() {
delete[] _elem;
_elem = nullptr;
}
2.2 - copy elements from array
Copy the elements between [lo,hi) from array A with protected access rights.
First, create a new (hi - lo) * 2 array, and then copy it one by one.
template <typename T>
void Vector<T>::copyFrom(T const* A, Rank lo, Rank hi) {
_elem = new T[_capacity = (hi - lo) * 2];
_size = 0;
while (lo < hi) {
_elem[_size++] = A[lo++];
}
return;
}
2.3 - overloaded assignment operator=
To facilitate the direct use of = to copy objects, overload = or call the copyFrom() function to copy elements one by one. The access permission is public.
template <typename T>
Vector<T>& Vector<T>::operator=(Vector<T> const& V) {
if (_elem)
delete[] _elem;
copyFrom(V._elem, 0, V._size);
return *this;
}
2.4 - capacity expansion
When the array space is full, double the capacity, open a new array, copy the original content, and finally release the original space.
After the allocation time complexity analysis, the allocation time complexity of this operation is O(1). The access rights are protected and can only be called when necessary (when inserting elements) in the class.
template <typename T>
void Vector<T>::expand() {
if (_size < _capacity)
return;
if (_capacity < DEFAULT_CAPACITY)
_capacity = DEFAULT_CAPACITY;
T* oldElem = _elem;
_elem = new T[_capacity <<= 1];
for (int i = 0; i < _size; ++i)
_elem[i] = oldElem[i];
delete[] oldElem;
return;
}
2.5 - volume reduction
Reduce the array space when the attractor is too small. This step is unnecessary for occasions where space requirements are not sensitive. Access rights protected.
template <typename T>
void Vector<T>::shrink() {
if (_capacity < DEFAULT_CAPACITY << 1)
return;
if (_size << 2 > _capacity)
return;
T* oldElem = _elem;
_elem = new T[_capacity >>= 1];
for (int i = 0; i < _size; ++i)
_elem[i] = oldElem[i];
delete[] oldElem;
return;
}
2.6 - overloaded subscript operator []
In order to directly reference the data items in the vector, the subscript operator [] is overloaded. The access is more intuitive and convenient. The access permission is public.
template <typename T>
T& Vector<T>::operator[](Rank r) const {
return _elem[r];
}
2.7 - scrambling
Two versions of interval scrambling and overall scrambling are provided.
Scrambling algorithm: from the back to the front, randomly pick one from the front element and exchange it with yourself.
Such an algorithm can ensure that all possible permutations of the same vector are listed uniformly.
template <typename T>
void Vector<T>::unsort(Rank lo, Rank hi) {
T* V = _elem + lo;
for (int i = hi - lo; i > 0; --i) {
swap(V[i - 1], V[rand() % i]);
}
}
template <typename T>
void Vector<T>::unsort() {
unsort(0, _size);
}
2.8 - equalizer and comparator
Static function, used only in the current file.
template <typename T>
static bool lt(T const* a, T const* b) {
return lt(*a, *b);
}
template <typename T>
static bool lt(T const& a, T const& b) {
return a < b;
}
template <typename T>
static bool eq(T const* a, T const* b) {
return eq(*a, *b);
}
template <typename T>
static bool eq(T const& a, T const& b) {
return a == b;
}
2.9 - unordered search
The method of sequential search is adopted.
template <typename T>
Rank Vector<T>::find(T const& e) const {
return find(e, 0, _size);
}
template <typename T>
Rank Vector<T>::find(T const& e, Rank lo, Rank hi) const {
while ((lo < hi--) && e != _elem[hi])
;
return hi;
}
2.10 - insertion
template <typename T>
Rank Vector<T>::insert(Rank r, T const& e) {
expand();
for (int i = _size; i > r; --i)
_elem[i] = _elem[i - 1];
_elem[r] = e;
_size++;
return r;
}
template <typename T>
Rank Vector<T>::insert(T const& e) {
return insert(_size, e);
}
2.11 - delete
Note that contrary to intuition, single element deletion is a special case of interval deletion, remove(r, r + 1);, Instead of iteratively implementing interval deletion with single element deletion, it will bring high time complexity.
template <typename T>
T Vector<T>::remove(Rank r) {
T e = _elem[r];
remove(r, r + 1);
return e;
}
template <typename T>
int Vector<T>::remove(Rank lo, Rank hi) {
if (lo == hi)
return 0;
while (hi < _size)
_elem[lo++] = _elem[hi++];
_size = lo;
shrink();
return hi - lo;
}
2.12 - unordered vector uniqueness
For the current element, find whether there are duplicate elements in its prefix, and the time complexity is O(n).
template <typename T>
int Vector<T>::deduplicate() {
int oldSize = _size;
Rank i = 1;
while (i < _size) {
(find(_elem[i], 0, i) < 0) ? ++i : remove(i);
}
return oldSize - _size;
}
2.13 - traversal
In the two versions, the function pointer and function object (imitation function) are used for traversal operation respectively.
template <typename T>
void Vector<T>::traverse(void (*visit)(T&)) {
for (int i = 0; i < _size; ++i) {
visit(_elem[i]);
}
return;
}
template <typename T>
template <typename VST>
void Vector<T>::traverse(VST& visit) {
for (int i = 0; i < _size; ++i) {
visit(_elem[i]);
}
return;
}
2.14 - count the number of adjacent reverse order pairs
template <typename T>
int Vector<T>::disordered() const {
int i = 1;
int count = 0;
for (i = 1; i < _size; ++i) {
if (_elem[i - 1] > _elem[i])
count++;
}
return count;
}
2.15 - ordered vector uniqueness
One pointer points to the end of the unique sequence, and the other pointer looks for different elements in the back and append s to the front.
template <typename T>
int Vector<T>::uniquify() {
Rank i = 0, j = 0;
while (++j < _size) {
if (_elem[i] != _elem[j])
_elem[++i] = _elem[j];
}
_size = ++i;
shrink();
return j - i;
}
2.16 - find
Perform binary search or Fibonacci search according to the search algorithm specified by the user.
template <typename T>
Rank Vector<T>::search(T const& e, SearchMethod m) const {
return (_size <= 0) ? -1 : search(e, 0, _size, m);
}
template <typename T>
Rank Vector<T>::search(T const& e, Rank lo, Rank hi, SearchMethod m) const {
switch (m) {
case BIN_SEARCH:
binSearch(_elem, e, lo, hi);
break;
case FIB_SEARCH:
fibSearch(_elem, e, lo, hi);
break;
default:
break;
}
}
Specific search algorithm:
Fibonacci search algorithm didn't understand very much. The main idea is to improve the dichotomy strategy and use the golden section ratio for division, which can improve the average efficiency.
//When multiple elements hit, the largest rank is returned. When the search fails, the failed location is returned
template <typename T>
static Rank binSearch(T* A, T const& e, Rank lo, Rank hi) {
while (lo < hi) {
Rank mi = (lo + hi) >> 1;
(e < A[mi]) ? hi = mi : lo = mi + 1;
}
return --lo;
}
//md can't understand
template <typename T>
static Rank fibSearch(T* A, T const& e, Rank lo, Rank hi) {
Fib fib(hi - lo);
while (lo < hi) {
while (hi - lo < fib.get())
fib.prev();
Rank mi = lo + fib.get() - 1;
if (e < A[mi])
hi = mi;
else if (e > A[mi])
lo = mi + 1;
else
return mi;
}
return -1;
}
2.17 - sequencer
10 sorting algorithms. The sorting algorithm is selected according to the parameters specified by the user.
template <typename T>
void Vector<T>::sort(Rank lo, Rank hi, SortMethod m) {
switch (m) {
case BUBBLE_SORT:
bubbleSort(lo, hi);
break;
case INSERTION_SORT:
insertionSort(lo, hi);
break;
case SHELL_SORT:
shellSort(lo, hi);
break;
case SELECTION_SORT:
selectionSort(lo, hi);
break;
case HEAP_SORT:
heapSort(lo, hi);
break;
case MERGE_SORT_ITERATIVELY:
mergeSort_iteratively(lo, hi);
break;
case MERGE_SORT_RECURSIVELY:
mergeSort_recursively(lo, hi);
break;
case QUICK_SORT:
quickSort(lo, hi);
break;
case COUNTING_SORT:
countingSort(lo, hi);
break;
case RADIX_SORT:
radixSort(lo, hi);
break;
default:
quickSort();
break;
}
return;
}
template <typename T>
void Vector<T>::sort(SortMethod m) {
sort(0, _size, m);
}
/*****protected****/
template <typename T>
void Vector<T>::bubbleSort(Rank lo, Rank hi) {
bool sorted = false;
while (!sorted) {
sorted = true;
for (int i = lo + 1; i < hi; ++i) {
if (_elem[i - 1] > _elem[i]) {
swap(_elem[i - 1], _elem[i]);
sorted = false;
}
}
hi--;
}
return;
}
template <typename T>
void Vector<T>::insertionSort(Rank lo, Rank hi) {
//TODO
return;
}
template <typename T>
void Vector<T>::shellSort(Rank lo, Rank hi) {
//TODO
return;
}
template <typename T>
Rank Vector<T>::max(Rank lo, Rank hi) {
//TODO
return 0;
}
template <typename T>
void Vector<T>::selectionSort(Rank lo, Rank hi) {
//TODO
return;
}
template <typename T>
void Vector<T>::heapSort(Rank lo, Rank hi) {
return;
}
template <typename T>
void Vector<T>::mergeSort_iteratively(Rank lo, Rank hi) {
//TODO
return;
}
template <typename T>
void Vector<T>::merge(Rank lo, Rank mi, Rank hi) {
Rank i = 0, j = 0, k = 0;
T* A = _elem + lo;
int lb = mi - lo;
T* B = new T[lb];
for (i = 0; i < lb; ++i)
B[i] = A[i];
T* C = _elem + mi;
int lc = hi - mi;
i = 0;
while ((j < lb) || (k < lc)) {
if ((j < lb) && (!(k < lc) || B[j] <= C[k]))
A[i++] = B[j++];
if ((k < lc) && (!(j < lb) || C[k] < B[j]))
A[i++] = C[k++];
}
delete[] B;
return;
}
template <typename T>
void Vector<T>::mergeSort_recursively(Rank lo, Rank hi) {
if (hi - lo < 2)
return;
int mi = (lo + hi) / 2;
mergeSort_iteratively(lo, mi);
mergeSort_recursively(mi, hi);
merge(lo, mi, hi);
return;
}
template <typename T>
Rank Vector<T>::partition(Rank lo, Rank hi) {
//TODO
return 0;
}
template <typename T>
void Vector<T>::quickSort(Rank lo, Rank hi) {
//TODO
return;
}
template <typename T>
void Vector<T>::countingSort(Rank lo, Rank hi) {
//TODO
return;
}
template <typename T>
void Vector<T>::radixSort(Rank lo, Rank hi) {
//TODO
return;
}
2.18 - size and space determination
template <typename T>
Rank Vector<T>::size() const {
return this->_size;
}
template <typename T>
bool Vector<T>::empty() const {
return !(this->_elem);
}
3 - source code
https://gitee.com/daniel187/dsa_tsu/blob/master/src/Vector.cpp