【STL源码分析】c++,List双向链表源码分析。自己实现list双向链表。

这篇具有很好参考价值的文章主要介绍了【STL源码分析】c++,List双向链表源码分析。自己实现list双向链表。。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

参考链接:https://blog.csdn.net/man_sion/article/details/71003095?

自己实现双向链表:

先抽取要实现的功能,由于迭代器有些麻烦,就不使用了。要实现的功能有,push_back,pop_back,insert(指定位置,指定值),insert(指定位置,list,区间值),reverse,clear,getsize,begin,end,构造和析构函数,empty。

相关力扣题目:设计链表 124ms

class MyLinkedList {
public:
    struct Node{
        Node * prev;
        Node *next;
        int val;
        Node(int x):prev(NULL),next(NULL),val(x){}
        Node():prev(NULL),next(NULL),val(-999){}
    };
    //构造的时候要创建头节点,size=0. index从0开始,head的下标是0
    //刚开始,头尾节点都是无值的 空节点。头尾节点是独立的节点,头节点的next指向第一个节点,尾节点指向最后一个节点的下一个节点(NULL)。
    MyLinkedList() {
        //初始化size为0,数据成员为无效值节点。
        size=0;
        this->head=new (Node ) ();
        this->tail=new (Node ) ();
        head->next=tail;
        tail->prev=head;
    }
    //写一个析构函数(未经验证,欢迎交流)
    ~MyLinkedList() {
    	//从temp到head全部删除
    	Node * temp=head;
    	while(temp!=NULL){
    		delete(temp);
    		temp=temp->next;
		}
	}
    //要进行有效性校验的,现在有size
    int get(int index) {
        if(index<0 || index>=size) return -1;
        Node * temp;
        //如果size为0,temp=head,不然temp指向第一个有效节点。
        if(size==0){
            temp=head;
        } 
        else {
            temp=head->next;
        }
        int i=0;
        while(i<index) {
            ++i;
            temp=temp->next;
        }
        if(temp==tail) return -1;
        else
        return temp->val;
    }
    //为了提高代码复用性,可以调用addAtIndex函数,方便维护!!!
    void addAtHead(int val) {
        addAtIndex(0,val);
    }
    //size为已有的元素个数,要插入的尾部位置正好索引为size
    void addAtTail(int val) {
        addAtIndex(size,val);
    }
    //考虑几个特殊情况,size=0,size=index
    void addAtIndex(int index, int val) {
        if(index<0 || index>size) return;
        Node * temp;
        if(size==0){
            temp=head;
        } 
        else {
            temp=head->next;
        }
        
        Node * node=new (Node ) (val); //*node后面是temp
        int i=0;
        //分为在头部、尾部、中间插入
        if(index==0){ 
            head->next->prev=node;
            node->next=head->next;
            head->next=node; 
            node->prev=head;
        }else if (index==size){
            tail->prev->next=node;
            node->prev=tail->prev;
            node->next=tail;
            tail->prev=node;
        }else{
            while(i<index) {
            ++i;
            temp=temp->next;
            }
            temp->prev->next=node;
            node->prev=temp->prev;
            node->next=temp;
            temp->prev=node;
        }
        size++;
    }
    
