C++学习之动态数组类的封装

发表于   |   分类于   |  

动态数组（Dynamic Array）是指动态分配的、可以根据需求动态增长占用内存的数组。为了实现一个动态数组类的封装，我们需要考虑几个问题：new/delete的使用、内存分配策略、类的四大函数（构造函数、拷贝构造函数、拷贝赋值运算符、析构函数）、运算符的重载。涉及到的知识点很多，鉴于本人水平有限，在这里只做简单的介绍。

内存分配策略

当用new为一个动态数组申请一块内存时，数组中的元素是连续存储的，例如 vector和string。当向一个动态数组添加元素时，如果没有空间容纳新元素，不可能简单地将新元素添加到内存中的其他位置——因为元素必须连续存储。所以必须重新分配一块更大的内存空间，将原来的元素从旧位置移动到新空间中，然后添加新元素，释放旧的内存空间。如果我们每添加一个新元素，就执行一次这样的内存分配和释放操作，效率将会慢到不行。

为了避免上述的代价，必须减少内存重新分配的次数。所以我们采取的策略是：在不得不分配新的内存空间时，分配比新的空间需求更大的内存空间（通常为2倍）。这样，在相当一段时间内，添加元素时就不用重新申请内存空间。注意，只有当迫不得已时才可以分配新的内存空间。

类的四大函数

一个C++类一般至少有四大函数，即构造函数、拷贝构造函数、拷贝赋值运算符、析构函数。如果类未自己定义上述函数，C++编译器将为其合成4个默认的版本。但是往往编译器合成的并不是我们所期望的，为此我们有必要自己定义它们。

构造函数

类的构造函数（constructor）用来初始化类对象的非static数据成员，无论何时只要类的对象被创建，就会执行构造函数。

1
2
3
4
5
6
class Foo {
public:
	Foo();  // 构造函数
	Foo(string &s);  // 接受一个参数的构造函数
	// ...
};

构造函数的名字和类名相同，没有返回类型。类可以包含多个构造函数（重载），它们之间在参数数量或类型上需要有所区别。构造函数有一个初始化部分和一个函数体，成员的初始化是在函数体执行之前完成的。

拷贝构造函数

如果一个构造函数的第一个参数是自身类类型的引用，且任何额外参数都有默认值，则此构造函数是拷贝构造函数（copy constructor）。

1
2
3
4
5
6
class Foo {
public:
	Foo();
	Foo(const Foo&);  // 拷贝构造函数
	// ...
};

拷贝构造函数定义了如何用一个对象初始化另一个同类型的对象。拷贝初始化通常使用拷贝构造函数来完成。拷贝初始化发生在下列情况中：

  • 使用等号（=）初始化一个变量
  • 将一个对象作为实参传递给一个非引用类型的形参
  • 从一个返回类型为非引用类型的函数返回一个对象
  • 用花括号列表初始化一个数组中的元素

拷贝赋值运算符

类的拷贝赋值运算符（copy-assignment operator）是一个名为operator=的函数。类似于其他任何函数，它也有一个返回类型和一个参数列表。

1
2
3
4
5
6
class Foo {
public:
	Foo();
	Foo& operator=(const Foo&);  // 赋值运算符
	// ...
};

拷贝赋值运算符定义了如何将一个对象赋值给另一个同类型的对象。赋值运算符是一个成员函数也是一个二元运算符，其左侧运算对象就绑定到隐式的this指针，右侧运算对象作为显式参数传递。注意：为了与内置类型的赋值保持一致，赋值运算符通常返回一个指向其左侧运算对象的引用。

析构函数

类的析构函数（destructor）用来释放类对象使用的资源并销毁类对象的非static数据成员，无论何时只要一个对象被销毁，就会自动执行析构函数。

1
2
3
4
5
class Foo {
public:
	~Foo();  // 析构函数
	// ...
};

