云南建设注册考试中心网站,wordpress扫描附件到新浪图床,建网站,广州 门户vector的模拟实现 前言一.默认成员函数1.1常用的构造函数1.1.1默认构造函数1.1.2 n个 val值的构造函数1.1.3 迭代器区间构造1.1.4 initializer_list 的构造 1.2析构函数1.3拷贝构造函数1.4赋值运算符重载 二.元素的插入,删除,查找操作2.1 operator[]重载函数2.2 push_back函数:… vector的模拟实现 前言一.默认成员函数1.1常用的构造函数1.1.1默认构造函数1.1.2 n个 val值的构造函数1.1.3 迭代器区间构造1.1.4 initializer_list 的构造 1.2析构函数1.3拷贝构造函数1.4赋值运算符重载 二.元素的插入,删除,查找操作2.1 operator[]重载函数2.2 push_back函数:尾插一个元素2.3 pop_back函数:尾删一个元素2.4 insert函数:指定位置插入元素2.5 erase:删除指定位置的元素 三.front和back函数以及迭代器的实现3.1 front函数: 获取第一个元素3.2 back函数: 获取最后一个元素3.3 begin和end函数3.4 swap函数 前言
vector是一个类模板,它本质是一个顺序表,通过我们之前的学习,我们一般会这样来定义一个顺序表:
templateclass T
class vector
{T* _a;size_t _size;size_t _capacity;
};这种定义方式当然是可以的,但是我们通过看P.J.版本的stl的源码会发现,其中对vector的定义大概是这样的:
templateclass T
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start nullptr;iterator _finish nullptr;// 最后一个元素的下一个位置iterator _end_of_storage nullptr;//当前容量的下一个位置};他是通过三个指针来维护这个顺序表的,我们这篇博客也是采用这种定义方式来实现一个简易版vector的.
一.默认成员函数
1.1常用的构造函数
1.1.1默认构造函数
默认构造是实现一个空的vector不分配任何内存。 代码实现:
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _end_of_storage - _start;
}测试用例:
int main()
{vectorint v;cout size: v.size() endl;cout capacity: v.capacity() endl;return 0;
}输出结果: size:0 capacity:0 1.1.2 n个 val值的构造函数
初始化一个vector,其中用n个val值得对象来填充. 代码示例: void reserve(size_t n) {if (n capacity()){size_t oldsize size();T* tmp new T[n];if (_start){//不可以这样写,因为如果vector中存的类型是自定义类型,存在浅拷贝的问题//memcpy(tmp, _start, sizeof(T) * size());for (size_t i 0; i oldsize; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start oldsize;_end_of_storage _start n;}}void push_back(const T x){if (_finish _end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish x;_finish;}vector(size_t n, const T val T()){//考虑到扩容带来的效率低下问题,我们可以提前开好足够大的空间reserve(n);for (size_t i 0; i n; i){push_back(val);}}测试用例:
int main()
{vectorint v2(10 , 1);cout size: v2.size() endl;cout capacity: v2.capacity() endl;return 0;
}输出结果: size:10 capacity:10 1.1.3 迭代器区间构造
代码实现: template class InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}测试用例:
int main()
{string s1 aaaaaaa;vectorchar v3(s1.begin(), s1.end());return 0;
}输出结果:
1.1.4 initializer_list 的构造
用一个初始化列表来构造 代码实现: vector(initializer_listT il){reserve(il.size());for (const auto e : il){push_back(e);}}测试用例:
int main()
{vectorint v4{ 1,2,3,4,5,6,7,8,9 };return 0;
}输出结果:
1.2析构函数
析构函数:完成对象中的资源的回收清理,防止出现内存泄露.
代码实现: ~vector(){delete[] _start;_start _finish _end_of_storage nullptr;}1.3拷贝构造函数
代码实现: vector(const vectorT v){reserve(v.capacity());for (auto e : v){push_back(e);}}测试用例:
int main()
{ vectorint v4{ 1,2,3,4,5,6,7,8,9 };vectorint v5 v4;return 0;
}输出结果:
1.4赋值运算符重载
代码实现: void swap(vectorint v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//依旧是熟悉的现代写法vectorT operator(vectorT v){swap(v);return *this;}这里复用的是拷贝构造,拷贝构造我们已经测试过了没有什么问题,这里应该也是正常的,这里就不测试了.
二.元素的插入,删除,查找操作
2.1 operator[]重载函数
这里我们需要重载两个版本,一个是普通对象调用,另一个是const对象调用. 代码实现: T operator[](size_t i){assert(i size());return _start[i];}const T operator[](size_t i) const{assert(i size());return _start[i];}测试用例:
int main()
{vectorint v1{ 1,2,3,4,5,6,7,8,9 };for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;return 0;
}输出结果: 1 2 3 4 5 6 7 8 9 2.2 push_back函数:尾插一个元素
代码实现: void push_back(const T x){if (_finish _end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish x;_finish;}测试用例:
int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;return 0;
}输出结果: 1 2 3 4 5 2.3 pop_back函数:尾删一个元素
实现思路: 1.将_finish指针向前移动一位即删除最后一个元素。 2.当size已经为0,即vector中已经没有数据时,就不再删除. 代码实现: void pop_back(){assert(size() 0);--_finish;}测试用例:
int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;v1.pop_back();for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;return 0;
}输出结果: 1 2 3 4 5 1 2 3 4 2.4 insert函数:指定位置插入元素
这里需要注意迭代器失效的问题,如果不了解什么是迭代器失效的小伙伴,可以去:vector ,里面有迭代器失效场景的详细介绍. 代码实现:
iterator insert(iterator pos, const T x)
{assert(pos _start);assert(pos _finish);if (_finish _end_of_storage){size_t len pos - _start;size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos x;_finish;return pos;
}测试用例:
int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;v1.insert(v1.begin() 2, 1000);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;return 0;
}输出结果: 1 2 3 4 5 1 2 1000 3 4 5 2.5 erase:删除指定位置的元素
erase同样也要注意迭代器失效.我们要通过返回一个更新之后的迭代器来避免迭代器失效场景的出现.
代码实现: iterator erase(iterator pos){assert(pos _start);assert(pos _finish);iterator it pos 1;while (it _finish){*(it - 1) *it;it;}--_finish;return pos;}测试用例:
int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;v1.erase(v1.begin() 2);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;}return 0;
}输出结果: 1 2 3 4 5 1 2 4 5 三.front和back函数以及迭代器的实现
3.1 front函数: 获取第一个元素
代码实现: T front(){assert(size() 0);return _start[0];}const T front() const{assert(size() 0);return _start[0];}
3.2 back函数: 获取最后一个元素
代码实现: T front(){assert(size() 0);return _start[0];}const T front() const{assert(size() 0);return _start[0];}
3.3 begin和end函数
代码实现: iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}3.4 swap函数
代码实现: void swap(vectorint v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}希望对大家有所帮助,感谢观看!
