當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

STL-Deque的实现

發布時間：2024/4/17 编程问答 32 豆豆

生活随笔收集整理的這篇文章主要介紹了 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的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

STL
deque

上一篇： x265-确定slice type-3
下一篇： x265-bitstream.h