C++模板机制 && ArrayList数据结构

ArrayList是java集合中重要的数据结构，用于数组动态存取，这里用C++参考jdk实现简单的ArrayList数据结构

• 使用数组

数组需要指定初始化长度，比如这里如果是int，长度是16*4

T arr[16];

• 使用指针

数组指针长度固定是8，扩容相对方便，这里使用指针数组

T *arr;

• C++ 方式

c++中一般用new delete，当然C++兼容C

开辟空间

this->arr = new T[this->size];

销毁空间

delete[] this->arr;

• C 方式

c中一般用 malloc free

开辟空间

this->arr = (T *)malloc(sizeof(T) * this->size);

销毁空间

free(this->arr);

#pragma once

//泛型
template

class ArrayList {
public:
    //默认构造
    ArrayList();

    //不能通过隐士调用
    explicit ArrayList(int capacity);

    //拷贝构造函数
    ArrayList(const ArrayList &arrayList);

    // 析构函数
    ~ArrayList();

    //新增
    void add(T val);

    //指定位置新增
    void add(T val, int size);

    //取数据
    T *get(int pos);

    //移除数据
    void remove(int index);

    //长度
    int getLength();

    //判空
    bool isEmpty();

    //数组不够了 扩容机制
    void resize();

private:
    //数组长度
    int size;

    //当前容量
    int actulSize;

    //1、用数组，长度是16*4
//    int arr2[16];
    //2、用指针,长度固定是8
    T *arr;
};

注意这里拷贝构造函数传的是别名，可能会改变源数据，因此可以根据实际情况选择需求和性能的折中点，关于参数为类、类指针、类别名可以参考C++核心知识梳理

#include "ArrayList.h"
#include "iostream"

using namespace std;

template
ArrayList::ArrayList(int capacity) {
    this->actulSize = 0;
    this->size = capacity;
    //开辟了要销毁new  delete  / malloc  free
    this->arr = new T[this->size];
}

template
ArrayList::~ArrayList() {
    if (this->arr != NULL) {
        delete[] this->arr;
        this->arr = NULL;
    }
}

template
ArrayList::ArrayList() {
    //默认长度
    this->size = 16;
    this->actulSize = 0;
    this->arr = new T[this->size];
}

template
//拷贝构造函数
ArrayList::ArrayList(const ArrayList &arr) {
    this->actulSize = arr.actulSize;
    this->size = arr.size;
    this->arr = new T[arr.size];
    for (int i = 0; i < size; ++i) {
        this->arr[i] = arr.arr[i];
    }
}

template
void ArrayList::add(T val) {
//    actulSize 最后一个位置  0
    add(val, actulSize);
}

template
void ArrayList::add(T val, int index) {
    if (index < 0 || index > size) {
        return;
    }
//    扩容 --->   0.75
    if (this->actulSize >= size) {
        resize();
    }
//    下标法    地址法
//   (*( this->arr+index)) = val;
    this->arr[index] = val;
    actulSize++;

}

template
void ArrayList::resize() {
    cout << "----------------resize-------" << endl;
    int newLength = size * 2;
    T *p = new T[newLength];
    for (int i = 0; i < size; ++i) {
        *(p + i) = arr[i];
    }
    delete[] this->arr;
    this->arr = p;
    this->size = newLength;
}

template
T *ArrayList::get(int index) {
    if (index < 0 || index > size) {
        return NULL;
    }

    return &this->arr[index];
}

template
void ArrayList::remove(int index) {
    if (index < 0 || index > size) {
        return;
    }
    //获取要移除的目标元素 arr[index]
    for (int i = index; i < size - 1; ++i) {
        arr[i] = arr[i + 1];
    }
    actulSize--;
}

template
int ArrayList::getLength() {
    return actulSize;
}

template
bool ArrayList::isEmpty() {
    return actulSize == 0;
}

#include 
#include "Arraylist.cpp"

using namespace std;

class Point {
public:
    int x;
    int y;

    Point() {
//        cout << "构造" << endl;//flush
    }

    Point(int x, int y) {
        this->x = x;
        this->y = y;
        cout << "构造-> Point(x=" << x << ",y=" << y << ")" << endl;//flush
    }

    Point(Point &p) {
        this->x = *new int;
        this->x = p.x;
        this->y = *new int;
        this->y = p.y;
    }

    void toString() const {
        cout << "toString-> Point(x=" << x << ",y=" << y << ")" << endl;//flush
    }
};

int main() {
    ArrayList points;
    Point p1(1, 2);
    Point p2(3, 4);
    Point p3(5, 6);
    Point p4(7, 8);
    points.add(p1);
    points.add(p2);
    points.add(p3);
    points.add(p4);
    points.remove(0);

    for (int i = 0; i < points.getLength(); ++i) {
        points.get(i)->toString();
    }
    return 0;
}

打印结果：

构造-> Point(x=1,y=2)
构造-> Point(x=3,y=4)
构造-> Point(x=5,y=6)
构造-> Point(x=7,y=8)
toString-> Point(x=3,y=4)
toString-> Point(x=5,y=6)
toString-> Point(x=7,y=8)