Be here, we are going to write an integer array class from scratch that implements most of the common functionality that containers should have. This array class is going to be a value container, which will hold copies of the elements it’s organizing. As the name suggests, the container will hold an array of integers, similar to std::vector<int>.
在这里，我们将从头开始编写一个整数数组类，该类实现容器应该具有的大多数常见功能。这个数组类将是一个值容器（指存储值而不是指针或引用），它将保存它正在组织的元素的副本。顾名思义，容器将保存一个整数数组，类似于std::vector<int>。
First, let’s create the IntArray.h file:
首先，让我们创建IntArray.h文件：
#ifndef INTARRAY_H
#define INTARRAY_H
class IntArray
{
};
#endif Our IntArray is going to need to keep track of two values: the data itself, and the size of the array. Because we want our array to be able to change in size, we’ll have to do some dynamic allocation, which means we’ll have to use a pointer to store the data.
我们的IntArray需要跟踪两个值：数据本身和数组的大小。因为我们希望数组能够改变大小，所以必须进行一些动态分配，这意味着必须使用指针来存储数据。
#ifndef INTARRAY_H
#define INTARRAY_H
class IntArray
{
private:
int m_length{};
int* m_data{};
};
#endif Now we need to add some constructors that will allow us to create IntArrays. We are going to add two constructors: one that constructs an empty array, and one that will allow us to construct an array of a predetermined size.
现在我们需要添加一些构造函数来创建intarray。我们将添加两个构造函数：一个构造空数组，另一个允许我们构造预定大小的数组。
#ifndef INTARRAY_H
#define INTARRAY_H
#include <cassert> // for assert()
class IntArray
{
private:
int m_length{};
int* m_data{};
public:
IntArray() = default;
IntArray(int length):
m_length{ length }
{
assert(length >= 0);
if (length > 0)
m_data = new int[length]{};
}
};
#endif We’ll also need some functions to help us clean up IntArrays. First, we’ll write a destructor, which simply deallocates any dynamically allocated data. Second, we’ll write a function called erase(), which will erase the array and set the length to 0.
我们还需要一些函数来帮助我们清理IntArrays。首先，我们将编写一个析构函数，它只需释放任何动态分配的数据。其次，我们将编写一个名为erase()的函数，该函数将擦除数组并将长度设置为0。
~IntArray()
{
delete[] m_data;
// we don't need to set m_data to null or m_length to 0 here, since the object will be destroyed immediately after this function anyway
}
void erase()
{
delete[] m_data;
// We need to make sure we set m_data to nullptr here, otherwise it will
// be left pointing at deallocated memory!
m_data = nullptr;
m_length = 0;
} Now let’s overload the [] operator so we can access the elements of the array. We should bounds check the index to make sure it’s valid, which is best done using the assert() function. We’ll also add an access function to return the length of the array. Here’s everything so far:
现在让我们重载[]操作符，以便访问数组的元素。我们应该对索引进行边界检查以确保其有效，这最好使用assert()函数来完成。我们还将添加一个访问函数来返回数组的长度。以下是目前为止的所有内容：
#ifndef INTARRAY_H
#define INTARRAY_H
#include <cassert> // for assert()
class IntArray
{
private:
int m_length{};
int* m_data{};
public:
IntArray() = default;
IntArray(int length):
m_length{ length }
{
assert(length >= 0);
if (length > 0)
m_data = new int[length]{};
}
~IntArray()
{
delete[] m_data;
// we don't need to set m_data to null or m_length to 0 here, since the object will be destroyed immediately after this function anyway
}
void erase()
{
delete[] m_data;
// We need to make sure we set m_data to nullptr here, otherwise it will
// be left pointing at deallocated memory!
m_data = nullptr;
m_length = 0;
}
int& operator[](int index)
{
assert(index >= 0 && index < m_length);
return m_data[index];
}
int getLength() const { return m_length; }
};
#endif At this point, we already have an IntArray class that we can use. We can allocate IntArrays of a given size, and we can use the [] operator to retrieve or change the value of the elements.
此时，我们已经有了一个可以使用的IntArray类。我们可以分配给定大小的数组，并且可以使用[]操作符检索或更改元素的值。
However, there are still a few thing we can’t do with our IntArray. We still can’t change its size, still can’t insert or delete elements, and we still can’t sort it.
然而，对于IntArray，仍然有一些事情我们不能做。我们仍然无法更改其大小，仍然无法插入或删除元素，仍然无法对其进行排序。
First, let’s write some code that will allow us to resize an array. We are going to write two different functions to do this. The first function, reallocate(), will destroy any existing elements in the array when it is resized, but it will be fast. The second function, resize(), will keep any existing elements in the array when it is resized, but it will be slow.
首先，让我们编写一些代码来调整数组的大小。我们将编写两个不同的函数来实现这一点。第一个函数reallocation()将在调整数组大小时销毁数组中的所有现有元素，但速度很快。第二个函数resize()将在调整数组大小时保留数组中的所有现有元素，但速度较慢。
// reallocate resizes the array. Any existing elements will be destroyed. This function operates quickly.
void reallocate(int newLength)
{
// First we delete any existing elements
erase();
// If our array is going to be empty now, return here
if (newLength <= 0)
return;
// Then we have to allocate new elements
m_data = new int[newLength];
m_length = newLength;
}
// resize resizes the array. Any existing elements will be kept. This function operates slowly.
void resize(int newLength)
{
// if the array is already the right length, we're done
if (newLength == m_length)
return;
// If we are resizing to an empty array, do that and return
if (newLength <= 0)
{
erase();
return;
}
// Now we can assume newLength is at least 1 element. This algorithm
// works as follows: First we are going to allocate a new array. Then we
// are going to copy elements from the existing array to the new array.
// Once that is done, we can destroy the old array, and make m_data
// point to the new array.
// First we have to allocate a new array
int* data{ new int[newLength] };
// Then we have to figure out how many elements to copy from the existing
// array to the new array. We want to copy as many elements as there are
// in the smaller of the two arrays.
if (m_length > 0)
{
int elementsToCopy{ (newLength > m_length) ? m_length : newLength };
// Now copy the elements one by one
for (int index{ 0 }; index < elementsToCopy; ++index)
data[index] = m_data[index];
}
// Now we can delete the old array because we don't need it any more
delete[] m_data;
// And use the new array instead! Note that this simply makes m_data point
// to the same address as the new array we dynamically allocated. Because
// data was dynamically allocated, it won't be destroyed when it goes out of scope.
m_data = data;
m_length = newLength;
} Whew! That was a little tricky!
呼！这有点棘手！
Many array container classes would stop here. However, just in case you want to see how insert and delete functionality would be implemented we’ll go ahead and write those too. Both of these algorithms are very similar to resize().
许多数组容器类将在此停止。然而，如果您想了解如何实现插入和删除功能，我们也将继续编写这些内容。这两种算法与resize()非常相似。
void insertBefore(int value, int index)
{
// Sanity check our index value
assert(index >= 0 && index <= m_length);
// First create a new array one element larger than the old array
int* data{ new int[m_length+1] };
// Copy all of the elements up to the index
for (int before{ 0 }; before < index; ++before)
data[before] = m_data[before];
// Insert our new element into the new array
data[index] = value;
// Copy all of the values after the inserted element
for (int after{ index }; after < m_length; ++after)
data[after+1] = m_data[after];
// Finally, delete the old array, and use the new array instead
delete[] m_data;
m_data = data;
++m_length;
}
void remove(int index)
{
// Sanity check our index value
assert(index >= 0 && index < m_length);
// If this is the last remaining element in the array, set the array to empty and bail out
if (m_length == 1)
{
erase();
return;
}
// First create a new array one element smaller than the old array
int* data{ new int[m_length-1] };
// Copy all of the elements up to the index
for (int before{ 0 }; before < index; ++before)
data[before] = m_data[before];
// Copy all of the values after the removed element
for (int after{ index+1 }; after < m_length; ++after)
data[after-1] = m_data[after];
// Finally, delete the old array, and use the new array instead
delete[] m_data;
m_data = data;
--m_length;
}
// A couple of additional functions just for convenience
void insertAtBeginning(int value) { insertBefore(value, 0); }
void insertAtEnd(int value) { insertBefore(value, m_length); } If we want to initialize a array with values, we can do so directly via the initializer list syntax.
如果要使用值初始化数组，可以直接通过初始化列表语法进行初始化。
The IntArray class also can have a constructor with an initializer list.
IntArray类还可以具有具有初始化列表的构造函数。
As a result, std::initializer_list can be used to implement constructors, assignment operators, and other functions that accept a list initialization parameter. std::initailizer_list lives in the <initializer_list> header.
因此，std::initializer_list可用于实现构造函数、赋值运算符和其他接受列表初始化参数的函数。std::initializer_list位于<initializer_list>头文件中。
IntArray(std::initializer_list<int> list) // allow IntArray to be initialized via list initialization
: IntArray(static_cast<int>(list.size())) // use delegating constructor to set up initial array
{
// Now initialize our array from the list
int count{ 0 };
for (auto element : list)
{
m_data[count] = element;
++count;
}
} Here is our IntArray container class in its entirety.
这是我们的IntArray容器类的全部内容。
IntArray.h:
#ifndef INTARRAY_H
#define INTARRAY_H
#include <cassert> // for assert()
class IntArray
{
private:
int m_length{};
int* m_data{};
public:
IntArray() = default;
IntArray(int length):
m_length{ length }
{
assert(length >= 0);
if (length > 0)
m_data = new int[length]{};
}
IntArray(std::initializer_list<int> list) // allow IntArray to be initialized via list initialization
: IntArray(static_cast<int>(list.size())) // use delegating constructor to set up initial array
{
// Now initialize our array from the list
int count{ 0 };
for (auto element : list)
{
m_data[count] = element;
++count;
}
}
~IntArray()
{
delete[] m_data;
// we don't need to set m_data to null or m_length to 0 here, since the object will be destroyed immediately after this function anyway
}
void erase()
{
delete[] m_data;
// We need to make sure we set m_data to nullptr here, otherwise it will
// be left pointing at deallocated memory!
m_data = nullptr;
m_length = 0;
}
int& operator[](int index)
{
assert(index >= 0 && index < m_length);
return m_data[index];
}
// reallocate resizes the array. Any existing elements will be destroyed. This function operates quickly.
void reallocate(int newLength)
{
// First we delete any existing elements
erase();
// If our array is going to be empty now, return here
if (newLength <= 0)
return;
// Then we have to allocate new elements
m_data = new int[newLength];
m_length = newLength;
}
// resize resizes the array. Any existing elements will be kept. This function operates slowly.
void resize(int newLength)
{
// if the array is already the right length, we're done
if (newLength == m_length)
return;
// If we are resizing to an empty array, do that and return
if (newLength <= 0)
{
erase();
return;
}
// Now we can assume newLength is at least 1 element. This algorithm
// works as follows: First we are going to allocate a new array. Then we
// are going to copy elements from the existing array to the new array.
// Once that is done, we can destroy the old array, and make m_data
// point to the new array.
// First we have to allocate a new array
int* data{ new int[newLength] };
// Then we have to figure out how many elements to copy from the existing
// array to the new array. We want to copy as many elements as there are
// in the smaller of the two arrays.
if (m_length > 0)
{
int elementsToCopy{ (newLength > m_length) ? m_length : newLength };
// Now copy the elements one by one
for (int index{ 0 }; index < elementsToCopy; ++index)
data[index] = m_data[index];
}
// Now we can delete the old array because we don't need it any more
delete[] m_data;
// And use the new array instead! Note that this simply makes m_data point
// to the same address as the new array we dynamically allocated. Because
// data was dynamically allocated, it won't be destroyed when it goes out of scope.
m_data = data;
m_length = newLength;
}
void insertBefore(int value, int index)
{
// Sanity check our index value
assert(index >= 0 && index <= m_length);
// First create a new array one element larger than the old array
int* data{ new int[m_length+1] };
// Copy all of the elements up to the index
for (int before{ 0 }; before < index; ++before)
data[before] = m_data[before];
// Insert our new element into the new array
data[index] = value;
// Copy all of the values after the inserted element
for (int after{ index }; after < m_length; ++after)
data[after+1] = m_data[after];
// Finally, delete the old array, and use the new array instead
delete[] m_data;
m_data = data;
++m_length;
}
void remove(int index)
{
// Sanity check our index value
assert(index >= 0 && index < m_length);
// If we're removing the last element in the array, we can just erase the array and return early
if (m_length == 1)
{
erase();
return;
}
// First create a new array one element smaller than the old array
int* data{ new int[m_length-1] };
// Copy all of the elements up to the index
for (int before{ 0 }; before < index; ++before)
data[before] = m_data[before];
// Copy all of the values after the removed element
for (int after{ index+1 }; after < m_length; ++after)
data[after-1] = m_data[after];
// Finally, delete the old array, and use the new array instead
delete[] m_data;
m_data = data;
--m_length;
}
// A couple of additional functions just for convenience
void insertAtBeginning(int value) { insertBefore(value, 0); }
void insertAtEnd(int value) { insertBefore(value, m_length); }
int getLength() const { return m_length; }
};
#endif Now, let’s test it just to prove it works:
现在，让我们测试一下，以证明它是有效的：
#include <iostream>
#include "IntArray.h"
int main()
{
// Declare an array with 10 elements
IntArray array(10);
// Fill the array with numbers 1 through 10
for (int i{ 0 }; i<10; ++i)
array[i] = i+1;
// Resize the array to 8 elements
array.resize(8);
// Insert the number 20 before element with index 5
array.insertBefore(20, 5);
// Remove the element with index 3
array.remove(3);
// Add 30 and 40 to the end and beginning
array.insertAtEnd(30);
array.insertAtBeginning(40);
// Print out all the numbers
for (int i{ 0 }; i<array.getLength(); ++i)
std::cout << array[i] << ' ';
std::cout << '\n';
return 0;
} This produces the result:
40 1 2 3 5 20 6 7 8 30 Although writing container classes can be pretty complex, the good news is that you only have to write them once. Once the container class is working, you can use and reuse it as often as you like without any additional programming effort required.
尽管编写容器类可能相当复杂，但好消息是您只需编写一次。一旦容器类开始工作，您就可以随时使用和重用它，而无需进行任何额外的编程工作。
It is also worth explicitly mentioning that even though our sample IntArray container class holds a built-in data type (int), we could have just as easily used a user-defined type (e.g. a Point class).
还值得一提的是，即使我们的示例IntArray容器类包含内置数据类型（int），我们也可以同样轻松地使用用户定义的类型（例如Point类）。
One more thing: If a class in the standard library meets your needs, use that instead of creating your own. For example, instead of using IntArray, you’re better off using std::vector<int>. It’s battle tested, efficient, and plays nicely with the other classes in the standard library. But sometimes you need a specialized container class that doesn’t exist in the standard library, so it’s good to know how to create your own when you need to. We’ll talk more about containers in the standard library once we’ve covered a few more fundamental topics.
还有一件事：如果标准库中的类满足您的需要，请使用它，而不是创建自己的类。例如，与其使用IntArray，不如使用std::vector<int>。它经过了严格测试，效率很高，并且与标准库中的其他类配合得很好。但有时您需要一个标准库中不存在的专用容器类，因此最好知道如何在需要时创建自己的容器类。一旦我们涵盖了一些更基本的主题，我们将进一步讨论标准库中的容器。
ref
https://www.learncpp.com/cpp-tutorial/container-classes/
-End-