动长数组(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() 只调整逻辑长度,不立即析构数组槽位中的对象。
跳转
下一个:顺序栈
上一个:顺序表