模拟实现vector容器
·
模拟实现vector容器，一方面能锻炼自己的代码写作能力，并且能了解到更多的“坑”，另一方面能让自己更熟悉vector容器
需要注意的地方都在代码中写了注释，例如在vector的拷贝构造中，为什么不能用memcpy，强烈建议看一遍我写的注释
迭代器部分的实现：
由于反向迭代器的部分容易让c++初始学习者反应不过来，因此我单独把迭代器部分的实现拿出来
正向迭代器的部分：
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;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _EndOfStorage = nullptr;
};
在实现反向迭代器前，一定要弄清楚rbegin()和rend()所指向的位置在哪，以及如何从end()变化成rbegin()以及如何从begin()变化成rend()
反向迭代器的部分我将其单独拧出来成一个reverse_iterator类
#pragma once
namespace wzn
{
template<class Iterator, class Ref, class Ptr>
struct Reverse_Iterator
{
typedef Reverse_Iterator<Iterator, Ref, Ptr> self;
Iterator _it;
Reverse_Iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
self& operator++()
{
--_it;
return *this;
}
self& operator--()
{
++_it;
return *this;
}
self operator++(int)
{
self tmp(*this);
--_it;
return tmp;
}
self operator--(int)
{
self tmp(*this);
++_it;
return tmp;
}
bool operator!=(const self& s) const
{
return _it != s._it;
}
};
}
其余部分：
#include <iostream>
#include <assert.h>
#include "Reverse_Iterator.h"
namespace wzn
{
template<class T>
class vector
{
public:
// 迭代器
typedef T* iterator;
typedef const T* const_iterator;
typedef Reverse_Iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_Iterator<const iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const iterator begin() const
{
return _start;
}
const iterator end() const
{
return _finish;
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin()+1);
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin()+1);
}
vector()
//: _start(nullptr)
//, _finish(nullptr)
//, _EndOfStorage(nullptr)
{}
/*
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _EndOfStorage(nullptr)
{
_start = new T[v.capacity()];
//不能用memcpy，假如是拷贝构造一个vector<string>，vector是深拷贝，但是里面的string是浅拷贝
//memcpy(_start,v._start,sizeof(T) * v.size());
for (size_t i = 0; i < v.size(); ++i)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_EndOfStorage = _start + v.capacity();
}
*/
vector(const vector<T>& v)
//: _start(nullptr)
//, _finish(nullptr)
//, _EndOfStorage(nullptr)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
vector(size_t n, const T& val = T())
//: _start(nullptr)
//, _finish(nullptr)
//, _EndOfStorage(nullptr)
{
resize(n,val);
}
vector(int n, const T& val = T())
{
resize(n,val);
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _EndOfStorage = nullptr;
}
}
void swap(vector<T>& v)
{
std::swap(_start,v._start);
std::swap(_finish, v._finish);
std::swap(_EndOfStorage, v._EndOfStorage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
// const T& x = T()而不是=0,T()是调用默认构造的意思，是为了适配自定义类型，内置类型也存在默认构造，例如int();
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
size_t oldlen = size();
if (_start)
{
// 不能用memcpy,假如vector<string>，memcpy对vector是深拷贝，但是对里面的string是浅拷贝
for (size_t i = 0; i < oldlen; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldlen; // 这里不用_start + size() 是因为size()是通过return _finish - _start得到的，前面_start已经做了修改了
_EndOfStorage = _start + n;
}
}
// 这里pos不能用引用,例如insertt(v.begin(),x),这里的begin()返回到寄存器的变量是临时变量，具有常性
// 再对这个临时变量进行引用，涉及到权限放大，引用不了。形参iterator加上const修饰后可以引用，但是pos的值却不能修改了
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _EndOfStorage)
{
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;
/*
这里或许想着用memmove替换while循环来提高效率，并且调用完后pos和pos+1位置指向同一个string数据
然后*pos = x，就不会有问题了，其实是大错特错
*pos = x 触发 string::operator=，而这个运算符的默认行为就是先释放当前对象持有的旧内存，再分配新内存存储新值
那应该如何提升？采用std::copy_backward，编译器会特殊优化
std::copy_backward的实现逻辑和上面的while循环一致，但是对于内置类型，编译器会优化，替换成memmove
*/
++_finish;
return pos;
}
void push_back(const T& x)
{
//// 扩容
//if (_finish == _EndOfStorage)
//{
// size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(newcapacity);
//}
//*_finish = x;
//++_finish;
insert(end(), x);
}
/*存在迭代器失效问题，部分平台不能跑
void erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator end = _finish - 1;
while (pos != end)
{
*pos = *(pos + 1);
++pos;
}
--_finish;
}
*/
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
//*(it - 1) = std::move(*it); // 移动语义优化（减少拷贝），需要迭代器支持
++it;
}
// 显示析构最后一个元素，该用法需要c++17
if constexpr (!std::is_trivially_destructible_v<T>)
{
(_finish - 1)->~T();
}
--_finish;
return pos;
}
void pop_back()
{
erase(--end());
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
size_t size() const
{
cout << "size()" << endl;
return _finish - _start;
}
size_t capacity() const
{
return _EndOfStorage - _start;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _EndOfStorage = nullptr;
};
}
更多推荐
2
0- 0
已为社区贡献4条内容
所有评论(0)