    //删除这个节点,要把其他节点的指针移动再删除
    void deleteAtIndex(int index) {
        printMylist();
        if(index<0 || index>=size) return;
        if(size==0) return; //没有节点的话不能删除直接返回。
        //temp是要删除的节点,temp的index=0
        Node * temp=head->next;
        int i=0;
        while(i<index) {
            ++i;
            temp=temp->next;
        }
        //注意空节点的特殊情况,删除头节点,删除尾节点,以及只有一个节点的情况
        if(size==1){ //temp=head->next  temp指向第一个节点
            head->next=temp->next;
            temp->next->prev=temp;
        }else{
            temp->prev->next=temp->next;
            temp->next->prev=temp->prev;
        }
        size--;
        delete(temp);
    }
    Node * begin(){
        return head;
    }
    Node * end(){
        return tail;
    }
    void printMylist(){
        cout<<endl;
        for(Node * it=head;it!=end();it=it->next){
            cout<<it->val;
        }
        cout<<endl;
    }
private:
    Node *tail;
    Node * head;          //双向链表,头节点指向第一个节点,尾节点指向最后一个节点的下一个节点(NULL)。
    int size;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

力扣官方解答: 36ms

struct DLinkListNode {
    int val;
    DLinkListNode *prev, *next;
    DLinkListNode(int _val) : val(_val), prev(nullptr), next(nullptr) {}
};

class MyLinkedList {
public:
    MyLinkedList() {
        this->size = 0;
        this->head = new DLinkListNode(0);
        this->tail = new DLinkListNode(0);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        DLinkListNode *curr;
        if (index + 1 < size - index) {
            curr = head;
            for (int i = 0; i <= index; i++) {
                curr = curr->next;
            }
        } else {
            curr = tail;
            for (int i = 0; i < size - index; i++) {
                curr = curr->prev;
            }
        }
        return curr->val;
    }
    
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        index = max(0, index);
        DLinkListNode *pred, *succ;
        if (index < size - index) {
            pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred->next;
            }
            succ = pred->next;
        } else {
            succ = tail;
            for (int i = 0; i < size - index; i++) {
                succ = succ->prev;
            }
            pred = succ->prev;
        }
        size++;
        DLinkListNode *toAdd = new DLinkListNode(val);
        toAdd->prev = pred;
        toAdd->next = succ;
        pred->next = toAdd;
        succ->prev = toAdd;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        DLinkListNode *pred, *succ;
        if (index < size - index) {
            pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred->next;
            }
            succ = pred->next->next;
        } else {
            succ = tail;
            for (int i = 0; i < size - index - 1; i++) {
                succ = succ->prev;
            }
            pred = succ->prev->prev;
        }
        size--;
        DLinkListNode *p = pred->next;
        pred->next = succ;
        succ->prev = pred;
        delete p;
    }
private:
    int size;
    DLinkListNode *head;
    DLinkListNode *tail;
};

小结:
1、使用nullptr代表空指针更规范,在c++11里引入了nullptr来代替NULL。因为NULL具有二义性,在一些隐式转换中可能被当做值0处理。在C语言中可以,因为C语言中NULL被定义为void *类型,使用时会隐式转换为其他类型。
2、get函数中进行了一个判断:根据index和size的关系判断从头或尾哪一边找到节点更快。
3、代码重用,比如在头尾添加节点可以调用addAtIndex函数。
4、addAtIndex函数中在根据index找位置的时候也可以使用判断,从头或尾哪一边找节点更快,即涉及到index的都可以进行该判断。

List双向链表源码分析:

按自己的理解分节解析,写在注释里了,欢迎一起交流~

1-98行

头文件和一些类的声明:

// list standard header

#if     _MSC_VER > 1000
#pragma once
#endif

#ifndef _LIST_
#define _LIST_
#include <cstddef>
#include <functional>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <xutility>

#ifdef  _MSC_VER
#pragma pack(push,8)
#endif  /* _MSC_VER */
_STD_BEGIN
		// TEMPLATE CLASS list
        //整个都是list类。
