- why
- 核心代码
- 定义
- 实现
我们使用C++创建一个普通的数组长度是不能变的, 现在我们写一个类似C++ STL里面vector的数组暂且叫他ArrayList吧
核心代码当数组元素不够的时候, 创建一个长度为原来的两倍的新数组, 将数组原数组的内容拷贝到新数组
T* a = new T[__capacity * 2];
memset(a, 0, __capacity * 2 * sizeof(T));
for (size_t i = 0, l = __capacity; i < l; i++) {
a[i] = __array[i];
}
__capacity *= 2;
delete[] __array;
__array = a;
定义
template <class T>
class ArrayList {
private:
T* __array;
size_t __capacity;
size_t cur;
const static size_t DEFAULT_LENGTH;
/**
* 使用特定值n分配内存
* @param n 初始元素的个数
* @return ArrayList对象的引用
*/
ArrayList& create(size_t n);
/**
* 使用默认值分配内存
* @return ArrayList对象的引用
*/
ArrayList& recreate();
/**
* i<->j
* @param i
* @param j
*/
void swap(int i, int j);
public:
/**
* 初始化(使用默认值)
*
*/
ArrayList();
/**
* 初始化
*
* @param n 初始化元素的个数
*/
ArrayList(size_t n);
/**
* 获取当前已经使用的数组大小
*
* @return cur
*/
size_t size();
/**
* 获取分配的数组最大长度
*
* @return __capacity
*/
size_t capacity();
/**
* 获取元素对应的下标(从前到后)
* @param t 待查找的元素
* @return 元素对应的下标, 或者-1(表示没有找到)
*/
long long indexOf(const T& t);
/**
* 获取元素对应的下标(从后到前)
* @param t 待查找的元素
* @return 元素对应的下标, 或者-1(表示没有找到)
*/
long long lastIndexOf(const T& t);
/**
* 获取下标对应的元素
* @param i 下标
* @throws Index out of length
* @return 如果没报错: 下标对应的元素
*/
T& at(size_t i);
/**
* 添加新元素
*
* @param t 待添加的元素
*/
void add(const T& t);
/**
* 插入元素
*
* @param i 待插入的下标
* @param t 待插入的元素
*/
void insert(size_t i, const T& t);
/**
* 删除指定元素
*
* @param i 待删的元素的下标
* @throws Exception : Index out of range
* @return 被删除的元素
*/
T remove(size_t);
/**
* 判断是否为空(没有元素)
* @return true如果为空, 否则false
*/
bool empty();
/**
* 释放内存&指针置空
*/
~ArrayList();
/**
* 对每一个元素做func *** 作
*
* @param func 消费函数
*/
void forEach(void (*func)(T));
/**
* 判断是否相同
* @param al 需要判断的数组
* @return true 相同, 否则false
*/
bool equals(ArrayList<T>& al);
/**
* 反转数组
*/
void reverse();
/**
* 部分反转数组
* @param i 开始下标(包括)
* @param j 结束下标(包括)
*/
void reverse(int i, int j);
friend bool operator==(ArrayList<T>& al1, ArrayList<T>& al2);
friend bool operator!=(ArrayList<T>& al1, ArrayList<T>& al2);
/**
* 将数组元素输出到标准流
* @param os 标准输出流对象
* @param al 数组对象
* @return 标准输出流对象
*/
template <class U>
friend std::ostream& operator<<(std::ostream& os, const ArrayList<U>& al);
/**
* 将数组元素输出到标准流
* @param os 标准输出流对象
* @param al 数组对象的指针
* @return 标准输出流对象
*/
template <class U>
friend std::ostream& operator<<(std::ostream& os, const ArrayList<U>* al);
};
实现
template <class T>
const size_t ArrayList<T>::DEFAULT_LENGTH = 8;
template <class T>
ArrayList<T>& ArrayList<T>::create(size_t n) {
__capacity = n;
cur = 0;
__array = new T[n];
memset(__array, 0, n * sizeof(T));
return *this;
}
template <class T>
ArrayList<T>& ArrayList<T>::recreate() {
T* a = new T[__capacity * 2];
memset(a, 0, __capacity * 2 * sizeof(T));
for (size_t i = 0, l = __capacity; i < l; i++) {
a[i] = __array[i];
}
__capacity *= 2;
delete[] __array;
__array = a;
return *this;
}
template <class T>
void ArrayList<T>::swap(int i, int j) {
T tmp = this->__array[i];
this->__array[i] = this->__array[j];
this->__array[j] = tmp;
}
template <class T>
ArrayList<T>::ArrayList() {
create(DEFAULT_LENGTH); // 不接收
}
template <class T>
ArrayList<T>::ArrayList(size_t n) {
create(n);
}
template <class T>
size_t ArrayList<T>::size() {
return cur;
}
template <class T>
size_t ArrayList<T>::capacity() {
return __capacity;
}
template <class T>
long long ArrayList<T>::indexOf(const T& t) {
for (size_t i = 0; i < cur; i++) {
if (__array[i] == t)
return i;
}
return -1ll;
}
template <class T>
long long ArrayList<T>::lastIndexOf(const T& t) {
for (long long i = cur - 1; i >= 0; i--) {
if (__array[i] == t)
return i;
}
return -1ll;
}
template <class T>
T& ArrayList<T>::at(size_t i) {
if (i >= __capacity || i < 0)
throw "Exception : Index out of range!";
return __array[i];
}
template <class T>
void ArrayList<T>::add(const T& t) {
if (cur == __capacity)
recreate();
__array[cur++] = t;
}
template <class T>
void ArrayList<T>::insert(size_t i, const T& t) {
if (cur >= __capacity)
recreate();
for (size_t k = cur; k > i; k--) {
__array[k] = __array[k - 1];
}
__array[i] = t;
cur++;
}
template <class T>
T ArrayList<T>::remove(size_t i) {
if (i >= __capacity || i < 0)
throw "Exception : Index out of range :(";
T t = move(__array[i]); // 不能返回引用
for (size_t k = i; k < cur - 1; k++) {
__array[k] = __array[k + 1];
}
--cur;
return t;
}
template <class T>
bool ArrayList<T>::empty() {
return cur == 0 ? true : false;
}
template <class T>
ArrayList<T>::~ArrayList() {
delete[] __array; // 还可以调用?
__array = nullptr;
}
template <class T>
void ArrayList<T>::forEach(void (*func)(T)) {
for (size_t i = 0; i < cur; i++) {
func(__array[i]);
}
}
template <class T>
bool ArrayList<T>::equals(ArrayList<T>& al) {
if (this->cur != al.size())
return false;
for (size_t i = 0; i < this->cur; i++) {
if (__array[i] != al.at(i))
return false;
}
return true;
}
template <class T>
void ArrayList<T>::reverse() {
reverse(0, cur);
}
template <class T>
void ArrayList<T>::reverse(int i, int j) {
if (i >= j)
return;
swap(i, j);
reverse(++i, --j);
}
template <class U>
std::ostream& operator<<(std::ostream& os, const ArrayList<U>& l) {
if (l.__array != nullptr)
for (size_t i = 0; i < l.cur; i++) {
os << *(l.__array + i) << " ";
}
else
os << "null ";
return os;
}
template <class U>
std::ostream& operator<<(std::ostream& os, const ArrayList<U>* l) {
if (l->__array != nullptr)
for (size_t i = 0; i < l->cur; i++) {
os << *(l->__array + i) << " ";
}
else
os << "null ";
return os;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)