目录

list的介绍

list的构造

list iterator的使用

list capacity

list element access

list modififiers

list的迭代器失效

关于迭代器

list的模拟实现

main.cpp

List.h

C语言总结在这常见八大排序在这

作者和朋友建立的社区：非科班转码社区-CSDN社区云

期待hxd的支持哈  

最后是打鸡血环节：你只管努力，剩下的交给天意    

list的介绍

list - C++ Reference (cplusplus.com)

 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list 的底层是带头双向循环链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。 3. list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高效。 4. 与其他的序列式容器相比 (array ， vector ， deque) ， list 通常在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比， list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list的第6 个元素，必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置，在这段位置上迭代需要线性的时间 另外， list 还需要一些额外的空间，以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 list 来说这可能是一个重要的因素) 早在C语言章节就已经实现过了带头双向循环链表了，但是这次C++不同的是迭代器类的实现，与以往有较大区别，注意理解

list的构造

构造函数（ (constructor) ）	接口说明
list (size_type n, const value_type& val = value_type())	构造的 list 中包含 n 个值为 val 的元素
list()	构造空的 list
list (const list& x)	拷贝构造函数
list (InputIterator fifirst, InputIterator last)	用 [fifirst, last) 区间中的元素构造 list

 其实学到这里了这什么函数是用来干什么的应该是一看就会了，但是考虑到文章的完整性和一些小白，就还是“冗余”得把这些函数及解释写了出来

list iterator的使用

函数声明	接口说明
begin + end	返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器                                 end（）就是头的位置
rbegin + rend	返回第一个元素的 reverse_iterator, 即 end 位置 ， 返回最后一个元素下一个位置的 reverse_iterator, 即 begin 位置

PS:

1. begin 与 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动 2. rbegin(end) 与 rend(begin) 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动

list capacity

函数声明	接口说明
empty	检测 list 是否为空，是返回 true ，否则返回 false
size	返回 list 中有效节点的个数

list element access

函数声明	接口说明
front	返回 list 的第一个节点中值的引用
back	返回 list 的最后一个节点中值的引用

list modififiers

函数声明	接口说明
push_front	在 list 首元素前插入值为 val 的元素
pop_front	删除 list 中第一个元素
push_back	在 list 尾部插入值为 val 的元素
pop_back	删除 list 中最后一个元素
insert	在 list position 位置中插入值为 val 的元素
erase	删除 list position 位置的元素
swap	交换两个 list 中的元素
clear	清空 list 中的有效元素

list的迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节 点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 ，因此 在 list 中进行插入时是不会导致 list 的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响 。

关于迭代器

迭代器是对原生态指针 ( 节点指针 ) 进行封装 迭 代 器 失 效 插入元素不会导致迭代器失效， 删除元素时，只会导致当前迭代 器失效，其他迭代器不受影响

list的模拟实现

main.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include"List.h"