template<class _Ty, class _A = allocator<_Ty> >         //allocator是空间适配器,使用模板实现,指定其类型为_Ty。它用于将内存的分配和对象的构造分离开来. 它分配的内存是原始的、未构造的.
	class list {                                        //new把内存分配和对象构造绑定在一起,可能造成资源浪费。
protected:
	struct _Node;
	friend struct _Node;
	typedef _POINTER_X(_Node, _A) _Nodeptr;

    //定义node,有next和pre,val
	struct _Node {
		_Nodeptr _Next, _Prev;
		_Ty _Value;
		};
	struct _Acc;
	friend struct _Acc;//声明为友元
        //分别有三个成员函数,返回上一个节点指针、下一个、返回节点的值
	struct _Acc {
		typedef _REFERENCE_X(_Nodeptr, _A) _Nodepref;
		typedef _A::reference _Vref;
		static _Nodepref _Next(_Nodeptr _P)
			{return ((_Nodepref)(*_P)._Next); }
		static _Nodepref _Prev(_Nodeptr _P)
			{return ((_Nodepref)(*_P)._Prev); }
		static _Vref _Value(_Nodeptr _P)
			{return ((_Vref)(*_P)._Value); }
		};
public:
	typedef list<_Ty, _A> _Myt;
	typedef _A allocator_type;
	typedef _A::size_type size_type;
	typedef _A::difference_type difference_type;
	typedef _A::pointer _Tptr;
	typedef _A::const_pointer _Ctptr;
	typedef _A::reference reference;
	typedef _A::const_reference const_reference;
	typedef _A::value_type value_type;
		// CLASS const_iterator 提供迭代器
	class iterator;
	class const_iterator;                  //difference_type表示差值类型,是迭代器的一种类型
	friend class const_iterator;        //--------------------------const_iterator类,继承Bidit双向迭代器类。迭代器是一个对象,通过运算符重载模拟了指针的一些功能。迭代器里的数据是 指向节点的指针
	class const_iterator : public _Bidit<_Ty, difference_type> {
	public:
		const_iterator()              //分别是空构造函数,通过节点构造,通过const类型迭代器的构造(拷贝该迭代器的指针,相当于拷贝构造)
			{}
		const_iterator(_Nodeptr _P)
			: _Ptr(_P) {}
		const_iterator(const iterator& _X)
			: _Ptr(_X._Ptr) {}
		const_reference operator*() const         //重载*,取节点的值
			{return (_Acc::_Value(_Ptr)); }
		_Ctptr operator->() const           // this是指针,指向当前迭代器对象,*this是解引用,得到当前迭代器对象,**this表示指向当前迭代器对象的指针,&表示引用
			{return (&**this); }
		const_iterator& operator++()          //重载前置++,让迭代器里的数据(指针)指向下一个,返回该迭代器
			{_Ptr = _Acc::_Next(_Ptr);
			return (*this); }
		const_iterator operator++(int)         //重载后置++,先记录当前迭代器tmp,++后再返回tmp
			{const_iterator _Tmp = *this;
			++*this;
			return (_Tmp); }
		const_iterator& operator--()         //分别重载前置--和后置--
			{_Ptr = _Acc::_Prev(_Ptr);
			return (*this); }
		const_iterator operator--(int)
			{const_iterator _Tmp = *this;
			--*this;
			return (_Tmp); }
		bool operator==(const const_iterator& _X) const      //重载==,判断指针是否同一个
			{return (_Ptr == _X._Ptr); }
		bool operator!=(const const_iterator& _X) const
			{return (!(*this == _X)); }
		_Nodeptr _Mynode() const               //得到当前迭代器的数据(指针)
			{return (_Ptr); }
	protected:
		_Nodeptr _Ptr;
		};
		// CLASS iterator

小结:
1、使用了allocator空间适配器,它是使用模板实现的。用于将内存分配与对象的构造分开来(区分于new),它分配的内存是原始,未构造的。
2、定义了Acc结构体,有三个成员函数:_Next,_Prev,_Vref分别返回下一个节点指针,上一个节点指针和该节点的值。
3、list类一共有三个数据成员,分别是allocator、Head、Size。
4、定义了const_iterator类,继承了Bidit类双向迭代器类。迭代器是一个类实例化后产生的对象,维护了private级别的指针成员。
5、迭代器里重载了前置后置++、–等符号,以及->、*等符号,来实现直接使用这些符号。以及一个Mynode成员函数,用来得到当前迭代器的数据成员(指针)。
6、利用模板类定义支持多种形式的list,在list类中定义node结构体。

99-220行:

	// CLASS iterator
	friend class iterator;
	class iterator : public const_iterator {  //------------------------------iterator类,继承const_iterator,与上面类似
	public:
		iterator()
			{}
		iterator(_Nodeptr _P)
			: const_iterator(_P) {}
		reference operator*() const
			{return (_Acc::_Value(_Ptr)); }
		_Tptr operator->() const
			{return (&**this); }
		iterator& operator++()
			{_Ptr = _Acc::_Next(_Ptr);
			return (*this); }
		iterator operator++(int)
			{iterator _Tmp = *this;
			++*this;
			return (_Tmp); }
		iterator& operator--()
			{_Ptr = _Acc::_Prev(_Ptr);
			return (*this); }
		iterator operator--(int)
			{iterator _Tmp = *this;
			--*this;
			return (_Tmp); }
		bool operator==(const iterator& _X) const
			{return (_Ptr == _X._Ptr); }
		bool operator!=(const iterator& _X) const
			{return (!(*this == _X)); }
		};
	typedef reverse_bidirectional_iterator<iterator,             //声明了reverse_iterator
		value_type, reference, _Tptr, difference_type>
			reverse_iterator;
	typedef reverse_bidirectional_iterator<const_iterator,
		value_type, const_reference, _Ctptr, difference_type>
			const_reverse_iterator;         //-------------------------------------声明一些接口
	explicit list(const _A& _Al = _A())   //explicit关键词,阻止隐式转换。 这是一个list的构造函数  list(_Al),_Al默认使用空构造函数 构造。三个参数 allocator,head,size分别初始化
		: allocator(_Al),
		_Head(_Buynode()), _Size(0) {}          //!!!重点,head节点使用Buynode的空构造函数,说明head指向空节点。
	explicit list(size_type _N, const _Ty& _V = _Ty(),      //list的构造函数   list(N,V,Al)参数分别是大小,迭代器和空间适配器。_Ty是模板类型,即节点里存入值的类型
		const _A& _Al = _A())
		: allocator(_Al),
		_Head(_Buynode()), _Size(0)
		{insert(begin(), _N, _V); }
	list(const _Myt& _X)              // 拷贝构造函数,传入参数是list。begin是head节点的下一个节点,从下一个节点开始拷贝整个链表
		: allocator(_X.allocator),
		_Head(_Buynode()), _Size(0)
		{insert(begin(), _X.begin(), _X.end()); }
	list(const _Ty *_F, const _Ty *_L, const _A& _Al = _A())          //拷贝构造,传入表示区间的迭代器。begin是head节点的下一个节点,从下一个节点开始拷贝整个链表
		: allocator(_Al),
		_Head(_Buynode()), _Size(0)
		{insert(begin(), _F, _L); }
	typedef const_iterator _It;
	list(_It _F, _It _L, const _A& _Al = _A()) //拷贝构造,以迭代器的区间
		: allocator(_Al),
		_Head(_Buynode()), _Size(0)
		{insert(begin(), _F, _L); }
	~list()                            //析构函数,erase清除区间值,释放头节点,清空size
		{erase(begin(), end());
		_Freenode(_Head);
		_Head = 0, _Size = 0; }
	_Myt& operator=(const _Myt& _X)
		{if (this != &_X)           //判断两个对象是否是同一个,如果是同一个直接返回自身。
			{iterator _F1 = begin();  //拿到自身的起始和结束迭代器。
			iterator _L1 = end();
			const_iterator _F2 = _X.begin();  //拿到X的起始和结束迭代器,使用const防止值被修改
			const_iterator _L2 = _X.end();
			for (; _F1 != _L1 && _F2 != _L2; ++_F1, ++_F2)     //使用与条件,F1或者F2任一迭代器先到达尾部则停止赋值。使用前置++减少临时对象拷贝
				*_F1 = *_F2;
			erase(_F1, _L1);//如果A比X长,A先结尾,F1=L1,使用insert插入X的剩余元素;如果A比X短,X先结尾,F2=L2,清空A的末尾未拷贝元素,insert不起作用。
			insert(_L1, _F2, _L2); }
		return (*this); }
	iterator begin()            //begin是头节点的下一个,end是头节点(一个空节点,用于标记位置)。
		{return (iterator(_Acc::_Next(_Head))); }
	const_iterator begin() const
		{return (const_iterator(_Acc::_Next(_Head))); }
	iterator end()
		{return (iterator(_Head)); }
	const_iterator end() const
		{return (const_iterator(_Head)); }
	reverse_iterator rbegin()
		{return (reverse_iterator(end())); }
	const_reverse_iterator rbegin() const
		{return (const_reverse_iterator(end())); }
	reverse_iterator rend()
		{return (reverse_iterator(begin())); }
	const_reverse_iterator rend() const
		{return (const_reverse_iterator(begin())); }
	void resize(size_type _N, _Ty _X = _Ty())           //调整链表大小,参数是大小N和默认插入节点。
		{if (size() < _N)
			insert(end(), _N - size(), _X);       //从尾部开始插入,插入N-size个
		else
			while (_N < size())
				pop_back(); }
	size_type size() const
		{return (_Size); }
	size_type max_size() const
		{return (allocator.max_size()); }
	bool empty() const                //判断链表是否为空
		{return (size() == 0); }
	_A get_allocator() const
		{return (allocator); }
	reference front()                   //返回头节点的下一个(即第一个元素),使用引用类型。返回指向该对象的指针。
		{return (*begin()); }
	const_reference front() const
		{return (*begin()); }
	reference back()                //返回头节点的上一个,即最后一个元素。
		{return (*(--end())); }
	const_reference back() const
		{return (*(--end())); }
	void push_front(const _Ty& _X)         //调用insert函数,代码重用。
		{insert(begin(), _X); }
	void pop_front()
		{erase(begin()); }
	void push_back(const _Ty& _X)
		{insert(end(), _X); }
	void pop_back()
		{erase(--end()); }
	void assign(_It _F, _It _L)          //区间赋值
		{erase(begin(), end());
		insert(begin(), _F, _L); }
	void assign(size_type _N, const _Ty& _X = _Ty())     
		{erase(begin(), end());
		insert(begin(), _N, _X); }

小结:

1、创建iterator类,继承const_iterator类,同样的重载了一些常用运算符。
2、explicit关键词,阻止隐式转换,只对只有一个参数的构造函数有效(或者从第二个参数开始都有默认赋值),因为编译器可能把该数据类型的数据隐式转换为该类型对象,优点是可以避免不合时宜的类型变换,缺点无。比如使用在构造函数上,explicit list(const _A& _Al = _A())。加上后,list x= _Al 就不行了,只能使用list x(_Al)的显式转换.
3、类构造函数默认情况下声明为隐式的即 implicit,与explicit相对。
4、重点:双向链表list的head指针指向空节点,begin()函数返回head->next,即head的下一个节点,而end()函数指向head节点(空节点),用于标记位置。因此从begin仍是第一个节点,end是最后一个有值节点的下一个空节点。head是最后一个有值节点的下一个空节点。
5、因为4,一般使用拷贝构造的时候,都调用begin函数开始;析构的时候也用begin和end函数返回的指针,当begin迭代器==end迭代器时erase结束,因此最后还要erase head节点。
6、使用前置++减少临时对象拷贝。
7、在一个函数里调用其他基础通用的函数,提高代码重用性。比如写了insert(iterator position,const T val)的具体实现,那么写insert(iterator P,size n,const T val),意思是在P位置插入n个值为val的节点,就可以直接for循环,里面调用insert函数了。erase(iterator P)也可以作为一个基础函数给同名参数列表不同的重载erase方法使用。

221-476行:

	iterator insert(iterator _P, const _Ty& _X = _Ty())         //在该位置插入一个节点B,参数分别是 迭代器位置,const的默认节点 ,返回新插入结点的迭代器。
		{_Nodeptr _S = _P._Mynode();                 //创建临时指针,指向参数迭代器指向的节点A。
		_Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));      // 新创建一个结点C,其next指向A,其pre指向A的前一个结点。A节点指向新创建的结点C。
		_S = _Acc::_Prev(_S);                             //指针指向C
		_Acc::_Next(_Acc::_Prev(_S)) = _S;             // C的前一个结点的下一个指向C
		allocator.construct(&_Acc::_Value(_S), _X);  //结点C变为结点B。allocator类的构造函数,第一个参数是一个指针,指向一片内存;第二个参数是args,用来构造一个对象,即以结点_X构造函数构造结点对象。
		++_Size;
		return (iterator(_S)); }                 
	void insert(iterator _P, size_type _M, const _Ty& _X)
		{for (; 0 < _M; --_M)
			insert(_P, _X); }
	void insert(iterator _P, const _Ty *_F, const _Ty *_L)
		{for (; _F != _L; ++_F)
			insert(_P, *_F); }
	void insert(iterator _P, _It _F, _It _L)
		{for (; _F != _L; ++_F)
			insert(_P, *_F); }
	iterator erase(iterator _P)                        //erase单个结点,传入要清除节点S的迭代器。利用Mynode函数拿到指向该位置的指针。同时P指针指向下一个结点。
		{_Nodeptr _S = (_P++)._Mynode();                
		_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);      //S的上一个节点指向S的下一个节点
		_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);		//S的下一个节点指向上一个节点。利用Prev和Next函数可以方便的拿到S节点的前后节点的指针,而不修改指向S节点的指针。
		allocator.destroy(&_Acc::_Value(_S));				//使用Acc:是为了声明是函数,因为node节点的值有同名数据。
		_Freenode(_S);                                      //freenode调用allocator的deallocate函数。
		--_Size;
		return (_P); }
	iterator erase(iterator _F, iterator _L)
		{while (_F != _L)
			erase(_F++);
		return (_F); }
	void clear()
		{erase(begin(), end()); }
	void swap(_Myt& _X)                              //单参数swap,传入的参数是list<_Ty, _A> X。即交换自身和传入的list。因为这是List的成员函数,里面的值就是本身的值。
		{if (allocator == _X.allocator)             //比较两个list的allocator,如果相同说明是同一个地址空间。一个list一共三个数据成员。
			{std::swap(_Head, _X._Head);
			std::swap(_Size, _X._Size); }
		else
			{iterator _P = begin();
			splice(_P, _X);
			_X.splice(_X.begin(), *this, _P, end()); }}
	friend void swap(_Myt& _X, _Myt& _Y)
		{_X.swap(_Y); }
	void splice(iterator _P, _Myt& _X)                 //splice成员函数,X.splice()。传入迭代器P,和一个list。在P位置剪切listX。
		{if (!_X.empty())                              //如果list非空,调用Splice函数。
			{_Splice(_P, _X, _X.begin(), _X.end());
			_Size += _X._Size;
			_X._Size = 0; }}
	void splice(iterator _P, _Myt& _X, iterator _F)
		{iterator _L = _F;
		if (_P != _F && _P != ++_L)
			{_Splice(_P, _X, _F, _L);
			++_Size;
			--_X._Size; }}
	void splice(iterator _P, _Myt& _X, iterator _F, iterator _L)
		{if (_F != _L)
			{if (&_X != this)
				{difference_type _N = 0;
				_Distance(_F, _L, _N);
				_Size += _N;
				_X._Size -= _N; }
			_Splice(_P, _X, _F, _L); }}
	void remove(const _Ty& _V)             //remove函数,移除所有值为V的元素
		{iterator _L = end();
		for (iterator _F = begin(); _F != _L; )
			if (*_F == _V)
				erase(_F++);
			else
				++_F; }
	typedef binder2nd<not_equal_to<_Ty> > _Pr1;
	void remove_if(_Pr1 _Pr)              //removeif,移除所有满足条件的结点。
		{iterator _L = end();
		for (iterator _F = begin(); _F != _L; )
			if (_Pr(*_F))               //比较传入的结点和当前值是否相等,相等的话erase这个结点,再++。
				erase(_F++);           
			else
				++_F; }
	void unique()                       //unique,删除重复元素。
		{iterator _F = begin(), _L = end();
		if (_F != _L)
			for (iterator _M = _F; ++_M != _L; _M = _F)
				if (*_F == *_M)           //初始值M=F=begin,M++,如果M与F相等,把M删除,F仍是前一个元素,M重新指向F,再++,再进入循环;否则,F往后移动=M,再执行M重新指向F,M++,进入循环。。。
					erase(_M);
				else
					_F = _M; }
	typedef not_equal_to<_Ty> _Pr2;
	void unique(_Pr2 _Pr)
		{iterator _F = begin(), _L = end();
		if (_F != _L)
			for (iterator _M = _F; ++_M != _L; _M = _F)
				if (_Pr(*_F, *_M))
					erase(_M);
				else
					_F = _M; }
	void merge(_Myt& _X)		         //合并。先判断两者是不是同一个list。要求是两个有序链表,合并以后也是有序的。
		{if (&_X != this)
			{iterator _F1 = begin(), _L1 = end();
			iterator _F2 = _X.begin(), _L2 = _X.end();
			while (_F1 != _L1 && _F2 != _L2)
				if (*_F2 < *_F1)             //如果值小的,先剪切进去。
					{iterator _Mid2 = _F2;
					_Splice(_F1, _X, _F2, ++_Mid2);
					_F2 = _Mid2; }
				else
					++_F1;
			if (_F2 != _L2)
				_Splice(_L1, _X, _F2, _L2);
			_Size += _X._Size;
			_X._Size = 0; }}
	typedef greater<_Ty> _Pr3;
	void merge(_Myt& _X, _Pr3 _Pr)                 
		{if (&_X != this)
			{iterator _F1 = begin(), _L1 = end();
			iterator _F2 = _X.begin(), _L2 = _X.end();
			while (_F1 != _L1 && _F2 != _L2)
				if (_Pr(*_F2, *_F1))
					{iterator _Mid2 = _F2;
					_Splice(_F1, _X, _F2, ++_Mid2);
					_F2 = _Mid2; }
				else
					++_F1;
			if (_F2 != _L2)
				_Splice(_L1, _X, _F2, _L2);
			_Size += _X._Size;
			_X._Size = 0; }}
	void sort()            //排序,利用merge函数和swap函数实现。
		{if (2 <= size())    //size为1不用排序。
			{const size_t _MAXN = 15;
			_Myt _X(allocator), _A[_MAXN + 1];     //利用数据成员allocator重新分配一个空间X,类别为A的数组
			size_t _N = 0;	
			while (!empty())		
				{_X.splice(_X.begin(), *this, begin());     //先把第一个节点剪切过来。
				size_t _I;
				for (_I = 0; _I < _N && !_A[_I].empty(); ++_I)        //_N在哪里赋值的?这个地方有点没看懂。
					{_A[_I].merge(_X);
					_A[_I].swap(_X); }
				if (_I == _MAXN)
					_A[_I].merge(_X);
				else
					{_A[_I].swap(_X);
					if (_I == _N)
						++_N; }}
			while (0 < _N)
				merge(_A[--_N]); }}
	void sort(_Pr3 _Pr)
		{if (2 <= size())
			{const size_t _MAXN = 15;
			_Myt _X(allocator), _A[_MAXN + 1];
			size_t _N = 0;
			while (!empty())
				{_X.splice(_X.begin(), *this, begin());
				size_t _I;
				for (_I = 0; _I < _N && !_A[_I].empty(); ++_I)
					{_A[_I].merge(_X, _Pr);
					_A[_I].swap(_X); }
				if (_I == _MAXN)
					_A[_I].merge(_X, _Pr);
				else
					{_A[_I].swap(_X);
					if (_I == _N)
						++_N; }}
			while (0 < _N)
				merge(_A[--_N], _Pr); }}
	void reverse()                             //翻转,先令L指向末尾。F指向开头。每一轮循环创建M=F,利用Splice函数在开头位置,贴上list本身的M~ M的下一个元素。一个一个元素贴,直到++F到end。
		{if (2 <= size())
			{iterator _L = end();
			for (iterator _F = ++begin(); _F != _L; )
				{iterator _M = _F;
				_Splice(begin(), *this, _M, ++_F); }}}
