一、运算符重载
C++的运算符重载:使对象的运算运算表现得和编译器内置类型一样
来看这段代码:
template <typename T>
T sum(T a, T b)
{
return a + b; // a调用加法函数,把b当做实参传进去 a.operator+(b)
}
这里的a、b
都没有指定类型,如果我们使用的是编译器的内置类型(例如int
)是没有问题的;但是如果T
类型是对象类型,即a、b
是两个对象,那么对象与对象的相加就要用到运算符重载了!
CComplex复数类
加法运算符重载:
class CComplex
{
public:
CComplex(int r = 0, int i = 0)
:_real(r), _imaginary(i) {}
CComplex operator+(const CComplex& c)
{
/*CComplex tmp;
tmp._real = this->_real + c._real;
tmp._imaginary = this->_imaginary + c._imaginary;
return tmp;*/
// 优化
return CComplex(this->_real + c._real, this->_imaginary + c._imaginary);
}
void show() { cout << "实部:" << _real << " 虚部:" << _imaginary << endl; }
private:
int _real;
int _imaginary;
};
int main()
{
CComplex c1(10, 10);
CComplex c2(20, 20);
// c1.operator+(c2) 加法运算符的重载函数
CComplex c3 = c1 + c2; // 也可以写成本质的形式 c1.operator+(c2)
c3.show(); // 实部:30 虚部:30
}
那么CComplex c4 = c1 + 20;
可不可以呢? 可以
// 本质是c1.operator+(20),实参是20,要 int->CComplex 类型转换
// 会在CComplex类中找构造函数CComplex(int)
// 这里找到CComplex(int r = 0, int i = 0),相当于给r传入20,i为默认的0,生成临时对象
CComplex c4 = c1 + 20;
c4.show(); // 实部:30 虚部:10
那么CComplex c5 = 30 + c1;
可不可以呢? 不可以
运行结果:没有找到接受“CComplex”类型的全局运算符(或没有可接受的转换)
分析:30写在了前面,编译器没有任何理由直接就给它做类型转换,因此无法调用成员方法中的运算符重载函数,因此执行失败。编译器做对象运算的时候,会调用对象的运算符重载函数(优先调用成员方法),如果没有成员方法,就在全局作用域找合适的运算符重载函数,因此现在没法调用到成员方法,并且还没写全局方法,所以报错
解决办法:我们在全局作用域下再提供一个运算符重载函数,同时在类中声明其为友元函数。
class CComplex
{
...
private:
...
friend CComplex operator+(const CComplex& c1, const CComplex& c2);
};
CComplex operator+(const CComplex& c1, const CComplex& c2)
{
return CComplex(c1._real + c2._real, c1._imaginary + c2._imaginary);
}
int main()
{
CComplex c1(10, 10);
...
// ::operator+(30, c1),调用全局方法
// 30会根据CComplex的构造函数做 int->CComplex 的类型转换
CComplex c5 = 30 + c1;
c5.show(); // 实部:40 虚部:10
}
友元函数和友元类的声明可以放在类定义中的任何部分,包括
private
部分。无论它们被声明在何处,都具有访问该类的私有和保护成员的权限。将友元声明放在private
部分通常可以更好地表达友元的特殊访问权限,并保持类的接口部分简洁明了。
可以看到全局的运算符重载可以实现:对象与对象运算、对象与整数运算、整数与对象运算
那么我先就可以把类中的CComplex operator+(const CComplex& c)
删除了,直接用全局的就好了,没必要多写一个
同时注意,全局方法不是用对象调的,因此不能写c1.operator+(c2)
,只能写c1 + c2
++运算符的重载
++/--
都是单目运算符,直接写operator++
这样写无法区分,因此有:
- 前置++:
operator++()
- 后置++:
operator++(int)
class CComplex
{
public:
...
// 后置++重载
CComplex operator++(int)
{
// CComplex tmp = *this;
// _real++;
// _imaginary++;
// return tmp;
// 优化
return CComplex(_real++, _imaginary++);
}
// 前置++重载
CComplex& operator++()
{
_real++;
_imaginary++;
return *this;
}
...
};
int main()
{
CComplex c1(10, 10);
...
CComplex c5 = 30 + c1;
c5.show(); // 实部:40 虚部:10
c5 = c1++;
c1.show(); // 实部:11 虚部:11
c5.show(); // 实部:10 虚部:10
c5 = ++c1;
c1.show(); // 实部:12 虚部:12
c5.show(); // 实部:12 虚部:12
}
复合赋值运算符重载
class CComplex
{
public:
...
CComplex& operator+=(const CComplex& c)
{
_real += c._real;
_imaginary += c._imaginary;
return *this;
}
...
};
int main()
{
CComplex c1(10, 10);
CComplex c2(20, 20);
c1 += c2;
c1.show(); // 实部:30 虚部:30
}
<<运算符重载
template<typename T>
void show(T a) { cout << a << endl; }
如果T
是int
,那没问题,如果现在T
是CComplex
,那么cout
如何打印一个对象呢?因此,我们需要对<<
进行重载
现在不是对象调用的方法,要写成全局方法
class CComplex
{
...
private:
...
friend ostream& operator<<(ostream& out, const CComplex& c);
};
ostream& operator<<(ostream& out, const CComplex& c)
{
out << "实部:" << c._real << " 虚部:" << c._imaginary << endl;
return out;
}
int main()
{
CComplex c1(10, 10);
// cout ::operator<<(cout, c1)
// ostream& operator<<(ostream& out, const CComplex& c)
// 返回值要是cout才对,返回之后是cout << endl;
cout << c1 << endl; // 实部:10 虚部:10
}
>>运算符重载
class CComplex
{
...
private:
...
friend istream& operator>>(istream& in, CComplex& c);
};
istream& operator>>(istream& in, CComplex& c)
{
in >> c._real >> c._imaginary;
return in;
}
int main()
{
CComplex c1;
CComplex c2;
cin >> c1 >> c2;
cout << c1 << c2 << endl;
}
二、实现C++标准库的string类
class String
{
public:
String(const char* p = nullptr)
{
if (p != nullptr)
{
_pstr = new char[strlen(p) + 1];
strcpy(_pstr, p);
}
else
{
_pstr = new char[1];
*_pstr = '\0';
}
}
~String()
{
delete[] _pstr;
_pstr = nullptr;
}
String(const String& str)
{
_pstr = new char[strlen(str._pstr) + 1];
strcpy(_pstr, str._pstr);
}
String& operator=(const String& str)
{
if (this == &str)
return *this;
delete[] _pstr;
_pstr = new char[strlen(str._pstr) + 1];
strcpy(_pstr, str._pstr);
return *this;
}
bool operator>(const String& str) const { return strcmp(_pstr, str._pstr) > 0; }
bool operator<(const String& str) const { return strcmp(_pstr, str._pstr) < 0; }
bool operator==(const String& str) const { return strcmp(_pstr, str._pstr) == 0; }
int length()const { return strlen(_pstr); }
const char* c_str()const { return _pstr; }
// 可读 char ch = str6[3]; 可写 str6[3] = '1';
char& operator[](int index) { return _pstr[index]; }
// 可读 char ch = str6[3]; 不可写
const char& operator[](int index)const { return _pstr[index]; }
private:
char* _pstr;
friend ostream& operator<<(ostream& out, const String& str);
friend String operator+(const String& str1, const String& str2);
};
String operator+(const String& str1, const String& str2)
{
char* ptmp = new char[strlen(str1._pstr) + strlen(str2._pstr) + 1];
strcpy(ptmp, str1._pstr);
strcat(ptmp, str2._pstr);
String tmp(ptmp);
delete[] ptmp;
return tmp;
}
ostream& operator<<(ostream& out, const String& str)
{
out << str._pstr;
return out;
}
int main()
{
String str1;
String str2 = "aaa";
String str3 = "bbb";
String str4 = str2 + str3;
String str5 = str2 + "ccc";
String str6 = "ddd" + str2;
cout << "str6:" << str6 << endl;
if (str5 > str6) cout << str5 << ">" << str6 << endl;
else cout << str5 << "<" << str6 << endl;
int len = str6.length();
for (int i = 0; i < len; ++i)
cout << str6[i] << " "; // str6.operator[](i),返回char&
cout << endl;
char buf[1024] = { 0 };
// c_str:string -> char*
strcpy(buf, str6.c_str());
cout << "buf:" << buf << endl;
return 0;
}
输出结果:
str6:dddaaa
aaaccc<dddaaa
d d d a a a
buf:dddaaa
存在的问题:operator+
效率低下
String operator+(const String& str1, const String& str2)
{
char* ptmp = new char[strlen(str1._pstr) + strlen(str2._pstr) + 1];
strcpy(ptmp, str1._pstr);
strcat(ptmp, str2._pstr);
String tmp(ptmp);
delete[] ptmp;
return tmp;
}
功能正确,效率低下。
ptmp
指向了一块内存,进行字符串拷贝与连接之后,将它当作一个参数传入tmp
字符串对象中,tmp
字符串构造函数中,又会根据外面传入的指针,开辟字符串底层的指针,再进行数据拷贝,最后再将字符串ptmp
内存delete
,return tmp;
析构tmp
总共发生了2次new
,2次delete
,效率太低。
改进:
String operator+(const String& str1, const String& str2)
{
String tmp;
tmp._pstr = new char[strlen(str1._pstr) + strlen(str2._pstr) + 1];
strcpy(tmp._pstr, str1._pstr);
strcat(tmp._pstr, str2._pstr);
return tmp;
}
直接定义一个tmp
对象,直接为其底层进行内存开辟,拷贝与连接也直接到其底层的字符串对象中,最后出作用域析构将其底层指针delete
。总共发生了1次new
,1次delete
,效率提高了。
但这依旧不是最优版本,return tmp;
会产生临时对象,调用拷贝构造又会进行内存开辟,临时对象还会析构。这也是需要优化的,在之后C++语言高级进阶课程的课程笔记中会讲到
三、迭代器
迭代器(iterator)是C++中用于遍历容器(如vector
、list
、deque
、set
、map
等)中元素的对象。迭代器提供了一种通用的方法来访问容器中的元素,而无需关心容器底层的实现细节(透明的访问容器内部的元素的值)。迭代器类似于指针,但它更加安全,因为它被设计为只能向前移动(除了双向迭代器和随机访问迭代器)。
在我们之后学习的泛型算法,接收的也都是迭代器
迭代器一般实现成容器的嵌套类型
实现string类的迭代器
class String
{
public:
...
class iterator
{
public:
iterator(char* p = nullptr) :_p(p) {}
bool operator!=(const iterator& it) const { return _p != it._p; }
void operator++() { ++_p; }
char& operator*() { return *_p; }
private:
char* _p;
};
// 返回的是容器底层首元素迭代器的表示
iterator begin() { return iterator(_pstr); }
// 返回的是容器末尾元素后继位置的迭代器的表示
iterator end() { return iterator(_pstr + length()); }
private:
char* _pstr;
....
};
int main()
{
String str1 = "Hello world!";
// String::iterator it = str1.begin();
auto it = str1.begin();
for (; it != str1.end(); ++it)
cout << *it << " ";
cout << endl;
// foreach的方式(底层也是通过迭代器遍历,如果把begin和end方法去掉,foreach会报错)
for (char ch : str1)
cout << ch << " ";
cout << endl;
return 0;
}
实现vector类的迭代器
之前实现了vector容器及其空间配置器 传送门,接下来我们实现一下vector类的迭代器
template<typename T>
class Allocator { ... };
template<typename T, typename Alloc = Allocator<T>>
class vector
{
public:
...
// 重载[]
T& operator[](int index)
{
if (index < 0 || index >= size())
throw "OutOfRangeException";
return _first[index];
}
// 迭代器一般实现成容器的嵌套类型
class iterator
{
public:
iterator(T* ptr = nullptr) :_ptr(ptr) {}
bool operator!=(const iterator& it) const { return _ptr != it._ptr; }
void operator++() { ++_ptr; }
T& operator*() { return *_ptr; } //可以修改,如 int data = *it; *it = 20;
const T& operator*() const { return *_ptr; } //不可修改
private:
T* _ptr;
};
// 需要给容器提供begin和end方法
iterator begin() { return iterator(_first); }
iterator end() { return iterator(_last); }
private:
T* _first;
T* _last;
T* _end;
...
};
int main()
{
vector<int> vec;
for (int i = 0; i < 5; ++i)
vec.push_back(i);
// 三种打印方式
int size = vec.size();
for (int i = 0; i < size; ++i)
cout << vec[i] << " ";
cout << endl;
for (auto it = vec.begin(); it != vec.end(); ++it)
cout << *it << " ";
cout << endl;
for (int i : vec) // 底层是迭代器实现,需要有begin和end
cout << i << " ";
cout << endl;
return 0;
}
迭代器失效的底层原理
迭代器的失效:对容器的操作影响了元素的存放位置,称为迭代器失效。
先来看vector
库
// 问题一:
vector<int>vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
//把vec容器中所有的偶数全部删除
auto it = vec.begin();
for (; it != vec.end(); ++it)
{
if (*it % 2 == 0)
{
// 迭代器失效问题,第一次调用erase之后,迭代器it就失效了
vec.erase(it);
// break;
// 加上break,只删第一个,就不会有问题;去掉break则报错
}
}
// 问题2:
vector<int>vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
// 给vec容器中所有的偶数前面添加一个比其小1的数字
auto it = vec.begin();
for (; it != vec.end(); ++it)
{
if (*it % 2 == 0)
{
// 迭代器失效问题,第一次调用insert之后,迭代器it就失效了
vec.insert(it, *it - 1);
// break;
// 加上break,只删第一个,就不会有问题;去掉break则报错
}
}
失效情况:
- 当容器调用
erase()
方法后,当前位置到容器末尾元素的所有迭代器全部失效 - 当容器调用
insert()
方法后,当前位置到容器末尾元素的所有迭代器全部失效 - 如果容器扩容,如调用
insert()
方法后的容器扩容,即在其他地方重新又开辟了一块内存,那么原来容器的所有迭代器就全都失效了
解决办法:对插入/删除点的迭代器进行更新操作
// 问题1解决:
vector<int>vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
auto it = vec.begin();
while (it != vec.end())
{
if (*it % 2 == 0)
it = vec.erase(it);
else
++it;
}
// 问题2解决:
vector<int>vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
auto it = vec.begin();
for (; it != vec.end(); ++it)
{
if (*it % 2 == 0)
{
it = vec.insert(it, *it - 1);
++it;
// 遇见偶数,在其前面插入一个,把偶数就挤到后面去了
// 所以it一共++两次,跳过偶数
}
}
接下来,解决我们自己写的vector的迭代器失效问题
在
iterator
类中私有成员下添加vector<T>* _pVec;
,让迭代器知道当前迭代的容器是哪个,因为不同容器之间不能相互比较,同一容器的迭代器比较才有意义容器迭代器失效增加代码,它是一个结构体维护的链表,写在
vector
类中
_cur
是指向某一个迭代器的指针
_next
是指向下一个Iterator_Base
结点
_head
是头节点
Iterator_Base
链表记录用户现在获取的是哪个元素的迭代器,增加或删除相应元素的时候,要让其失效并重新更新。// 容器迭代器失效增加代码 // struct中的成员默认都是public的 struct Iterator_Base { Iterator_Base(iterator* c = nullptr, Iterator_Base* n = nullptr) :_cur(c), _next(n) {} iterator* _cur; Iterator_Base* _next; }; Iterator_Base _head;
迭代器
iterator
的构造函数:新生成当前容器某一个位置元素的迭代器iterator(vector<T>* pvec = nullptr, T* ptr = nullptr) :_pVec(pvec), _ptr(ptr) { // 这里是链表的头插法 Iterator_Base* itb = new Iterator_Base(this, _pVec->_head._next); _pVec->_head._next = itb; }
原先写的重载函数要检查有效性
bool operator!=(const iterator& it) const { // 检查迭代器有效性 if (_pVec == nullptr || _pVec != it._pVec) throw "iterator incompatible!"; return _ptr != it._ptr; } void operator++() { // 检查迭代器有效性 if (_pVec == nullptr) throw "iterator invalid!"; ++_ptr; } T& operator*() //可以修改,如 int data = *it; *it = 20; { // 检查迭代器有效性 if (_pVec == nullptr) throw "iterator invalid!"; return *_ptr; } const T& operator*() const //不可修改 { // 检查迭代器有效性 if (_pVec == nullptr) throw "iterator invalid!"; return *_ptr; }
verify
检查迭代器失效。在我们增加或删除后,把我们当前节点的地址到末尾的地址,全部传入verify
进行检查,在存储的迭代器链表上进行遍历,若在检查范围内,就将相应迭代器指向容器的指针_pVec
置为空,即为失效的迭代器。// 检查迭代器失效 void verify(T* first, T* last) { Iterator_Base* pre = &this->_head; // 指向头结点 Iterator_Base* it = this->_head._next; // 指向第一个结点 while (it != nullptr) { // 在传入范围内,则置成失效 if (it->_cur->_ptr >= first && it->_cur->_ptr < last) { // 迭代器失效,把iterator持有的容器指针置nullptr it->_cur->_pVec = nullptr; // 删除当前迭代器节点,继续判断后面的迭代器节点是否失效 pre->_next = it->_next; delete it; it = pre->_next; } else { pre = it; it = it->_next; } } }
pop_back
中加入了verfiy
void pop_back() { if (empty()) return; verify(_last - 1, _last); // --_last; // 不仅要--_last,还需要析构删除的元素 --_last; _allocator.destruct(_last); }
若为
erase(it);
,则verify(it._ptr, _last);
若为insert(it);
,则verify(it._ptr, _last);
自定义
insert
实现(不考虑扩容与it._ptr
合法性)
容器之前使用空间配置器实现的,在某个位置插入,要把后面的元素都往后挪
即从最后一个元素开始,每个元素往后拷贝构造,同时把本身位置的元素析构// 自定义vector容器insert方法实现 // 不考虑扩容与it._ptr合法性 iterator insert(iterator it, const T& val) { verify(it._ptr, _last); T* p = _last; while (p > it._ptr) { _allocator.construct(p, *(p - 1)); _allocator.destruct(p - 1); p--; } _allocator.construct(p, val); _last++; return iterator(this, p); }
如果要考虑扩容,那就要
verify(_first, _last);
使所有位置的迭代器都失效自定义erase实现
在某个位置删除元素,后面所有元素都要往前挪
即从当前位置开始,把当前元素析构,把下一个的元素拷贝构造到当前位置
测试案例1: 使用pop_back
看一下迭代器失效
int main()
{
vector<int> vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
auto it1 = vec.end();
vec.pop_back();
auto it2 = vec.end();
cout << (it1 != it2) << endl; // 1
// pop_back之后verify使it1失效
}
测试案例2: 使用insert
并对迭代器更新
int main()
{
vector<int> vec(200);
for (int i = 0; i < 20; ++i)
vec.push_back(i);
for (int v : vec)
cout << v << " ";
cout << endl;
auto it = vec.begin();
for (; it != vec.end(); ++it)
{
if (*it % 2 == 0)
{
it = vec.insert(it, *it - 1); // 更新当前增加位置迭代器
++it;
// 遇见偶数,前面插入一个,把偶数就挤到后面去了,所以it一共++两次,跳过偶数
}
}
for (int v : vec)
cout << v << " ";
cout << endl;
}
运行结果:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
-1 0 1 1 2 3 3 4 5 5 6 7 7 8 9 9 10 11 11 12 13 13 14 15 15 16 17 17 18 19
测试案例3: 使用erase并
对迭代器更新
int main()
{
vector<int> vec(200);
for (int i = 0; i < 20; ++i)
vec.push_back(i);
for (int v : vec)
cout << v << " ";
cout << endl;
// 把vec容器中所有的偶数全部删除
auto it = vec.begin();
while (it != vec.end())
{
if (*it % 2 == 0)
it = vec.erase(it);
else
++it;
}
for (int v : vec)
cout << v << " ";
cout << endl;
}
运行结果:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 3 5 7 9 11 13 15 17 19
完整源码:
// 定义容器的空间配置器,和C++标准库的allocator实现一样
template<typename T>
class Allocator
{
public:
T* allocate(size_t size) // 负责内存开辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void* p) // 负责内存释放
{
free(p);
}
void construct(T* p, const T& val)// 负责对象构造
{
new (p) T(val); // 定位new
// 在指定内存上构造一个值为val的对象,这回调用T的拷贝构造
}
void destruct(T* p) // 负责对象析构
{
p->~T(); // ~T()代表了T类型的析构函数
}
};
// 注意不要只写Allocator,这是模板名称,要是类名称才对
template<typename T, typename Alloc = Allocator<T>>
class vector
{
public:
vector(int size = 10)
{
// 需要把内存开辟和对象构造分开处理
// _first = new T[size];
_first = _allocator.allocate(size);
_last = _first;
_end = _first + size;
}
~vector()
{
// 析构容器中有效的元素,然后释放_first指针指向的堆内存
// delete[] _first;
for (T* p = _first; p != _last; ++p)
_allocator.destruct(p); // 析构有效元素
_allocator.deallocate(_first); // 释放堆上的数组内存
_first = _last = _end = nullptr;
}
vector(const vector<T>& vec)
{
int size = vec._end - vec._first;
// _first = new T[size];
_first = _allocator.allocate(size);
int len = vec._last - vec._first;
for (int i = 0; i < len; ++i)
{
// _first[i] = vec._first[i];
_allocator.construct(_first + i, vec._first[i]);
}
_last = _first + len;
_end = _first + size;
}
vector<T>& operator=(const vector<T>& vec)
{
if (this == &vec)
return *this;
// delete[] _first;
// 和析构~vector()一样
for (T* p = _first; p != _last; ++p)
_allocator.destruct(p); // 析构有效元素
_allocator.deallocate(_first); // 释放堆上的数组内存
// 和拷贝构造一样
int size = vec._end - vec._first;
// _first = new T[size];
_first = _allocator.allocate(size);
int len = vec._last - vec._first;
for (int i = 0; i < len; ++i)
{
// _first[i] = vec._first[i];
_allocator.construct(_first + i, vec._first[i]);
}
_last = _first + len;
_end = _first + size;
}
void push_back(const T& val)
{
if (full())
expend();
// *_last++ = val;
// 现在要在_last指针指向的内存构造一个值为val的对象
_allocator.construct(_last, val);
++_last;
}
void pop_back()
{
if (empty())
return;
verify(_last - 1, _last);
// --_last;
// 不仅要--_last,还需要析构删除的元素
--_last;
_allocator.destruct(_last);
}
T back() const
{
return *(_last - 1);
}
bool full() const { return _last == _end; }
bool empty() const { return _first == _last; }
int size() const { return _last - _first; }
// 重载[]
T& operator[](int index)
{
if (index < 0 || index >= size())
throw "OutOfRangeException";
return _first[index];
}
// 迭代器一般实现成容器的嵌套类型
class iterator
{
public:
friend class vector<T>;
iterator(vector<T>* pvec = nullptr, T* ptr = nullptr)
:_pVec(pvec), _ptr(ptr)
{
// 这里是链表的头插法
Iterator_Base* itb = new Iterator_Base(this, _pVec->_head._next);
_pVec->_head._next = itb;
}
bool operator!=(const iterator& it) const
{
// 检查迭代器有效性
if (_pVec == nullptr || _pVec != it._pVec)
throw "iterator incompatible!";
return _ptr != it._ptr;
}
void operator++()
{
// 检查迭代器有效性
if (_pVec == nullptr)
throw "iterator invalid!";
++_ptr;
}
T& operator*() //可以修改,如 int data = *it; *it = 20;
{
// 检查迭代器有效性
if (_pVec == nullptr)
throw "iterator invalid!";
return *_ptr;
}
const T& operator*() const //不可修改
{
// 检查迭代器有效性
if (_pVec == nullptr)
throw "iterator invalid!";
return *_ptr;
}
private:
T* _ptr;
// 当前迭代器迭代的是哪个容器
vector<T>* _pVec;
// 写成 vector<T, Alloc> 也行,Alloc不写用的默认的
};
// 需要给容器提供begin和end方法
iterator begin() { return iterator(this, _first); }
iterator end() { return iterator(this, _last); }
// 检查迭代器失效
void verify(T* first, T* last)
{
Iterator_Base* pre = &this->_head; // 指向头结点
Iterator_Base* it = this->_head._next; // 指向第一个结点
while (it != nullptr)
{
// 在传入范围内,则置成失效
if (it->_cur->_ptr >= first && it->_cur->_ptr < last)
{
// 迭代器失效,把iterator持有的容器指针置nullptr
it->_cur->_pVec = nullptr;
// 删除当前迭代器节点,继续判断后面的迭代器节点是否失效
pre->_next = it->_next;
delete it;
it = pre->_next;
}
else
{
pre = it;
it = it->_next;
}
}
}
// 自定义vector容器insert方法实现
// 不考虑扩容与it._ptr合法性
iterator insert(iterator it, const T& val)
{
verify(it._ptr, _last);
T* p = _last;
while (p > it._ptr)
{
_allocator.construct(p, *(p - 1));
_allocator.destruct(p - 1);
p--;
}
_allocator.construct(p, val);
_last++;
return iterator(this, p);
}
// 自定义vector容器erase方法实现
iterator erase(iterator it)
{
verify(it._ptr, _last);
T* p = it._ptr;
while (p < _last - 1)
{
_allocator.destruct(p);
_allocator.construct(p, *(p + 1));
p++;
}
// 把_last-1位置的元素单独析构,再把_last指向他
_allocator.destruct(p);
_last--;
return iterator(this, it._ptr);
}
private:
T* _first; // 指向数组起始位置
T* _last; // 指向数组中有效元素的后继位置
T* _end; // 指向数组空间的后继位置
Alloc _allocator; // 定义容器的空间配置器对象
// 容器迭代器失效增加代码
// struct中的成员默认都是public的
struct Iterator_Base
{
Iterator_Base(iterator* c = nullptr, Iterator_Base* n = nullptr)
:_cur(c), _next(n) {}
iterator* _cur;
Iterator_Base* _next;
};
Iterator_Base _head;
void expend()
{
int size = _end - _first;
//T* ptmp = new T[2 * size];
T* ptmp = _allocator.allocate(2 * size);
for (int i = 0; i < size; ++i)
{
// ptmp[i] = _first[i];
_allocator.construct(ptmp + i, _first[i]);
}
//delete[] _first;
for (T* p = _first; p != _last; ++p)
_allocator.destruct(p); // 析构有效元素
_allocator.deallocate(_first); // 释放堆上的数组内存
_first = ptmp;
_last = _first + size;
_end = _first + 2 * size;
}
};
四、剖析new的delete的原理
在之前这篇文章当中简单介绍过new与delete
这里我们再来看一下new与malloc、delete与free的区别
new与malloc的区别:
malloc
按字节开辟内存(要用sizeof
);new
开辟内存时需要指定类型(new int[10]
)malloc
开辟内存返回的都是void*
;new
相当于运算符重载函数,返回值自动转为指定的类型的指针malloc
只负责开辟内存空间;new
不仅仅也有malloc
功能,还可以进行数据的初始化(new int(20);
new int[20](); // 20个都置为零
)malloc
开辟内存失败返回nullptr
指针;new
抛出的是bad_alloc
类型的异常,不能通过返回值和空指针进行比较,一般使用try catch
malloc
开辟单个元素内存与数组内存是一样的,都是给字节数;new
开辟时对单个元素内存后面不需要[]
,而数组需要[]
并给上元素个数
free和delete的区别:
delete
先调用析构函数,再free
,如果是普通类型,例如int*
的指针,那么两者一样free
不管释放单个元素内存还是数组内存,只需要传入内存的起始地址即可delete
释放单个元素内存,不需要加中括号,但释放数组内存时需要加中括号
现在来深入剖析一下new与delete的原理
int* p = new int;
delete p;
反汇编:
可见new
与delete
其底层其实就是他们重载函数函数的调用
我们实现一下new
与delete
的重载函数
// 如果是对象,首先调用operator new开辟内存空间,然后调用对象的构造函数
void* operator new(size_t size)
{
void* p = malloc(size);
if (p == nullptr)
throw bad_alloc();
cout << "operator new addr: " << p << endl;
return p;
}
// delete p; 如果是对象,首先调用析构函数,再调用operator delete释放内存空间
void operator delete(void* p)
{
cout << "operator delete addr: " << p << endl;
free(p);
}
int main()
{
// 一般new会用try catch包裹
// try {
// int* p = new int;
// delete p;
// }
// catch (const bad_alloc& err) {
// cerr << err.waht() <<endl;
// }
int* p = new int;
delete p;
return 0;
}
运行结果:
operator new addr: 013A2D28
operator delete addr: 013A2D28
注意:构造和析构函数的调用由编译器在调用
operator new/delete
的时候自动处理,因此在重载函数里只需要处理内存开辟/释放的部分
再来实现一下带数组的new
和delete
void* operator new[](size_t size)
{
void* p = malloc(size);
if (p == nullptr)
throw bad_alloc();
cout << "operator new[] addr: " << p << endl;
return p;
}
void operator delete[](void* p)
{
cout << "operator delete[] addr: " << p << endl;
free(p);
}
int main()
{
int* q = new int[10];
delete[] q;
return 0;
}
运行结果:
operator new[] addr: 00EE2D28
operator delete[] addr: 00EE2D28
那么,new new[] delete delete[]
能混用吗?C++为什么区分单个元素和数组的内存分配和释放呢?
普通类型:能够混用
int *p = new int;
delete[]p;
int *q = new int[10];
delete q;
对于整型来说,没有构造函数与析构函数,针对于int
类型,new
与delete
功能只剩下malloc
和free
的功能,可以混用
类:不能混用
创建一个Test类
class Test
{
public:
Test() { cout << "Test()构造" << endl; }
~Test() { cout << "~Test()析构" << endl; }
private:
int ma; // 作用只是体现出一个Test对象是4个字节
};
代码示例:
Test* p1 = new Test();
delete p1;
// delete[] p1; // 不能混用,报错
运行结果:
operator new addr: 013F2D28
Test()构造
~Test()析构
operator delete addr: 013F2D28
代码示例:
Test* p2 = new Test[5];
cout << "p2: " << p2 << endl;
delete[] p2;
// delete p2; // 不能混用,报错
运行结果:
operator new[] addr: 00CF0B90
Test()构造
Test()构造
Test()构造
Test()构造
Test()构造
p2: 00CF0B94 # p2比operator new[] addr多4,前面4个存储数组的信息
~Test()析构
~Test()析构
~Test()析构
~Test()析构
~Test()析构
operator delete[] addr: 00CF0B90
针对以上结果,我们来分析一下
对于new Test[5]
,Test
对象占4字节,分配了5个Test
对象,那么一共占用20个字节吗?并不是
还要多开辟一块内存(根据类型大小不同,一般4字节),来存储数组中对象的个数
即new Test[5]
总共开辟4 + 5 * 4
个字节
new Test[5]
给用户返回的是0x104
,p2
指向的是0x104
但是delete[]
让编译器知道释放的是一个数组,那么会从0x100
开始释放内存
如果写delete p2
,是从0x104
释放,编译器会认为p2
只是指向了一个对象,因此只会将Test[0]
对象析构,程序崩溃
对p1
而言,从0x104
开始开辟内存,只有一个对象,但是delete[] p1
会让编译器从0x100
开始释放一个对象数组的内存,因此程序崩溃
结论:
- 对于普通的编译器内置类型,可以混用
- 自定义的类类型,有析构函数,为了调用正确的析构函数,那么开辟对象数组时会多开辟4个字节记录对象的个数,不能混用