析构函数的名字由波浪号（~）加类名构成，也没有返回类型。由于析构函数不接受参数，因此它不能被重载。析构函数有一个函数体和一个析构部分，销毁一个对象时，首先执行析构函数体，然后按初始化顺序的逆序销毁成员。

运算符的重载

重载的运算符是具有特殊名字的函数：它们的名字由关键字operator和其后要定义的运算符号共同组成。和其他函数一样，重载的运算符也包含返回类型、参数列表、函数体，比如拷贝赋值运算符。

当我们定义重载的运算符时，必须首先决定是将其声明为类的成员函数还是声明为一个普通的非成员函数。有些运算符必须作为成员，而另一些运算符作为普通函数比作为成员更好：

  • 赋值（=）、下标（[ ]）、调用（( )）和成员访问箭头（->）运算符必须是成员。
  • 复合赋值运算符一般来说应该是成员，但并非必须，这一点与赋值运算符略有不同。
  • 改变对象状态的运算符或者与给定类型密切相关的运算符，如递增、递减、解引用运算符，通常应该是成员。
  • 具有对称性的运算符可能转换任意一端的运算对象，例如算术、相等性、关系和位运算符等，因此它们通常应该是普通的非成员函数。

当然，除了赋值运算符之外，我们还需要为动态数组定义下标运算符operator []。下标运算符必须是成员函数。为了让下标可以出现在赋值运算符的任意一端，下标运算符函数通常返回所访问元素的引用。

动态数组类的封装

下面给出了动态数组DArray类的接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class DArray
{
private:
	double *m_Data;  // 存放数组的动态内存指针
	int m_Size;      // 数组的元素个数
	int m_Max;       // 预留给动态数组的内存大小
private:
	void Init();     // 初始化
	void Free();     // 释放动态内存
	inline bool InvalidateIndex(int nIndex);  // 判断下标的合法性
public:
	DArray();        // 默认构造函数
	DArray(int nSize, double dValue = 0);  // 构造函数，设置数组大小，默认值为dValue
	DArray(const DArray& arr);  // 拷贝构造函数
	DArray& operator=(const DArray& arr);  // 拷贝赋值运算符
	~DArray();       // 析构函数

	void Print();    // 输出显式所有数组元素的值
	int GetSize();   // 获取数组的大小（元素个数）
	void SetSize(int nSize);  // 重新设置数组的大小
	double GetAt(int nIndex);  // 获取指定位置元素
	void SetAt(int nIndex,double dValue); // 重置指定元素的值
	void PushBack(double dValue);  // 追加一个新元素到数组末尾
	void DeleteAt(int nIndex);     // 删除指定位置地元素
	void InsertAt(int nIndex, double dValue);  // 插入一个新的元素到数组中
	double operator[](int nIndex) const;      // 重载下标运算符[]
};

下面是我的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
void DArray::Init()
{
	m_Size = 0;   // 默认情况下数组不包含元素
	m_Max = 1;
	m_Data = new double[m_Max];
}

void DArray::Free()
{
	delete [] m_Data;
}

bool DArray::InvalidateIndex(int nIndex)
{
	if(nIndex>=0 && nIndex<m_Size)
		return false;
	else
		return true;
}

// 默认构造函数
DArray::DArray()
{
	Init();
}

// 构造函数
DArray::DArray(int nSize, double dValue)
{
	if(nSize == 0)
		Init();
	else
	{
		m_Size = nSize;
		m_Max = nSize*2;
		m_Data = new double[m_Max];
		for(int i=0; i<nSize; ++i)
			m_Data[i]=dValue;
	}
}

// 拷贝构造函数
DArray::DArray(const DArray& arr)
{
	m_Size = arr.m_Size;  /*复制常规成员*/
	m_Max = arr.m_Max;
	m_Data = new double[m_Max];   /*复制指针指向的内容*/
	memcpy(m_Data, arr.m_Data, m_Size*sizeof(double));
}