protected:
	_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)             //Buynode结构体,是指针,构造函数,默认参数是0,即空指针,如果传入参数则前后分别指向传入的参数
		{_Nodeptr _S = (_Nodeptr)allocator._Charalloc(
			1 * sizeof (_Node));
		_Acc::_Next(_S) = _Narg != 0 ? _Narg : _S;
		_Acc::_Prev(_S) = _Parg != 0 ? _Parg : _S;
		return (_S); }
	void _Freenode(_Nodeptr _S)                    //释放结点,使用与allocator构造函数相反的deallocate
		{allocator.deallocate(_S, 1); }
	void _Splice(iterator _P, _Myt& _X, iterator _F, iterator _L)            //Splice函数,传入迭代器,list2,迭代器区间iter1~iter2。将list2中的某一段位置iter1 ~ iter2的元素剪贴到list1中的position位置
		{if (allocator == _X.allocator)										//L迭代器取的是L的前一个节点。F~L区间其实是左闭右开区间。
			{_Acc::_Next(_Acc::_Prev(_L._Mynode())) =                    //L的前一个节点的下一个指向P
				_P._Mynode();
			_Acc::_Next(_Acc::_Prev(_F._Mynode())) =                      //F的前一个节点的下一个指向L
				_L._Mynode();
			_Acc::_Next(_Acc::_Prev(_P._Mynode())) =                      //P的前一个节点的下一个指向F
				_F._Mynode();
			_Nodeptr _S = _Acc::_Prev(_P._Mynode());                     //S指向P的前一个节点。P的前一个节点指向L的前一个节点
			_Acc::_Prev(_P._Mynode()) =
				_Acc::_Prev(_L._Mynode());
			_Acc::_Prev(_L._Mynode()) = 								//L的前一个节点指向F的前一个节点
				_Acc::_Prev(_F._Mynode());
			_Acc::_Prev(_F._Mynode()) = _S; }							//F的前一个节点指向S
		else
			{insert(_P, _F, _L);              //否则在P位置直接插入F-L区间元素。
			_X.erase(_F, _L); }}
	void _Xran() const
		{_THROW(out_of_range, "invalid list<T> subscript"); }
	_A allocator;           //list的成员,分别是空间适配器,头节点指针,list大小
	_Nodeptr _Head;                 
	size_type _Size;
	};
		// list TEMPLATE OPERATORS
