STL-Deque的实现
1.STL-Deque的原理
元素的插入
buyback:
pointer _P = allocator.allocate(_DEQUESIZE, (void*)0);
?? ??? ?if (empty())
?? ??? ?{
?? ??? ??? ?_Mapsize = _DEQUEMAPSIZE;
?? ??? ??? ?size_type _N = _Mapsize / 2;
?? ??? ??? ?_Getmap();
?? ??? ??? ?_Setptr(_Map + _N, _P);
?? ??? ??? ?_First = iterator(_P + _DEQUESIZE / 2, _Map + _N);
?? ??? ??? ?_Last = _First;
?? ??? ?}
當deque為空時
當為empty時,雙端隊列的實現就是分配一個空間,重中間分開,前部分是_First,后半部分是_Last; _First從中間位置,后退插入;_Last從中間往后插入;這樣就實現了front和back插入。
map空間不足的增長
1.超過前半部分(_first)的空間
創建map空間,并把原來的map空間拷貝新分配的空間;新分配的空間,僅僅給前半部分的使用。
_Mapptr _M = _Growmap(2 * _I);
?? ??? ??? ?_Setptr(--M, P);
?? ??? ??? ?_First = iterator(_P + _DEQUESIZE, _M);
?? ??? ??? ?_Last = iterator(_Last._Next, _M + _I);
2.超過后半部分(_Last)的空間
創建map空間,并把原來的map空間拷貝新分配的空間。新分配的空間,不再從中間劃分,僅僅給后半部使用;
int _I = _Last._Map - _First._Map + 1;
?? ??? ??? ?_Mapptr _M = _Growmap(2 * _I);//增加映射器
?? ??? ??? ?_Setptr(_M + 1,_P);
//維護原來的空間
?? ??? ??? ?_First = iterator(_First._Next, _M);
?? ??? ??? ?_Last = iterator(_P, _M + _I);
元素的刪除操作
1.前向刪除pop_front
刪除前向元素,包括兩個方面,當整個_First的_Map指向的空間沒有了,一個是_First的指針的域的更新(_First,_Last,_Next,_Map),前向是插入式倒退進行,那刪除就是前進方式,_Next肯定執行新空間的頭部。
allocater.destroy(_First._Next++);
_First = iterator(*_First._Map, _First._Map);
另外一個方面就是空間的回收工作,一個空間管理者map空間,一個數據空間;首先會destory掉這個元素值得空間,然后會判斷當前的一段空間是否到達末尾,如果到達就會先刪除
掉這個_First指向的map空間;
_Freeptr(_First._Map++);//刪除指向的_Map空間
如果這個時候,整個deque為空了,就要刪除整個_Map.
_Freemap();
2.后向刪除pop_back
刪除后向元素,當整個_Last指向的_Map的空間沒有了,也包括兩個方面,一個是_Last的指針域的更新的,由于后向是前進插入的,那刪除就是后退方式,_Next肯定指向新空間的尾部。
_Last = iterator(*_Last._Map + _DEQUESIZE, _Last._Map);
另一方面是是空間回收工作,一個_map空間,一個是數據空間;
_Freeptr(_Last.Map--);
allocator.destroy(--_Last._Next);
如果剛好整個deque的空間為空了:
_Freemap();
數據的訪問
通過迭代器
iterator operator ++() {
?? ??? ??? ?if (++_Next == _Last) {
?? ??? ??? ??? ?_First = *++_Map;
?? ??? ??? ??? ?_Last = _First + _DEQUESIZE;
?? ??? ??? ??? ?_Next = _First;
?? ??? ??? ?}
?? ??? ??? ?return *this;
?? ??? ?}
數據的插入
- 情況1.當插入的iterator為begin時,就是push_front
if (_X == begin()) {
?? ??? ??? ?push_front(_V);
?? ??? ?}
- 情況2.當插入的iterator為end()時,就是push_back
?else if (_X == end()) {
?? ??? ??? ?push_back(_V);
?? ??? ?}
- 情況3:由于插入需要移動元素,如果距離頭部的距離小于1/2的總大小,就移動頭部的元素,否則移動后面的元素;
?else {
?? ??? ??? ?difference_type _off = _X - begin();
?? ??? ??? ?Myiterator _S;
?? ??? ??? ?if (_off < size() / 2) {
?? ??? ??? ??? ?push_front(front());
?? ??? ??? ??? ?_S = begin() + _off;
? ? ? ? ? ? ? ? 這個是把元素拷貝,begin()+2的原因是,頭部的一個元素往前拷貝了一下,因此頭部的兩個元素都是第一個元素值。從第二個開始拷貝,開始的位置從begin()+1,覆蓋掉一個相同的元素。
?? ??? ??? ??? ?std::copy<deque::Myiterator,deque::Myiterator>((begin() + 2),_S,(begin() + 1));
?? ??? ??? ?}
?? ??? ??? ?else {
?? ??? ??? ??? ?push_back(back());
?? ??? ??? ??? ?_S = begin() + _off;
這個是拷貝元素從從后往前拷貝,原理相同
?? ??? ??? ??? ?std::copy_backward(_S,(end() - 2),(end() - 1));
?? ??? ??? ?}
?? ??? ??? ?*_S = _V;
?? ??? ?}
?? ??? ?
?? ?}
源碼:
deque.h
#pragma once
#include"xmemory.h"
#define _DEQUEMAPSIZE 2
#define _DEQUESIZE ((4096<sizeof(_Ty))?1:4096/sizeof(_Ty))
template<class _Ty, class _A=Allocator<_Ty> >
class deque {
public:
?? ?using size_type = typename _A::size_type;
?? ?using difference_type = typename _A::difference_type;
?? ?using reference = typename _A::reference;
?? ?using pointer = typename _A::pointer_type;
?? ?typedef _Ty** _Mapptr;
?? ?class Myiterator{
?? ?public:
?? ??? ?using size_type = typename _A::size_type;
?? ??? ?using difference_type = typename _A::difference_type;
?? ??? ?using reference = typename _A::reference;
?? ??? ?using pointer = typename _A::pointer_type;
?? ??? ?typedef const _Ty& const_reference;
?? ??? ?typedef _Ty value_type;
?? ??? ?using iterator_category = typename std::bidirectional_iterator_tag;
?? ??? ?friend class deque;
?? ?public:
?? ??? ?explicit Myiterator() :_First(0), _Last(0), _Next(0), _Map(0) {
?? ??? ?}
?? ??? ?//,_Last(*_M+_DEQUESIZE),_Next(_P),_map(_M)
?? ??? ?Myiterator(pointer _P, _Mapptr _M):_First(*_M), _Last((*_M + _DEQUESIZE)), _Next(_P), _Map(_M) {
?? ??? ?}
?? ??? ?bool operator ==(const Myiterator& _X) {
?? ??? ??? ?return _Next == _X._Next;
?? ??? ?}
?? ??? ?bool operator !=(const Myiterator& _X) {
?? ??? ??? ?return !(*this == _X);
?? ??? ?}
?? ??? ?reference operator*() {
?? ??? ??? ?return *_Next;
?? ??? ?}
?? ??? ?pointer operator->() {
?? ??? ??? ?return **this;
?? ??? ?}
?? ??? ?Myiterator operator ++() {
?? ??? ??? ?if (++_Next == _Last) {
?? ??? ??? ??? ?_First = *++_Map;
?? ??? ??? ??? ?_Last = _First + _DEQUESIZE;
?? ??? ??? ??? ?_Next = _First;
?? ??? ??? ?}
?? ??? ??? ?return *this;
?? ??? ?}
?? ??? ?Myiterator operator++(int) {
?? ??? ??? ?Myiterator temp = *this;
?? ??? ??? ?++*this;
?? ??? ??? ?return temp;
?? ??? ?}
?? ??? ?Myiterator operator--() {
?? ??? ??? ?if (_Next == _First) {
?? ??? ??? ??? ?_First = *--_Map;
?? ??? ??? ??? ?_Last = _First + _DEQUEMAPSIZE;
?? ??? ??? ??? ?_Next = _Last;
?? ??? ??? ?}
?? ??? ??? ?--_Next;
?? ??? ??? ?return *this;
?? ??? ?}
?? ??? ?Myiterator operator --(int) {
?? ??? ??? ?Myiterator temp = *this;
?? ??? ??? ?--*this;
?? ??? ??? ?return temp;
?? ??? ?}
?? ??? ?void _Add(difference_type _N) {
?? ??? ??? ?difference_type _off = _N + (_Next - _First);
?? ??? ??? ?difference_type _Moff = (_off >= 0) ? _off / _DEQUESIZE : (-1)*((_DEQUESIZE - 1 - _off) / _DEQUESIZE);
?? ??? ??? ?if (_Moff == 0) {
?? ??? ??? ??? ?_Next += _N;
?? ??? ??? ?}
?? ??? ??? ?else {
?? ??? ??? ??? ?_Map += _Moff;
?? ??? ??? ??? ?_First = *_Map;
?? ??? ??? ??? ?_Last = _First + _DEQUESIZE;
?? ??? ??? ??? ?_Next = _First + (_off - _Moff + _DEQUESIZE);
?? ??? ??? ?}
?? ??? ?}
?? ??? ?Myiterator operator+=(difference_type _N) {
?? ??? ??? ?_Add(_N);
?? ??? ??? ?return *this;
?? ??? ?}
?? ??? ?Myiterator operator-=(difference_type _N) {
?? ??? ??? ?_Add(-_N);
?? ??? ??? ?return *this;
?? ??? ?}
?? ??? ?Myiterator operator+(difference_type _N) {
?? ??? ??? ?Myiterator temp = *this;
?? ??? ??? ?return temp+=_N;
?? ??? ?}
?? ??? ?Myiterator operator-(difference_type _N) {
?? ??? ??? ?Myiterator temp = *this;
?? ??? ??? ?return temp-=_N;
?? ??? ?}
?? ??? ?difference_type operator-(const Myiterator& _X) {
?? ??? ??? ?return (_Map == _X._Map ? (_Next - _X._Next) : _DEQUESIZE * (_Map - _X._Map - 1) + (_Next - _First) + (_X._Last - _X._Next));
?? ??? ?}
?? ??? ?
?? ?protected:
?? ??? ?pointer _First, _Last, _Next;
?? ??? ?_Mapptr _Map;
?? ?};
public:
?? ?explicit deque(const _A& A1 = _A()) :allocator(A1), _First(), _Last(), _Map(0), _Size(0) {
?? ?}
?? ?
?? ?void insert(Myiterator& _X, const _Ty& _V) {
?? ??? ?if (_X == begin()) {
?? ??? ??? ?push_front(_V);
?? ??? ?}
?? ??? ?else if (_X == end()) {
?? ??? ??? ?push_back(_V);
?? ??? ?}
?? ??? ?else {
?? ??? ??? ?difference_type _off = _X - begin();
?? ??? ??? ?Myiterator _S;
?? ??? ??? ?if (_off < size() / 2) {
?? ??? ??? ??? ?push_front(front());
?? ??? ??? ??? ?_S = begin() + _off;
?? ??? ??? ??? ?
?? ??? ??? ??? ?std::copy<deque::Myiterator,deque::Myiterator>((begin() + 2),_S,(begin() + 1));
?? ??? ??? ?}
?? ??? ??? ?else {
?? ??? ??? ??? ?push_back(back());
?? ??? ??? ??? ?_S = begin() + _off;
?? ??? ??? ??? ?std::copy_backward(_S,(end() - 2),(end() - 1));
?? ??? ??? ?}
?? ??? ??? ?*_S = _V;
?? ??? ?}
?? ??? ?
?? ?}
?? ?void push_back(const _Ty& _X) {
?? ??? ?if (empty() || _Last._Next == _Last._Last) {
?? ??? ??? ?_Buyback();
?? ??? ??? ?allocator.construct(_Last._Next++, _X);
?? ??? ?}
?? ??? ?else if (_Last._Next + 1 == _Last._Last) {
?? ??? ??? ?allocator.construct(_Last._Next++, _X);
?? ??? ??? ?_Buyback();
?? ??? ?}
?? ??? ?else {
?? ??? ??? ?allocator.construct(_Last._Next++, _X);
?? ??? ?}
?? ??? ?++_Size;
?? ?}
?? ?void push_front(const _Ty& _X) {
?? ??? ?if (empty() || _First._Next == _First._First) {
?? ??? ??? ?_Buyfront();
?? ??? ?}
?? ??? ?allocator.construct(--_First._Next, _X);
?? ?}
?? ?size_type size() {
?? ??? ?return _Size;
?? ?}
?? ?bool empty() {
?? ??? ?return size() == 0;
?? ?}
protected:
?? ?void _Getmap() {
?? ??? ?_Map = (_Mapptr)allocator._Charallocate(_Mapsize * sizeof(pointer));
?? ?}
?? ?_Mapptr _Growmap(size_type _Newsize) {
?? ??? ?_Mapptr _M = (_Mapptr)allocator._Charallocate(_Newsize * sizeof(pointer));
?? ??? ?std::copy(_First._Map, _Last._Map + 1, _M + _Newsize / 4);
?? ??? ?allocator.deallocate(_Map, _Mapsize);
?? ??? ?_Map = _M;
?? ??? ?_Mapsize = _Newsize;
?? ??? ?return (_M + _Newsize / 4);
?? ?}
?? ?void _Setptr(_Mapptr _M, pointer _P) {
?? ??? ?*_M = _P;
?? ?}
?? ?void _Buyback() {
?? ??? ?pointer _P = allocator.allocate(_DEQUESIZE);
?? ??? ?if (empty())
?? ??? ?{
?? ??? ??? ?_Mapsize = _DEQUEMAPSIZE;
?? ??? ??? ?size_type _N = _Mapsize / 2;
?? ??? ??? ?_Getmap();
?? ??? ??? ?_Setptr(_Map + _N, _P);
?? ??? ??? ?_First =Myiterator((pointer)(_P + _DEQUESIZE / 2), _Map + _N);
?? ??? ??? ?_Last = _First;
?? ??? ?}
?? ??? ?else if (_Last._Map < _Map + (_Mapsize - 1)) {
?? ??? ??? ?_Setptr(++_Last._Map, _P);
?? ??? ??? ?_Last = Myiterator(_P, _Last._Map);
?? ??? ?}
?? ??? ?else {
?? ??? ??? ??? ?int _I = _Last._Map - _First._Map + 1;
?? ??? ??? ??? ?_Mapptr _M = _Growmap(2 * _I);
?? ??? ??? ??? ?_Setptr((_M + _I),_P);
?? ??? ??? ??? ?_First = Myiterator(_First._Next, _M);
?? ??? ??? ??? ?_Last = Myiterator(_P, _M + _I);
?? ??? ?}
?? ?}
?? ?void _Buyfront() {
?? ??? ?pointer _P = allocator.allocate(_DEQUESIZE);
?? ??? ?if (empty()) {
?? ??? ??? ?_Mapsize = _DEQUEMAPSIZE;
?? ??? ??? ?size_type _N = _Mapsize / 2;
?? ??? ??? ?_Getmap();
?? ??? ??? ?_Setptr(_Map + _N, _P);
?? ??? ??? ?_First = Myiterator(_P + (_DEQUESIZE / 2 + 1), _Map + _N);
?? ??? ??? ?_Last = _First;
?? ??? ?}
?? ??? ?else if (_Map < _First._Map) {
?? ??? ??? ?_Setptr(--_First._Map, _P);
?? ??? ??? ?_First = Myiterator(_P + _DEQUESIZE, _First._Map);
?? ??? ?}
?? ??? ?else if(_First._Map==_Last._Map){
?? ??? ??? ?_Setptr(_Last._Map++, *_Last._Map);
?? ??? ??? ?_Setptr(_First._Map + 1, *_First._Map);
?? ??? ??? ?_Setptr(_First._Map, _P);
?? ??? ??? ?_First = Myiterator(_P + _DEQUESIZE, _First._Map);
?? ??? ?}
?? ??? ?else {
?? ??? ??? ?int _I = _Last._Map - _First._Map + 1;
?? ??? ??? ?_Mapptr _M = _Growmap(2 * _I);
?? ??? ??? ?_Setptr(--_M, _P);
?? ??? ??? ?_First = Myiterator(_P + _DEQUESIZE, _M);
?? ??? ??? ?_Last = Myiterator(_Last._Next, _M + _I);
?? ??? ?}
?? ?}
?? ?void _Freeptr(_Mapptr _M) {
?? ??? ?allocator.deallocate(*_M, _DEQUESIZE);
?? ?}
?? ?void _Freemap() {
?? ??? ?allocator.deallocate(_Map, _Mapsize);
?? ?}
?? ?void _Freefront() {
?? ??? ?_Freeptr(_First._Map++);
?? ??? ?if (empty()) {
?? ??? ??? ?_First = Myiterator();
?? ??? ??? ?_Last = _First;
?? ??? ??? ?_Freemap();
?? ??? ?}
?? ??? ?else
?? ??? ??? ?_First = Myiterator(*_First._Map, _First._Map);
?? ?}
?? ?void pop_front() {
?? ??? ?allocator.destroy(_First._Next++);
?? ??? ?--size;
?? ??? ?if (empty() || _First._Next == _First._Last) {
?? ??? ??? ?_Freefront();
?? ??? ?}
?? ?}
?? ?void _Freeback() {
?? ??? ?_Freeptr(_Last.Map--);
?? ??? ?if (empty()) {
?? ??? ??? ?if (_First._Map == _Last._Map) {
?? ??? ??? ??? ?_Freeptr(_First._Map);
?? ??? ??? ?}
?? ??? ??? ?_First = Myiterator();
?? ??? ??? ?_Last = _First;
?? ??? ??? ?_Freemap();
?? ??? ?}
?? ??? ?else {
?? ??? ??? ?_Last = Myiterator(*_Last._Map + _DEQUESIZE, _Last._Map);
?? ??? ?}
?? ?}
?? ?void pop_back() {
?? ??? ?if (_Last._Next == _Last._First) {
?? ??? ??? ?_Freeback();
?? ??? ?}
?? ??? ?if (!empty()) {
?? ??? ??? ?allocator.destroy(--_Last._Next);
?? ??? ?}
?? ??? ?--size;
?? ??? ?if (empty()) {
?? ??? ??? ?_Freeback();
?? ??? ?}
?? ?}
public:
?? ?Myiterator begin() {
?? ??? ?return _First;
?? ?}
?? ?Myiterator end() {
?? ??? ?return _Last;
?? ?}
?? ?reference front() {
?? ??? ?return *_First;
?? ?}
?? ?reference back() {
?? ??? ?return *_Last;
?? ?}
private:
?? ?_A allocator;
?? ?Myiterator _First, _Last;
?? ?_Mapptr _Map;
?? ?size_type _Mapsize, _Size;
};
xmemory.h:
#pragma once
template <class _Ty>
_Ty* _allocate(size_t _N, _Ty*) {
?? ?if (_N < 0)
?? ??? ?_N = 0;
?? ?return (_Ty*)operator new(_N * sizeof(_Ty));
}
template <class _T1, class _T2>
void _Construct(_T1* p, const _T2& _v) {
?? ?new ((void*)p) _T1(_v);
}
template<class _Ty>
void _Destroy(_Ty* _P) {
?? ?_P->~_Ty();
}
template <class _Ty>
class Allocator {
public:
?? ?typedef size_t size_type;
?? ?typedef int difference_type;
?? ?typedef _Ty* pointer_type;
?? ?typedef _Ty& reference;
?? ?typedef const _Ty& const_reference;
?? ?pointer_type allocate(size_type n) {
?? ??? ?return _allocate(n, pointer_type(0));
?? ?}
?? ?char* _Charallocate(size_type n) {
?? ??? ?return _allocate(n, (char*)0);
?? ?}
?? ?void deallocate(void* p, size_type n) {
?? ??? ?operator delete(p);
?? ?}
?? ?void construct(pointer_type _P, const_reference _V) {
?? ??? ?_Construct(_P, _V);
?? ?}
?? ?void destroy(pointer_type _P) {
?? ??? ?_Destroy(_P);
?? ?}
?? ?size_t max_size() const
?? ?{
?? ??? ?size_t _N = (size_t)(-1) / sizeof(_Ty);
?? ??? ?return _N;
?? ?}
};
?
?
總結
以上是生活随笔為你收集整理的STL-Deque的实现的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: x265-确定slice type-3
- 下一篇: x265-bitstream.h