C++ implements dynamic array function

  • 2020-06-12 10:02:32
  • OfStack

An array of

An array is a linear table data structure. It USES one continuous memory space to store one set of data with the same data type.

1. Linear table: data storage is like 1 line 1 structure, the data on each linear table only has at most two directions before and after, such as number group, linked list, queue, stack and so on are this structure, so the implementation of the dynamic operation of array, other structures can also be easily similar implementation. More importantly, looking at the source code after that makes it much easier. (The blogger himself looked at the STL source code profile)
2. Nonlinear tables: such as 2-tree, heap, graph, etc.
3. Continuous memory space and the same data type: when the array is inserted or deleted, in order to ensure the continuity of data, a lot of data moving is often needed, which is very inefficient.

Dynamic array function implementation

1. Array initialization

Considering the memory leaks that can occur when data is moved during capacity expansion, the blogger adopts the two-handed principle of setting 1 memory flag bit ItemsFlag. When ItemsFlag = 0, using preitems; When ItemsFlag = 1, using items. The expansion part below has concrete realization. The default array size is 10.


enum { MAX = 10 };
explicit GenericArray(int ss = MAX);
template<class T>
GenericArray<T>::GenericArray(int ss) : capacity(ss),counts(0)
{
 itemsFlag = 0;
 preitems = new T[capacity];
 items = nullptr;
}

2. Destructor

Free memory.


template<class T>
GenericArray<T>::~GenericArray()
{ 
 if (preitems != nullptr)
 delete[]preitems; 
 if (items != nullptr)
 delete[]items;
}

3. Check subscripts

Check to see if the index you want to operate on is in the array capacity range.


template<class T>
bool GenericArray<T>::checkIndex(int index)
{
 if (index < 0 || index >= capacity)
 {
  int cap = capacity - 1;
  cout << "Out of the range! Please ensure the index be 
  in 0 ~ " << cap << '\n';
  return false;
 }
 return true;
}

4. Get the number and capacity of elements, and determine whether the array is empty or full


int count()const { return counts; }
int getCapacity()const { return capacity; }
bool isEmpty()const { return counts == 0; }
bool isFull()const { return counts >= capacity; }

5. Fetch the corresponding value of the index, modify the value according to the index, print out, and whether it contains a certain value


template<class T>
T GenericArray<T>::get(int index)
{
 if (!itemsFlag)
 return preitems[index];
 else
 return items[index];
}
void GenericArray<T>::set(int index, T elem)
{
 if(checkIndex(index))
 {
 if (!itemsFlag)
 preitems[index] = elem;
 else
 items[index] = elem;
 return;
 }
}
template<class T>
void GenericArray<T>::printArray()const
{
 for (int i = 0; i < counts; i++)
 if (!itemsFlag)
  cout << preitems[i] << '\t';
 else
  cout << items[i] << '\t'; 
 cout << '\n';
 return;
}
template<class T>
bool GenericArray<T>::contains(T arr)
{
 for (int i = counts - 1; i >= 0; i--)
 if (!itemsFlag)
 {
  if (arr == preitems[i])
  return true;
 }
 else
 {
  if (arr == items[i])
  return true;
 }
 return false;
}

6. Find a value subscript, delete a value

When looking for the index of a value, it is necessary to consider whether the value is repeated in the array, so the blogger USES a structure findArrIndex to store the number of times the value is repeated and the corresponding index.


struct findArrIndex
{
 int numIndex;
 int *findIndex;
};
template<class T>
void GenericArray<T>::find(T arr, findArrIndex *ps)
{
 ps->findIndex = new int[counts];
 ps->numIndex = 0;
 for (int i = 0, j = 0; i < counts; i++, j++)
 if (!itemsFlag)
 {
  if (arr == preitems[i])
  {
  (ps->findIndex)[j] = i;
  (*ps).numIndex++;
  cout << i << '\t';
  }
 }
 else
  if (arr == items[i])
  {
  (ps->findIndex)[j] = i;
  (*ps).numIndex++;
  cout << i << '\t';
  }
 cout << '\n';
 return;
}
template<class T>
void GenericArray<T>::removeElement(findArrIndex *ps)
{
 for (int i = ps->numIndex; i > 0; i--)
 remove((ps->findIndex)[i - 1]);
 delete[](ps->findIndex);
}
template<class T>
void GenericArray<T>::set(int index, T elem)
{
 if(checkIndex(index))
 {
 if (!itemsFlag)
 preitems[index] = elem;
 else
 items[index] = elem;
 return;
 }
}

