加载中

手写数据结构·线性表02:动长数组

动长数组(Vector)

template<class T>
class Vector {
    T* data;
    int n, cap;

    void expand(){
        int newCap = (cap==0 ? 1 : cap*2);
        T* tmp = new T[newCap];
        for(int i=0;i<n;i++) tmp[i]=data[i];
        delete[] data;
        data=tmp; cap=newCap;
    }

public:
    Vector(int capacity=10){
        if(capacity<0) throw invalid_argument("Vector capacity < 0");
        cap=capacity; n=0;
        data = (cap==0 ? nullptr : new T[cap]);
    }

    ~Vector(){ delete[] data; }

    Vector(const Vector& other){
        n=other.n; cap=other.cap;
        data = (cap==0 ? nullptr : new T[cap]);
        for(int i=0;i<n;i++) data[i]=other.data[i];
    }

    Vector& operator=(const Vector& other){
        if(this==&other) return *this;
        T* tmp = (other.cap==0 ? nullptr : new T[other.cap]);
        for(int i=0;i<other.n;i++) tmp[i]=other.data[i];
        delete[] data;
        data=tmp; n=other.n; cap=other.cap;
        return *this;
    }

    bool empty() const { return n==0; }
    int size() const { return n; }
    int capacity() const { return cap; }

    T& operator[](int i){ return data[i]; }
    const T& operator[](int i) const { return data[i]; }

    T& at(int i){
        if(i<0 || i>=n) throw out_of_range("Vector::at");
        return data[i];
    }

    void reserve(int newCap){
        if(newCap<=cap) return;
        T* tmp = new T[newCap];
        for(int i=0;i<n;i++) tmp[i]=data[i];
        delete[] data;
        data=tmp; cap=newCap;
    }

    void push_back(const T& x){
        if(n==cap) expand();
        data[n++]=x;
    }

    bool pop_back(){ if(empty()) return false; n--; return true; }

    bool insert(int pos,const T& x){
        if(pos<0 || pos>n) return false;
        if(n==cap) expand();
        for(int i=n;i>pos;i--) data[i]=data[i-1];
        data[pos]=x; n++;
        return true;
    }

    bool erase(int pos){
        if(pos<0 || pos>=n) return false;
        for(int i=pos;i<n-1;i++) data[i]=data[i+1];
        n--;
        return true;
    }

    int find(const T& x) const{
        for(int i=0;i<n;i++) if(data[i]==x) return i;
        return -1;
    }

    void clear(){ n=0; }
};

工程细节

  • n 是有效元素数,cap 是已分配槽位数,始终满足 0 <= n <= cap;两者不能混用。
  • 扩容依次分配更大的数组、复制有效元素、delete[] 旧数组、替换指针;数组释放不能写成 delete。
  • 复制构造与赋值都要复制元素,不能只复制 data 指针;赋值先检查 this == &other,再分配新数组,最后释放旧数组。
  • 扩容会使旧指针和引用失效。待插入值若引用自身元素,应先在外部保存副本,避免扩容或搬移影响它。
  • clear()、erase() 和 pop_back() 只调整逻辑长度,不立即析构数组槽位中的对象。

跳转

下一个:顺序栈

上一个:顺序表

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/dd0bc08c/

版权声明:本文采用 CC BY-NC-SA 4.0 许可协议