C++ shows you how to implement a variable length array
- 2020-06-19 11:28:06
- OfStack
Implement a custom variable length array type
Suppose we want to implement an array that expands automatically, what function do we want to implement? Let's look at the implementation of the main function below to see what functions we need to implement.
int main()
{
MyArray a; // The initialized array is empty
for(int i = 0; i < 5; ++i)
a.push_back(i); // push_back It's a member function
MyArray a2,a3;
a2 = a; // Overload the assignment operator function
// Due to the 1 other a2 = a Statement, so a.length() It's actually a2.length()
for(int i = 0; i < a.length(); ++i)
cout << a2[i] << " ";
a2 = a3; // a2 It's an empty array
for(int i = 0; i < a2.length(); ++i) // a2.length() return 0
cout << a2[i] << " ";
cout << endl;
a[3] = 100; // overloading [] Operator function
MyArray a4(a); // Overload the 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
The way to do it, what are the things to do? Let me start with column 1:
To store array elements with dynamically allocated memory, you need a pointer member variable Overload assignment = operator Overload the [] operator Overload the copy constructor Implement the push_back and length() functions
Steps to implement the 02 MyArray class
To implement a variable length array class, the following seven functions are basically required:
class MyArray // Variable length array class
{
public:
// 1. The constructor, s Represents the number of elements in the array
MyArray(int s = 0);
// 2. Copy constructor
MyArray(MyArray &a);
// 3. The destructor
~MyArray();
// 4. Overloaded assignment = Operator function for assignment between array objects
MyArray & operator=(const MyArray & a);
// 5. overloading [] Operator function to get the value of the pair of array indices
int & operator[](int i);
// 6. join 1 To the end of the array
void push_back(int v);
// 7. Gets the length of the array
int length();
private:
int m_size; // Number of array elements
int* m_ptr; // Points to an array that is dynamically allocated
};
1. Constructor
The purpose of the constructor is to initialize an array as follows:
// The constructor
MyArray::MyArray(int s = 0):m_size(s)
{
// When the initialization length is zero 0 Array pointer is empty
if(s == 0)
m_ptr = NULL;
// When the initialization length is not 0 , then apply for a space of the corresponding size
else
m_ptr = new int[s];
}
Copy the constructor
Copy constructor is to produce 1 and into one kind of object, but the MyArray class is a pointer member variables, so we must with deep copy of the only way to realize the copy constructor, if use the default copy constructor, leads to two object pointer member variables to address is the same one, it is very dangerous.
// Copy constructor
MyArray::MyArray(const MyArray &a)
{
// Also initialized if the pointer address of the referenced array object is null 1 An empty array
if(a.m_ptr == NULL)
{
m_ptr = NULL;
m_size = 0;
}
// Applies if the array object being entered has data 1 Finally, copy the data and size of the object into the parameter array.
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 the destructor is to free the resources of the array
// The destructor
MyArray::~MyArray()
{
// If the pointer address is not null, the resource is freed
if(m_ptr)
delete [] m_ptr;
}
4. Overload assignment = operator function
Overloading the assignment = operator is designed so that the array in the left object of the = sign is the same size and content as the one on the right
// Overloaded assignment = Operator function
MyArray & MyArray::operator=(const MyArray & a)
{
if(m_ptr == a.m_ptr) // To prevent a=a This assignment causes an error
return *this;
if(a.m_ptr == NULL) // if a The array inside is empty
{
if(m_ptr)
delete [] m_ptr; // Frees the resources of the old array
m_ptr = NULL;
m_size = 0;
return *this;
}
if(m_size < a.m_size) // If the original space is large enough, there is no need to allocate new space
{
if(m_ptr)
delete [] m_ptr; // Frees the resources of the old array
m_ptr = new int[a.m_size]; // Request a new memory address
}
memcpy(m_ptr, a.m_ptr, sizeof(int)*a.m_size);
m_size = a.m_size;
return *this;
}
Overload the [] operator function
The purpose of overloading the [] operator is to get the array value of the corresponding subscript through the [] operator
// overloading [] Operator function
int & MyArray::operator[](int i)
{
return m_ptr[i]; // Returns the array value of the corresponding subscript
}
6. A function that adds elements to the end of an array
The purpose of the push_back function is to add a new element to the end of the array
// Add at the end of the array 1 An element
void MyArray::push_back(int v)
{
if(m_ptr) // If the array is not empty
{
int *tmpPtr = new int[m_size + 1]; // Reallocation of space
memcpy(tmpPtr, m_ptr, sizeof(int)*m_size); // Copy the original array contents
delect [] m_ptr;
m_ptr = tmpPtr;
}
else // If the array is already empty
{
m_ptr = new int[1];
}
m_ptr[m_size++] = v; // Add new array elements
}
7. The function that gets the length of the array
The length() function is simpler and returns the member variable m_size, which is the length of the array
// A function that gets the length of an array
int MyArray:;length()
{
return m_size;
}
03 summary
The overall code for the variable length array type implementation is as follows:
class MyArray
{
public:
// 1. The constructor, s Represents the number of elements in the array
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 original array contents
m_size = a.m_size;
}
}
// 3. Copy constructor
~MyArray()
{
if(m_ptr)
delete [] m_ptr;
}
// 4. Overloaded 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 original array contents
m_size = a.m_size;
return *this;
}
// 5. overloading [] Operator function
int & operator[](int i)
{
return m_ptr[i];
}
// 6. Add at the end of the array 1 A new element
void push_back(int v)
{
if(m_ptr) // If the array is not empty
{
int *tmpPtr = new int[m_size + 1]; // Reallocation of space
memcpy(tmpPtr, m_ptr, sizeof(int)*m_size); // Copy the original array contents
delete [] m_ptr;
m_ptr = tmpPtr;
}
else // If the array is already empty
{
m_ptr = new int[1];
}
m_ptr[m_size++] = v; // Add new array elements
}
// 7. Gets the length of the array
int length()
{
return m_size;
}
private:
int m_size; // Number of array elements
int* m_ptr; // Points to an array that is dynamically allocated
};
In fact, this variable length array class is missing 1 function, such as: delete a certain element of the function, empty the array, etc., which can be left for you to think about.
In addition, there is room for optimization of push_back function. Every element added to the current push_back function will reallocate new memory, which will increase the overhead. Then, the optimization idea is as follows:
Allocate 1 n size space in advance, and when the array size is insufficient, proceed to reassign 2n size space, and so on.