// 拷贝赋值运算符
DArray& DArray::operator=(const DArray& arr)
{
	if(this == &arr)  /*自赋值*/
		return *this;
	m_Size = arr.m_Size;
	m_Max = arr.m_Max;
	/* 先将右侧对象拷贝到临时对象中，然后再销毁左侧对象*/ 
	double *m_Temp = new double[m_Max];
	memcpy(m_Temp, arr.m_Data, m_Size*sizeof(double));
	delete [] m_Data;
	m_Data = m_Temp;

	return *this;
}

// 析构函数
DArray::~DArray()
{
	Free();
}

// 打印数组
void DArray::Print()
{
	if(m_Size == 0)
	{
		cout << "Error: The empty array can't be Printed." << endl;
		exit(0);
	}
	else
	{
		for(int i=0; i<m_Size; ++i)
			cout << m_Data[i] << " ";
		cout << endl;
	}
}

// 获取数组大小
int DArray::GetSize()
{
	return m_Size;
}

// 重置数组大小
void DArray::SetSize(int nSize)
{
	if(nSize < m_Size)   /*截断*/
	{
		for(int i=nSize; i<m_Size; ++i)
			m_Data[i] = 0;
	}
	if(m_Size<=nSize && nSize<=m_Max)  /*新增元素置0*/
	{
		for(int i=m_Size; i<nSize; ++i)
			m_Data[i] = 0;
	}
	if(nSize > m_Max)   /*需要重新分配空间*/
	{
		m_Max = nSize*2;
		double *temp = new double[m_Max];
		memcpy(temp, m_Data, m_Size*sizeof(double));
		for(int i=m_Size; i<nSize; ++i)
			temp[i] = 0;
		delete [] m_Data;
		m_Data = temp;
	}
	m_Size = nSize; /*设置数组大小*/
}

// 获取指定位置元素
double DArray::GetAt(int nIndex)
{
	if(InvalidateIndex(nIndex))
	{
		cout << "Error: the index of GetAt is invalid!" << endl;
		exit(0);
	}
	return m_Data[nIndex];
}

// 设置指定位置元素的值
void DArray::SetAt(int nIndex, double dValue)
{
	if(InvalidateIndex(nIndex))
	{
		cout << "Error: the index of SetAt is invalid!" << endl;
		exit(0);
	}
	else
	{
		m_Data[nIndex] = dValue;
	}
}

// 追加一个新元素到数组末尾
void DArray::PushBack(double dValue)
{
	if(m_Size < m_Max)
	{
		m_Data[m_Size] = dValue;
	}
	else  
	{
		m_Max = m_Max*2;
		double* temp = new double[m_Max];
		memcpy(temp, m_Data, m_Size*sizeof(double));
		delete [] m_Data;
		m_Data = temp;
		m_Data[m_Size] = dValue;
	}
	++m_Size;  /*数组大小加1*/
}

// 从数组中删除一个元素
void DArray::DeleteAt(int nIndex)
{
	if(InvalidateIndex(nIndex))
	{
		cout << "Error: the index of DeleteAt is invalid." << endl;
		exit(0);
	}
	else
	{	
		for(int i=nIndex; i<m_Size; ++i)
			m_Data[i] = m_Data[i+1];
		m_Data[m_Size-1] = 0;
		--m_Size;
	}
}

// 插入一个新元素到指定位置
void DArray::InsertAt(int nIndex, double dValue)
{
	if(nIndex<0 || nIndex>m_Size)
	{
		cout << "Error: the index of InsertAt is invalid!" << endl;
		exit(0);
	}

	if(m_Size < m_Max)  /* 未满，插入 */
	{
		for(int i=m_Size-1; i>=nIndex; --i)
			m_Data[i+1] = m_Data[i];
		m_Data[nIndex] = dValue;
	}
	else               /* 重新分配空间 */
	{
		m_Max = m_Max*2;
		double* temp = new double[m_Max];
		memcpy(temp, m_Data, m_Size*sizeof(double));
		delete [] m_Data;
		m_Data = temp;
		for(int i=m_Size-1; i>=nIndex; --i)
			m_Data[i+1] = m_Data[i];
		m_Data[nIndex] = dValue;
	}
	++m_Size;  /* 数组大小加1 */
}