int main()
{
	my_list l;
	l.insert(l.begin(), 1);
	l.insert(l.end(), 2);
	l.insert(l.end(), 2);
	l.insert(l.end(), 2);
	l.insert(l.end(), 7);
	l.insert(l.end(), 5);
	l.push_back(100);
	l.push_back(150);
	l.push_back(11);
	l.push_front(33);
	l.push_front(66);
	my_list::iterator it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	cout << endl;

	l.pop_back();
	l.pop_back();
	l.pop_front();
	l.pop_front();
	it = l.begin();

	it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	cout << endl;

	it = l.begin();
	while (it != l.end())
	{
		if (*it % 2 == 0)
		{
			it = l.erase(it);
		}
		else
		{
			it++;
		}
	}

	it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	cout << endl;

	my_list l2(l);
	it = l2.begin();
	while (it != l2.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	cout << endl;

	it = l.begin();
	my_list::iterator it2 = --it;

	cout << *it << endl;
	cout << *it2 << endl;
	//cout << l.front() << endl;
	//cout << l.back() << endl;

	//cout <<  *(l.begin()--) << endl;
	//cout << *(--l.begin()) << endl;
	//cout << *(l.begin()++) << endl;
	//cout << *(++l.begin()) << endl;
}

List.h

#include
#include
#include

using std::cout;
using std::endl;

// List的节点类
template
struct ListNode
{
    ListNode(const T& val = T())
        :_pPre(nullptr),
        _pNext(nullptr),
        _val(val)
    {}
    ListNode* _pPre;
    ListNode* _pNext;
    T _val;
};

//List的迭代器类
template
struct  ListIterator
{
    typedef ListNode* PNode;
    typedef ListIterator Self;

    //给reverse_iterator 用 ，这样反向迭代器类就可以不用传后面两个参数了
    typedef  T& Ref;
    typedef  T* Ptr;

    ListIterator(PNode pNode = nullptr)
        :_pNode(pNode)
    {}
    //it1(it2)
    ListIterator(const Self& l)
    {
        _pNode = l._pNode;
    }
    //模板参数  Ref    Ptr 的作用   ，返回 const和非const对象(由传参决定)
    //(其实就是两个类了，同一个类模板，参数不同，会实例化出不同类型的对象)
    Ref operator*()
    {
        return _pNode->_val;
    }
    Ptr operator->()             //注意返回值                            
    {
        //return &(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 !(operator==(l));
    }
    bool operator==(const Self& l)
    {
        return _pNode == l._pNode;
    }
    PNode _pNode;
};

//List的反向迭代器类
template
struct  ReverseIterator
{
    typedef typename ListIterator::Ref Ref;
    typedef typename ListIterator::Ptr Ptr;
    typedef ReverseIterator Self;

    ReverseIterator(ListIterator it)
        :_it(it)
    {}
    //it1(it2)
    ReverseIterator(const Self& l)
    {
        _it = l._it;
    }

    Ref operator*()
    {
        ListIterator temp(_it);
        --temp;
        return *temp;
    }
    Ptr operator->()             //注意返回值                            
    {
        return &(operator*());
    }
    Self& operator++()
    {
        --_it;
        return *this;
    }
    Self operator++(int)
    {
        Self temp(*this);
        --_it;
        return temp;
    }
    Self& operator--()
    {
        ++_it;
        return *this;
    }
    Self& operator--(int)
    {
        Self temp(*this);
        ++_it;
        return temp;
    }
    bool operator!=(const Self& l)
    {
        return _it != l._it;
    }
    bool operator==(const Self& l)
    {
        return _it == l._it;
    }
    ListIterator _it;
};

//list类
template
class my_list
{
    typedef ListNode Node;
    typedef Node* PNode;
public:
    typedef ListIterator iterator;
    //只有后面两个加上const是因为只有这里是控制const迭代器不能修改的地方
    typedef ListIterator const_iterator;

    typedef ReverseIterator reverse_itrator;
    typedef ReverseIterator const_reverse_itrator;
public:
    ///
    // List的构造
    my_list()
    {
        CreateHead();
    }
    my_list(int n, const T& value = T())
    {
        CreateHead();
        for (int i = 0; i < n; i++)
        {
            push_back(value);
        }
    }
    template 
    my_list(Iterator first, Iterator last)
    {
        CreateHead();
        while (first != last)
        {
            push_back(*first);
            first++;
        }
    }
    //lt1(lt2)                 lt2
    my_list(const my_list& l)
    {
        CreateHead();
        my_list tmp(l.begin(), l.end());
        this->swap(tmp);
    }
    my_list& operator=(my_list l)
    {
        this->swap(l);
        return *this;
    }
    ~my_list()
    {
        clear();
        delete _pHead;
        _pHead = nullptr;
    }
    ///
    // List Iterator
    iterator begin()
    {
        return iterator(_pHead->_pNext);
    }
    iterator end()
    {
        return iterator(_pHead);
    }
    const_iterator begin()const
    {
        return const_iterator(_pHead->_pNext);
    }
    const_iterator end()const
    {
        return const_iterator(_pHead);
    }

    // List Reversez_Iterator
    reverse_itrator rbegin()
    {
        return reverse_itrator(iterator);
    }
    reverse_itrator rend()
    {
        return reverse_itrator(iterator);
    }
    const_reverse_itrator crbegin()const
    {
        return const_reverse_itrator(const_iterator);
    }
    const_reverse_itrator crend()const
    {
        return const_reverse_itrator(const_iterator);
    }

    ///
    // List Capacity
    size_t size()const
    {
        size_t sz = 0;
        iterator it = begin();
        while (it != end())
        {
            sz++;
            it++;
        }
        return sz;
    }
    bool empty()const
    {
        return size() == 0;
    }
    
    // List Access
    T& front()
    {
        return _pHead->_pNext->_val;
    }
    const T& front()const
    {
        return _pHead->_pNext->_val;
    }
    T& back()
    {
        return _pHead->_pPre->_val;
    }
    const T& back()const
    {
        return _pHead->_pPre->_val;
    }
    
    // List Modify
    void push_back(const T& val) { insert(end(), val); }
    void pop_back() { erase(--end()); }
    void push_front(const T& val) { insert(begin(), val); }
    void pop_front() { erase(begin()); }
    // 在pos位置前插入值为val的节点
    iterator insert(iterator pos, const T& val)
    {
        //    prev  new  cur 
        Node* newnode = new Node(val);
        Node* cur = pos._pNode;
        Node* prev = cur->_pPre;

        prev->_pNext = newnode;
        newnode->_pPre = prev;
        newnode->_pNext = cur;
        cur->_pPre = newnode;

        //返回新插入的位置
        return iterator(newnode);
    }
    // 删除pos位置的节点，返回该节点的下一个位置
    iterator erase(iterator pos)
    {
        assert(pos != end());

        Node* cur = pos._pNode;
        Node* prev = cur->_pPre;
        Node* next = cur->_pNext;

        prev->_pNext = next;
        next->_pPre = prev;
        delete cur;
        //匿名对象
        return iterator(next);
    }
    void clear()
    {
        iterator it = begin();
        while (it != end())
        {
            it = erase(it);
            it++;
        }
    }
    void swap(my_list& l)
    {
        std::swap(_pHead, l._pHead);
    }
private:
    void CreateHead()
    {
        _pHead = new Node();
        _pHead->_pPre = _pHead;
        _pHead->_pNext = _pHead;
    }
    PNode _pHead;
};

最后的最后，创作不易，希望读者三连支持

赠人玫瑰，手有余香