高效实现动态数组

一、什么是动态数组

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

在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
    


     
四、动态数组的优缺点

     
1. 优点

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

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

     
2. 缺点

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


     
五、总结

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