目录
实现框架
一、基本的结构雏形
首先我们将所需的成员变量一一罗列出来
//为了避免和库里的vector产生冲突，在自己的命名空间内实现vector
namespace vec
{
template<class T>//通过模板能够实现不同类型的数据存储
class vector
{
public:
typedef T* iterator;
/*
各类函数功能实现
*/
private:
iterator _start; //指向容器中的起始位置
iterator _finish; //指向容器中最后一个有效数据的下一个位置
iterator _end_of_storage; //指向容器中现有容量的位置
};
}
二、默认成员函数
1.构造函数
1.无参构造
对于vector的无参构造，我们只需要将三个成员变量置为空指针即可。
//构造函数 --- 无参构造
vector()
//初始化成员列表
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
2.迭代器区间构造
当我们想要以某个
对象的
区间来进行初始化时，就需要用到模板了。它既可以是类模板，也可以是函数模板。
例如：
用一个常量字符串来构造vector
const char* p = "hello"; vector<char>v(p, p + 2);
用一个数组来构造vector
int a[5] = { 1,2,3,4,5 }; vector<int>v1(a, a + sizeof(a) / sizeof(a[0]));
用一个string类来构造vector
string s1("hello"); vector<char>v2(s1.begin(), s1.end());
//构造函数 --- 迭代器区间构造
template <class InputIterator>//既是一个类模板的成员函数，又可以是一个函数模板
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);//尾插
++first;
}
}
2.拷贝构造
对于拷贝构造函数，因为涉及到深浅拷贝的问题，我们这里提供传统写法与现代写法。
1.传统写法
/*用v1去拷贝构造v2*/
//v2(v1)
//传统写法1
vector(const vector<T>& v)
{
_start = new T[v.capacity()]; //让v2开辟一块和v1一样大小的空间
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
memcpy(_start, v._start, v.size() * sizeof(T));
}
//v2(v1)
//传统写法2
vector(const vector<T>& v)
{
_start = new T[v.capacity()]; //让v2开辟一块和v1一样大小的空间
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];//通过循环进行赋值
}
//最后调整_finish和_end_of_storage的大小
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
以上两种写法存在样的区别呢？
写法1：依然存在浅拷贝的问题；写法2彻底完成了深拷贝的问题；
从代码上来看，两者的区别在于写法1对于数据的拷贝采用的是
memcpy
函数，写法2对于数据的拷贝采用的是for循环进行
赋值
拷贝；两者在拷贝数据的方式上对于内置类型或不需要进行深拷贝的自定义类型，完全是满足要求的；但是当vector存储的是string时，一定存在问题。
vector<string>v1
存储了5个数据，每个数据都是string类，
vector<string>v2(v1),
v2也开辟了5个空间，并且在memcpy下完成拷贝，但是它们却指向了同一块空间，在调用析构函数时，就会导致同一块空间释放多次，最终内存泄露。
对于写法2，它会去调用string类的赋值重载函数进行一个深拷贝
2.现代写法
//v2(v)
//现代写法
vector(const vector<T>& v)//也支持vector(const vector& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end()); //通过迭代器区间对tmp进行拷贝
swap(tmp); //交换v2和tmp的数据
//this->swap(tmp);
}
3.赋值运算符重载函数
和拷贝构造一样，使用memcpy时存在浅拷贝的问题
1.传统写法
//v1 = v2
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v) //防止自己给自己赋值
{
delete[] _start; //先将v1的空间释放掉
_start = new T[v.capacity()]; //再开辟一块和v2一样大小的空间
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];//通过循环进行赋值
}
//最后调整_finish和_end_of_storage的大小
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
return *this;
}
2.现代写法
//v1 = v2
//现代写法
vector<T>& operator=(vector<T> v)//v2传给v，实际上拷贝构造一个和v2一样的v
{
swap(v); //然后直接交换数据即可
return *this;
}
4.析构函数
//析构函数
~vector()
{
if (_start)//防止对空指针进行释放
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
5.操作符重载函数
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
三、迭代器相关的函数
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.size和capacity
size_t size() const
{
return _finish - _start;//返回的是容器中有效数据的个数
}
size_t capacity() const
{
return _end_of_storage - _start;//返回的是容器的实际有效容量
}
2.reserve
reserve增容：
1.当 n > capacity 时，将capacity扩大到n；
2.当 n < capacity 时，不进行任何操作；
void reserve(size_t n)
{
if (n > capacity())//判断是否需要扩容
{
//扩容
size_t sz = size(); //提前算好增容前的数据个数
T* tmp = new T[n]; //开辟n个空间
if (_start)
{
//数据拷贝，也不能去使用memcpy函数
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[]_start; //释放旧空间
}
_start = tmp; //指向新空间
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
对于reserve，我还需要注意两个问题：
1.对增容前的数据个数进行记录
如果不提前算好增容前的数据个数，而是在增容完后更新_start，对于_finish和_end_of_storage都会出现问题，因为增容完后，就需要释放旧空间。
2.增容前后的数据拷贝不能使用memcpy
如果使用memcpy进行数据的拷贝后，随着_start的释放，tmp作为新的_start后，当进行访问操作时，就存在非法访问
3.resize
当n<size时，是缩容，相应的数据会减少，只需要调整一下_finish的位置
当n>size时，我们还需要判断n是否大于capacity，是否增容
在resize函数中的第二个参数val，采用的是缺省（匿名对象），因为我们并不知道T是什么类型，如果是int/int*给val = 0是可以的，但是T还有可能是vector，我们给到匿名对象作为缺省值的好处在于，对于内置类型它也有自己的默认构造函数
例如: int i = int(); // i = 0 int j = int(10);// j = 10
当我们不给val传任何参数时，它会去调用自己的默认构造函数给val
void resize(size_t n, const T& val = T())
//T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
五、增删查改相关的函数
1.push_back
尾插数据时，首先需要判断容器是否已满，若满则去调用reserve
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
2.pop_back
在进行尾删时，需要判断容器是否为空，我们这里并没有实现vector的判空操作，可以利用_finish和_start之间的关系进行判断。
void pop_back(const T& x)
{
assert(_finish > _start);
--_finish;
}
3.insert
insert是在某个位置插入数据，插入数据就存在是否扩容，如果不需要扩容，插入数据时不会存在然后的问题；如果需要扩容，但未调整pos，会存在pos失效；
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
//扩容会导致pos失效，需要更新一下pos
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
void test_vector4()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<int>::iterator it = find(v1.begin(), v1.end(), 2);
if (it != v1.end())
{
//如果insert中发生了扩容，那么会导致it指向的空间被释放
//it本质就是一个野指针，这种问题，我们叫做迭代器失效
v1.insert(it, 30);
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
当插入数据需要扩容时，扩容会将旧空间的数据拷贝到新空间，再释放旧空间，此时pos就指向了一块释放的空间，再对pos位置进行访问时，就属于野指针问题，一般我们还需要加上对pos位置的提前调整，防止迭代器失效。
insert的返回值是
iterator：
虽然在插入数据的过程中调整了pos，解决了内部的迭代器失效问题，但是外部的迭代器（
it
）还是失效的，我们需要将更新后的迭代器利用返回值的形式返回，防止需要再次使用这个迭代器时发生失效。
4.erase
erase也会存在迭代器失效的问题
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
void test_vector5()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
//要求删除v1中所有的偶数
// g++下 vs下
// 1 2 3 4 5 --> 正常 断言报错 vector的迭代器的失效主要是在insert和erase中
// 1 2 3 4 --> 崩溃 断言报错
// 1 2 4 5 --> 结果不对 断言报错
//测试库中的erase --- 存在失效
vector<int> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);
v2.push_back(5);
std::vector<int>::iterator it = v2.begin();
while (it != v2.end())
{
if (*it % 2 == 0)
{
v2.erase(it);
}
++it;
}
/*************************************************/
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
it = v1.erase(it);//每次跟新一下迭代器，不会存在失效了
}
else
{
++it;
}
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
5.swap
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
六、完成代码
#pragma once
namespace vec
{
template<class T>
class vector
{
//typedef T* iterator;//typedef也受访问限定符的限制，放在这里默认是私有的
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;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
//v2(v1)
//传统写法
/*
vector(const vector<T>& v)
{
_start = new T[v.capacity()];
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
memcpy(_start, v._start, v.size() * sizeof(T));//存在浅拷贝
}
vector(const vector<T>& v)
{
_start = new T[v.capacity()]; //让v2开辟一块和v一样大小的空间
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v[i];//通过循环进行赋值
}
//最后调整_finish和_end_of_storage的大小
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
*/
//v2(v1)
//现代写法
//一个类模板的成员函数，又可以是一个函数模板
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(const vector<T>& v)//也支持vector(const vector& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
//this->swap(tmp);
}
//v1 = v2
//vector<T>& operator=(const vector<T>& v) //传统写法
//vector& operator=(vector v)语法上也支持这样写
vector<T>& operator=(vector<T> v)//推荐写
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
//扩容
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * size());存在浅拷贝
for (size_t i = 0; i < sz; i++)
{
//T是int，一个一个拷贝没问题
//T是自定义类型，一个个拷贝调用的是深拷贝赋值，也没问题
tmp[i] = _start[i];
}
delete[]_start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
void resize(size_t n, const T& val = T())
//T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
//扩容会导致pos失效，需要更新一下pos
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
//扩容
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
void pop_back(const T& x)
{
assert(_finish > _start);
--_finish;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}