一、vector的介绍及使用
1.1 介绍vector
vector是一个可变大小数组的容器，与数组一样，vector也是一块连续的空间，可以像数组一样对元素进行高效的遍历访问，但是普通数组的大小是不变的，vector可以改变自身大小。vector是采用动态分配数组来存储数据，即插入新元素时要改变存储空间大小，往往要分配一个新的数组，然后把原来数组的元素转移到新的空间里。vector的尾插尾删效率高，中间插入和删除效率较低。
1.2 vector的使用
1.2.1 构造
1️⃣无参
vector()
vector<int> v;
2️⃣构造并初始化n个val
vector（size_type n, const value_type& val = value_type()）
vector<int> v(10, 7);
3️⃣拷贝构造
vector (const vector& x)
vector<int> v1{
1,2,3,4 };
vector<int> v2(v1);
4️⃣使用迭代器进行初始化构造
vector (InputIterator first, InputIterator last)
vector<int> v1{
5,6,7,8};
vector<int> v2(v1.begin(), v1.end());
1.2.2 遍历访问
1️⃣begin+end
vector<int> v{
1,2,3,4,5 };
auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
获取数组第一个元素的位置，像指针一样遍历整个数组，直到最后一个元素结束。auto是自动推导类型。
2️⃣下标：operator[ ]
vector<int> v{
1,2,3,4,5 };
for (int i = 0; i < 5; i++)
{
cout << v[i] << " ";
}
cout << endl;
3️⃣范围for
vector<int> v{
1,2,3,4,5 };
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
1.2.3 容量空间
1️⃣获取元素个数
vector<int> v{
1,2,3,4,5 };
cout << v.size() << endl;//5
2️⃣获取容量大小
vector<int> v{
1,2,3,4,5 };
cout << v.capacity() << endl;//5
3️⃣判断是否为空
vector<int> v;
cout << v.empty() << endl;
4️⃣改变vector的size
void resize (size_type n, value_type val = value_type());
vector<int> v{
1,2,3,4,5 };
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
v.resize(10, 9);
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
如果超出原来的存储空间，那么capacity也会改变
5️⃣改变vector的capacity
void reserve (size_type n);
vector<int> v{
1,2,3,4,5 };
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
v.reserve(10);
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
cout << v.size() << endl;
cout << v.capacity() << endl;
1.2.4 增删查改
1️⃣尾插
vector<int> v{
1,2,3,4,5 };
v.push_back(9);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
2️⃣尾删
vector<int> v{
1,2,3,4,5 };
v.pop_back();
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
3️⃣查找
注意查找不是vector的接口，是算法模块实现的。
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
vector<int> v{
1,2,3,4,5 };
auto it = find(v.begin(), v.end(), 2);
cout << *it << endl;//2
4️⃣交换
void swap (vector& x);
vector<int> v1{
1,2,3,4,5 };
vector<int> v2{
6,7,8,9,10 };
v2.swap(v1);
5️⃣在pos位置插入
iterator insert (iterator position, const value_type& val);
vector<int> v{
1,2,3,4,5 };
auto pos = find(v.begin(), v.end(), 2);
v.insert(pos, 10);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
6️⃣在pos位置删除
iterator erase (iterator position);//指定位置删除
iterator erase (iterator first, iterator last);//指定范围删除
有两种写法：
// 一：
vector<int> v{
1,2,3,4,5 };
auto pos = find(v.begin(), v.end(), 2);
v.erase(pos);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
// 二：
vector<int> v{
1,2,3,4,5 };
v.erase(v.begin() + 1, v.end() - 1);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
注意：insert 和 erase 一般只使用一次，重复使用可能导致迭代器失效。
二、vector的模拟实现
2.1 成员变量
vector的迭代器是一个原生指针，它的三个成员变量分别是：
typedef T* iterator;
typedef const T* const_iterator;
//————————
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
这里在声明时先给成员变量缺省值为空指针，声明时给缺省值是给初始化列表的，后续写的时候就比较方便。
2.2 迭代器相关函数
begin函数返回空间的起始位置，end函数返回空间的最后一个有效元素的下一位。
// 通过迭代器访问元素时可修改
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
// 通过迭代器访问元素时不可修改
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
2.3 构造-析构-赋值重载
2.3.1 无参构造
没有传参数
vector()
{
}
2.3.2 有参构造1
代码：
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
reserve(last - first);//复用扩容函数
while (first != last)//判断条件
{
push_back(*first);//复用尾插函数
++first;//尾插一次后加1
}
}
这个函数看起来有些奇怪，为啥还要套一层模板呢？使用这里就不说了，其实这个构造函数的作用是：只要传进来的是迭代器就可以初始化该迭代器的内容，前提是该迭代器是指向连续物理空间的指针。比如用vector定义了一个v1，v1已经是构造好的，有具体的元素；再定义一个v2，我想让v2的内容跟v1是一样的，就可以使用这个函数，传的迭代器指向的是v1的头和尾，它就会构造出和v1一样的内容。前面的使用方法有代码。不仅可以vector传vector，还可以list传vector，只要是迭代器即可。
2.3.3 有参构造2
vector(size_t n, const T& x = T())
{
resize(n, x);//复用修改元素个数函数
}
vector(int n, const T& x = T())
{
resize(n, x);//复用修改元素个数函数
}
该构造函数是初始化为n大小的空间，每个元素是x。可以直接复用resize函数，下面会介绍。这里写了两个构造函数唯一的区别是size_t 和int ，因为如果只有size_t 类型的那个构造函数，构造时不会调用该函数，会调用前面的构造函数（有参构造1），这与函数模板的匹配调用原则有关。假如传进来的n不是size_t 类型，那么它就要发生隐式类型转换，但是编译器想，隐式类型转换感觉麻烦，就使用有模板的那个函数。
为了防止出现以上情况，同时是模拟实现，要尽可能像标准库里面的vector，所以多重载了一个函数，它的参数n是int 类型的，这样的话传进来的参数n是int 类型，那么它就会直接调用这个构造函数，避免了以上情况。
2.3.4 拷贝构造
拷贝构造要注意深浅拷贝问题
1️⃣写法1
vector(const vector<T>& v)
{
_start = new T[v.capacity()];//开一样大的空间
memcpy(_start, v._start, sizeof(T) * v.size());//拷贝数据
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
与string的拷贝构造类似，开一块新空间，拷贝数据后，指向这个新空间，这样防止两个指针指向同一块空间。
写法1还要注意memcpy的深浅拷贝问题，与元素的类型有关，这个在后面会具体介绍，现在假设统一使用的元素类型先是 int 类型。
1️⃣写法2
vector(const vector<T>& v)
{
reserve(v.capacity());//复用扩容函数
for (const auto& e : v)//范围for循环直接放入数据即可
{
push_back(e);//复用尾插函数
}
}
先开与参数v一样大的空间，然后使用范围for直接放入数据，只要参数v里面有元素，都可以把元素一个一个的尾插到要构造的空间里面，同时也不影响v，最终完成拷贝构造。
2.3.5 赋值重载
1️⃣写法1
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)//相同就不用赋值
{
T* tmp = new T[v.capacity()];//临时空间
memcpy(tmp, v._start, sizeof(T) * v.size());//拷贝数据
delete[] _start;//清理旧空间
_start = tmp;//指向新空间
_finish = _start + v.size();//
_endofstorage = _start + v.capacity();
}
return *this;
}
1️⃣写法2
与string的是一样的，直接代码：
vector<T>& operator=(vector<T> v)
{
swap(v);//复用交换函数
return *this;
}
//交换
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
2.3.6 析构
如果空间里有元素才清理，让3个指针置空；没有元素本来就是空指针不能清理。
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;//
}
}
2.4 容量操作
2.4.1 size和capacity
根据三个指针的指向，可以确定有效元素个数和容量的区间
//返回个数
size_t size() const
{
return _finish - _start;
}
//返回容量
size_t capacity() const
{
return _endofstorage - _start;
}
2.4.2 reserve
如果存储的元素超出原来的空间大小要扩容，扩容要开辟一块新空间，然后拷贝数据到新空间里，再让指针重新指向这块新空间。
代码：
//扩容
void reserve(size_t n)
{
if (n > capacity())//满了要扩容
{
size_t old = size();//记录当前元素个数
T* tmp = new T[n];//新空间
if(_start)
{
//memcpy(tmp, _start, sizeof(T) * old);//将数据拷贝到新空间-浅拷贝
for (size_t i = 0; i < old; i++)
{
tmp[i] = _start[i];//深拷贝
}
delete[] _start;//释放就空间
}
_start = tmp;//指向新空间
_finish = _start + old;//防止迭代器失效
_endofstorage = _start + n;
}
}
问题1：为什么要定义变量old
开空间拷贝数据后，旧空间被释放，指向新空间，_finish等于_start 加上元素个数，注意，如果没有old前面先记录元素个数的值，加上的是调用size函数返回的元素个数，那么就会出现迭代器失效问题。因为_start已经指向新的空间，而_finish还是指向旧空间的某个位置，那个不同空间相减就出问题了。
所以这里提前用变量old记录好元素的个数，_finsih等于_start+old，就不会出现以上情况。
问题2：memcpy是浅拷贝
元素类型是int 等内置类型没关系，如果是自定义类型，比如string，这里就会出现浅拷贝的问题。
深拷贝的做法是以赋值的形式逐个把旧空间的字符串给新空间：
2.4.3 resize
该函数可通过参数n修改元素个数，超出容量也会扩容。主要分为以下3点：
1.n小于等于元素个数
2.n大于元素个数且小于等于容量
3.n大于容量
代码：
void resize(size_t n, const T& x = T())
{
if (n <= size())
{
_finish = _start + n;//修改_finish指向即可
}
else//n>size()
{
size_t len = n - size();//n与元素个数的差值
if (n > capacity())//n大于容量要扩容
{
reserve(n);//复用扩容函数
}
while (len--)//插入len个x，只要n大于size()都要插入
{
*_finish = x;
++_finish;
}
}
}
2.5 插入与删除
2.5.1 尾插
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
尾插数据，_finish 指向同_endofstorage说明空间内数据已满，要扩容。然后插入在_finish指向的位置插入数据，_finish往后移。
2.5.2 尾删
void pop_back()
{
assert(size() > 0);//有元素才能删
--_finish;
}
2.5.3 pos位置插入
首先断言pos的位置是否合理，然后凡是插入数据，都要检查是否需要扩容。接着挪动数据，在pos位置插入新的元素。
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);//检查pos位置是否合理
size_t len = pos - _start;//记录pos与开始位置差值
if (_finish == _endofstorage)//满了要扩容
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
pos = _start + len;//防止迭代器失效
}
iterator end = _finish - 1;
while (end >= pos)//挪动数据
{
*(end + 1) = *end;
--end;
}
*pos = x;//插入新数据
++_finish;
return pos;
}
这里唯一要注意的是如果有发生扩容，pos的位置要进行更新。
2.5.3 pos位置删除
判断pos位置是否合理，然后挪动数据往前覆盖一个元素。
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
2.6 遍历访问
遍历访问有两种实现方式，一种是迭代器，前面已经写过了，另一种是方括号重载运算符，即我们常见的下标。
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
2.7 全部代码
2.7.1 vector.h
#include <iostream>
#include <assert.h>
using namespace std;
namespace yss
{
template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
//构造1
vector()
{
}
//构造2
vector(size_t n, const T& x = T())
{
resize(n, x);
}
vector(int n, const T& x = T())
{
resize(n, x);
}
//构造3
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
reserve(last - first);
while (first != last)
{
push_back(*first);
++first;
}
}
//拷贝构造
//写法1
//vector(const vector<T>& v)
//{
// _start = new T[v.capacity()];//开一样大的空间
// memcpy(_start, v._start, sizeof(T) * v.size());//拷贝数据
// _finish = _start + v.size();//
// _endofstorage = _start + v.capacity();
//}
//写法2
vector(const vector<T>& v)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
//赋值重载
//写法1
//vector<T>& operator=(const vector<T>& v)
//{
// if (this != &v)
// {
// T* tmp = new T[v.capacity()];//临时空间
// memcpy(tmp, v._start, sizeof(T) * v.size());//拷贝数据
// delete[] _start;
// _start = tmp;
// _finish = _start + v.size();//
// _endofstorage = _start + v.capacity();
// }
// return *this;
//}
//写法2
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
//析构
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;//
}
}
//返回个数
size_t size() const
{
return _finish - _start;
}
//返回容量
size_t capacity() const
{
return _endofstorage - _start;
}
//交换
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
//扩容
void reserve(size_t n)
{
if (n > capacity())//满了要扩容
{
size_t old = size();//记录当前元素个数
T* tmp = new T[n];//新空间
if(_start)
{
//memcpy(tmp, _start, sizeof(T) * old);//将数据拷贝到新空间-浅拷贝
for (size_t i = 0; i < old; i++)
{
tmp[i] = _start[i];//深拷贝
}
delete[] _start;//释放就空间
}
_start = tmp;//指向新空间
_finish = _start + old;//防止迭代器失效
_endofstorage = _start + n;
}
}
//改变元素个数
void resize(size_t n, const T& x = T())
{
if (n <= size())
{
_finish = _start + n;
}
else
{
size_t len = n - size();
if (n > capacity())
{
reserve(n);
}
while (len--)
{
*_finish = x;
++_finish;
}
}
}
//尾插
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
//尾删
void pop_back()
{
assert(size() > 0);
--_finish;
}
//pos位置插入
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
size_t len = pos - _start;//记录pos与开始位置差值
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
pos = _start + len;//防止迭代器失效
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
//pos位置删除
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
//下标
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
2.7.2 test.cpp
#include"vector.h"
int main()
{
/*yss::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;*/
/*yss::vector<int> v(10);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;*/
/*yss::vector<int> v1(5, 99);
yss::vector<int> v2(v1.begin(), v1.end());
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;*/
/*yss::vector<int> v1(5, 55);
yss::vector<int> v2(v1);
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;*/
/*yss::vector<int> v1(7, 44);
yss::vector<int> v2 = v1;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;*/
/*yss::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
auto pos = find(v.begin(), v.end(), 2);
v.insert(pos, 99);
for (auto e : v)
{
cout << e << " ";
}*/
/*yss::vector<int> v;
v.push_back(1);
v.push_back(22);
v.push_back(43);
v.push_back(64);
v.push_back(85);
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;*/
return 0;
}
