अंतिम अद्यतन：2026-10-12

STL deque सोर्स कोड विश्लेषण

0.प्रस्तावना

deque एक दोनों ओर खुला, खंडित-संतत रैखिक स्पेस है (सरल रूप में समझें तो: डबल-एंडेड क्यू), जिसमें सिरे तथा पूंछ दोनों ओर से एलिमेंट्स का इंसर्शन और डिलीशन किया जा सकता है।

deque तथा vector का सबसे बड़ा अंतर यह है:

• deque निरंतर समय (constant time) में सिरे पर एलिमेंट इंसर्ट या डिलीट करने की अनुमति देता है;

• deque एक खंडित-संतत रैखिक स्पेस है, जिसमें कभी भी एक नया स्पेस-खंड जोड़ा जा सकता है;

deque, vector की तरह नहीं है — vector में जब मेमोरी कम पड़ती है तो मेमोरी पुनः आवंटित करनी/डेटा कॉपी करना/मूल स्पेस जारी करना पड़ता है; हालाँकि deque का इटरेटर डिज़ाइन vector से जटिल है, क्योंकि इटरेटर के लिए साधारण पॉइंटर का उपयोग नहीं किया जा सकता, इसलिए जहाँ तक संभव हो vector का ही उपयोग करें।

1.deque सेंट्रल कंट्रोलर

उपयोगकर्ता को देखने में deque निरंतर स्पेस प्रयोग करता प्रतीत होता है, पर वास्तव में वह खंडित-संतत रैखिक स्पेस है। खंडित स्पेस के प्रबंधन के लिए deque कंटेनर में map को पेश किया गया है, जिसे सेंट्रल कंट्रोलर कहा जाता है। map एक निरंतर स्पेस है जिसका प्रत्येक एलिमेंट बफर की ओर इशारा करने वाला पॉइंटर है, और बफर ही deque का डेटा संग्रह करने वाला वास्तविक अंग है।

उपरोक्त चित्र में, buffer को बफर कहा जाता है, तथा map size दर्शाने वाला निरंतर स्पेस का खंड ही सेंट्रल कंट्रोलर है।

सेंट्रल कंट्रोलर में map size, buffer की ओर इशारा करने वाला पॉइंटर, तथा deque का आरंभिक इटरेटर और अंतिम इटरेटर शामिल हैं।

_Tp     **_M_map;
size_t      _M_map_size;
iterator    _M_start;
iterator    _M_finish;

चूँकि buffer भी एक पॉइंटर है, इसलिए _Tp पॉइंटर का पॉइंटर है।

deque, _Deque_base से इनहेरिट करता है, और _Deque_base के भीतर एक _M_impl है।

नीचे के चित्र तथा उपरोक्त विवरण के आधार पर जाना जा सकता है कि सेंट्रल कंट्रोलर _Deque_impl द्वारा कार्यान्वित किया जाता है।

तथा deque आधार क्लास _Deque_base का उपयोग करके मेमोरी प्रबंधन तथा सेंट्रल कंट्रोलर प्रबंधन पूरा करता है।

2.अत्याधुनिक इटरेटर

deque के लिए, इसका इटरेटर डिज़ाइन बहुत ही शानदार है!

नीचे के चित्र में दिखाया गया है:

पहले अपेक्षाकृत महत्वपूर्ण मेंबर्स पर नज़र डालते हैं:

typedef _Tp             **_Map_pointer;
_Tp     *_M_cur;
_Tp     *_M_first;
_Tp     *_M_last;
_Map_pointer    _M_node;

आख़िर ये क्या हैं? नाम से ही सरलता से पता चल जाता है। deque के लिए — जो एक खंडित-संतत स्पेस है — इटरेटर ऑपरेशन करते समय उपरोक्त _M_cur विशिष्ट एलिमेंट की ओर इशारा करता है, _M_first उस buffer खंड के पहले एलिमेंट की ओर, _M_last अंतिम एलिमेंट की ओर (जो वैध एलिमेंट नहीं है), तथा _M_node सेंट्रल कंट्रोलर की ओर इशारा करता है। इसीलिए यह पॉइंटर का पॉइंटर है।

उदाहरण के लिए, मान लीजिए इटरेटर अभी ++ ऑपरेशन करता है और वर्तमान buffer की जगह खत्म हो जाती है — तब एक ऐसे पॉइंटर की आवश्यकता होती है जो सेंट्रल कंट्रोलर पर लौट सके, अगला buffer खंड ले सके, _M_first तथा _M_last की पॉइंटर स्थिति रीसेट कर सके, ताकि _M_cur नए buffer खंड में निर्दिष्ट स्थिति की ओर इशारा करे।