template<class _Ty, class _A> inline
	bool operator==(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (_X.size() == _Y.size()
		&& equal(_X.begin(), _X.end(), _Y.begin())); }
template<class _Ty, class _A> inline
	bool operator!=(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (!(_X == _Y)); }
template<class _Ty, class _A> inline
	bool operator<(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (lexicographical_compare(_X.begin(), _X.end(),
		_Y.begin(), _Y.end())); }
template<class _Ty, class _A> inline
	bool operator>(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (_Y < _X); }
template<class _Ty, class _A> inline
	bool operator<=(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (!(_Y < _X)); }
template<class _Ty, class _A> inline
	bool operator>=(const list<_Ty, _A>& _X,
		const list<_Ty, _A>& _Y)
	{return (!(_X < _Y)); }
_STD_END
#ifdef  _MSC_VER
#pragma pack(pop)
#endif  /* _MSC_VER */

#endif /* _LIST_ */

/*
 * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED. 
 * Consult your license regarding permissions and restrictions.
 */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

小结

1、其实sort函数有点没看懂,好像跟平常惯用的排序不太一样。之后查了其他资料再补充。
2、创建的Acc结构体下的 Prev和Next函数很经典,提供通过迭代器指针得到指针返回值,支持迭代赋值(有个其他词语,忘记是什么了),就是能一层层的得到返回值,很好用。