Expansion and 7.

When adding data operation, it is necessary to determine whether the array capacity is enough. If not, it is necessary to consider expansion.


template<class T>
void GenericArray<T>::renewCapacity()
{
 cout << "The array's capacity is small! Renew capacity.\n";
 if (capacity < 1000)
 capacity = capacity << 1;
 else
 capacity = capacity >> 1 + capacity;
 if (!itemsFlag)
 {
 itemsFlag = 1;
 items = new T[capacity];
 for (int i = 0; i<counts; i++)
  *(items + i) = *(preitems + i);
  //items[i]=proitems[i];
 //cout << items << '\n';
 //cout << preitems << '\n';
 delete[]preitems;
 preitems = nullptr;
 }
 else
 {
 itemsFlag = 0;
 preitems = new T[capacity];
 for (int i = 0; i<counts; i++)
  *(preitems + i) = *(items + i);
 delete[]items;
 items = nullptr;
 }
}

8. Add data: Array add data include index subscript interpolation, array header interpolation, array tail interpolation. Essentially, the latter two can be achieved by calling the index-subscript interpolation function. As mentioned earlier, the complexity of adding an array is a large amount of data movement: to insert an element into k by index index, you need to move the elements in k ~ n one bit back, then insert the element and update the number of elements. If inserted to the end of the array, time complexity O(1); Insert into array header, time complexity O(n); The average time complexity of inserts is (1+2+... +n) /n = O(n).
In addition, there is an optimization problem: if the array is an unordered array, no data need to be moved during insertion: If an element is inserted into the k position of the array, first the element at that position is moved to the end of the array, and then the element to be inserted into the k position, the time complexity is O(1).


template<class T>
void GenericArray<T>::add(int index, T elem)
{
 if (isFull())
 {
 cout << "Array is full!" << '\n';
 renewCapacity();
 }
 if (checkIndex(index))
 if(!itemsFlag)
 {
  for (int i = counts; i > index; i--)
  preitems[i] = preitems[i - 1];
  preitems[index] = elem;
 }
 else
 {
  for (int i = counts; i > index; i--)
  items[i] = items[i - 1];
  items[index] = elem;
 }
 counts++;
 return;
}

template<class T>
void GenericArray<T>::addFirst(T elem)
{
 add(0, elem);
}

template<class T>
void GenericArray<T>::addLast(T elem)
{
 add(counts, elem);
}

9. Delete data: Array deletion includes deletion by index subscript, array header and array tail. Essentially, the latter two can be achieved by calling the index-subscript deletion function. Similar to the above, the complex operation of array deletion is also a large amount of data moving work: to delete an element according to the index index, the elements of k+1 ~ n need to be moved forward 1 bit to update the number of elements. If the end of the array is deleted, the number of elements can be reduced by 1, and the time complexity is O(1). Delete array header, time complexity O(n); Average time complexity of deletions (1+2+... +n) /n = O(n)
In addition, there is an optimization problem: if you want to delete the value in the array for many times, you can mark the value to be deleted first, and delete the value once after marking, which greatly reduces the number of moves.


template<class T>
T GenericArray<T>::remove(int index)
{
 if (!isEmpty())
 { 
 if (checkIndex(index))
 {
  if (!itemsFlag)
  {
  T temp = preitems[index];
  for (int i = index+1; i < counts; i++)
   preitems[i - 1] = preitems[i];
  counts--;
  return temp;
  }
  else
  {
  T temp = items[index];
  for (int i = index + 1; i < counts; i++)
   items[i - 1] = items[i];
  counts--;
  return temp;
  }
 }
 }
 else
 {
 cout << "Array is empty!" << '\n';
 return -1;
 }
}
template<class T>
T GenericArray<T>::removeFirst()
{
 return remove(0);
}
template<class T>
T GenericArray<T>::removeLast()
{
 return remove(counts - 1);
}

Well, that's pretty much it.

In the end, it is important to look at the source code.


Related articles: