文章目录
- vector的模拟实现
vector的模拟实现
- begin()
- end()
- size()
- capacity()
- reserve()
- push_back()
- pop_back()
- empty()
- operator[]
- insert()
vector.h
#pragma once#include<iostream>
#include<list>
#include<assert.h>
#include<string>using namespace std;namespace wbc
{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;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}// 扩容void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}size_t size() const {return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty(){return _finish == _start;}void pop_back(){assert(!empty());--_finish;}iterator insert(iterator pos, const T& x){if (_finish == _end_of_storage){// 扩容后_start可能会变size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;// 所以更新一下pos,不让pos指向原来的空间}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};/*void vector_print(const vector<int>& v){vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto x : v){cout << x << " ";}cout << endl;}*/template<class T>void vector_print(const vector<T>& v){// 规定没有实例化的类模版里取东西，编译器是无法区分const_iterator是// 静态成员变量还是类型,加了typename 就表明是类型// typename vector<T>::const_iterator it = v.begin();auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto x : v){cout << x << " ";}cout << endl;}void test_vector1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i = 0; i < v.size(); i++)cout << v[i] << " ";cout << endl;vector<int>::iterator it = v.begin();for (size_t i = 0; i < v.size(); i++){cout << *it << " ";++it;}cout << endl;for (auto x : v)cout << x << " ";cout << endl;vector_print(v);vector<double> vv;vv.push_back(1.1);vv.push_back(2.2);vv.push_back(3.3);vv.push_back(4.4);vv.push_back(5.5);vector_print(vv);}void test_vector2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vector_print(v);v.insert(v.begin() + 2, 30);vector_print(v);int x;cin >> x;auto pos = find(v.begin(), v.end(), x);if (pos != v.end()){pos = v.insert(pos, 30);//(*pos) *= 10;(*(pos+1)) *= 10;}vector_print(v);}
}
test.cpp
#include"vector.h"int main()
{wbc::test_vector2();return 0;
}
模版不能分离到两个文件 .h和.cpp,会出现链接错误
reserve是不缩容的
- vector<vector< int >> 调用的是两个类的模版
- vector的底层
protected:
iterator start;
// 数据开始的位置
iterator finish; // 指针 + size()
// 数据结束的下一个位置
iterator end_of_storage;// 指针 + capacity()
// 空间结束的下一个位置insert_aux(end(),x);
// end() 数据结束的下一个位置
// 在最后一个位置插入x,相当于尾插
- reserve是怎么给_start,_finish和_end_of_storage的？
// 错误写法
reserve(n > capacity)
{_start = tmp;_finish = tmp + size();// size() 为 _finish - _start// 之前的_finish减去更新后的_start// 这样肯定是错误的_end_of_storage = _start + n;
}size_t size()
{return _finish - _start;
}
// 正确写法
reserve(n > capacity)
{_finish = tmp + size();// size()为0_start = tmp;_end_of_storage = _start + n;
}
- vector< T >:: const_iterator it = v.begin(),vector< T >未实例化会分不清是类型还是静态成员变量 ？
vector< int > :: const_iterator it = v.begin()
实例化后的vector< int > 可以取到类型
：：域作用限定符后面会跟类型或静态成员变量
template<class T>void vector_print(const vector<T>& v){// 规定没有实例化的类模版里取东西，编译器是无法区分const_iterator是// 静态成员变量还是类型,加了typename 就表明是类型// typename vector<T>::const_iterator it = v.begin();auto it = v.begin();
