vector

Original link: https://yousazoe.top/archives/8c47f151.html

introduction

The purpose of this course is to focus on the design and implementation of various data structures, revealing the laws, principles and methods, and at the same time, aiming at algorithm design and performance analysis, to enable students to understand and master the main routines and methods. This article will explain the data structure vector and finding and sorting.

abstract data type

interface and implementation

Vectors belong to the most basic linear structure, which we generally call linear sequences.

In this chapter we will demonstrate and discuss two issues around this data structure:

1. How to customize and implement a data structure according to a unified interface specification
2. Around this data structure, it shows how to use more efficient algorithms to make our external interfaces work more efficiently: search, sort

First we have to distinguish abstract data types and data structures:

• abstract data type = data model + a set of operations defined on the model
• Data structure = a set of algorithms that implement ADT based on a specific language

More vividly, we can compare the data structure to a certain product such as a car. As a user Application, he only cares about the functions that the external features of this product can provide; the implementer Implementation needs to be responsible for these functions and how the features are implemented.

Vector ADT

The so-called vector is actually a generalization and generalization of the data organization form of array in high-level programming languages ​​such as C++.

rank access

The so-called array in these high-level programming languages ​​is actually a continuous memory space, which is evenly divided into several units, and each unit will respond to each other with a number and can be accessed directly.

The vector can be considered as the abstraction and generalization of the array, which is also encapsulated by a set of abstract elements in the linear order just now. The difference is that the original access method through the subscript i becomes the rank rank.

In addition, the type of elements in the vector has been expanded, not limited to a specific basic type, and all its operations, management and maintenance are more simplified, and can be completed through a unified interface.

Vector ADT Interface

Various operations can be performed on vectors through these operation interfaces, and vector operations can only be performed through these operation interfaces.

Interface operation example

Construction and Destruction

• SourceCode

 # ifndef SRC_VECTOR_H
 #define SRC_VECTOR_H

 # define DEFAULT_CAPACITY 3 // Default initial capacity

 namespace Vector {
 using Rank = int ; // rank

 template < typename T> class Vector {
 protected :
 T* _elem; // data
 Rank _size; // scale
 Rank _capacity; // capacity

 void expand () ; // Insufficient space to expand
 void shrink () ; // fill too small shrink
 void copyFrom (T const * A, Rank lo, Rank hi) ; // copy array range

 Rank maxItem (Rank lo, Rank hi) ; // select the largest element
 Rank partition (Rank lo, Rank hi) ; // Axis point construction algorithm

 void selectionSort (Rank lo, Rank hi) ; // selection sort

 bool bubble (Rank lo, Rank hi) ; // scan swap
 void bubbleSort (Rank lo, Rank hi) ; // bubble sort

 void merge (Rank lo, Rank mid, Rank hi) ; // Merge algorithm
 void mergeSort (Rank lo, Rank hi) ; // merge sort

 void heapSort (Rank lo, Rank hi) ; // heap sort
 void quickSort (Rank lo, Rank hi) ; // quicksort
 void shellSort (Rank lo, Rank hi) ; // Hill sort

 public :
 /* Constructor*/
 Vector ( int c = DEFAULT_CAPACITY, Rank s = 0 , T v = 0 ) {
 _elem = new T[_capacity = c];
 for (_size = 0 ; _size < s; ++_size)
 _elem[_size] = v;
 }

 Vector (T const * A, Rank n) { copyFrom (A, 0 , n); }
 Vector (T const * A, Rank lo, Rank hi) { copyFrom (A, lo, hi); }
 Vector (Vector<T> const & V) { copyFrom (V._elem, 0 , V._size); }
 Vector (Vector<T> const & V, Rank lo, Rank hi) { copyFrom (V._elem, lo, hi); }

 /* destructor */
 ~ Vector () { delete [] _elem; }

 /* read-only interface */
 Rank size () const { return _size; } // scale
 bool empty () const { return !_size; } // Empty

 Rank find (T const & e) const { return find (e, 0 , _size); } // unordered vector overall search
 Rank find (T const & e, Rank lo, Rank hi) ; // Unordered vector interval search

 Rank search (T const & e) const { // Ranked vector overall search
 return (_size <= 0 )? -1 : search (e, 0 , _size);
 }
 Rank search (T const & e, Rank lo, Rank hi) const ; // ordered vector interval search

 /* writable interface */
 T& operator [] (Rank r); // overload the subscript operator
 const T& operator [] (Rank r) const ;
 Vector<T>& operator = (Vector<T> const &); // overloaded assignment operator

 T remove (Rank r) ; // remove a single element
 int remove (Rank lo, Rank hi) ; // remove range element
        
Rank insert (Rank r, T const & e) ; // insert element
 Rank insert (T const & e) { return insert (_size, e); } // insert last element
        
void sort (Rank lo, Rank hi) ; // interval sort
 void sort () { sort ( 0 , _size); } // overall sort

 void unsort (Rank lo, Rank hi) ; // Interval scrambling
 void unsort () { unsort ( 0 , _size); } // overall scrambling

 /* Traverse the interface */
 void traverse ( void (*) (T&)) ; // function pointer traversal
 template < typename VST> void traverse (VST&) ; // function object traversal
 };
 }

 # endif //SRC_VECTOR_H

The whole Vector is encapsulated, and the operation interface interface from various user applications is provided outside, which is equivalent to the instruction manual of a Vector structure.

 /* Constructor*/
 Vector ( int c = DEFAULT_CAPACITY, Rank s = 0 , T v = 0 ) {
 _elem = new T[_capacity = c];
 for (_size = 0 ; _size < s; ++_size)
 _elem[_size] = v;
 }

 Vector (T const * A, Rank n) { copyFrom (A, 0 , n); }
 Vector (T const * A, Rank lo, Rank hi) { copyFrom (A, lo, hi); }
 Vector (Vector<T> const & V) { copyFrom (V._elem, 0 , V._size); }
 Vector (Vector<T> const & V, Rank lo, Rank hi) { copyFrom (V._elem, lo, hi); }

 /* destructor */
 ~ Vector () { delete [] _elem; } 

copy

 template < typename T>
 void Vector<T>:: copyFrom ( const T *A, Rank lo, Rank hi) {
 _elem = new T[_capacity = 2 *(hi - lo)];
 _size = 0 ;

 while (lo < hi)
 _elem[_size++] = A[lo++];
 }

The copy operation doubles the _elem space, and then copies the interval elements in sequence.

scalable vector

scalable vector

Now we use _size for actual size and _capacity for total capacity.

 T* _elem; // data
 Rank _size; // scale
 Rank _capacity; // capacity

The problem here is that once _capacity is determined it will be immutable in the current scheme, and such a strategy obviously has obvious shortcomings. This deficiency is reflected in two aspects:

• Overflow (overflow): _elem[] is not enough to hold all elements, although the system still has enough space at this time
• Underflow: few elements in _elem[] , fill factor = _size/_capacity << 50%

Dynamic space management

Appropriately expand the internal array capacity when an overflow is imminent.

Incremental expansion

Double expansion

unordered vector

ordered vector

unique

binary search

Fib lookup

interpolated lookup

bubble sort

merge sort

bitmap

This article is reproduced from: https://yousazoe.top/archives/8c47f151.html
This site is for inclusion only, and the copyright belongs to the original author.