【C++初阶】--- vector容器功能模拟实现

1.什么是vector？

在 C++ 里，std::vector 是标准模板库（STL）提供的一个非常实用的容器类，它可以看作是动态数组

2.成员变量

iterator _start;：指向 vector 中第一个元素的指针。
iterator _finish;：指向 vector 中最后一个元素的下一个位置的指针。
iterator _end_of_storage;：指向 vector 所分配内存空间的末尾的指针。

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;
}

3.构造函数

3.1默认构造

因为三个成员变量都有缺省值，我们只需要显示写默认构造即可，他们会在初始化链表处初始化。

//写法1：
vector()
{}
//写法2：
vector() = default;//C++11支持强制生成默认构造

3.2拷贝构造

1. 调用 reserve 函数，提前为新 vector 对象分配足够的内存空间，其大小和 v 的元素数量相同，此步骤可以避免后续添加元素时的频繁扩容。
2. 借助范围 for 循环遍历 v 中的每个元素，使用引用 auto& 避免不必要的拷贝（特别是当元素为自定义类型时）。
3. 对 v 中的每个元素，调用 push_back 函数将其添加到新 vector 对象的末尾。

//拷贝构造
vector(const vector<T>& v)
{//提前开好空间reserve(v.size());//如果元素是自定义类型,用引用可以减少拷贝for (auto& ch : v){//尾插数据push_back(ch);}
}

3.3迭代器构造函数

迭代器构造函数需要我们传两个迭代器，我们使用范围for将元素尾插至新构造的vector对象中，构造的范围是[first,last)
注意：类模板的成员函数，也可以是函数模板，我们可以将这个迭代器构造函数写成模板，优点是可以用不同的类构造vector对象，前提是元素类型需相同，如：int

//迭代器构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}

3.4半缺省构造函数

我们可以通过半缺省构造函数构造一个有n个val值得vector对象

1. 使用resver提前开好空间，避免后续插入元素时频繁扩容
2. 使用for循环尾插n个值为val的元素，如果不传参使用的是缺省值T()
3. 对于内置类型（如 int、double、char 等），T() 会进行值初始化。对于数值类型，会初始化为 0；对于指针类型，会初始化为 nullptr。
4. 对于自定义类型，T() 会调用该类型的默认构造函数。如果没有显式定义默认构造函数，编译器会自动生成一个（前提是该类没有其他带参数的构造函数

注意：我们使用半缺省构造函数的时候传参需要注意，如下：如果不显示第一个参数是size_t，编译器会优先调用更符合的构造函数，即会上面的迭代器构造函数

//u表示10是size_t类型
vector<int> v1(10u,1);

//用n个val进行构造，T()是匿名对象
vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){//如果用这种，_finish记得++//*_finish = val;//_finish++;push_back(val);}
}

4.析构函数

三个指针指向同一块空间的不同位置，使用delete释放的时候我们需要使用指向vector中第一个元素的指针，同一块空间不能进行多次释放。

//析构
~vector()
{if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
}

5.iterators

5.1begin()/end()

//普通对象使用
iterator begin()
{return _start;
}iterator end()
{return _finish;
}//const对象使用
const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}

6.内联函数

6.1size()

size_t size() const
{return _finish - _start;
}

6.2capacity()

size_t capacity() const
{return _end_of_storage - _start;
}

6.3empty()

bool empty() const
{return _start == _finish;
}

6.4clear()

void clear()
{_finish = _start;
}

6.5swap()

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}

6.7=运算符重载

普通写法：

1. 先清除当前vector对象中的所有元素
2. 提前开头看见，避免后续频繁扩容
3. 使用范围for依次将元素尾插至当前vector对象

//赋值运算符重载
vector<T>& operator=(const vector<T>& v)
{if (this != &v){//先清理原先数据clear();//提前开好空间reserve(v.size());//如果数据是自定义类型可以减少拷贝for (auto& ch : v){push_back(ch);}}return *this;
}

现代写法：

//赋值运算符重载，现代写法
//这里是拷贝，不是引用，且不加const
vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

6.8[]运算符重载

//普通对象使用
T& operator[](size_t i)
{//i不能越界assert(i < size());return _start[i];
}//const对象使用
const T& operator[](size_t i) const
{//i不能越界assert(i < size());return _start[i];
}

7.尾插/尾删元素

7.1push_back()

1. 判断空间是否已满，已满需进行扩容操作，使用三木操作符，如果当前vector对象空间对空，扩容至4个元素，不为空则选择2倍扩容。
2. 尾插元素，_finish指针向后移动一位

//尾插
//如果是自定义类型，用引用可以减少拷贝
void push_back(const T& x)
{//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;_finish++;
}

7.2pop_back()

1. 判断当前vector对象中是否还剩余元素，元素为0则断言失败
2. 还有元素则将_finish指针前移一位

//尾删
void pop_back()
{//判空assert(!empty());_finish--;
}

8.在pos位置插入删除元素

8.1insert()

1. 判断pos位置的有效性，可插入范围为[_start,_finish]
2. 判断空间是否足够，不够则进行扩容操作
   注意：如果进行扩容操作，则会造成迭代器失效，需要更新下迭代器
3. 将pos位置及之后的数据向后移动一位
4. 在pos位置插入元素，返回pos位置的迭代器

//在pos位置插入数据
iterator insert(iterator pos, const T& x)
{//pos有效性assert(pos >= _start && pos <= _finish);//扩容if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());//扩容后pos迭代器会失效,需要更新一下pos = _start + len;}//将pos及之后的数据往后移动一位iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}

8.2erase()

1. 判断pos位置的有效性，可删除范围为[_start,_finish)
2. 将pos之后的数据向前移动一位，将pos位置的数据进行覆盖
3. 别忘了将_finish指针也前移一位

//删除pos位置的数据
template<class T>
void vector<T>::erase(iterator pos)
{//pos有效性assert(pos >= _start && pos < _finish);//向前移动数据iterator it = pos + 1;while (it != end()){*(it - 1) = *it;it++;}--_finish;
}

9.空间大小和数据大小调整

9.1resize()

将vector对象中的数据个数调整至n个，如果n小于当前元素个数，将当前元素个数调整为n，如果n大于当前元素个数，使用val对其进行填充。

//调整长度
template<class T>
void vector<T>::resize(size_t n, T val)
{//n小于长度，缩减长度if (n < size()){_finish = _start + n;}//n大于长度，在后面补元素else{//可能需要扩容reserve(n);//从原数据结尾开始补while (_finish < _start + n){//*_finish = val;//_finish++;push_back(val);}}
}

9.2reserve()

将空间大小扩容至n，如果n小于当前空间大小，不进行操作和改变

1. 保存旧空间大小old_size,否则后续：
   _start = tmp;
   _finish = tmp + size();
   而size()是_finish-_start,从而_finish = tmp + size()=_start+_finish-_start=_finish
2. new新空间，大小为n
3. 将原对象内容进行深拷贝，不能使用memcpy进行拷贝
   
4. 释放原空间，更新成员变量

template<class T>
void vector<T>::reserve(size_t n)
{//n大于空间大小才扩容if (n > capacity()){size_t old_size = size();//new个新空间T* tmp = new T[n];//memcpy对于内置类型是深拷贝，对于自定义类型是浅拷贝,所以不能用memcpy//memcpy(tmp, _start, size() * sizeof(T));for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}//销毁旧空间数据delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}
}

10打印vector对象内容

C++规定：没有实例化的类模板里取东西，编译器不能区分这里的const_vector是类型还是变量，在前面加上typename表示取的是类型。
当然也可以使用auto自动识别类型。

//打印顺序表的模板
template<class T>
void print_vector(const vector<T>& v)
{//auto it = v.begin();typename vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;/*	for (auto ch : v){cout << ch << " ";}cout << endl;*/
}

通用打印模板：

//通用打印模板
template<class Container>
void print_vector(const Container& v)
{auto it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;//或者//for (auto ch : v)//{//	cout << ch << " ";//}//cout << endl;
}