C++详解如何实现动态数组

动态数组

示例代码

运行环境

运行效果

动态数组

动态数组Vector可以动态扩展内存，其采用连续的内存空间，当内存空间不足，便以原来的容量的2倍或者1.5倍成倍的扩展，将原有的数组元素拷贝到新分配的内存空间中，释放原有的内存空间，新的元素将存入的新分配的内存空间。

示例代码

动态数组vector的size函数和capacity函数，分别作为求数组中现有的元素的个数和数组所能容纳的元素的个数。下面直接上实现的代码。

DynamicArray .h

#pragma once
class DynamicArray {
public:
DynamicArray();
~DynamicArray();
void push_back_Array(int value);
void insertValueByPosArray(size_t pos,int value);
void removeByValueFromArray(int value);
void removeByPosFromArray(size_t pos);
int findPosByValueArray(int value);
int findValueByPosArray(size_t pos);
void reclaimSpaceArray();
void clearArray();
int getCapacity();
int getCount();
void printArray();
private:
int *m_pArr;
size_t m_size;
size_t m_capacity;
};

DynamicArray .cpp

#include "DynamicArray.h"
#include <iostream>
using namespace std;
// DynamicArray.cpp 
DynamicArray::DynamicArray()
{
m_size = 0;
m_capacity = 20;
m_pArr = new int[m_capacity];
if (m_pArr == nullptr)
{
cout << "new 开辟空间失败" << endl;
}
}
DynamicArray::~DynamicArray()
{
if (m_pArr != nullptr) 
{
delete[] m_pArr;
m_pArr = nullptr;
}
m_size = 0;
m_capacity = 0;
}
void DynamicArray::push_back_Array(int value)//push_back
{
if (m_pArr == nullptr)
{
return;
}
reclaimSpaceArray();
m_pArr[m_size] = value;
m_size++;
}
void DynamicArray::insertValueByPosArray(size_t pos, int value)//插入insert(可以在前，中，后插入)
{
if (m_pArr == nullptr)
{
return;
}
reclaimSpaceArray();
for (size_t i = m_size - 1; i >= pos; --i)//pos为下标的数，从0开始
{
m_pArr[i + 1] = m_pArr[i];
}
m_pArr[pos] = value;
m_size++;
}
void DynamicArray::removeByValueFromArray(int value)
{
if (m_pArr == nullptr)
{
return;
}
int nPos = findPosByValueArray(value);
removeByPosFromArray(nPos);
}
void DynamicArray::removeByPosFromArray(size_t pos)//pos为下标的数，从0开始
{
if (m_pArr == nullptr)
{
return ;
}
if (pos < 0 || pos >= m_size)//pos的最大值为m_size-1
{
return ;
}
//找到被删除位置的下一位
for (size_t i = pos + 1; i < m_size; ++i)
{
m_pArr[i - 1] = m_pArr[i];
}
m_size--;
}
int DynamicArray::findPosByValueArray(int value)
{
size_t nPos = -1;
if (m_pArr == nullptr)
{
return nPos;
}
for (size_t i = 0; i < m_size; ++i)
{
if (m_pArr[i] == value)
{
nPos = i;
break;
}
}
return nPos;
}
int DynamicArray::findValueByPosArray(size_t pos)
{
if (m_pArr == nullptr)
{
return -1;
}
if (pos < 0 || pos >= m_size)
{
return -1;
}
return m_pArr[pos];
}
void DynamicArray::reclaimSpaceArray()
{
if (m_size == m_capacity)
{
int *newArr = new int[m_capacity * 2];
if (newArr == nullptr)
{
cout << "new 开辟空间失败" << endl;
return;
}
memset(newArr, 0, m_capacity * 2 * sizeof(int));//第三个参数为字节数
memcpy(newArr, m_pArr, m_size * sizeof(int));//第三个参数为字节数
//下面这种逐个赋值的方式也可以使用
//for (size_t i = 0; i < m_capacity; i++)
//{
//newArr[i] = m_pArr[i];
//}
m_capacity = m_capacity * 2;
if (m_pArr) {
delete[] m_pArr;
m_pArr = nullptr;
}
m_pArr = newArr;
}
}
void DynamicArray::clearArray()//vector中clear()只是改变size的大小
{
m_size = 0;
}
int DynamicArray::getCapacity()
{
return m_capacity;
}
int DynamicArray::getCount()
{
return m_size;
}
void DynamicArray::printArray()
{
for (size_t i = 0; i < m_size; ++i)
{
//下面两种方式打印都可以
cout << m_pArr[i] << " ";
//int ret = findValueByPosArray(i);
//cout<< ret<< " ";
}
cout << endl;
}

main.cpp

#include <iostream>
#include "DynamicArray.h"
using namespace std;
void test() {
DynamicArray * pArray = new DynamicArray;
int i = 0;
while (i++ < 11) 
{
pArray->push_back_Array(i);
}
pArray->printArray();
cout <<"size= "<< pArray->getCount() << endl;
cout << "容量： " << pArray->getCapacity() << endl;
pArray->insertValueByPosArray(5,12);
pArray->printArray();
cout << "insert after size= " << pArray->getCount() << endl;
cout << "insert after 容量： " << pArray->getCapacity() << endl;
pArray->removeByValueFromArray(2);
pArray->printArray();
cout << "remove after size= " << pArray->getCount() << endl;
cout << "remove after 容量： " << pArray->getCapacity() << endl;
pArray->removeByPosFromArray(3);
pArray->printArray();
cout << "remove by pos after size= " << pArray->getCount() << endl;
cout << "remove by pos after 容量： " << pArray->getCapacity() << endl;
cout<<"find 2 of pos: "<<pArray->findPosByValueArray(2)<<endl;
cout << "find 8 of pos: " << pArray->findPosByValueArray(8) << endl;
cout << "value at pos of 6: " << pArray->findValueByPosArray(6) << endl;
pArray->clearArray();
cout << "size= " << pArray->getCount() << endl;
cout << "容量： " << pArray->getCapacity() << endl;
if (pArray)
{
delete pArray;
pArray = nullptr;
}
}
int main()
{
test();
return 0;
}

运行环境

以上代码的运行环境为：vs2017控制台输出程序。

运行效果