STL容器之list源碼詳細(xì)解讀

更新時(shí)間：2024年01月03日 09:10:42 作者：DivineH

這篇文章主要介紹了STL容器之list源碼詳細(xì)解讀,相對(duì)于vector的連續(xù)線性空間,list就顯得更加復(fù)雜,它每插入或者刪除一個(gè)元素,就配置或釋放一個(gè)元素空間,需要的朋友可以參考下

簡(jiǎn)介

相對(duì)于vector的連續(xù)線性空間，list就顯得更加復(fù)雜，它每插入或者刪除一個(gè)元素，就配置或釋放一個(gè)元素空間。

因此，list對(duì)于空間的利用非常精準(zhǔn)，一點(diǎn)也不浪費(fèi)，而且，對(duì)于任何位置的插入或者刪除，list永遠(yuǎn)是常數(shù)時(shí)間。

構(gòu)造函數(shù)

explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
// 構(gòu)造擁有 n 個(gè)有值 value 的元素的容器
list(size_type __n, const _Tp& __value,
    const allocator_type& __a = allocator_type())
: _Base(__a)
{ insert(begin(), __n, __value); }
explicit list(size_type __n)
: _Base(allocator_type())
{ insert(begin(), __n, _Tp()); }
// 構(gòu)造擁有范圍 [first, last) 內(nèi)容的容器
list(const _Tp* __first, const _Tp* __last,
    const allocator_type& __a = allocator_type())
: _Base(__a)
{ this->insert(begin(), __first, __last); }
list(const_iterator __first, const_iterator __last,
    const allocator_type& __a = allocator_type())
: _Base(__a)
{ this->insert(begin(), __first, __last); }
// 拷貝構(gòu)造函數(shù)
list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())
{ insert(begin(), __x.begin(), __x.end()); }

對(duì)于list中的每一個(gè)節(jié)點(diǎn)，都被封裝成了_List_node對(duì)象：

// 雙向鏈表
struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};

// list 節(jié)點(diǎn)
template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data; // 節(jié)點(diǎn)存儲(chǔ)的值
};

即list是通過雙向循環(huán)鏈表來組織節(jié)點(diǎn)的。

主要函數(shù)

push_back

void push_back(const _Tp& __x) { insert(end(), __x); } // 插入一個(gè)節(jié)點(diǎn)，作為尾節(jié)點(diǎn)
// 在__position之前插入節(jié)點(diǎn)__x
iterator insert(iterator __position, const _Tp& __x) {
    _Node* __tmp = _M_create_node(__x);
    // 調(diào)整雙向指針，插入新元素
    __tmp->_M_next = __position._M_node;  // list為雙向鏈表
    __tmp->_M_prev = __position._M_node->_M_prev;
    __position._M_node->_M_prev->_M_next = __tmp;
    __position._M_node->_M_prev = __tmp;
    return __tmp;
}

push_back插入一個(gè)節(jié)點(diǎn)，作為尾結(jié)點(diǎn)，都是雙向鏈表的常用操作，這里不再贅述。

push_front

void push_front(const _Tp& __x) { insert(begin(), __x); }  // 插入一個(gè)節(jié)點(diǎn) __x，作為頭結(jié)點(diǎn)
iterator insert(iterator __position, const _Tp& __x) {
    _Node* __tmp = _M_create_node(__x);
    // 調(diào)整雙向指針，插入新元素
    __tmp->_M_next = __position._M_node;  // list為雙向鏈表
    __tmp->_M_prev = __position._M_node->_M_prev;
    __position._M_node->_M_prev->_M_next = __tmp;
    __position._M_node->_M_prev = __tmp;
    return __tmp;
}

push_front同樣是調(diào)用了insert(iterator, const _Tp&)來完成插入操作的。

clear

void clear() { _Base::clear(); }
template <class _Tp, class _Alloc>
void 
_List_base<_Tp,_Alloc>::clear() 
{
  _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next;  // 指向開始節(jié)點(diǎn)，begin()
  while (__cur != _M_node) {
    _List_node<_Tp>* __tmp = __cur;
    __cur = (_List_node<_Tp>*) __cur->_M_next;
    _Destroy(&__tmp->_M_data);  // 銷毀(析構(gòu)并釋放)一個(gè)節(jié)點(diǎn)
    _M_put_node(__tmp);
  }
  // 恢復(fù) _M_node 原始狀態(tài)
  _M_node->_M_next = _M_node;
  _M_node->_M_prev = _M_node;
}

clear時(shí)從頭結(jié)點(diǎn)到尾結(jié)點(diǎn)，依次釋放每一個(gè)節(jié)點(diǎn)的內(nèi)存空間。

特點(diǎn)

由于list是通過雙向鏈表來實(shí)現(xiàn)的，它的迭代器要提供前移、后移的能力，所以list提供了Bidirectional iterator；插入、刪除節(jié)點(diǎn)的效率很高。

與vector的區(qū)別

vector為存儲(chǔ)的對(duì)象分配一塊連續(xù)的地址空間，隨機(jī)訪問效率很高。但是插入和刪除需要移動(dòng)大量的數(shù)據(jù)，效率較低。尤其當(dāng)vector中存儲(chǔ)的對(duì)象較大，或者構(gòu)造函數(shù)復(fù)雜，則在對(duì)現(xiàn)有的元素進(jìn)行拷貝的時(shí)候會(huì)執(zhí)行拷貝構(gòu)造函數(shù)。
list中的對(duì)象是離散的，隨機(jī)訪問需要遍歷整個(gè)鏈表，訪問效率比vector低。但是在list中插入元素，尤其在首尾插入，效率很高，只需要改變?cè)氐闹羔槨?/li>
vector是單向的，而list是雙向的；
向量中的iterator在使用后就釋放了，但是鏈表list不同，它的迭代器在使用后還可以繼續(xù)用；鏈表特有的；

到此這篇關(guān)于STL容器之list源碼詳細(xì)解讀的文章就介紹到這了,更多相關(guān)STL容器list 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: