1.查看vector的源代码
2.模拟实现迭代器
#pragma once
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
typedef T* iterator;//typedef会受到访问限定符的限制
typedef const T* const_iterator;
//const迭代器是指向的对象不能修改，否则岂不是遍历时it都不能++了
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(3);
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
}3.成员函数
3.1构造和析构
#pragma once
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}3.2拷贝构造
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
//vector的拷贝构造
//注意：vector中拷贝数据，数据是内置类型才可以使用memcpy
//否则比如是string，又会出现深层次的浅拷贝问题
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)//这里不初始化的话，去reserve时会是随机值
{
reserve(v.capacity());//capacity函数也要加上const
for (auto& e : v)
{
push_back(e);
}
}
//注意使用引用，T是小对象还好，如果是大对象，代价就大了
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector8()
{
//不写拷贝构造，编译器默认是浅拷贝
//所以不写拷贝构造时,程序会崩溃
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<int> v2(v1);
//vector<int>、vector<string>不是同一个类型
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
}3.3赋值重载
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
void swap(vector<T>& tmp)
{
std::swap(_start, tmp._start);//不加std找不到库中的swap
std::swap(_finish, tmp._finish);
std::swap(_end_of_storage, tmp._end_of_storage);
}
//赋值重载
vector<T>& operator=(vector<T> tmp)//调用赋值要先传参，v3传给tmp是拷贝构造
{
swap(tmp);
return *this;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector8()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
v3.push_back(40);
v1 = v3;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
}3.4.补充：类模板的一个奇怪用法
我们可以发现，库中的拷贝构造，x的类型写的是vector，而不是vector<T>
已知类名不是类型，然而事实上，在类里面，要使用类型的话，使用vector也可以，但不建议这么使用
3.5使用迭代器区间去构造
namespace jxy
{
template <class T>
class vector
{
public:
//注意：在一个类模板里面还可以正常写模板函数
template <class InputIterator>
vector(InputIterator first, InputIterator last)
//VS2019的编译器对内置类型进行了处理，初始化成了0，所以这里没有问题
//但内置类型编译器不一定会处理，所以需要自己写初始化列表
{
while (first != last)
{
push_back(*first);
first++;
}
}
private:
iterator _start = nullptr;//这里把缺省值给上就不需要写初始化列表了
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
void test_vector9()
{
vector<int> v2;
v2.push_back(10);
v2.push_back(20);
v2.push_back(30);
v2.push_back(40);
vector<int> v3(v2.begin(), v2.end());
string str("hello world");
vector<int> v4(str.begin(), str.end());
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}
}为什么要写成模板函数？
因为如果这里使用iterator而不使用模板的话，那么vector使用该构造时就只能使用vector类型的迭代器区间来初始化。而如果写成模板的话，就可以使用各种类型的迭代器来初始化了，只要数据类型匹配就可以。
3.6使用n个val去构造
namespace jxy
{
template <class T>
class vector
{
public:
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
void test_vector9()
{
vector<int> v0(10, 0);//但这里会报错
vector<string> v1(10, "xxxx");//这里正常
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
}
所以我们可以给int类型单独写一个重载函数来解决问题
//有更匹配的之后，就不会去实例化模板了
vector(int n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}4. Capacity
4.1 size和capacity
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
size_t size()
{
return _finish - _start;
}
size_t capacity()
{
return _end_of_storage - _start;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}4.2reserve
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
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());
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
};
}4.3resize
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
//void resize(size_t n,T value=T())
void resize(size_t n, const T& value = T())
{
if (n <= size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = value;
_finish++;
}
}
}
};
void test_vector3()
{
vector<string> v1;
v1.resize(10);
//空的string不会打印出来东西
//v1.resize(10, string("xxx"));
//可以填写匿名对象
//v1.resize(10, "xxx");
//甚至还可以这样写，因为单参数构造函数支持隐式类型转换
vector<int*> v2;
v2.resize(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
}关于resize的参数
void resize(size_t n,T value=T())
这里缺省值不能给0，因为T的类型不能确定就是int
它也可以是double、string等等，所以这里是不能给固定值的
T类型的匿名对象，本质是调用默认构造，然后调用拷贝构造，优化为直接构造
void resize(size_t n, const T& value = T())
这样写就是创建一个匿名对象，然后去引用它
const引用会延长匿名对象的生命周期，延长到val不使用了，就结束了
匿名对象、临时对象具有常性，必须加const
这里缺省值是调用默认构造生成的值
那么问题又来了，如果T是自定义类型，那么匿名对象是有构造函数的
那如果T是内置类型呢？
比如是int，它又没有构造函数，怎么办？事实上，模板设计出来以后，C++语法进行了升级
内置类型也可以认为有构造函数，否则泛型编程就无法使用
void test_vector2()
{//这样写是可以的
int a = 0;
int b(1);
int c = int(2);//在面向对象编程中，可以说一切都是对象
}
5. Element access
5.1 operator[]
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
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;
iterator _finish;
iterator _end_of_storage;
};
}6. Modifiers
6.1 push_back
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
void push_back(const T& x)
{
if (_finish == _end_of_storage)//判断容量是否已满
{
size_t sz = size();
size_t cap = capacity() == 0 ? 4 : capacity() * 2;
//容量为0就开空间，否则就2倍扩容，然后拷贝数据，释放旧空间
T* tmp = new T[cap];
if (_start != nullptr)
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + cap;
}
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}还可以去复用reserve来实现
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}6.2 insert
错误示范：
namespace jxy
{
//模板尽量不要分离编译
template <class T>
class vector
{
public:
void insert(iterator pos,const T& val)
{
assert(pos >= begin());
assert(pos <= end());
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity()*2);
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = val;
_finish++;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(3);
for (auto e:v)
{
cout << e << " ";
}
cout << endl;
v.insert(v.begin() + 2, 100);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//头插
//这里的头插就不需要单独处理了，因为pos不可能是0
v.insert(v.begin(), 100);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
}
但是，只要把测试代码稍作修改，就会发现问题。
void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(3);
v.push_back(4);
v.push_back(4);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//第一次插入数据
v.insert(v.begin() + 2, 100);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//第二次插入数据
v.insert(v.begin(), 100);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//此时push_back如果去复用insert，程序会崩溃
}
6.2.1迭代器失效：野指针
此时就涉及到一个问题，迭代器失效。
insert的正确写法：
void insert(iterator pos,const T& val)
{
assert(pos >= begin());
assert(pos <= end());
if (_finish == _end_of_storage)
{
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 = val;
_finish++;
}
6.3 erase
namespace jxy
{
template <class T>
class vector
{
public:
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector5()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(3);
v.push_back(4);
v.push_back(4);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
vector<int>::iterator pos = v.begin();
v.erase(pos);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
}
6.3.1迭代器失效
何为迭代器失效？
迭代器失效就是不能再使用这个迭代器了，如果使用了，那么结果就是未定义的。
迭代器失效就不能使用它来访问了。
void test_vector6()
{
//想要删除所有偶数
std::vector<int> v;
//1.
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
//2.
//v.push_back(1);
//v.push_back(2);
//v.push_back(3);
//v.push_back(4);
//v.push_back(5);
//v.push_back(6);
//此时多插了个数据就会出问题
//3.
//v.push_back(2);
//v.push_back(2);
//v.push_back(3);
//v.push_back(4);
//v.push_back(5);
//此时程序可以正常运行，但是结果不对，偶数没有删除完
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
auto it = v.begin();
while (it != v.end())
{
//VS2019会进行强制检查
//erase以后认为it就失效了，不允许访问，访问就会报错
if ((*it%2) == 0)
{
v.erase(it);
}
it++;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
6.3.2解决方案
库里erase的实现：
所以要对测试代码进行改进
void test_vector6()
{
//想要删除所有偶数
std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(8);
v.push_back(8);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
auto it = v.begin();
while (it != v.end())
{
if ((*it%2) == 0)
{
it=v.erase(it);
}
else
{
it++;//不删除时才去++
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}此时库中的erase也可以正常使用了。
再来修改下我们模拟实现的erase
namespace jxy
{
template <class T>
class vector
{
public:
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(8);
v.push_back(8);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
auto it = v.begin();
while (it != v.end())
{
if ((*it%2) == 0)
{
it=v.erase(it);
//或者erase不去更改，让它的返回值类型依旧是void，这里写作 v.erase(it); 也可以
}
else
{
it++;//不删除时才去++
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
}6.4总结
使用insert和erase后，我们都认为迭代器失效，不能再访问，使用的话结果是未定义的。
如果想继续使用，可以使用返回值来控制
7.关于深层次的浅拷贝问题
7.1引入
namespace jxy
{
template <class T>
class vector
{
public:
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());
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector7()
{
//深拷贝问题
vector<string> v;
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
//v.push_back("111111111111111111111");
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
}
这是为什么？
7.2解决方案
经过分析可知，主要的问题就是出在memcpy上，那么应该如何改写代码，使得string能够进行深拷贝呢？
实际上只要把memcpy改写成for循环，调用string的赋值就可以解决问题了。
namespace jxy
{
template <class T>
class vector
{
public:
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)//旧空间有可能为空
{
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
//string的赋值重载就是深拷贝
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector7()
{
//深拷贝问题
vector<string> v;
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
}
进一步改进：
这里直接写深拷贝，还是有些浪费，拷贝数据，还要释放旧的空间
如果string使用引用计数的浅拷贝，就非常有价值了。
8.练习题
17. 电话号码的字母组合 - 力扣（LeetCode）
![[ 蓝桥 ·算法双周赛 ] 第 19 场 小白入门赛](https://i-blog.csdnimg.cn/direct/b7139597fb4e4e349b68c13cbc5566cd.png)
