1、list的介紹與使用

1.1 list的介紹

list文檔介紹

1. list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
2. list的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過(guò)指針指向其前一個(gè)元素和后一個(gè)元素。
3. list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡(jiǎn)單效。
4. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率更好。
5. 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機(jī)訪(fǎng)問(wèn)，比如：要訪(fǎng)問(wèn)list的第6個(gè)元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線(xiàn)性的時(shí)間開(kāi)銷(xiāo)；list還需要一些額外的空間，以保存每個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)信息(對(duì)于存儲(chǔ)類(lèi)型較小元素的大list來(lái)說(shuō)這可能是一個(gè)重要的因素)

1.2 list的使用

list中的接口比較多，此處類(lèi)似，只需要掌握如何正確的使用，然后再去深入研究背后的原理，已達(dá)到可擴(kuò)展的能力。

2、list迭代器

此處，我們可暫時(shí)將迭代器理解成一個(gè)指針，該指針指向list中的某個(gè)節(jié)點(diǎn)。
list我們都知道，它不是連續(xù)的空間，是我們將下一個(gè)位置的地址保存起來(lái)，通過(guò)地址走到下一個(gè)，因此我們需要重載一些運(yùn)算符。
后移的++（前置后置）
前移的 --（前置后置）
解引用的*，->
相等判斷的 ==，!=

這里我們?yōu)閘ist節(jié)點(diǎn)創(chuàng)建一個(gè)類(lèi)，后面直接使用這個(gè)類(lèi)就可以了，再寫(xiě)一個(gè)缺省的構(gòu)造函數(shù)，為后面開(kāi)節(jié)點(diǎn)提供便利。

// List的節(jié)點(diǎn)類(lèi)
template<class T>
struct ListNode
{
    ListNode(const T& val = T())
        :_pPre(nullptr)
        ,_pNext(nullptr)
        ,_val(val)
    {}

    ListNode<T>* _pPre;
    ListNode<T>* _pNext;
    T _val;
};


//List的迭代器類(lèi)
template<class T, class Ref, class Ptr>
class ListIterator
{
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;
public:
    ListIterator(PNode pNode = nullptr)
        :_pNode(pNode)
    {}

    ListIterator(const Self& l)
    {
        _pNode = l._pNode;
    }

    T& operator*()
    {
        return _pNode->_val;
    }

    T* operator->()
    {
        return &_pNode->_val;
    }

    Self& operator++()
    {
        _pNode = _pNode->_pNext;
        return *this;
    }

    Self& operator++(int)
    {
        Self tmp(*this);
        _pNode = _pNode->_pNext;

        return tmp;
    }

    Self& operator--()
    {
        _pNode = _pNode->_pPre;
        return *this;
    }

    Self& operator--(int)
    {
        Self tmp(*this);
        _pNode = _pNode->_pPre;

        return tmp;
    }

    bool operator!=(const Self& l)
    {
        return _pNode != l._pNode;
    }

    bool operator==(const Self& l)
    {
        return _pNode == l._pNode;
    }

//private:
    PNode _pNode;
};

3、list的構(gòu)造

構(gòu)造我們已經(jīng)寫(xiě)了太多了，對(duì)于這些接口直接秒殺。
空參構(gòu)造list：

list()
{
    _pHead = new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;
}

拷貝構(gòu)造list：

list(const list<T>& l)
{
    _pHead = new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;

    for (auto e : l)
    {
        push_back(e);
    }
}

n個(gè)值為val的構(gòu)造：

list(int n, const T& value = T())
{
    _pHead = new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;
    
    for (int i = 0; i < n; i++)
    {
        push_back(value);
    }
}

迭代器區(qū)間構(gòu)造：

template <class Iterator>
list(Iterator first, Iterator last)
{
    CreateHead();
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

4、list常用接口的實(shí)現(xiàn)

我們實(shí)現(xiàn)的是雙向帶頭循環(huán)的list，因此結(jié)構(gòu)為：

我們先將得到頭尾的接口實(shí)現(xiàn)一下：

iterator begin()
{
    return _pHead->_pNext;
}
iterator end()
{
    return _pHead;
}
const_iterator begin() const
{
    return _pHead->_pNext;
}
const_iterator end() const
{
    return _pHead;
}

4.1 list capacity

這里兩個(gè)接口都比較簡(jiǎn)單，我們直接秒殺。

size_t size() const
{
    int count = 0;

    const_iterator it = begin();
    while (it != end())
    {
        ++count;
        ++it;
    }
    return count;
}
bool empty() const
{
    return _pHead == _pHead->_pNext;
}

4.2 插入刪除、交換、清理

4.2.1 insert任意位置插入

思路：
1、我們先new一個(gè)節(jié)點(diǎn)newnode，并賦值為x（這里就會(huì)去調(diào)用list節(jié)點(diǎn)類(lèi)里面的構(gòu)造函數(shù)）；
2、記下pos位置前一個(gè)節(jié)點(diǎn)prev，將newnode, prev, pos三個(gè)節(jié)點(diǎn)連接起來(lái)；
3、返回newnode的迭代器。

代碼實(shí)現(xiàn)：

// 在pos位置前插入值為val的節(jié)點(diǎn)
iterator insert(iterator pos, const T& val)
{
    PNode cur = pos._pNode;
    PNode prev = cur->_pPre;

    PNode newnode = new Node(val);
    prev->_pNext = newnode;
    newnode->_pPre = prev;
    newnode->_pNext = cur;
    cur->_pPre = newnode;

    return newnode;
}

4.2.2 push_front頭插

對(duì)于頭插來(lái)說(shuō)，我們直接復(fù)用插入的代碼就可以。
頭插就是在鏈表的頭部插入一個(gè)元素，因此就是 insert(begin(), x);

void push_front(const T& val) { insert(begin(), val); }

4.2.3 push_back尾插

對(duì)于尾插也是一樣的，直接復(fù)用insert代碼。
因?yàn)槲覀僱ist是雙向帶頭循環(huán)鏈表，尾插 insert(end(), x) 直接在尾部前插入即可。end()返回的就是頭結(jié)點(diǎn)，頭結(jié)點(diǎn)是哨兵位節(jié)點(diǎn)，因此在end()前插就是尾插。

void push_back(const T& val) { insert(end(), val); }

4.2.4 erase任意位置刪除

思路：
1、分別記下pos前后位置的節(jié)點(diǎn)，prev，next；
2、將prev與next連接起來(lái)，釋放pos位置節(jié)點(diǎn)；
3、飯后pos下一個(gè)位置的節(jié)點(diǎn)。

// 刪除pos位置的節(jié)點(diǎn)，返回該節(jié)點(diǎn)的下一個(gè)位置
iterator erase(iterator pos)
{
    PNode cur = pos._pNode;
    PNode prev = cur->_pPre;
    PNode next = cur->_pNext;

    delete cur;
    prev->_pNext = next;
    next->_pPre = prev;

    return next;
}

4.2.5 pop_front頭刪

對(duì)于頭刪來(lái)說(shuō)，我們直接復(fù)用erase代碼就可以了。
頭刪直接刪除掉頭部就可以了，erase(begin())。

void pop_front() { erase(begin()); }

4.2.6 pop_back尾刪

尾刪也是復(fù)用erase代碼，就是刪掉列表的最后一個(gè)節(jié)點(diǎn)，erase(–end())。

void pop_back() { erase(--end()); }

這里為什么–end()，這里end()返回的是頭結(jié)點(diǎn)，因?yàn)橐獎(jiǎng)h除尾結(jié)點(diǎn)，所以需要–end()，才是真正的尾結(jié)點(diǎn)。

4.2.7 swap()

list的swap交換，只要交換兩個(gè)鏈表的頭結(jié)點(diǎn)就可以，因?yàn)槭擎準(zhǔn)酱鎯?chǔ)的，更換頭指針即可。庫(kù)中提供的交換直接復(fù)用就可以。

void swap(list<T>& l) { std::swap(_pHead, l._pHead); }

4.2.8 clear

對(duì)于鏈表的clear，我們需要釋放掉每一個(gè)有效節(jié)點(diǎn)，因此我們遍歷一遍，并復(fù)用erase。

void clear()
{
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);
    }
}

5、list迭代器失效問(wèn)題

前面說(shuō)過(guò)，此處大家可將迭代器暫時(shí)理解成類(lèi)似于指針，迭代器失效即迭代器所指向的節(jié)點(diǎn)的無(wú)效，即該節(jié)點(diǎn)被刪除了。因?yàn)閘ist的底層結(jié)構(gòu)為帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，因此在list中進(jìn)行插入時(shí)是不會(huì)導(dǎo)致list的迭代器失效的，只有在刪除時(shí)才會(huì)失效，并且失效的只是指向被刪除節(jié)點(diǎn)的迭代器，其他迭代器不會(huì)受到影響。

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		//這里如果先刪掉了，再去更新迭代器已經(jīng)被失效影響了
		lt.erase(it);
		++it;
	}

	return 0;
}

改正：

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		//這里如果先刪掉了，再去更新迭代器已經(jīng)被失效影響了
		lt.erase(it++);
	}

	return 0;
}

6、list與vector對(duì)比

vector與list都是STL中非常重要的序列式容器，由于兩個(gè)容器的底層結(jié)構(gòu)不同，導(dǎo)致其特性以及應(yīng)用場(chǎng)景不同，其主要不同如下：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-695896.html

到了這里，關(guān)于[C++] STL_list常用接口的模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！