目录
一、vector基本概念
1.1、构造函数
1.2、析构函数
1.3、插入元素
1.4、删除元素
1.5、重载运算符
二、完整代码
一、vector基本概念
C++中的vector是一种动态数组,它可以根据需要自动调整大小。vector是C++标准模板库(STL)中的一个容器,它可以存储任意类型的元素,如整数、浮点数、字符串等。使用vector时,不需要关心数组的大小,因为它会自动管理内存。
vector的基本操作包括添加元素、删除元素、访问元素等。例如,可以使用push_back()
函数向vector末尾添加元素,使用pop_back()
函数删除vector末尾的元素,使用下标访问元素等。此外,vector还支持迭代器,可以方便地遍历vector中的所有元素。
vector的优点包括:
- 动态调整大小,不需要预先分配固定大小的内存;
- 支持随机访问,访问速度较快;
- 提供了丰富的成员函数,方便操作。
然而,vector的缺点是插入和删除元素的效率较低,因为可能需要移动大量元素来重新排列。在需要频繁插入和删除元素的场景下,可以考虑使用其他容器,如list。C++ STL中已经有了vector,其底层数据结构就是线性表,你可以理解为:动态数组,他在内存中存储是连续的,而链表就不是线性的。本文使用c++自定义个MyVector类。
1.1、构造函数
MyVector类需要维护三个成员:
- int* array_:假定这是一个int型动态数组
- int size_:表示当前数组中已经塞进去几个元素
- int capacity_:表示当前数组最多能塞进几个元素,如果容量不够,还要扩容,后面会讲,注:size_ <= capacity_
MyVector::MyVector()
{
size_ = 0;
capacity_ = 10;
array_ = new int[capacity_];
}
1.2、析构函数
没什么特别的地方,就是delete[]成员array_就行。
MyVector::~MyVector()
{
delete[] array_;
cout << "free " << array_ << endl;
}
1.3、插入元素
实现一个push_back方法,和std::vector一样的。插入元素的时候,要判断容量是否用完;如果空间不够,那就申请一块更大的空间,再将原来的数据拷贝过来,然后释放原来的数据,最后插入新的元素。所以,这里应该知道,std::vector是的使用的时候,最好能够预留好(reserve)合适的空间。
void MyVector::push_back(int value)
{
if (empty()) return;
//判断空间是否足够
if (size_ == capacity_)
{
int* newspace = new int[capacity_ * 2]; // 扩容
memcpy(newspace, array_, capacity_ * sizeof(int));// 备份 - > newsapce
delete[] array_;// 删除旧空间
capacity_ *= 2;//扩容
array_ = newspace;//转移旧空间的值 - > 新空间
}
//在末尾插入元素
array_[size_] = value;
size_++;
}
1.4、删除元素
给定需要删除元素的索引pos或者value,就能删除元素。C++ STL中的std::vector删除元素和这里一样,都会涉及拷贝数据。
依据索引pos删除元素:
void MyVector::removeByPose(int pos)
{
if (empty()) return;
if (pos < 0 || pos >= size_)//越界
{
cout << "out of range!" << endl;
return;
}
for (int i = pos; i < (size_ - 1); i++) //注意越界
{
array_[i] = array_[i + 1];
}
size_--;
}
依据索引值value删除元素:
void MyVector::removeByValue(int value)
{
if (empty()) return;
int pos = find(value);
if (pos == -1)
{
cout << "没有元素:" << value << endl;
return;
}
removeByPose(pos);
}
1.5、重载运算符
这样就可以直接使用下标直接访问元素。
int& operator[](int index)// 可以是返回引用
{
return array_[index];
}
二、完整代码
vector的优点:访问任何一个元素,直接使用下表就行,例如arr[2],速度很快。缺点:删除元素性能开销大。以下给出完整代码:
#include<iostream>
using namespace std;
class MyVector
{
public:
MyVector();
~MyVector();
void push_back(int value);
void removeByPose(int pos);
void removeByValue(int value);
int find(int value);
int& operator[](int index)// 可以是返回引用
{
return array_[index];
}
void show() const;
void clear()
{
size_ = 0;
}
bool empty()
{
if (array_ == nullptr)
return true;
else
return false;
}
public:
int* array_;
int size_;
int capacity_;
};
MyVector::MyVector()
{
size_ = 0;
capacity_ = 10;
array_ = new int[capacity_];
}
MyVector::~MyVector()
{
delete[] array_;
cout << "free " << array_ << endl;
}
void MyVector::push_back(int value)
{
if (empty()) return;
//判断空间是否足够
if (size_ == capacity_)
{
int* newspace = new int[capacity_ * 2]; // 扩容
memcpy(newspace, array_, capacity_ * sizeof(int));// 备份 - > newsapce
delete[] array_;// 删除旧空间
capacity_ *= 2;//扩容
array_ = newspace;//转移旧空间的值 - > 新空间
}
//在末尾插入元素
array_[size_] = value;
size_++;
}
void MyVector::show() const
{
cout << "size_ = " << size_ << " ||";
for (int i = 0; i < size_; i++)
{
cout << array_[i] << " ";
}
cout << endl;
}
void MyVector::removeByPose(int pos)
{
if (empty()) return;
if (pos < 0 || pos >= size_)//越界
{
cout << "out of range!" << endl;
return;
}
for (int i = pos; i < (size_ - 1); i++) //注意越界
{
array_[i] = array_[i + 1];
}
size_--;
}
int MyVector::find(int value)
{
if (empty()) return -1;
int pos = -1;
for (int i = 0; i < size_; i++)
{
if (array_[i] == value)
{
pos = i;
break;
}
}
return pos;
}
void MyVector::removeByValue(int value)
{
if (empty()) return;
int pos = find(value);
if (pos == -1)
{
cout << "没有元素:" << value << endl;
return;
}
removeByPose(pos);
}
int main()
{
MyVector vec;
for (int i = 0; i < 12; i++)
{
vec.push_back(i * i);
}
vec.push_back(88);
vec.show();
vec.removeByPose(1);
vec.show();
vec.removeByPose(2);
vec.show();
vec.removeByValue(49);
vec.show();
int position = vec.find(25);
//测试重载
cout << "test for overload " << endl;
for (int i = 0; i < vec.size_; i++)
{
cout << vec[i] << " ";
}
cout << endl;
vec.clear();
vec.show();
return 1;
}
下图是执行效果: