vector
MySTL开发日志（一）
Date：2022.4.15
开发内容：vector基本组成、基本函数
实现了：vector的构造函数、push_back、pop_back、insert、
find、erase、clear、empty和迭代器等功能,
测试了基本功能，无bug
https://moonweb.top 版权所有
/*******************************************************
//
// MySTL开发日志
// Date：2022.4.15
// 开发内容：vector基本组成、基本函数
// 实现了：vector的构造函数、push_back、pop_back、insert、
// find、erase、clear、empty和迭代器等功能,
// 测试了基本功能，无bug
//
//
// https://moonweb.top 版权所有
//
********************************************************/
#pragma once
template <typename T>
class vector
{
private:
typedef T* iterator;
T* pointer_to_arr;
size_t _capacity;
size_t curSize;
iterator _begin;
iterator _finish;
iterator _end_of_storage;
void _resize()
{
size_t oldCapacity = _capacity;
T* oldArr = pointer_to_arr;
curSize = _capacity;
if (oldCapacity == 0) //如果当前无元素
{
_capacity = 1; //扩容为1
}
else
{ //否则扩容为原来的2倍
_capacity = 2 * oldCapacity;
}
T* newarr = new T[_capacity];
for (int i = 0; i < _capacity; i++) newarr[i] = 0; //把新数组初始化
for (int i = 0; i < oldCapacity; i++) newarr[i] = oldArr[i]; //把原数组的数据拷贝到新数组中
pointer_to_arr = newarr; //数组指针指向新数组
_begin = pointer_to_arr; //更新迭代器
_finish = pointer_to_arr + curSize;
_end_of_storage = pointer_to_arr + _capacity;
}
void _copy(iterator ite) //把ite之后的元素向前移动一位，删除ite的元素
{
iterator iite = ite + 1;
while (iite != end() + 1) *ite++ = *iite++;
}
void move_behind(iterator ite) //把ite及以后的元素向后移动
{
iterator tmp = end();
while (tmp != ite)
{
*tmp = *(tmp - 1 );
tmp--;
}
}
void move_behind(iterator ite, size_t n) //把ite及以后的元素向后移动
{
iterator tmp = end();
while (n--)
{
*tmp = *(tmp - 1);
tmp--;
}
}
public:
vector()
{ //初始化数组和迭代器
pointer_to_arr = nullptr;
_begin = pointer_to_arr;
_finish = pointer_to_arr;
_end_of_storage = pointer_to_arr;
curSize = 0;
_capacity = 0;
}
vector(size_t cap)
{
T* arr = new T[cap]; //初始化数组和迭代器
for (int i = 0; i < cap; i++) arr[i] = 0;
pointer_to_arr = arr;
_begin = pointer_to_arr;
_finish = pointer_to_arr+ cap;
_end_of_storage = pointer_to_arr + cap;
curSize = cap;
_capacity = cap;
}
vector(size_t cap, const T& value)
{ //初始化数组和迭代器
T* arr = new T[cap];
pointer_to_arr = arr;
for (int i = 0; i < cap; i++) arr[i] = value;
_begin = pointer_to_arr;
_finish = pointer_to_arr + cap;
_end_of_storage = pointer_to_arr + cap;
curSize = cap;
_capacity = cap;
}
void push_back(T val)
{
if (_finish == _end_of_storage)
{
_resize();
}
curSize++;
*_finish = val;
_finish++;
}
void pop_back()
{
if (_capacity > 0)
{
curSize--;
_finish--;
}
}
void insert(iterator ite, T val) //在ite之前插入元素val
{
iterator tmp = ite;
size_t move_behind_nums = 0; //记录有多少个元素需要向后移动
size_t need_to_insert_index = 0; //记录需要插入元素的下标
for (auto i = ite; i != end(); i++) move_behind_nums++;
for (auto i = begin(); i != ite; i++) need_to_insert_index++;
if (ite != end()) //如果不是在最后插入元素
{
if (_finish == _end_of_storage) //如果空间不足需要扩容
{
_resize(); //扩容后迭代器失效，无法用迭代器判断位置，需要通过传入需要移动元素的数量来确定位置。
move_behind(ite, move_behind_nums);
}
else move_behind(ite); //不需要扩容则通过迭代器判断位置
*(begin()+ need_to_insert_index) = val; //插入元素
curSize++; //移动迭代器
_finish++; //移动迭代器
}
else
{
push_back(val);
}
}
void insert(iterator ite, size_t n, T val)
{
//TODO
}
//查找元素第一次出现的位置，返回迭代器
iterator find(T&& val)
{
iterator ite = begin();
while(ite != end())
{
if (*ite == val) return ite;
ite++;
}
return end();
}
iterator erase(iterator ite) //删除指定位置的元素
{
if (ite + 1 != end()) //如果当前不是最后一个元素
{
_copy(ite); //把ite后面的元素向前移动一位
}
_finish--;
curSize--;
return ite;
}
iterator erase(iterator beg, iterator end)
{
//TODO
}
void clear() //清除所有元素
{
curSize = 0;
_finish = _begin;
}
T front() const
{
return *begin();
}
T back()
{
return *(end()-1);
}
T operator[](const size_t idx)
{
return *(begin() + idx);
}
size_t size() const
{
return curSize;
}
size_t capacity() const
{
return _capacity;
}
bool empty() const
{
return begin() == end();
}
iterator begin() const
{
return _begin;
}
iterator end() const
{
return _finish;
}
};
MySTL开发日志（二）
Date：2022.4.16
开发内容：vector基本组成、基本函数
实现了：vector的resize,reverse,reserve,at,data，erase等成员函数及其重载版本
修改了：size(),capacity()成员函数的实现方式，删除了两个成员变量。更加符合STL源码。
https://moonweb.top 版权所有
/*******************************************************
//
// MySTL开发日志
// Date：2022.4.16
// 开发内容：vector基本组成、基本函数
// 实现了：vector的resize,reverse,reserve,at,data，erase等成员函数及其重载版本
// 修改了：size(),capacity()成员函数的实现方式，删除了两个成员变量。更加符合STL源码。
//
//
// https://moonweb.top 版权所有
//
********************************************************/
inline iterator erase(iterator _beg, iterator _end) //删除[_beg,_end) 范围内的所有元素
{
size_t num = _end - _beg; //统计删除的元素个数
iterator tmp = _beg;
if (_end != end())
{
iterator ite = _end; //将后续元素移动到前面
while (ite != end())
{
*tmp++ = *ite++;
}
_finish = tmp; //更改迭代器
return _beg; //返回删除元素的下一个元素的迭代器
}
else
{
_finish = _beg;
return _end;
}
}
inline void reverse(iterator _beg, iterator _end) //翻转[_beg,end)内的元素
{
if (_beg >= _end) return;
auto i = _beg, j = _end - 1;
while (i < j)
{
auto tmp = *i;
*i = *j;
*j = tmp;
i++;
j--;
}
}
inline void resize(size_t& newsize) //扩容
{
size_t curSize = size();
if (newsize == curSize) return; //如果容量相等则返回
else if (newsize < curSize) //如果容量变小则调用erase删除后续元素
{
erase(begin() + newsize, end());
return;
}
else //如果容量增加则扩容
{
_resize(newsize);
return;
}
}
inline void resize(size_t newsize,T&& val) //扩容
{
size_t curSize = size();
if (newsize == curSize) return; //如果容量相等则返回
else if (newsize < curSize) //如果容量变小则调用erase删除后续元素
{
erase(begin() + newsize, end());
return;
}
else //如果容量增加则扩容
{
_resize(newsize,val);
return;
}
}
inline void reserve(size_t& newsize)
{
size_t curSize = size();
if (newsize <= curSize) return;
else
{
_reverse(newsize);
return;
}
}
inline T at(const size_t& idx) const
{
return *(begin() + idx);
}
inline T* data() const //返回数组第一个元素的指针
{
return begin();
}
inline size_t size() const
{
return _finish-_begin;
}
inline size_t capacity() const
{
return _end_of_storage-_begin;
}
MySTL开发日志（三）
Date：2022.4.17
开发内容：vector基本组成
实现了：vector的拷贝构造函数和赋值运算符，实现了vector的深拷贝。
修改了：修复了某些情况会导致内存泄漏的bug，将类成员函数的实现放在类外
https://moonweb.top 版权所有
/*******************************************************
//
// MySTL开发日志
// Date：2022.4.17
// 开发内容：vector基本组成、基本函数
// 实现了：vector的拷贝构造函数和赋值运算符，实现了vector的深拷贝。将类成员函数的实现放在类外
// 修改了：修复了某些情况会导致内存泄漏的bug。
//
//
// https://moonweb.top 版权所有
//
********************************************************/
template <typename T>
vector<T>& vector<T>::operator=(vector<T>& vec)
{
if (this != &vec)
{
T* p = new T[vec.size()];
this->pointer_to_arr = p;
for (int i = 0; i < vec.size(); i++) p[i] = vec[i];
_begin = this->pointer_to_arr;
_finish = _begin + vec.size();
_end_of_storage = _finish;
}
return *this;
}
template <typename T>
vector<T>::vector(vector& vec)
{
T* p = new T[vec.size()];
this->pointer_to_arr = p;
for (int i = 0; i < vec.size(); i++) p[i] = vec[i];
_begin = this->pointer_to_arr;
_finish = _begin + vec.size();
_end_of_storage = _finish;
}
list
MySTL开发日志（四）
Date：2022.4.18
开发内容：list基本组成，list迭代器类、list节点类。
实现了：list的节点类的实现、迭代器类的构造函数、重载操作符、list类的insert,push_back,begin,end等函数
https://moonweb.top 版权所有
/*******************************************************
//
//
// Date：2022.4.18
// 开发内容：list基本组成，list迭代器类、list节点类。
// 实现了：list的节点类的实现、迭代器类的构造函数、重载操作符、
// list类的insert,push_back,begin,end等函数
// https://moonweb.top 版权所有
//
//
//
********************************************************/
#pragma once
#include<iostream>
using namespace std;
template <class T>
struct _list_Node
{
public:
_list_Node<T>* next;
_list_Node<T>* pre;
T val;
friend ostream& operator<<(ostream& out,_list_Node<T>& node) //重载输出节点值
{
out << (&node)->val;
return out;
}
};
template<class T>
class _list_iterator
{
public:
typedef T value_type;
typedef _list_Node<T>* node_type;
typedef _list_iterator<T> self;
node_type node; //指向节点的指针
_list_iterator(node_type x) :node(x) {}
_list_iterator(const _list_iterator& x) :node(x.node){}//重载<<输出地址
friend ostream& operator<<(ostream& os,self ite)
{
os << &ite;
return os;
}
bool operator==(self x) //重载迭代器==
{
return node == x.node;
}
bool operator!=(self x) //重载迭代器！=
{
return node != x.node;
}
value_type operator *() //重载迭代器*ite
{
return node->val;
}
self& operator++() //重载++ite
{
node =node->next;
return *this;
}
self operator++(int) //重载ite++
{
auto tmp = *this;
++* this;
return tmp;
}
self& operator--() //重载--ite
{
node = node->pre;
return *this;
}
self operator--(int) //重载ite--
{
auto tmp = *this;
--* this;
return tmp;
}
};
template <class T>
class list
{
public:
typedef _list_Node<T> node_type; //指向尾结点后的空白节点的指针
typedef _list_Node<T>* pointer;
typedef T value_type;
typedef _list_iterator<T> iterator;
node_type* node;
private:
pointer create_node(value_type val);
pointer create_node();
void empty_initialize();
public:
list();
iterator begin();
iterator end();
bool empty() const;
void push_back(value_type val);
iterator insert(iterator pos, value_type v);
};
template<class T> //创建一个空节点
typename list<T>::pointer list<T>::create_node(value_type v)
{
node_type* p = new node_type;
p->val = v;
p->next = p;
p->pre = p;
return p;
}
template<class T>
typename list<T>::pointer list<T>::create_node() //创建一个空节点
{
node_type* p = new node_type;
p->val = 0;
p->next = p;
p->pre = p;
return p;
}
template<class T>
inline void list<T>::empty_initialize()
{
node_type* p = new node_type;
p->next = p;
p->pre = p;
node = p;
}
template<class T> //无参构造函数
list<T>::list()
{
empty_initialize();
}
template<class T>
typename list<T>::iterator list<T>::begin()
{
return iterator(node->next); //返回构造的迭代器类对象
}
template<class T>
typename list<T>::iterator list<T>::end()//返回构造的迭代器类对象
{
return iterator(node);
}
template<class T>
bool list<T>::empty() const
{
return node->next == node;
}
template<class T>
inline typename list<T>::iterator list<T>::insert(iterator pos, value_type v) //在pos前面插入v节点
{
pointer tmp = create_node(v);
tmp->next = pos.node;
tmp->pre = pos.node->pre;
(pos.node->pre)->next = tmp;
pos.node->pre = tmp;
return iterator(tmp);
}
template<class T>
void list<T>::push_back(value_type val)
{
insert(end(), val);
}
MySTL开发日志（五）
Date：2022.4.19
开发内容：list成员函数
实现了：list的push_front,push_back,pop_front,
pop_back,front,back,size,clear,remove等函数
https://moonweb.top 版权所有
/*******************************************************
//
//
// Date：2022.4.19
// 开发内容：list成员函数
// 实现了：list的push_front,push_back,pop_front,
// pop_back,front,back,size,clear,remove等函数
//
//
// https://moonweb.top 版权所有
//
//
//
********************************************************/
template<class T>
inline typename list<T>::reference list<T>::front()
{
return *begin();
}
template<class T>
inline typename list<T>::reference list<T>::back()
{
iterator tmp = end();
--tmp;
return *tmp;
}
template<class T>
inline void list<T>::push_back(value_type val)
{
insert(end(), val);
}
template<class T>
inline void list<T>::push_front(value_type val)
{
insert(begin(), val);
}
template<class T>
inline void list<T>::pop_back()
{
iterator tmp = end();
erase(--tmp);
}
template<class T>
inline void list<T>::pop_front()
{
erase(begin());
}
template<class T>
inline typename list<T>::value_type list<T>::size()
{
iterator _begin = begin();
value_type num = 0;
while (_begin != end())
{
num++;
_begin++;
}
return num;
}
template<class T>
inline void list<T>::clear()
{
pointer cur = node->next; //找到begin迭代器
while (cur!=node) //遍历所有节点
{
pointer tmp = cur;
cur = cur->next;
destroy_node(tmp); //释放所有节点
}
node->next = node; //恢复初始状态
node->pre = node;
}
template<class T>
inline void list<T>::remove(value_type val) //移除所有值为val的节点
{
iterator cur = begin();
while (cur != end())
{
iterator tmp = cur;
cur++;
if (*tmp == val) erase(tmp);
}
}
MySTL开发日志（六）
Date：2022.4.20
开发内容：list成员函数，vector的列表初始化
实现了：list的 merge,sort,splice,swap,resize，reverse等函数，
list的列表初始化和vector的列表初始化
https://moonweb.top 版权所有
/*******************************************************
//
//
// Date：2022.4.20
// 开发内容：list成员函数，vector的列表初始化
// 实现了：list的 merge,sort,splice,swap,resize，reverse等函数，
// list的列表初始化和vector的列表初始化
//
//
// https://moonweb.top 版权所有
//
//
//
********************************************************/
template<class T>
inline void list<T>::merge(list<T>& x) //将两个有序链表合并
{
iterator first1 = begin();
iterator last1 = end();
iterator first2 = x.begin();
iterator last2 = x.end();
while(first1 != last1 && first2 != last2)
if (*first2 < *first1)
{
iterator next = first2;
transfer(first1, first2, ++next);
first2 = next;
}
else
{ ++first1;
}
if (first2 != last2) transfer(last1, first2, last2);
}
template<class T>
inline void list<T>::splice(iterator pos, list<T>& x, iterator first, iterator last) //将[first,last)的元素移动到pos之前
{
if (first != last)
{
transfer(pos, first, last);
}
}
template<class T>
inline void list<T>::splice(iterator pos, list<T>& x, iterator i) //将i之前的元素移动到pos之前
{
iterator j = i;
++j;
if (pos == i || pos == j)
{
return;
}
transfer(pos, i, j);
}
template<class T>
inline void list<T>::splice(iterator pos, list<T>& x) //将x移动到pos之前
{
if (!x.empty)
{
transfer(pos, x.begin(), x.end());
}
}
template<class T>
inline void list<T>::swap(list<T>& x)
{
list<T> t;
t.splice(t.end(),x, x.begin(), x.end());
x.clear();
x.splice(x.end(),*this, this->begin(), this->end());
this->clear();
this->splice(this->end(),t, t.begin(), t.end());
}
template<class T>
inline void list<T>::resize(value_type n)
{
resize(n, 0);
}
template<class T>
inline void list<T>::resize(value_type n, value_type val)
{
size_t size = this->size();
if (n == size) return;
else if (n < size)
{
while (n != size)
{
pop_back();
size--;
}
}
else if (n > size)
{
while (n != size)
{
push_back(val);
size++;
}
}
}
deque
MySTL开发日志（七）
Date：2022.4.22
开发内容：deque容器迭代器
实现了：deque的迭代器类的自增自减，随机访问，大小比较等重载运算符，缓冲区等相关函数及成员。
https://moonweb.top 版权所有
/*******************************************************
//
//
// Date：2022.4.22
// 开发内容：deque容器迭代器
// 实现了：deque的迭代器类的自增自减，随机访问，大小比较等重载运算
// 符，缓冲区等相关函数及成员
//
//
// https://moonweb.top 版权所有
//
//
//
********************************************************/
template <class T>
class _deque_iterator
{
public:
typedef _deque_iterator<T> self;
typedef T** map_pointer;
typedef T value_type;
typedef T& reference;
typedef T* pointer;
pointer cur; //指向缓冲区内的当前元素
pointer first; //指向缓冲区内的首个元素
pointer last; //指向缓冲区内的最后元素
map_pointer node; //指向中控器的节点的指针
size_t _deque_buf_size(size_t n, size_t sz)
{
if (n != 0) return n;
else if (sizeof(value_type) < 512) return 512 / sz;
else return 1;
}
size_t buf_size() //获得缓冲区大小
{
return _deque_buf_size(32, sizeof(value_type));
}
void set_node(map_pointer new_node) //指向下一个缓冲区
{
node = new_node;
first = *new_node;
last = first + buf_size();
}
reference operator*() const //获取迭代器指向的元素
{
return *cur;
}
pointer operator->() const
{
return &(*operator());
}
self& operator++()
{
++cur;
if (cur == last)
{
set_node(node + 1);
cur = first;
}
return* this;
}
self operator++(int)
{
self tmp = *this;
++* this;
return tmp;
}
self& operator--()
{
--cur;
if (cur == first)
{
set_node(node - 1);
cur = last;
}
return*this;
}
self operator--(int)
{
self tmp = *this;
--* this;
return tmp;
}
self& operator+=(size_t n)
{
size_t offset = n + (cur - first);
if (offset >= 0 && offset <= buf_size()) //目标在同一缓冲区内
{
cur += n;
}
else
{
size_t t = offset>0?offset/buf_size():-(-offset-1)/buf_size()-1;
set_node(node + t);
cur = first + (offset - t * buf_size());
}
return *this;
}
self operator+(size_t n)
{
self tmp = *this;
return tmp += n;
}
self& operator-=(size_t n)
{ //调用operator+= 实现operator-=
return *this += -n;
}
self operator-(size_t n)
{
self tmp = *this;
return tmp -= n;
}
reference operator[](size_t n) //随机访问
{
return *(*this + n);
}
bool operator==(const self& x)
{
return this->cur == x.cur;
}
bool operator!=(const self& x)
{
return this->cur != x.cur;
}
bool operator<(const self& x)
{
return node == x.node ? (cur < x.cur) : (node < x.node);
}
bool operator>(const self x)
{
return node == x.node ? (cur > x.cur) : (node > x.node);
}
};
MySTL开发日志（八）
Date：2022.4.25
开发内容：deque容器
实现了：deque的begin,end,front,back,下标访问操作符，empty和中控器的空间配置等功能。
https://moonweb.top 版权所有
/*******************************************************
//
//
// Date：2022.4.25
// 开发内容：deque容器
// 实现了：deque的begin,end,front,back,下标访问操作符，
// empty和中控器的空间配置等功能。
//
//
// https://moonweb.top 版权所有
//
//
//
********************************************************/
template<class T>
inline typename deque<T>::iterator deque<T>::begin()
{
return start;
}
template<class T>
inline typename deque<T>::iterator deque<T>::end()
{
return finish;
}
template<class T>
inline typename deque<T>::reference deque<T>::operator[](size_t n)
{
return start[n];
}
template<class T>
inline typename deque<T>::reference deque<T>::front()
{
return *start;
}
template<class T>
inline typename deque<T>::reference deque<T>::back()
{
auto tmp = finish;
tmp--;
return *tmp;
}
template<class T>
inline typename deque<T>::value_type deque<T>::size()
{
return (finish - start);
}
template<class T>
inline bool deque<T>::empty()
{
return start == finish;
}
template<class T>
inline typename deque<T>::map_pointer deque<T>::_allocate_map(int map_size)
{
pointer *t = new pointer[map_size];
std::memcpy(t, map, sizeof(map));
map = t;
return map;
}
template<class T>
inline void deque<T>::create_map_and_nodes(int n)
{
size_t nodeNums = n / buf_size() + 1; //需要节点数=元素个数/每个缓冲区内的元素数量 + 1，非空节点数
map_size = nodeNums + 2; //前后各保留两个空节点，在扩容时使用。
map = _allocate_map(map_size); //创建map中控器节点
map_pointer newstart = map + (map_size - nodeNums) / 2;
map_pointer newfinish = newstart + nodeNums - 1;
map_pointer cur;
for (cur = newstart; cur <= newfinish; cur++)
{
*cur = allocate_buf(); //TODO //为每个中控器节点配置缓冲区
}
start.set_node(newstart);
finish.set_node(newfinish);
start.cur = start.first;
finish.cur = finish.first + n % buf_size();
}
MySTL开发日志（九）
Date：2022.4.26
开发内容：deque容器
实现了：deque的默认构造函数，push_back,push_back_aux,迭代器重载运算符等
修复了：当扩容时忽略边界问题导致的元素丢失的问题
https://moonweb.top 版权所有
/*******************************************************
//
//
// Date：2022.4.26
// 开发内容：deque容器
// 实现了：deque的默认构造函数，push_back,push_back_aux，迭代器重载运算符等
// 修复了：当扩容时忽略边界问题导致的元素丢失的问题
//
// https://moonweb.top 版权所有
//
//
//
********************************************************/
template<class T>
inline void deque<T>::push_back(const value_type& val)
{
if (finish.cur != finish.last - 1) //如果缓冲区还有空间，则直接原地构造
{
*finish.cur = val;
finish.cur++;
}
else
{
push_back_aux(val); //否则调用辅助函数
}
}
template<class T>
inline void deque<T>::push_back_aux(const value_type& n)
{
value_type t = n;
*(finish.node + 1) = allocate_buf(); //配置新的缓冲区
*finish.cur = t; //push_back元素
finish.set_node(finish.node + 1); //更改指针指向
finish.cur = finish.first; //更改指针指向
}
template<class T>
inline deque<T>::deque() //默认构造函数
{
map = nullptr;
fill_initialize(0,0);
map_size = 0;
}
int operator-(self& x)
{
return buf_size() * (node - x.node - 1) + (cur - first) + x.last - x.cur;
}
MySTL开发日志（十）
Date：2022.5.1
开发内容：deque容器
实现了：deque的析构函数，clear，pop_back,pop_front、pop_back_aux,push_back_aux等函数
https://moonweb.top 版权所有
/*******************************************************
//
//
// Date：2022.5.1
// 开发内容：deque容器
// 实现了：deque的析构函数，clear，pop_back,pop_front、
// pop_back_aux,push_back_aux等函数
//
//
// https://moonweb.top 版权所有
//
//
//
********************************************************/
template<class T>
inline void deque<T>::pop_back()
{
if (finish.cur != finish.first) //如果有一个以上剩余元素
{
finish.cur--; //直接移动指针
}
else
{ //否则调用辅助函数
pop_back_aux();
}
}
template<class T>
inline void deque<T>::pop_front()
{
if (start.cur != start.last-1) //如果有一个以上剩余元素
{
start.cur++; //直接移动指针
}
else
{
pop_front_aux(); //否则调用辅助函数
}
}
template<class T>
inline void deque<T>::clear() //调用析构函数再调用构造函数
{
if (map != nullptr)
{
for (int i = 0; i < map_size; i++)
{
auto idx = map + i;
delete[] idx;
idx = nullptr;
}
}
map = nullptr;
fill_initialize(0, 0);
map_size = 0;
}
template<class T>
inline void deque<T>::pop_back_aux()
{
finish.set_node(finish.node - 1); //调整指针指向
destroy(finish.cur);
finish.cur = finish.last - 1;
}
template<class T>
inline void deque<T>::pop_front_aux()
{
start.set_node(start.node + 1); //调整指针指向
destroy(start.cur);
start.cur = start.first;
}
MySTL开发日志（十一）
Date：2022.5.3
开发内容：deque容器
实现了：deque的insert,insert_aux等函数
修复了：在调用erase等函数需要移动元素时，在某些时候会移动失败的情况
https://moonweb.top 版权所有
/*******************************************************
//
//
// Date：2022.5.3
// 开发内容：deque容器
// 实现了：deque的insert,insert_aux等函数
// 修复了：在调用erase等函数需要移动元素时，在某些时候会移动
// 败的情况
//
//
//
// https://moonweb.top 版权所有
//
//
//
********************************************************/
template<class T>
inline typename deque<T>::iterator deque<T>::insert(iterator ite, value_type val)
{
if (ite.cur == start.cur)
{
push_front(val);
return start;
}
else if (ite.cur == finish.cur)
{
push_back(val);
iterator tmp = finish;
tmp--;
return tmp;
}
return insert_aux(ite, val);
}
template<class T>
inline typename deque<T>::iterator deque<T>::insert_aux(iterator ite, value_type& val)
{
int idx = ite - start; //插入点之前的元素个数
value_type xx = val;
if (idx < size() / 2)
{
push_front(front());
iterator front1 = start;
front1++;
iterator front2 = front1;
front2++;
ite = start + idx;
iterator ite1 = ite;
ite1++;
copy(front2, ite1, front1);
}
else
{
push_back(back());
iterator back1 = finish;
back1--;
iterator back2 = back1;
back2--;
ite = start + idx;
copy_backward(ite, back2, back1);
}
*ite = xx;
return ite;
}
MySTL开发日志（十二）
Date：2022.5.5
开发内容：deque容器
实现了：deque的构造函数，带参构造函数
修复了：带参构造函数的非正常初始化的问题
https://moonweb.top 版权所有
/*******************************************************
//
//
// 2022.5.5
// 开发内容：deque容器
// 实现了：deque的构造函数，带参构造函数
// 修复了：带参构造函数的非正常初始化的问题
//
//
//
// https://moonweb.top 版权所有
//
//
//
********************************************************/
template<class T>
inline deque<T>::deque(int n, const value_type& val) //有参构造函数
{
map = nullptr;
fill_initialize(0, val);
map_size = 0;
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
template<class T>
inline deque<T>::deque(int n)
{
map = nullptr;
fill_initialize(0, 0);
map_size = 0;
for (int i = 0; i < n; i++)
{
push_back(0);
}
}
template<class T>
inline deque<T>::deque() //默认构造函数
{
map = nullptr;
fill_initialize(0,0);
map_size = 0;
}
stack
MySTL开发日志（十三）
Date：2022.5.7
开发内容：deque、stack
实现了：stack的push，pop，size,top,empty等成员函数
修复了：deque的push_back方法的底层实现，修复了在无元素时调用push_back会导致崩溃的情况，修改了部分容器的size函数的返回值类型
https://moonweb.top 版权所有
/*******************************************************
//
// MySTL开发日志
// Date：2022.5.7
// 开发内容：deque、stack
// 实现了：stack的push，pop，size,top,empty等成员函数
// 修复了：deque的push_back方法的底层实现，
// 修复了在无元素时调用push_back会导致崩溃的情况
// 修改了部分容器的size函数的返回值类型
//
//
// https://moonweb.top 版权所有
//
********************************************************/
#pragma once
#include"deque.h"
template<class T,class sequence=deque<T>>
class stack
{
public:
typedef T value_type;
typedef T* pointer;
typedef value_type& reference;
sequence c; //底层容器
public:
stack() :c() {} //默认构造函数
bool empty();
void push(value_type x);
void pop();
size_t size();
reference top();
};
template<class T, class sequence>
inline bool stack<T, sequence>::empty()
{
return c.empty();
}
template<class T, class sequence>
inline void stack<T, sequence>::push(value_type x)
{
c.push_back(x);
}
template<class T, class sequence>
inline void stack<T, sequence>::pop()
{
c.pop_back();
}
template<class T, class sequence>
inline size_t stack<T, sequence>::size()
{
return c.size();
}
template<class T, class sequence>
inline typename stack<T, sequence>::reference stack<T, sequence>::top()
{
return c.back();
}
queue
MySTL开发日志（十四）
Date：2022.5.8
开发内容：queue
实现了：stack的push，pop，size,empty,back,front等成员函数
https://moonweb.top 版权所有
/*******************************************************
//
//
// Date：2022.5.8
// 开发内容：queue
// 实现了：stack的push，pop，size,empty,back,front等成员函数
//
//
//
//
// https://moonweb.top 版权所有
//
********************************************************/
#pragma once
#include"deque.h"
using namespace std;
template <class T,class sequence=deque<T>>
class queue
{
public:
typedef T value_type;
typedef T* pointer;
typedef value_type& reference;
protected:
sequence c; //底层容器
public:
queue() :c() {}
queue(initializer_list<T> x) :c()
{
for (auto ite = x.begin(); ite != x.end(); ite++)
{
push(*ite);
}
}
bool empty();
void push(value_type x);
void pop();
size_t size();
reference back();
reference front();
};
template<class T, class sequence>
inline bool queue<T, sequence>::empty()
{
return c.empty();
}
template<class T, class sequence>
inline void queue<T, sequence>::push(value_type x)
{
c.push_back(x);
}
template<class T, class sequence>
inline void queue<T, sequence>::pop()
{
c.pop_front();
}
template<class T, class sequence>
inline size_t queue<T, sequence>::size()
{
return c.size();
}
template<class T, class sequence>
inline typename queue<T, sequence>::reference queue<T, sequence>::back()
{
return c.back();
}
template<class T, class sequence>
inline typename queue<T, sequence>::reference queue<T, sequence>::front()
{
return c.front();
}
Q.E.D.