अब हम शुरुआत के चित्र पर लौटते हैं:

सबसे ऊपर वाला iterator उपरोक्त पॉइंटर्स के ब्लॉक के साथ दिया गया चित्र ही है।

तो buffer की गणना कैसे कार्यान्वित होती है?

सोर्स कोड में गणना पास किए गए टाइप के आधार पर होती है: यदि पास किया गया टाइप 512 बाइट्स से छोटा है, तो buffersize 512/sizeof(_Tp) होता है, और 512 से अधिक होने पर 1।

static size_t _S_buffer_size()
_GLIBCXX_NOEXCEPT
{
    return(__deque_buf_size( sizeof(_Tp) ) );
}

__deque_buf_size का कार्यान्वयन

#ifndef _GLIBCXX_DEQUE_BUF_SIZE
#define _GLIBCXX_DEQUE_BUF_SIZE 512
#endif
inline size_t
__deque_buf_size( size_t
            __size )
{
    return(__size < _GLIBCXX_DEQUE_BUF_SIZE
            ? size_t( _GLIBCXX_DEQUE_BUF_SIZE / __size ) : size_t( 1 ) );
}

पिछले कुछ अनुभागों के सोर्स कोड में ट्रेट्स (traits) तकनीक का उल्लेख किया गया था; प्रत्येक इटरेटर के लिए निम्नलिखित पाँच प्रकार के typedef एम्बेड करने होते हैं:

typedef std::random_access_iterator_tag iterator_category;
typedef _Tp             value_type;
typedef _Ptr                pointer;
typedef _Ref                reference;
typedef ptrdiff_t           difference_type;

इससे यह भी जाना जा सकता है कि deque का इटरेटर रैंडम-एक्सेस इटरेटर: random_access_iterator_tag उपयोग करता है।

vector का उपयोग किया गया इटरेटर भी यही है। 侯捷 शिक्षक के अनुसार, निरंतर buffer ही vector है, जो इटरेटर के tag टाइप से पूर्णतः मेल खाता है।

अब इस शक्तिशाली इटरेटर के कुछ ऑपरेटर ओवरलोड्स देखते हैं:

विस्तृत व्याख्या कोड के भीतर दी गई है।

वैल्यू-प्राप्ति (dereference) ऑपरेटर

reference
operator*() const
_GLIBCXX_NOEXCEPT
{
    return(*_M_cur);
}


pointer
operator->() const
_GLIBCXX_NOEXCEPT
{
    return(_M_cur);
}

बेशक, उपरोक्त -> को * ऑपरेटर को सीधे कॉल करके भी कार्यान्वित किया जा सकता है, उदाहरण के लिए:

pointer
operator->() const
_GLIBCXX_NOEXCEPT
{
    return &(operator*());
}

++ तथा -- ऑपरेटर

// 前置++操作符
_Self &
operator++()
_GLIBCXX_NOEXCEPT
{
    // 先++，判断是否到了buffer的末尾，如果到了末尾，就要跳到下一个buffer。
    ++_M_cur;
    if ( _M_cur == _M_last ) // _M_last指向的不是有效元素，保留节点  
    {
        _M_set_node( _M_node + 1 );
        _M_cur = _M_first;
    }
    return(*this);
}

// 后置++操作符
_Self
operator++( int )
_GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;
    ++*this;
    return(__tmp);
}

// 前置--操作符
_Self &
operator--()
_GLIBCXX_NOEXCEPT
{
    // 先判断是否到了起始位置，如果到了，由于需要进行--操作，那么就应该进入前一个buffer
    if ( _M_cur == _M_first )
    {
        _M_set_node( _M_node - 1 );
        _M_cur = _M_last;
    }
    --_M_cur;
    return(*this);
} //先在容器头部插入与第一个元素相同的元素

// 后置--操作符
_Self
operator--( int )
_GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;    /* 定义一个副本 */
    --*this;                /* 迭代器自减操作 */
    return(__tmp);
}

n दूरी तक छलांग लगाने वाला ऑपरेटर

/*
* 实现随机取,迭代器可以直接跳跃n个距离
* 将迭代器前移n个距离,当n负值时就为下面的operator-=操作
*/
_Self &
operator+=( difference_type __n )