// 重载下标运算符[]
double DArray::operator[](int nIndex) const
{
	if(nIndex<0 || nIndex>=m_Size)
	{
		cout << "Error: the index in [] is invalid!" << endl;
		exit(0);
	}
	return m_Data[nIndex];
}

经过简单的测试，暂时还没有发现Bug。可能测试并不全面，如果你发现了问题，希望你能在评论里告诉我，万分感谢！！！



附：String类的实现

C++ 的一个常见面试题是让你实现一个 String 类，限于时间，不可能要求具备 std::string 的功能，但至少要求能正确管理资源。

如果你弄懂了上面DArray类的写法，那么实现String类应该就不难了。因为面试官一般只是想考查你能不能正确地写出构造函数、析构函数、拷贝构造函数、拷贝赋值运算符以及+、[ ]、<<、>>运算符重载等等。下面给出一个String类的接口，你可以自己试试手实现一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class String{  
    friend ostream& operator<< (ostream&,String&); //重载<<运算符  
    friend istream& operator>> (istream&,String&); //重载>>运算符  
public:  
    String();   // 默认构造函数
    String(const char* str);       // 带参构造函数  
    String(const String& rhs);        // 拷贝构造函数 
    String& operator=(const String& rhs);   // 拷贝赋值运算符  
    String operator+(const String& rhs) const;  //operator+  
    bool operator==(const String&);              //operator==
    bool operator!=(const String&);              //operator!=   
    char& operator[](unsigned int);              //operator[]  
    size_t size() const;  
    const char* c_str() const;
    ~String();    // 析构函数 
private:  
    char *m_data; // 用于保存字符串  
};

下面是String类的实现，注意一些得分点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// 默认构造函数
String::String()
	:m_data(new char[1])
{
	m_data[0] = '\0';  /*得分点：空字符串存放结束标志'\0'*/
}

// 带参的构造函数
String::String(const char* str)
	:m_data(new char[strlen(str)+1])
{
	strcpy(m_data,str);
}

// 拷贝构造函数
String::String(const String& rhs)
{
	m_data = new char[strlen(rhs.m_data)+1];
	strcpy(m_data, rhs.m_data);
}

// 拷贝赋值运算符
String& String::operator=(const String& rhs)
{
	if(this == &rhs)  /*得分点：自赋值*/
		return *this;  
	delete [] m_data; /*得分点：释放左侧对象资源*/
	m_data = new char[strlen(rhs.m_data)+1];
	strcpy(m_data, rhs.m_data);
	return *this;
}

// 析构函数
String::~String()
{
	delete [] m_data;
}

// operator+
String String::operator+(const String& rhs) const
{
	String newStr;
	newStr.m_data = new char[strlen(m_data)+strlen(rhs.m_data)+1];
	strcpy(newStr.m_data, m_data);
	strcat(newStr.m_data, rhs.m_data);
	return newStr;
}

// operator==
bool String::operator==(const String& rhs)
{
	if(strcmp(m_data, rhs.m_data) == 0) /*相等返回0*/
		return true;
	else
		return false;
}

// operator!=
bool String::operator!=(const String& rhs)
{
	return !(*this == rhs);
}

// operator[]
char& String::operator[](unsigned int index)
{
	if(index>=0 && index<strlen(m_data))
	{
		return m_data[index];
	}
	else
	{
		cout << "Error: the index of [] is invalid." << endl;
		exit(0);
	}
}

// 获取String大小
size_t String::size() const
{
	return strlen(m_data);
}

// 获取C风格字符串
const char* String::c_str() const
{
	return m_data;
}

// 重载<<运算符
ostream& operator<<(ostream& os, String& str)
{
	os << str.m_data;
	return os;
}

// 重载>>运算符
istream& operator>>(istream& is, String& str)
{
	char temp[255];
	is >> temp;
	str = temp;
	return is;
}