C++コンテナにおけるlistのまとめとその実現

list
Listは双方向先頭ループチェーンテーブルであり、いくつかのノードからなり、各ノードにはデータブロック、前駆ポインタ、および後駆動ポインタが含まれている.listは非連続空間に格納されるためvectorに比べてlistのランダム検索能力は弱く,検索時間の複雑度はO(n)である.メリット:

挿入、要素削除のコストが小さい

は両端で動作可能

である.

連続したメモリ領域を必要としない欠点:

ランダムアクセスはサポートされていません[]、at

メモリ消費量

関連使用関数:

push_back				  
pop_back				  
push_front				  
pop_front				  
erase					        
insert					        
clear					  list
size					    
resize					        
swap					      
emplace_front			  （      ）
emplace_back			  （      ）
splice					  list
unique					  
sort					  （      ）
merge					     
reverse					  

具体的にはhttp://www.cplusplus.com/reference/list/list/
List反復器の実装:オリジナルポインタでカプセル化し、カスタムクラスを生成します.

template           //  
struct ListNode{
    ListNode(const T& val = T())
    :_val(val)
    ,_pre(nullptr)
    ,_next(nullptr)
    {}
    T _val;
    ListNode* _pre;
    ListNode* _next;
};

template			//  iterator 
class _ListIterator{
public:  
    typedef ListNode Node;
    typedef _ListIterator Self;    		//Pre  T& 	Arc T*
public:
    Node* _node;
    _ListIterator(Node* node)
    :_node(node)
    {
    }
    Arc operator*()						//           
    {
        return _node->_val;
    }

    Pre operator->()					//    ->         
    {
        return &(_node->_val);
    }

    Self& operator++()          //  ++
    {
        _node = _node->_next;
        return *this;
    }
    
    Self operator++(int)       //  ++
    {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    
    Self& operator--()
    {
        _node= _node->_pre;
        return *this;
    }

    Self operator--(int)
    {
        Self tmp(*this);
        _node = _node->_pre;
        return tmp;
    }
    Self& operator+(size_t n)
    {
        for(int i =0; i_next;
        }
        return *this;
    }
    bool operator!=(const Self& l)
    {
        return _node!=l._node;
    }

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

Listの一部の機能の実現:

template
class List{
    typedef ListNode Node;
public:    
    typedef _ListIterator iterator;
    typedef _ListIterator const_iterator;

    List()
    :_head(new Node)
    {
        _head->_next = _head;
        _head->_pre = _head;
    }
    

    ~List()
    {
        if(_head)
        {
            Clear();
            delete _head;
            _head = nullptr;
        }
    }

    List(List& l)				//    	   
    {
        _head = new Node;
        _head->_next = _head;
        _head->_pre = _head;
        for(auto&e : l)
        {
            PushBack(e);
        }
    }

    List& operator=(const List l)         //          
    {
        swap(_head,l._head);
        return *this;  
    }

    void Clear()												//  
    {
        if(_head)
        {
            Node* cur = _head->_next;
            while(cur != _head)
            {
                Node* next =cur->_next;
                delete cur;
                cur = next;
            }
            _head->_next = _head;
            _head->_pre = _head;   
        }
    }

    void PushBack(const T& val)					//  
    {
        Node* cur = new Node(val);  
        Node* pre = _head->_pre;

        cur->_pre = pre;
        cur->_next = _head;
        pre->_next = cur;
        _head->_pre = cur;
    }

 	void PopBack()								//  
	{
        Node* cur = _head->_pre;
        cur->_pre->_next = _head;
        _head->_pre = cur->_pre;
        delete cur;
    }

	void PushFront(const T& val)			//  
	{
        Node* cur = new Node(val);
        Node* next = _head->_next;
        next->_pre = cur;
        cur->_next = next;
        cur->_pre = _head;
        _head->_next = cur;
    }

	void PopFront()						//  
	{
        Node* cur = _head->_next;
        cur->_next->_pre = _head;
        _head->_next = cur->_next;
        delete cur;
    }  

    void Insert(iterator pos, const T& val)				//       
    {
        Node* cur = new Node(val);
        Node* _pos = pos._node;

        _pos->_pre->_next = cur;
        cur->_pre = _pos->_pre;
        cur->_next = _pos;
        _pos->_pre = cur;

    }
    //       
    iterator Erase(iterator pos)
	{
		if (pos != end())
		{
			Node* cur = pos._node;
			Node* prev = cur->_pre;
			Node* next = cur->_next;

			prev->_next = next;
			next->_pre = prev;

			delete cur;
			cur = nullptr;
			pos = iterator(next);
		}

		return pos;
		
	}
    iterator begin()				//     
    {
        return iterator(_head->_next);
    }
    iterator end()
    {
        return iterator(_head);
    }
    const_iterator begin()const	//const   
    {
        return const_iterator(_head->_next);
    }
    const_iterator end()const
    {
        return const_iterator(_head);
    }

    bool Empty()
    {
        return _head==_head->_next;
    }

    size_t Size()
    {
        size_t sz = 0;
        Node *cur = _head->_next;
        while(cur != _head)
        {
            sz++;
            cur = cur->_next;
        }
        return sz;
    }
    void Resize(size_t num, const T& val = T())
    {
        size_t sz = Size();
        if(sz<=num)
        {
            for(int i =sz; i_next->_val;
    }
    T& Back()						//          
    {
        return _head->_pre->_val;
    }
    const T& Front()const
    {
        return _head->_next->_val;
    }
    const T& Back()const
    {
        return _head->_pre->_val;
    }
private:
    Node* _head;
};

一部の機能は後でさらに実現する時間があります.