_GLIBCXX_NOEXCEPT
{
    const difference_type __offset = __n + (_M_cur - _M_first);
    /*
        * 若前移n个距离后，目标依然在同一个缓冲区
        * 则直接前移n个距离
        */
    if ( __offset >= 0 && __offset < difference_type( _S_buffer_size() ) )
        _M_cur += __n;
    else {
        /*
            * 若前移n个距离后,目标超出了缓冲区范围
            * __offset>0   __offset / difference_type(_S_buffer_size())计算向后移动多少个缓冲区
            * __offset<=0  -difference_type((-__offset - 1) / _S_buffer_size()) - 1计算向前移动多少个缓冲区
            */
        const difference_type __node_offset =
            __offset > 0 ? __offset / difference_type( _S_buffer_size() )
            : -difference_type( (-__offset - 1)
                        / _S_buffer_size() ) - 1;
        /* 调整到正确的缓冲区,此时_M_first已经修改了 */
        _M_set_node( _M_node + __node_offset );
        /* 修改为正确的指针位置 */
        _M_cur = _M_first + (__offset - __node_offset
                        * difference_type( _S_buffer_size() ) );
    }
    return(*this);
}

नीचे ये सभी ऑपरेटर उपरोक्त += ऑपरेटर को कॉल करके कार्यान्वित किए गए हैं:

/*
    * 操作符+重载
    * 返回操作之后的副本
    */
_Self
operator+( difference_type __n ) const
_GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;
    /* 调用operator+=操作 */
    return(__tmp += __n);
}


/* 利用operator+=操作实现 */
_Self &
operator-=( difference_type __n )
_GLIBCXX_NOEXCEPT
{
    return(*this += -__n);
}


/*
    * 操作符-重载
    * 返回操作之后的副本
    */
_Self
operator-( difference_type __n ) const
_GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;    /*  保存副本 */
    return(__tmp -= __n);   /* 调用operator-=操作符 */
}


/* 返回指定位置的元素，即实现随机存取 */
reference
operator[]( difference_type __n ) const
_GLIBCXX_NOEXCEPT
{
    return(*(*this + __n) );    /* 该函数调用operator+,operator* */
}

buffer छलांग

पहले वाले ++ तथा -- जैसे ऑपरेटर _M_set_node फंक्शन को कॉल करते हैं; इस फंक्शन का कार्य buffer्स के बीच छलांग लगाना तथा _M_node, _M_first, _M_last की दिशा बदलना है।

/**
    *  Prepares to traverse new_node.  Sets everything except
    *  _M_cur, which should therefore be set by the caller
    *  immediately afterwards, based on _M_first and _M_last.
    */
void
_M_set_node( _Map_pointer __new_node )
_GLIBCXX_NOEXCEPT
{
    _M_node     = __new_node;                                           /* 指向新的节点 */
    _M_first    = *__new_node;                                          /* 指向新节点的头部 */
    _M_last     = _M_first + difference_type( _S_buffer_size() );       /* 指向新节点的尾部 */
}

इस प्रकार हमने deque के इटरेटर कार्यान्वयन का विस्तार समझाना पूरा कर लिया।

3.deque

begin() फंक्शन

_M_start रिटर्न करता है।

iterator
begin()
_GLIBCXX_NOEXCEPT
{
    return(this->_M_impl._M_start);
}

end() फंक्शन

_M_finish रिटर्न करता है।

iterator
end()
_GLIBCXX_NOEXCEPT
{
    return(this->_M_impl._M_finish);
}

size() फंक्शन

size_type
size() const

_GLIBCXX_NOEXCEPT
{
    return(this->_M_impl._M_finish - this->_M_impl._M_start);
}

resize() फंक्शन

पास किए गए आकार के अनुसार, यदि वह कुल size से अधिक है, तो __new_size-size() स्पेस पुनः आवंटित करके विस्तार किया जाता है, अन्यथा size()-__new_size डेटा हटा दिया जाता है। उदाहरण के लिए, अभी 20 स्पेस हैं और resize(12) करने पर पीछे के 8 स्पेस का डेटा हटा दिया जाता है तथा स्पेस जारी कर दिया जाता है।

void
resize( size_type __new_size )
{
    const size_type __len = size();
    if ( __new_size > __len )
        _M_default_append( __new_size - __len );
    else if ( __new_size < __len )
        _M_erase_at_end( this->_M_impl._M_start
                    + difference_type( __new_size ) );
}

empty() फंक्शन

केवल दो पॉइंटर्स की स्थिति की तुलना करना पर्याप्त है।

bool
empty() const

