文章目录
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();