C++实现动态数组(ArrayList)
本文最后更新于 222 天前,其中的信息可能已经有所发展或是发生改变。

ArrayList依赖于数组,而数组可以随机访问,因此读取的效率要比链表高。相比链表的实现,ArrayList也要简单不少。

List接口

和上一篇提到的双向链表一样,先让ArrayList实现List接口。

template<class T>
class List {
public:
    virtual void add(T value) = 0;
    virtual void add(T value, int position) = 0;
    virtual T get(int position) = 0;
    virtual T remove(int position) = 0;
    virtual inline int getSize() = 0;

protected:
    int size = 0;
    void checkIndexOutOfRange(int index) {
        if (index < 0 || (index >= this->size && this->size > 0)) {
            throw IndexOutOfRangeException(this->size, index);
        }
    }
};

ArrayList类

首先定义几个常量:

#define CAPACITY_STEP 10
#define MAX_CAPACITY 65535
#define COLLAPSE_THRESHOLD 0.5

这两个常量用于数组扩容:

  • CAPACITY_STEP 每次扩容容量
  • MAX_CAPACITY 最大数组长度

而COLLAPSE_THRESHOLD用于数组缩容,用于数组的利用率比较,如果小于这个阈值,则需要进行缩容操作。

template<class T>
class ArrayList : public List<T> {
private:
    T* data;
    int capacity = 10;

    void expandCapacity();
    void collapseCapacity();

public:
    /* Implements of List.h */
    void add(T value);
    void add(T value, int position);
    T get(int position);
    T remove(int position = 0);
    inline int getSize() {
        return this->size;
    }

    explicit ArrayList(int initialCapacity) {
        this->capacity = initialCapacity;
    }

    explicit ArrayList<T>() {
        this->data = (T*) malloc(sizeof(T) * capacity);
    }

    ~ArrayList() {
        delete this->data;
    }

    void printArrayList() {
        printf("Size/Cap: %d / %d\n", this->size, this->capacity);
        for (int i = 0; i < this->size; i++) {
            printf("%d\n", this->get(i));
        }
    }
};

和链表不同的是,动态数组的元素必须排列在一起,因此在插入或删除元素时,需要把相应的元素全部前移后后移,以保证有空位给新加入的元素且动态数组的中间没有空位。

但由于数组是固定长度的,因此当下标超过数组长度时,需要重新根据扩容机制创建一个新的数组,并将旧数组的元素拷贝到新数组中,这样就实现了数组扩容。

数组扩容

template<class T>
void ArrayList<T>::expandCapacity() {
    // Check whether it need to expand
    if (this->size >= this->capacity) {
        this->capacity += CAPACITY_STEP;
        if (this->capacity > MAX_CAPACITY) {
            this->capacity = MAX_CAPACITY;
        }
        T* t = (T*) malloc(sizeof(T) * this->capacity);
        memcpy(t, this->data, sizeof(T) * this->size);
        delete this->data;
        this->data = t;
    }
}

数组缩容

template<class T>
void ArrayList<T>::collapseCapacity() {
    double usage = (double) this->size / this->capacity;
    if (usage < COLLAPSE_THRESHOLD) {
        int newCapacity = CAPACITY_STEP * ceil((double) this->size / CAPACITY_STEP);
        T* newArray = (T*) malloc(sizeof(T) * newCapacity);
        for (int i = 0; i < this->size; i++) {
            newArray[i] = this->data[i];
        }

        this->capacity = newCapacity;
        delete this->data;
        this->data = newArray;
    }
}

添加元素

template<class T>
void ArrayList<T>::add(T value, int position) {
    expandCapacity();
    if (position >= this->size) {
        add(value);
    } else {
        for (int i = this->size; i > position; i--) {
            this->data[i] = this->data[i - 1];
        }
        this->data[position] = value;
        this->size++;
    }
}

template<class T>
void ArrayList<T>::add(T value) {
    expandCapacity();
    this->data[this->size] = value;
    this->size++;
}

删除元素

template<class T>
T ArrayList<T>::remove(int position) {
    this->checkIndexOutOfRange(position);
    T t = this->get(position);
    for (int i = position; i < this->size - 1; i++) {
        this->data[i] = this->data[i + 1];
    }
    this->size--;
    return t;
}

获取元素

template<class T>
T ArrayList<T>::get(int position) {
    this->checkIndexOutOfRange(position);
    return this->data[position];
}
未经允许禁止转载本站内容,经允许转载后请严格遵守CC-BY-NC-ND知识共享协议4.0,代码部分则采用GPL v3.0协议
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