常用語言中的動態(tài)數(shù)組的示例包括Java和C＃中的ArrayList讯柔，C ++中的Vector缨历，.NET中的List <>，Python的list等
我們這里實現(xiàn)的動態(tài)數(shù)組與上述各種語言中的相似，動態(tài)數(shù)組的大小可以在運行時動態(tài)修改。動態(tài)數(shù)組的元素占用連續(xù)的內存塊雄可，一旦創(chuàng)建，就無法更改其大小缠犀。 當內存空間所剩無幾数苫，就可以分配更大的內存塊，將內容從原始數(shù)組復制到該新空間辨液，然后繼續(xù)填充可用的"插槽"虐急。動態(tài)數(shù)組在創(chuàng)建時會分配預定數(shù)量的內存，然后在需要時以一定的比例增長室梅。 這些參數(shù)，初始大小和增長因子在性能方面至關重要疚宇。 如果初始大小和增長因子較小亡鼠，那么您最終將不得不經(jīng)常重新分配內存，這對性能方面并不理想敷待； 另一方面间涵，如果分配的內存塊過高，則可能會有大量空閑的堆內存塊榜揖，并且調整大小操作可能需要更長的時間勾哩。 這里的權衡是非常重要的。
其實我這里的動態(tài)數(shù)組的實現(xiàn),內存分配機制是模仿举哟，C++標準庫中的vector/string思劳，他們從內存池中申請的內存塊數(shù)量是上一次申請內存塊數(shù)量的2倍。這個是增長因子充分平衡了性能和內存空間的消耗妨猩。
類接口
C語言編寫一個動態(tài)整數(shù)數(shù)組,但要兼容不同的基本數(shù)據(jù)類型,你可能要需要編寫較為復雜宏函數(shù)來模擬C++泛型相同的效果潜叛。而C++本身已經(jīng)集成了模板和類的垃圾回收機制,以模板為基礎的泛型技術可以很輕松地編寫出管理任何數(shù)據(jù)類型和自動內存回收的動態(tài)數(shù)組-v-!!，那么實現(xiàn)動態(tài)數(shù)組的首選語言就是C++了壶硅，我們定義了動態(tài)數(shù)組的類接口威兜。
#define CAPACITY 15
#define SHK_FACTOR 3
#define EXP_FACTOR 2
template <typename T>
class ArrayList
{
private:
T *d_arr;
size_t d_capacity;
size_t d_size;
void expand(void);
void shrink(void);
long cvt_signed_number(size_t n);
inline void set_capacity(size_t n);
public:
//默認的構造函數(shù)
ArrayList();
//自定義的構造函數(shù)
ArrayList(const size_t &&n);
//自定義的構造函數(shù)
ArrayList(const T *data, size_t n);
//copy構造函數(shù)
ArrayList(const ArrayList &oth);
//move構造函數(shù)
ArrayList(ArrayList &&oth) : d_size(oth.d_size);
~ArrayList();
//下標訪問
T &operator[](long n);
//ArrayLIst尺寸
size_t size() const;
//ArrayList當前分配內存數(shù)
size_t capacity() const;
//交換兩個ArrayList對象
void swap(ArrayList &oth);
//尾部插入
void push_back(const T &v);
void show_array();
//查找特定元素值的索引,約定返回size_t的上限值表示找不到元素
inline size_t find(const T &v);
//按值刪除
bool remove(const T &v);
//刪除指定索引的值
void removeAt(long n);
//按索引位置插入值
void insert(size_t ix, T v);
//尾部彈出數(shù)據(jù)
T pop();
//清空整個容器
void clean();
};
構造函數(shù)的實現(xiàn)
//默認的構造函數(shù)
template <class T>
ArrayList<T>::ArrayList()
{
d_size = 0;
d_capacity = CAPACITY;
d_arr = new T[d_capacity];
}
//自定義的構造函數(shù)
template <class T>
ArrayList<T>::ArrayList(const size_t &&n) : d_size(n)
{
set_capacity(n);
d_arr = new T[d_capacity];
}
//自定義的構造函數(shù)
template <class T>
ArrayList<T>::ArrayList(const T *data, size_t n)
: d_capacity(CAPACITY)
{
if (n > 0)
{
std::cout << "ArrayList 普通函數(shù)調用" << std::endl;
d_arr = new T[n];
for (size_t i = 0; i < n; i++)
{
*(d_arr + i) = *(data + i);
}
d_size = n;
}
};
//copy構造函數(shù)
template <class T>
ArrayList<T>::ArrayList(const ArrayList &oth)
: d_size(oth.d_size)
{
std::cout << "ArrayList copy函數(shù)調用" << std::endl;
set_capacity(oth.d_size);
d_arr = new T[d_capacity];
for (size_t i = 0; i < oth.d_size; i++)
{
*(d_arr + i) = *(oth.d_arr + i);
}
};
//move構造函數(shù)
template <class T>
ArrayList<T>::ArrayList(ArrayList &&oth) : d_size(oth.d_size)
{
std::cout << "ArrayList move函數(shù)調用" << std::endl;
d_arr = oth.d_arr;
oth.d_size = 0;
oth.d_arr = nullptr;
}
析構函數(shù)的實現(xiàn)
顯式定義構造函數(shù)是一個非常好的習慣,對于很多的內存回收的文章講述的僅僅是delete[]操作釋放堆內存,而沒有將指向堆內存的T類型指針重置為nullptr，我認為這是一個很好的習慣庐椒，C風格中的回收內存的小技巧椒舵，這個是值得繼承的好習慣,我為什么這么說？
若將內部d_arr的T類型指針在delete[]前约谈，你可以嘗試用一個全局變量p來緩存該指針,且d_arr沒有重置為nullptr的話笔宿，你再次使用該全局變量p犁钟，會仍然訪問到原來指針所指向內存區(qū)域的數(shù)據(jù),雖然原有的內存返回給堆管理器了，但原本的數(shù)據(jù)值還在內存塊,對于程序的數(shù)據(jù)保密性不是個好主意措伐。
//內存回收
template <class T>
ArrayList<T>::~ArrayList()
{
std::cout << "ArrayList析構函數(shù)" << std::endl;
if (d_arr != nullptr)
{
delete[] d_arr;
}
}
內存擴容的實現(xiàn)
expand()是一個私有的內部成員函數(shù),它內部完成了向內存池申請比現(xiàn)有內存更大的內存空間(是原有內存空間的2倍)特纤，然后將原有內存空間中的元素拷貝到新的內存空間，最后將舊的內存空間釋放返還給內存池侥加。具體示意圖如下：
expand成員函數(shù)的實現(xiàn)
//內部擴容操作
template <class T>
void ArrayList<T>::expand()
{
d_capacity = d_size * EXP_FACTOR;
T *tmp = new T[d_capacity];
for (auto i = 0; i < d_size; i++)
{
*(tmp + i) = *(d_arr + i);
}
delete[] d_arr;
d_arr = tmp;
}
shrink()成員函數(shù)的實現(xiàn)
關于如何將超出額度的空閑的內存返還給內存池捧存，我這里定制的策略的是在每次pop/或者remove操作過程中，我們都檢測d_capacity/d_size的比值担败，如果該比值達到3昔穴，我們就調用shrink()成員函數(shù),將額外閑置的內存返還給內存池,僅保留的內存總量是以使用的2倍,也就是空閑的內存僅僅是以使用的1倍多一點。
如上圖示例所示提前，我們假設分配了32個內存塊給順序表,在操作順序表的過程當中吗货，已存在的元素是10個的話，我們會將原有的內存塊所見縮減為20個內存塊,當縮減后的空閑內存塊是已用內存塊的1倍多一點狈网。
//內存收縮操作
template <class T>
void ArrayList<T>::shrink(){
size_t k = d_capacity / d_size;
if (k >= SHK_FACTOR)
{
d_capacity = d_size * EXP_FACTOR;
T *tmp = new T[d_capacity];
for (auto i = 0; i < d_size; i++)
{
*(tmp + i) = *(d_arr + i);
}
delete[] d_arr;
d_arr = tmp;
}
}
重載operator [] (int)
我們希望順序表是可以類似Python的list那樣提供逆序訪問的能力宙搬，比方說,對于一個長度為9的列表,我們通過下標 a[-1]等價于訪問a[8]的元素，請參見如下圖拓哺。
實現(xiàn)類似Python列表的訪問能力非常簡單,上圖我們知道對應位置的順序index(用m表示)和逆序index(用n表示)的絕對值的和等于該列表的長度(用length表示,始終是非負數(shù))勇垛，我們得到如下簡單的結論。
若 n<0且-length ≤ n < 0;
那么m=length+n,且0≤m≤length-1
即n的有效范圍 可以 0≤n≤length-1 或 -length ≤n <0
實際上我們若提供一個的負整數(shù)n時,(-length ≤ n < 0)士鸥，最終會轉換回順序index的非負整數(shù)闲孤，那么operator[]的索引操作符重寫如下。在重載operator[]的同時烤礁，我們需要面size_t類型的d_size轉換為帶符號的整數(shù)的問題讼积，具體的問題描述可以看我之前寫的隨筆《C/C++ 有符號和無符號數(shù)字的迷途》
template <class T>
inline long ArrayList<T>::cvt_signed_number(size_t n)
{
size_t x = static_cast<size_t>(std::numeric_limits<long>::max());
if (n > x)
{
clean();
throw std::overflow_error("參數(shù)n轉換錯誤");
}
return static_cast<long>(n);
}
template <class T>
inline void ArrayList<T>::set_capacity(size_t n)
{
if (n > CAPACITY)
{
d_capacity = n * EXP_FACTOR;
}
else
{
d_capacity = CAPACITY;
}
}
template <class T>
T &ArrayList<T>::operator[](long n)
{
long size = cvt_signed_number(d_size);
if (n >= size || n < -size)
{
std::cout << "ArrayList下標溢出" << std::endl;
ArrayList<T>::clean();
exit(0);
}
if (n >= 0)
{
return d_arr[n];
}
else
{
return d_arr[d_size + n];
}
}
刪除特定位值的元素
其實沒什么好說的，刪除中間位值的元素脚仔，實際上就是從傳入索引位值算起勤众，后續(xù)的元素依次將其元素值向各自的前一個元素拷貝并覆蓋原先的元素值，拷貝過程結束后鲤脏，d_size減1决摧，最后一個元素會被作為一個閑置的內存塊留作以后的備用,這個過程的時間消耗是O(n)原理圖如下：
remove成員函數(shù)實現(xiàn)
//刪除特定的元素
//按值刪除
bool remove(const T &v)
{
if (d_size > 0)
{
size_t k = 0;
//查找元素所在索引位置
k = find(v);
std::cout << "刪除的元素index是:" << k << std::endl;
if (k == std::numeric_limits<size_t>::max())
{
std::cout << "沒有找到該元素" << std::endl;
return false;
}
for (auto j = k; j < d_size; j++)
{
d_arr[j] = d_arr[j + 1];
}
--d_size;
shrink();
return true;
}
return false;
}
removeAt()成員函數(shù)實現(xiàn)
//刪除指定索引的元素
//刪除指定索引的值
void removeAt(long n)
{
long size = cvt_signed_number(d_size);
if (n >= size || n < -size)
{
clean();
std::cout << "Error: out of index!!" << std::endl;
}
long k = (n >= 0) ? n : size + n;
for (auto j = k; j < size; j++)
{
d_arr[j] = d_arr[j + 1];
}
d_size = --size;
shrink();
}
從特定位值插入元素
從特定的位值插入元素,際上就是從傳入索引位值算起，后續(xù)的元素依次將其元素值向各自的后一個元素拷貝并覆蓋原先的元素值凑兰，拷貝過程結束后掌桩，修改指定索引的元素的值,d_size增加1,備用內存塊即減少1。但插入元素很可能導致分配的內存塊空間所剩無幾,所以每次插入操作前姑食，都需要通過比較d_size和d_capacity兩個計數(shù)器波岛，如果d_size等于或大于d_capacity即會觸發(fā)內部的expand函數(shù)申請內存擴容。expand成員函數(shù)的行為可以查看上文的描述音半。插入元素本身的時間消耗就是O(n),加之expand的時間消耗也是O(n)则拷，所以此時的時間成本是最高的贡蓖。
//按索引位置插入值
template <class T>
void ArrayList<T>::insert(size_t ix, T v)
{
size_t old_size = d_size;
++d_size;
if (d_size >= d_capacity)
{
expand();
}
size_t e = old_size - 1;
if (ix < e)
{
//在插入元素的索引的后續(xù)元素往后移動
for (auto k = e; k >= ix; k--)
{
d_arr[k + 1] = d_arr[k];
}
d_arr[ix] = v;
}
}
查找元素
//查找特定元素值的索引,約定返回size_t的上限值表示找不到元素
inline size_t ArrayList<T>::find(const T &v)
{
if (d_size > 0)
{
for (auto i = 0; i < d_size; i++)
{
if (d_arr[i] == v)
{
return i;
}
}
}
return std::numeric_limits<size_t>::max();
}
清空所有元素
//清空整個列表
template <class T>
void ArrayList<T>::clearn()
{
delete[] d_arr;
d_size = d_capacity = 0;
}
尾部插入
//尾部插入元素
template <class T>
void ArrayList<T>::push(T value)
{
if (d_size >= d_capacity)
{
expand();
}
*(d_arr + d_size++) = value;
length = d_size;
}
尾部彈出
//尾部彈出數(shù)據(jù)
template <class T>
T ArrayList<T>::pop()
{
--d_size;
shrink();
return d_arr[d_size];
}
清空整個列表
template <class T>
void ArrayList<T>::clearn()
{
delete[] d_arr;
d_size = d_capacity = d_idles = length = capacity = 0;
}
顯示數(shù)組
//顯示數(shù)組
template <class T>
void ArrayList<T>::show_array()
{
std::cout << "[";
for (size_t i = 0; i < d_size - 1; i++)
{
std::cout << *(d_arr + i) << ",";
}
std::cout << d_arr[d_size - 1] << "]" << std::endl;
}
最后順序表的API測試
#include <iostream>
using namespace std;
void ArrayListTest(){
ArrayList<int> arr;
for (size_t i = 0; i < 32; i++)
{
std::cout << i << ":push_back(" << i * 3 << ")" << std::endl;
sleep(1);
arr.push_back(i * 3);
}
arr.show_array();
cout << "size():" << arr.size() << endl;
cout << "capacity:" << arr.capacity() << endl;
int i = 0;
while (arr.size() >= 10)
{
std::cout << i << ":remove first elem(" << arr[0] << ")" << std::endl;
sleep(0.7);
arr.removeAt(0);
}
std::cout << "刪除操作測試后..." << std::endl;
arr.show_array();
cout << "size():" << arr.size() << endl;
cout << "capacity:" << arr.capacity() << endl;
std::cout << "push操作測試..." << std::endl;
for (size_t i = 0; i < 5; i++)
{
arr.push_back(2 * (10 - i));
std::cout << i << "arr.push_back(" << arr[-1] << ")" << std::endl;
sleep(1);
}
arr.show_array();
cout << "size():" << arr.size() << endl;
cout << "capacity:" << arr.capacity() << endl;
std::cout << "索引操作符測試..." << std::endl;
cout << "arr[-1]:" << arr[-1] << endl;
cout << "arr[-3]:" << arr[-3] << endl;
cout << "arr[-10]:" << arr[-10] << endl;
arr.show_array();
cout << "size():" << arr.size() << endl;
cout << "capacity:" << arr.capacity() << endl;
cout << "在索引 6位值插入操作" << endl;
arr.insert(6, 345);
arr.show_array();
cout << "pop 操作彈出: " << arr.pop() << " 之后size()是 " << arr.size() << endl;
cout << "pop 操作彈出: " << arr.pop() << "之后size()是 " << arr.size() << endl;
cout << "pop 操作彈出: " << arr.pop() << " 之后size()是 " << arr.size() << endl;
arr.show_array();
arr.remove(345);
cout << "刪除元素后:"
<< "當前size()是" << arr.size() << endl;
arr.show_array();
std::cout << "swap測試" << std::endl;
int x[5] = {1, 2, 3, 4, 5};
int y[3] = {71, 14, 32};
ArrayList<int> a(x, 5);
ArrayList<int> b(y, 3);
a.swap(b);
std::cout << "a:" << std::endl;
a.show_array();
std::cout << "b:" << std::endl;
b.show_array();
}
int main(int argc, char const *argv[])
{
ArrayList<int> v1(1000);
ArrayList<int> v2(std::move(v1));
return 0;
}
以下這是測試結果，
結語
這個ArrayList是后門討論排序算法煌茬，設計模式斥铺，以及C++其他高級特性會經(jīng)常用到的,并且這個順序表用到了很多C++的特性，它的內存管理和C++標準的順序容器是類似的坛善。OK性能測試的話晾蜘，等我將全系列的數(shù)據(jù)結構寫完，再與C++內置的容器做個性能分析眠屎。