码一个SGI版本的sort源码分析:
https://feihu.me/blog/2014/sgi-std-sort/#stdsort文章来源地址https://www.toymoban.com/news/detail-438776.html

到了这里,关于【STL源码分析】c++,List双向链表源码分析。自己实现list双向链表。的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ ——STL容器【list】模拟实现

    代码仓库: list模拟实现 list源码 数据结构——双向链表 源码的list是双向带头循环链表,所以我们定义两个节点,一个指向下一个,一个指向前一个 list类包含一个 _head 头节点,然后为了方便查出当前有多少个节点,还能多定义一个 _size 源码的迭代器设置了三个模板参数:

    2024年02月15日
    浏览(45)
  • [ C++ ] STL---list的模拟实现

    目录 结点类的模拟实现 迭代器类的模拟实现 构造函数 前置++与后置++ 前置- -与后置 - - == 与 !=运算符重载 * 运算符重载 - 运算符重载 普通迭代器总体实现代码 list类的实现 list类的成员变量 构造函数 迭代器 insert() erase() push_front/push_back/pop_front/pop_back front/back clear() empty()

    2024年04月09日
    浏览(59)
  • 【C++】STL---list的模拟实现

    上次模拟实现了一个vector容器,那么我们这次来实现一个list(链表)容器,链表在实际的开发中并不常见。但是也是一种很重要的数据结构,下面给大家介绍一下链表(list) 和 vector(顺序表)的区别。 list 和 vector 一样,是一个存储容器。不同的是vector在内存中是连续存储的,而

    2024年01月22日
    浏览(52)
  • C++ [STL之list模拟实现]

    本文已收录至《C++语言》专栏! 作者:ARMCSKGT list的底层与vector和string不同,实现也有所差别,特别是在迭代器的设计上,本节将为大家介绍list简单实现,并揭开list迭代器的底层! 本文介绍list部分简单接口,以list迭代器的介绍为主! list底层是一个带头双向循环链表,在节

    2024年02月09日
    浏览(38)
  • stl_list类(使用+实现)(C++)

    list是一个可以在常熟范围内任意位置进行插入和删除的序列式容器。 底层是带头双向循环链表 (链接中有对带头双向循环链表的逻辑分析)。 (constructor)构造函数声明 接口说明 list() 无参构造 list(size_type n, const T val = T() 构造并初始化n个val list(const list x) 拷贝构造 list(InputI

    2024年02月14日
    浏览(66)
  • 【C++】STL中List的详细实现解析

    在 C++ STL(标准模板库)中, List 是一个带头双向链表,可以存储多个元素并且支持动态调整大小,适合频繁插入和删除操作;而 Vector 是一个动态数组,元素在内存中是连续存储的,适合需要快速随机访问的场景。 List 提供了添加、删除、查找等操作,而 Vector 除了这些基本

    2024年02月21日
    浏览(40)
  • 【C++】STL——list深度剖析 及 模拟实现

    这篇文章我们来继续STL的学习,今天我们要学习的是list,也是STL中容器的一员。 和之前一样,我们还是先学习它的使用,然后再对它进行一个深度剖析和模拟实现。 1.1 list的介绍 list的文档介绍 list的底层实现其实就是我们之前数据结构学过的带头双向循环链表: 1.2 list的使

    2024年02月05日
    浏览(43)
  • C++ STL学习之【list的模拟实现】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 A year from now you may wish you had started today. 明年今日,你会希望此时此刻的自己已经开始行动了。 STL 中的 list 是一个双向带头循环链表,作为链表的终极形态,各项操作性能都很优秀,尤其是 list 中迭代器

    2024年02月04日
    浏览(41)
  • 【C++】STL之list容器的模拟实现

    个人主页:🍝在肯德基吃麻辣烫 分享一句喜欢的话:热烈的火焰,冰封在最沉默的火山深处。 本文章进入C++STL之list的模拟实现。 在STL标准库实现的list中,这个链表是一个== 双向带头循环链表==。 说明: list是一个类,成员变量为_head 节点类node,是每一个节点。 list的迭代

    2024年02月17日
    浏览(52)
  • C++ stl容器list的底层模拟实现

    目录 前言: 1.创建节点 2.普通迭代器的封装 3.反向迭代器的封装 为什么要对正向迭代器进行封装? 4.const迭代器 5.构造函数 6.拷贝构造 7.赋值重载 8.insert 9.erase 10.析构 11.头插头删,尾插尾删 12.完整代码+简单测试 总结: 1.创建节点 注意给缺省值,这样全缺省就会被当做默认

    2024年04月23日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包