模板 =》 实现一个C++ STL里面的一个顺序容器 vector 向量容器（底层是数组，内存是连续的，2倍扩容
vecotor：使用了三个指针！！！
#includeusing namespace std; template //初始化，让用户不用指定，用默认的 class vector { public: vector(int size = 10)//构造函数 { _first = new T[size]; _last = _first; _end = _first + size; } ~vector()//析构函数 { //析构容器有效的元素，然后释放_first指针指向的堆内存 delete[]_first; _first = _last = _end = nullptr; } //重写拷贝构造函数 vector(const vector & rhs) { int size = rhs._end - rhs._first;//空间大小 _first = new T[size]; int len = rhs._last - rhs._first;//有效数据的长度 for (int i = 0; i < len; ++i) { _first[i] = rhs._first[i]; } _last = _first + len; _end = _first + size; } //重写赋值重载函数 vector & operator=(const vector & rhs) { if (this == &rhs) return *this; delete[]_first; int size = rhs._end - rhs._first; _first = new T[size]; int len = rhs._last - rhs._first; for (int i = 0; i < len; ++i) { _first[i] = rhs._first[i]; } _last = _first + len; _end = _first + size; return *this; } void push_back(const T& val)//向容器末尾添加元素 { if (full()) expand(); *_last++ = val; //_last指针指向的内存构造一个值为val的对象 } void pop_back()//从容器末尾删除元素 { if (empty()) return; --_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; } private: T* _first;//指向数组起始的位置 T* _last; //指向数组中有效元素的后继位置 T* _end;//指向数组空间的后继位置 void expand()//容器的二倍扩容 { int size = _end - _first; T *ptmp = new T[2 * size]; for (int i = 0; i < size; ++i) { ptmp[i] = _first[i]; } delete[]_first; _first = ptmp; _last = _first + size; _end = _first + 2 * size; } }; int main() { vector vec; for (int i = 0; i < 20; ++i) { vec.push_back(rand() % 100); } while (!vec.empty()) { cout << vec.back() << " "; vec.pop_back(); } cout << endl; return 0; }
上面用类模板实现了一个容器类！
上面写的和容器中的vector有什么区别？
- 缺一个非常重要的东西：空间配置器allocator！！！
STL中的vector：
问题：容器为什么要用空间配置器allocator，不用会怎么样？
2、理解容器空间配置器allocator的重要性
重要性：
- 容器的空间配置器allocator 做四件事情 内存开辟/内存释放 对象构造/对象析构
如果我们不使用空间配置器，仅仅是实现普通的vector类；
我们定义一个测试类Test：
现在只是定义了一个vector，没有push过元素。
但是运行一下
一个空容器，竟然构造了10个Test对象，出作用域析构的时候，析构了10个Test对象。
但是目前我们就定义了一个空容器，没有放任何东西，为什么要构造这么多对象出来？
- 因为我们在vector的构造函数中使用了new操作了，不仅仅开辟了空间，还在每个内存空间上构造了对象；
- 这对象不是我们想要的，如果我们传了1000，只是定义了容器，但是又构造了1000次，析构1000次，这不合理！！！
我们在构造时需要把内存开辟和对象构造分开处理！！！
- 当我定义容器对象的时候，底层应该只是负责开辟空间而已，不能去构造对象的！
- 析构的时候，不能直接用delete，delete相当于数组的每个元素都当做有效对象去析构了，我们应该怎么操作？
数组可能很长，但是里面可能只有几个元素：
我们应该是在容器不需要的时候，把里面的有效元素析构掉，然后把整个数组的内存释放掉。析构函数应该是析构容器有效的元素，然后释放_first指针指向的堆内存。）
我们写代码进行测试：
push_back：
- 按道理来说，push_back之前，容器只开辟了内存，没有在内存上构造对象；
- 当执行push_back的时候，这里的t1,t2,t3相当于在容器底层的某一块内存上构造新对象。
- 但是现在不是这样，现在生成容器的时候底层是用new，相当于容器的每个内存空间都放了一个Test对象，相当于是把t1,t2,t3去给Test对象赋值，这个逻辑不正确！！！
pop_back：
- 对于pop_back，这个容器底层的对象很可能有占用外部资源；
- 而现在的pop_back只是把last指针，减减了而已，这个外部资源很可能找不到了，被下次push_back的新的指针覆盖了。
- pop_back的对象很可能占用外部资源，不能不管。（之前的代码是没有管的，只是指针–）
而且我们还不能用delete去释放它， 因为delete不仅仅析构对象和外部资源，还把这个数组的内存空间给free掉了。
在内存管理中，我们不能直接用new和delete：
- new：内存开辟和对象构造在一起；
- delete：对象析构和内存释放在一起；
因此我们要将 内存开辟/内存释放 对象构造/对象析构 分开。
#includeusing namespace std; template //初始化，让用户不用指定，用默认的 class vector { public: vector(int size = 10)//构造函数 { _first = new T[size]; _last = _first; _end = _first + size; } ~vector()//析构函数 { //析构容器有效的元素，然后释放_first指针指向的堆内存 delete[]_first; _first = _last = _end = nullptr; } //重写拷贝构造函数 vector(const vector & rhs) { int size = rhs._end - rhs._first;//空间大小 _first = new T[size]; int len = rhs._last - rhs._first;//有效数据的长度 for (int i = 0; i < len; ++i) { _first[i] = rhs._first[i]; } _last = _first + len; _end = _first + size; } //重写赋值重载函数 vector & operator=(const vector & rhs) { if (this == &rhs) return *this; delete[]_first; int size = rhs._end - rhs._first; _first = new T[size]; int len = rhs._last - rhs._first; for (int i = 0; i < len; ++i) { _first[i] = rhs._first[i]; } _last = _first + len; _end = _first + size; return *this; } void push_back(const T& val)//向容器末尾添加元素 { if (full()) expand(); *_last++ = val; //_last指针指向的内存构造一个值为val的对象 } void pop_back()//从容器末尾删除元素 { if (empty()) return; --_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; } private: T* _first;//指向数组起始的位置 T* _last; //指向数组中有效元素的后继位置 T* _end;//指向数组空间的后继位置 void expand()//容器的二倍扩容 { int size = _end - _first; T *ptmp = new T[2 * size]; for (int i = 0; i < size; ++i) { ptmp[i] = _first[i]; } delete[]_first; _first = ptmp; _last = _first + size; _end = _first + 2 * size; } }; class Test { public: Test() { cout << "Test()" << endl; } ~Test() { cout << "~Test()" << endl; } Test(const Test&) { cout << "Test(const Test&)" << endl; } }; int main() { Test t1, t2, t3; cout << "-------------------" << endl; vector vec; vec.push_back(t1); vec.push_back(t2); vec.push_back(t3); cout << "-------------------" << endl; vec.pop_back();//只需要析构对象，不许释放内存。 要把对象的析构和内存释放分离开 不能用delete cout << "-------------------" << endl; return 0; }
这就引出了容器空间配置器！
容器的空间配置器allocator 做四件事情 内存开辟/内存释放 对象构造/对象析构
#includeusing namespace std; //定义容器的空间配置器，和C++标准库的allocator实现一样 template struct Allocator//模板类 struct定义 默认公有的 { 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 } void destroy(T* p)//负责对象析构 { p->~T();//~T()代表了T类型的析构函数 p指向的对象的析构 } }; template >//初始化，让用户不用指定，用默认的 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.destroy(p);//把_first指针指向的数组的有效元素进行析构操作 } //再释放内存 _allocator.deallocate(_first);//释放堆上的数组内存 _first = _last = _end = nullptr; } //重写拷贝构造函数 vector(const vector & rhs) { int size = rhs._end - rhs._first;//空间大小 //_first = new T[size]; //内存开辟 _first = _allocator.allocate(size); int len = rhs._last - rhs._first;//有效数据的长度 //对象构造 for (int i = 0; i < len; ++i) { //_first[i] = rhs._first[i]; _allocator.construct(_first + i, rhs._first[i]); } _last = _first + len; _end = _first + size; } //重写赋值重载函数 vector & operator=(const vector & rhs) { if (this == &rhs) return *this; //delete[]_first; //先析构对象 for (T* p = _first; p != _last; ++p) { _allocator.destroy(p);//把_first指针指向的数组的有效元素进行析构操作 } //释放内存 _allocator.deallocate(_first); int size = rhs._end - rhs._first; //_first = new T[size]; _first = _allocator.allocate(size); int len = rhs._last - rhs._first; for (int i = 0; i < len; ++i) { //_first[i] = rhs._first[i]; _allocator.construct(_first + i, rhs._first[i]); } _last = _first + len; _end = _first + size; return *this; } void push_back(const T& val)//向容器末尾添加元素 { if (full()) expand(); //*_last++ = val; _last指针指向的内存构造一个值为val的对象 _allocator.construct(_last, val); _last++; } void pop_back()//从容器末尾删除元素 { if (empty()) return; //--_last; //不仅要把_last指针--，还需要析构删除的元素 --_last; _allocator.destroy(_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; } private: T* _first;//指向数组起始的位置 T* _last; //指向数组中有效元素的后继位置 T* _end;//指向数组空间的后继位置 Alloc _allocator;//定义容器的空间配置器对象 void expand()//容器的二倍扩容 { 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.destroy(p); } _allocator.deallocate(_first); _first = ptmp; _last = _first + size; _end = _first + 2 * size; } }; class Test { public: Test() { cout << "Test()" << endl; } ~Test() { cout << "~Test()" << endl; } Test(const Test&) { cout << "Test(const Test&)" << endl; } }; int main() { Test t1, t2, t3; cout << "-------------------" << endl; vector vec; vec.push_back(t1); vec.push_back(t2); vec.push_back(t3); cout << "-------------------" << endl; vec.pop_back();//只需要析构对象。 要把对象的析构和内存释放分离开 delete cout << "-------------------" << endl; return 0; }
- pop_back调用了析构函数，将对象析构了！
- push_back时，这里是在底层针对t1t2t3调用拷贝构造了对象