_GLIBCXX_NOEXCEPT
{
    return(this->_M_impl._M_finish == this->_M_impl._M_start);
}

back फंक्शन

reference
back()
_GLIBCXX_NOEXCEPT       // 指向finish的前一个位置
{
    iterator __tmp = end();
    --__tmp;
    return(*__tmp);
}

push_front फंक्शन

void
push_front( const value_type &__x )
{
    //若当前缓冲区存在可用空间
    if ( this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first )
    {
        this->_M_impl.construct( this->_M_impl._M_start._M_cur - 1, __x );// 直接构造对象
        --this->_M_impl._M_start._M_cur;    // 调整指针所指位置
    } else
        _M_push_front_aux( __x );   // 需分配一段新的连续空间
}

push_back फंक्शन

void
push_back( const value_type &__x )
{
    //若当前缓冲区存在可用空间
    if ( this->_M_impl._M_finish._M_cur
            != this->_M_impl._M_finish._M_last - 1 )
    {
        this->_M_impl.construct( this->_M_impl._M_finish._M_cur, __x ); // 直接构造对象
        ++this->_M_impl._M_finish._M_cur;       //调整指针所指位置
    } else     // 若当前缓冲区不存在可用空间
    // 需分配一段新的连续空间
        _M_push_back_aux( __x );
}

उपरोक्त के संगत pop ऑपरेशन इनके ठीक विपरीत होते हैं।

insert() फंक्शन

insert फंक्शन काफी रोचक है — पास किए गए इटरेटर की स्थिति के अनुसार देखा जाता है कि वह आरंभ या अंत में है या नहीं: यदि आरंभ में है तो सीधे push_front फंक्शन कॉल होता है, अंत में है तो सीधे push_back फंक्शन, अन्यथा कंटेनर में एलिमेंट सीधे इंसर्ट कर दिया जाता है।

template <typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
insert(iterator __position, const value_type& __x)
{
        if (__position._M_cur == this->_M_impl._M_start._M_cur)   
    {
        push_front(__x);
        return this->_M_impl._M_start;
    }
        else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
    {
        push_back(__x);
        iterator __tmp = this->_M_impl._M_finish;
        --__tmp;
        return __tmp;
    }
        else  //否则在容器直接插入数据
        return _M_insert_aux(__position._M_const_cast(), __x);
}

और उपरोक्त कंटेनर में एलिमेंट सीधे इंसर्ट करने वाला फंक्शन इंसर्शन बिंदु की गणना करता है — यदि वह अपेक्षाकृत आगे है तो आगे इंसर्ट किया जाता है, पीछे की ओर हो तो पीछे:

template<typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
_M_insert_aux(iterator __pos, const value_type& __x)
{
    value_type __x_copy = __x; // XXX copy
    difference_type __index = __pos - this->_M_impl._M_start;  //计算插入点之前元素个数
    if (static_cast<size_type>(__index) < size() / 2)   //若插入点之前的元素较少
        {
        push_front(_GLIBCXX_MOVE(front())); //先在容器头部插入与第一个元素相同的元素
        iterator __front1 = this->_M_impl._M_start;
        ++__front1;
        iterator __front2 = __front1;
        ++__front2;
        __pos = this->_M_impl._M_start + __index;
        iterator __pos1 = __pos;
        ++__pos1;
        _GLIBCXX_MOVE3(__front2, __pos1, __front1); // 元素搬移
        }
    else
    {
        push_back(_GLIBCXX_MOVE(back()));
        iterator __back1 = this->_M_impl._M_finish;
        --__back1;
        iterator __back2 = __back1;
        --__back2;
        __pos = this->_M_impl._M_start + __index;
        _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
    }
    *__pos = _GLIBCXX_MOVE(__x_copy);       // 在安插点上设定新值
    return __pos;
}

संबंधित विषय

• STL array सोर्स कोड विश्लेषण | C++那些事
• STL string गहन विश्लेषण | C++那些事
• STL string इंटरव्यू प्रश्न विस्तृत व्याख्या | C++那些事
• STL खाली बेस क्लास ऑप्टिमाइज़ेशन EBO | C++那些事
• STL स्वहस्त लिखी हैश तालिका कार्यान्वयन | C++那些事
• STL hashtable हैश तालिका | C++那些事
• STL इटरेटर सोर्स कोड विश्लेषण | C++那些事
• STL list सोर्स कोड विश्लेषण | C++那些事
• STL map तथा multimap | C++那些事
• STL queue तथा stack सोर्स कोड विश्लेषण | C++那些事

टिप्पणियाँ