文章目录
- vector类的模拟实现
- 1.默认成员变量和函数
- 2.迭代器函数
- 3.空间容量和长度
- 4.[ ]下标调用
- 5.插入操作（尾插）
- 6.调整容量大小
- 7.判空操作
- 8.删除操作
- 9.插入操作
- 10.size空间大小
- 11.消除操作
vector类的模拟实现
1.默认成员变量和函数
首先自定义构造vector类的默认成员变量和函数
声明和定义均在头文件（自己创建的vector.h中进行，主函数仅调用函数
#pragma once
#include <iostream>
using namespace std;
#include <vector>
namespace pzh //自定义的命名空间名称
{
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; //空间的最后位置
}
}
2.迭代器函数
typedef T* iterator; //普通迭代器
typedef const T* const_iterator; //const迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
迭代器输出容器：
void test_vector()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
输出结果：
3.空间容量和长度
定义常规函数：
size_t capacity() const //空间容量
{
return _end_of_storage - _start;
}
size_t size() const //空间内容长度
{
return _finish - _start;
}
4.[ ]下标调用
const T& operator[](size_t pos) const
{
assert(pos < size()); //需要包含头文件#include <assert.h>
return _start[pos];
}
5.插入操作（尾插）
void push_back(const T& x) //插入
{
if (_finish == _end_of_storage) //检查容量
{
reserve(capacity() == 0 ? 4 : capacity() * 2); //检查空间，不足时调整容量大小, 扩容2倍
}
*_finish = x;
++_finish;
}
6.调整容量大小
void reserve(size_t n) //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 = tmp + sz;
_end_of_storage = _start + n;
}
}
功能测试：
main.cpp函数：
#define _CRT_SECURE_NO_WARNINGS
#include "vector.h"
int main()
{
test_vector(); //调用函数，测试功能
return 0;
}
测试函数：
void test_vector()
{
vector<int> 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;
}
测试结果：
7.判空操作
可以想象成以恶搞指针，指针通常有空指针，也就是所谓的判空操作：
bool empty()
{
return _start == _finish; //空返回1，非空返回0
}
测试函数：
void test_vector()
{
vector<int> v1;
cout << v1.empty() << endl;
v1.push_back(1);
cout << v1.empty() << endl;
}
测试结果：
8.删除操作
void pop_back() //删除
{
assert(!empty());
--_finish;
}
测试函数：
void test_vector()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.pop_back(); //无参，删除最后一个元素
for (auto e : v1)
{
cout << e << " ";
}
}
输出结果i：
9.插入操作
void insert(iterator pos, const T& val) //在pos位置插入val值
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage) //检查容量
{
size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;
reserve(newCapacity);
pos = _start + size(); // 如果发生了增容，需要重置pos
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
}
测试函数：
void test_vector()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.insert(v1.begin(), 0); //在最开始位置插入0
v1.insert(v1.begin() + 3, 100);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
输出结果：
10.size空间大小
void resize(size_t n,T val = T())
{
if(n < size())
{
//删除数据
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
测试函数：
void test_vector()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.resize(3);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
v1.resize(6);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
输出结果：
11.消除操作
iterator erase(iterator pos)
{
//挪动数据进行删除
iterator begin = pos + 1;
while (begin != _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
测试函数：
void test_vector()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.erase(v1.begin()+2); //删除第三个位置的元素
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
输出结果：
综上：
vector.h文件全部内容：
#pragma once
#include <iostream>
using namespace std;
#include <assert.h>
namespace pzh //自定义的命名空间名称
{
template<class T> //类模板
class vector
{
public:
typedef T* iterator; //普通迭代器
typedef const T* const_iterator; //const迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
vector() //构造函数
: _start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
~vector() //析构函数
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
size_t size() const
{
return _finish - _start;
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
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 = tmp + sz;
_end_of_storage = _start + n;
}
}
bool empty()
{
return _start == _finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
void insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;
reserve(newCapacity);
pos = _start + size();
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
}
void resize(size_t n, T val = T())
{
if (n < size())
{
//删除数据
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
iterator erase(iterator pos)
{
iterator begin = pos + 1;
while (begin != _finish)
{
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
void test_vector()
{
//.......
//测试函数
}
}
main.cpp函数内容：
#define _CRT_SECURE_NO_WARNINGS
#include "vector.h"
int main()
{
pzh::test_vector();
return 0;
}
