01 implement custom variable length array type
Suppose we want to implement an array that will be automatically expanded. What functions should we implement? First, from the implementation given by the main function below, we can see what functions we need to implement.
int main()
{
MyArray a; // Initialized array is empty
for(int i = 0; i < 5; ++i)
a.push_back(i); // Push back is a member function
MyArray a2,a3;
a2 = a; // Overloaded assignment operator function
// Since the previous a2 = a statement, a.length() is actually a2.length()
for(int i = 0; i < a.length(); ++i)
cout << a2[i] << " ";
a2 = a3; // a2 is an empty array
for(int i = 0; i < a2.length(); ++i) // a2.length() returns 0
cout << a2[i] << " ";
cout << endl;
a[3] = 100; // Overloaded [] operator function
MyArray a4(a); // Overload copy constructor
for(int i = 0; i < a4.length(); ++i)
cout << a4[i] << " ";
return 0;
}Output results:
0 1 2 3 4 0 1 2 100 4
What should we do to achieve this? Let me list:
- To store array elements in dynamically allocated memory, you need a pointer member variable
- Overloaded assignment = operator
- Overload [] operator
- Overload copy constructor
- Implement the push back and length() functions
02 implementation steps of myArray class
To implement a variable length array class, you need to implement the following seven functions:
class MyArray // Variable length array class
{
public:
// 1. Constructor, s represents the number of array elements
MyArray(int s = 0);
// 2. Copy constructor
MyArray(MyArray &a);
// 3. Destructor
~MyArray();
// 4. Overload assignment = operator function, used for assignment between array objects
MyArray & operator=(const MyArray & a);
// 5. Overload [] operator function to get the value of array subscript pair
int & operator[](int i);
// 6. Add an element to the end of the array
void push_back(int v);
// 7. Get the length of the array
int length();
private:
int m_size; // Number of array elements
int* m_ptr; // Array pointing to dynamic allocation
};1. Constructor
The purpose of the constructor is to initialize an array. The code is as follows:
// Constructor
MyArray::MyArray(int s = 0):m_size(s)
{
// When initializing an array of length 0, the array pointer is null
if(s == 0)
m_ptr = NULL;
// When the initialization length is not 0, the space of corresponding size will be applied
else
m_ptr = new int[s];
}2. Copy constructor
The purpose of copy constructor is to produce the same object as the input parameter object, but since MyArray class has pointer member variables, we must use the method of deep copy to implement copy constructor. If we use the default copy constructor, the pointer member variables of the two objects will point to the same address, which is very dangerous.
// copy constructor
MyArray::MyArray(const MyArray &a)
{
// If the pointer address of the array object of the input parameter is null, an empty array is also initialized
if(a.m_ptr == NULL)
{
m_ptr = NULL;
m_size = 0;
}
// If the array object of the input parameter has data, apply for a new address, and finally copy the data and size of the array object of the input parameter.
else
{
m_ptr = new int[a.m_size];
memcpy(m_ptr, a.m_ptr, sizeof(int)*a.m_size);
m_size = a.m_size;
}
}3. Destructor
The purpose of destructors is to free the resources of arrays
// Destructor
MyArray::~MyArray()
{
// Release resource if pointer address is not empty
if(m_ptr)
delete [] m_ptr;
}4. Overload assignment = operator function
The purpose of overloading the assignment = operator function is to make the array stored in the object on the left of the = sign the same size and content as the object on the right
// Overloaded assignment = operator function
MyArray & MyArray::operator=(const MyArray & a)
{
if(m_ptr == a.m_ptr) // Prevent errors caused by assignments such as a=a
return *this;
if(a.m_ptr == NULL) // If the array in a is empty
{
if(m_ptr)
delete [] m_ptr; // Freeing resources from old arrays
m_ptr = NULL;
m_size = 0;
return *this;
}
if(m_size < a.m_size) // If the original space is large enough, no new space will be allocated
{
if(m_ptr)
delete [] m_ptr; // Freeing resources from old arrays
m_ptr = new int[a.m_size]; // Request new memory address
}
memcpy(m_ptr, a.m_ptr, sizeof(int)*a.m_size);
m_size = a.m_size;
return *this;
}5. Overload [] operator function
The purpose of overloading the [] operator function is to get the array value of the corresponding subscript through the [] operator
// Overloaded [] operator function
int & MyArray::operator[](int i)
{
return m_ptr[i]; // Returns the array value of the corresponding subscript
}6. Functions adding elements to the end of the array
The purpose of the push back function is to add a new element to the end of the array
// Add an element at the end of the array
void MyArray::push_back(int v)
{
if(m_ptr) // If the array is not empty
{
int *tmpPtr = new int[m_size + 1]; // Reallocate space
memcpy(tmpPtr, m_ptr, sizeof(int)*m_size); // Copy the contents of the original array
delect [] m_ptr;
m_ptr = tmpPtr;
}
else // If the array is empty
{
m_ptr = new int[1];
}
m_ptr[m_size++] = v; //Add new array elements
}7. Get the function of array length
The length() function is relatively simple. It directly returns the member variable m_size, which is the length of the array
// Function to get the length of an array
int MyArray:;length()
{
return m_size;
}03 summary
The whole code of variable length array type is as follows:
class MyArray
{
public:
// 1. Constructor, s represents the number of array elements
MyArray(int s = 0):m_size(s)
{
if(s == 0)
m_ptr = NULL;
else
m_ptr = new int[s];
}
// 2. Copy constructor
MyArray(const MyArray &a)
{
if(a.m_ptr == NULL)
{
m_ptr = NULL;
m_size = 0;
}
else
{
m_ptr = new int[a.m_size];
memcpy(m_ptr, a.m_ptr, sizeof(int)*a.m_size); // Copy the contents of the original array
m_size = a.m_size;
}
}
// 3. Copy constructor
~MyArray()
{
if(m_ptr)
delete [] m_ptr;
}
// 4. Overload assignment = operator function
MyArray & operator=(const MyArray & a)
{
if(m_ptr == a.m_ptr)
return *this;
if(a.m_ptr == NULL)
{
if(m_ptr)
delete [] m_ptr;
m_ptr = NULL;
m_size = 0;
return *this;
}
if(m_size < a.m_size)
{
if(m_ptr)
delete [] m_ptr;
m_ptr = new int[a.m_size];
}
memcpy(m_ptr, a.m_ptr, sizeof(int)*a.m_size); // Copy the contents of the original array
m_size = a.m_size;
return *this;
}
// 5. Overload [] operator function
int & operator[](int i)
{
return m_ptr[i];
}
// 6. Add a new element at the end of the array
void push_back(int v)
{
if(m_ptr) // If the array is not empty
{
int *tmpPtr = new int[m_size + 1]; // Reallocate space
memcpy(tmpPtr, m_ptr, sizeof(int)*m_size); // Copy the contents of the original array
delete [] m_ptr;
m_ptr = tmpPtr;
}
else // If the array is empty
{
m_ptr = new int[1];
}
m_ptr[m_size++] = v; //Add new array elements
}
// 7. Get the length of the array
int length()
{
return m_size;
}
private:
int m_size; // Number of array elements
int* m_ptr; // Array pointing to dynamic allocation
};In fact, the variable length array class lacks the following functions, such as the function to delete an element, the function to empty an array, etc., which can be left for you to think about.
There is also room for optimization in the push back function. Every element added to the current push back function will reallocate new memory, which will increase the cost. Then, the optimization idea is as follows:
Allocate a space of N in advance. When the array size is not enough, continue to reallocate the space of 2n, and so on.