高效实现动态数组

小蓝 • 2024-12-12 12:03 • 编程

一、什么是动态数组

动态数组是一种可以在运行时根据需要扩展或缩小大小的数组结构。相较于静态数组，动态数组具有更高的灵活性。

在C++中，我们可以使用STL中的vector来实现动态数组。

二、使用vector的基本操作

C++ STL中的vector是一个动态数组，提供了方便的操作方法。

1. 定义vector

#include 
using namespace std;

vector vec; //定义一个空的整型vector
vector vec(size); //定义一个有size个元素的整型vector

2. 添加元素

我们可以使用push_back()或insert()函数来添加元素。

vec.push_back(1); //在vector的尾部添加元素1
vec.insert(vec.begin()+index, 1); //在vector的指定位置添加元素1，index表示位置

3. 删除元素

我们可以使用erase()函数来删除元素。

vec.erase(vec.begin()+index); //删除vector的指定位置元素，index表示位置

4. 访问元素

我们可以使用下标操作符[]、at()函数或迭代器访问vector中的元素。

vec[index]; //通过下标访问vector中的元素
vec.at(index); //通过at()函数访问vector中的元素
for (auto it=vec.begin(); it!=vec.end(); ++it) //通过迭代器访问vector中的元素
    cout << *it << " ";
cout << endl;

5. 获取vector大小

我们可以使用size()函数获取vector中元素的数量。

vec.size(); //获取vector中元素的个数

三、自定义动态数组

除了使用STL中的vector，我们也可以手动实现动态数组。

1. 实现原理

动态数组可以理解为一个静态数组加上一个计数器。当静态数组存储空间不足时，我们可以使用new运算符动态申请更多的空间，并将旧数据复制到新空间中。

2. 实现代码

以下是一个简单的动态数组实现：

template 
class Array {
private:
    T* data; //指向数据的指针
    int size; //数组中元素的数量
    int capacity; //数组中可以存储的元素数量

public:
    Array(int cap=10) : size(0), capacity(cap) { //构造函数
        data = new T[capacity];
    }

    ~Array() { //析构函数
        delete[] data;
    }

    void resize(int new_cap) { //调整数组大小
        T* new_data = new T[new_cap];
        for (int i=0; i= capacity) {
            resize(2*capacity); //如果存储空间满了，扩大空间
        }
        data[size++] = elem;
    }

    void insert(T elem, int index) { //在指定位置插入元素
        if (size >= capacity) {
            resize(2*capacity); //如果存储空间满了，扩大空间
        }
        for (int i=size; i>index; --i) {
            data[i] = data[i-1]; //元素后移
        }
        data[index] = elem;
        ++size;
    }

    void erase(int index) { //删除指定位置的元素
        for (int i=index+1; i<size; ++i) {
            data[i-1] = data[i]; //元素前移
        }
        --size;
        if (size <= capacity/4) {
            resize(capacity/2); //如果存储空间过多，缩小空间
        }
    }

    T operator[](int index) { //重载下标操作符
        return data[index];
    }

    int getSize() { //获取数组中元素数量
        return size;
    }
};

四、动态数组的优缺点

1. 优点

动态数组的大小是动态可变的，可以根据需要灵活调整。

动态数组支持尾部添加元素的高效操作，相较链表，具有更高的内存缓存优化效果。

2. 缺点

动态数组的调整操作需要消耗一定的时间，删除操作可能会导致数组空间浪费，增加空间时可能分配不到连续的内存块。

五、总结

本文介绍了如何使用STL中的vector来实现动态数组，以及手动实现动态数组的基本原理和代码示例。动态数组相较于静态数组具有更高的灵活性和操作效率，但也存在空间浪费等问题。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/237130.html