一、list使用介紹

1. ?list的底層是帶頭雙向鏈表結(jié)構(gòu)，雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過(guò)指針指向其前一個(gè)元素和后一個(gè)元素。
2. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率更好
3. list最大的缺陷是不支持任意位置的隨機(jī)訪問(wèn)，比如：要訪問(wèn)list的第6個(gè)元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時(shí)間開(kāi)銷；

常用接口：

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

代碼演示：

    list<int> l1;                         // 構(gòu)造空的l1
    list<int> l2(4, 100);                 // l2中放4個(gè)值為100的元素
    list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左閉右開(kāi)的區(qū)間構(gòu)造l3
    list<int> l4(l3);                    // 用l3拷貝構(gòu)造l4

    // 以數(shù)組為迭代器區(qū)間構(gòu)造l5
    int array[] = { 16,2,77,29 };
    list<int> l5(array, array + sizeof(array) / sizeof(int));

    // 列表格式初始化C++11
    list<int> l6{ 1,2,3,4,5 };

list iterator的使用

對(duì)于迭代器的使用我們可以把它理解為一個(gè)指針，指向ist的某個(gè)節(jié)點(diǎn)

【注意】
1. begin與end為正向迭代器，對(duì)迭代器執(zhí)行++操作，迭代器向后移動(dòng)
2. rbegin(end)與rend(begin)為反向迭代器，對(duì)迭代器執(zhí)行++操作，迭代器向前移動(dòng)

代碼演示：

    list<int> lt(4, 100);  
    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        ++it;
    }       
    cout << endl;

    // C++11范圍for的方式遍歷
    for (auto& e : lt)
        cout << e << " ";
     cout << endl;

list modi?ers

代碼演示：

void TestList1()
{
    int array[] = { 1, 2, 3 };
    list<int> L(array, array + sizeof(array) / sizeof(array[0]));

    // 在list的尾部插入4，頭部插入0
    L.push_back(4);
    L.push_front(0);

    // 刪除list尾部節(jié)點(diǎn)和頭部節(jié)點(diǎn)
    L.pop_back();
    L.pop_front();
}

// insert /erase 
void TestList2()
{
    int array1[] = { 1, 2, 3 };
    list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

    // 獲取鏈表中第二個(gè)節(jié)點(diǎn)
    auto pos = ++L.begin();
    cout << *pos << endl;

    // 在pos前插入值為4的元素
    L.insert(pos, 4);

    // 在pos前插入5個(gè)值為5的元素
    L.insert(pos, 5, 5);

    // 在pos前插入[v.begin(), v.end)區(qū)間中的元素
    vector<int> v{ 7, 8, 9 };
    L.insert(pos, v.begin(), v.end());

    // 刪除pos位置上的元素
    L.erase(pos);

    // 刪除list中[begin, end)區(qū)間中的元素，即刪除list中的所有元素
    L.erase(L.begin(), L.end());
}

// resize/swap/clear
void TestList3()
{
    // 用數(shù)組來(lái)構(gòu)造list
    int array1[] = { 1, 2, 3 };
    list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));

    // 交換l1和l2中的元素
    list<int> l2;
    l1.swap(l2);

    // 將l2中的元素清空
    l2.clear();
    cout << l2.size() << endl;
}

其他接口

二、與vector對(duì)比

vector與list排序效率對(duì)比：

void test_op1()
{
	srand(time(0));
	const int N = 1000000;

	list<int> lt1;
	list<int> lt2;

	vector<int> v;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		lt1.push_back(e);
		v.push_back(e);
	}

	int begin1 = clock();
	// 
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

?

void test_op2()
{
	srand(time(0));
	const int N = 1000000;

	list<int> lt1;
	list<int> lt2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		lt1.push_back(e);
		lt2.push_back(e);
	}

	int begin1 = clock();
	// vector

	vector<int> v(lt2.begin(), lt2.end());
	// 
	sort(v.begin(), v.end());

	// lt2
	lt2.assign(v.begin(), v.end());

	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

可見(jiàn)list的排序效率是非常低的，甚至將list的數(shù)據(jù)導(dǎo)入vector中排完序在導(dǎo)回來(lái)的效率都比直接在list中排序的效率快，這是因?yàn)閘ist不支持下標(biāo)隨機(jī)訪問(wèn)，只能依靠迭代器迭代到指定位置訪問(wèn)，而排序過(guò)程中避免不了需要訪問(wèn)大量中間元素，所以list并不適合對(duì)數(shù)據(jù)進(jìn)行排序

三、list迭代器問(wèn)題

鏈表節(jié)點(diǎn)與鏈表結(jié)構(gòu)

節(jié)點(diǎn)包含三部分：前驅(qū)指針、后驅(qū)指針、數(shù)據(jù)。list封裝了頭節(jié)點(diǎn)的指針，可以根據(jù)該指針對(duì)后續(xù)節(jié)點(diǎn)進(jìn)行遍歷

    template<class T>
	struct ListNode
	{
		ListNode* _next;
		ListNode* _prev;
		T _data;
        //節(jié)點(diǎn)的構(gòu)造函數(shù)
		ListNode(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

    template<class T>
	class list
	{
        void Empty_Init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		//構(gòu)造函數(shù)
		list()
		{
			Empty_Init();
		}

	private:
		Node* _head;
		size_t _size;
	};

如何設(shè)定list迭代器

????????在string與vector的模擬實(shí)現(xiàn)中，迭代器使用的都是原生指針T*，這是因?yàn)樵羔樋梢詽M足迭代器的要求，++可以指向下一個(gè)元素，解引用可以訪問(wèn)該元素，他們可以使用原生指針的根本原因是他們儲(chǔ)存數(shù)據(jù)的結(jié)構(gòu)都是連續(xù)的物理地址。

? ? ? ? 在list中原生指針Node*不能滿足我們的要求，因?yàn)閘ist的節(jié)點(diǎn)都是依靠指針連接起來(lái)的，其物理地址并不是連續(xù)的，++指向的并不是下一個(gè)元素，而是指向了跳過(guò)了一個(gè)Node的大小的的地址，并且迭代器希望解引用直接可以訪問(wèn)節(jié)點(diǎn)中的數(shù)據(jù)，而*（Node*）卻是一個(gè)節(jié)點(diǎn)類型，所以在list中使用原生指針并不符合迭代器的要求。

? ? ? ? ?所以我們可以自己新建一個(gè)類，作為迭代器的類型，在其中封裝了頭節(jié)點(diǎn)，就可以訪問(wèn)該鏈表了，并且我們?cè)谠擃愔锌梢酝ㄟ^(guò)運(yùn)算符重載改變++與解引用的行為，這樣就可以使用迭代器訪問(wèn)鏈表數(shù)據(jù)了

    template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T> Self;

		Node* _node;
		ListIterator(Node* _node)
			:_node(_node)
		{}

		T& operator*()
		{
			return _node->_data;
		}

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

	};
    
    template<class T>
	class list
	{
        void Empty_Init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
    
		//構(gòu)造函數(shù)
		list()
		{
			Empty_Init();
		}
        
        iterator begin()
		{
			//隱式類型轉(zhuǎn)換
			return _head->_next;
		}

		iterator end()
		{
			//隱式類型轉(zhuǎn)換
			return _head;
		}
	private:
		Node* _head;
		size_t _size;
	};

完善迭代器功能??

operator->的重載

????????但是上述代碼具有一定的局限性，例如當(dāng)T為一個(gè)結(jié)構(gòu)體A時(shí)，*iterator返回的是結(jié)構(gòu)體A，想要訪問(wèn)結(jié)構(gòu)體中的數(shù)據(jù)還需要用 .?例如：*(it).a1，但是這樣寫(xiě)有點(diǎn)多次一舉，因?yàn)榈鱥t本身就是指向節(jié)點(diǎn)的指針，訪問(wèn)數(shù)據(jù)可以直接使用 ->,例如：it->a1,所以我們還需要將->重載一下

  T* operator->()
 {
    //返回?cái)?shù)據(jù)的地址
	return &_node->_data;
 }

結(jié)構(gòu)體Ａ存儲(chǔ)在節(jié)點(diǎn)的＿data中，這里返回了＿data的地址，如果按照正常的思路進(jìn)行訪問(wèn)，應(yīng)該按照如下的方式：it.operator->()->_a1?應(yīng)該是兩個(gè)箭頭，第一個(gè)箭頭代表運(yùn)算符的重載，第二個(gè)代表指針解引用訪問(wèn)數(shù)據(jù)。
但是編譯器為了方便查看會(huì)進(jìn)行優(yōu)化，將兩個(gè)箭頭變成了一個(gè)箭頭 it->_a1?，這樣直接可以訪問(wèn)

const迭代器

const的本質(zhì)就是為了禁止對(duì)成員進(jìn)行修改，所以我們只需要const迭代器只需要對(duì)非const迭代器稍加修改即可

    template<class T>
	struct ListConstIterator
	{
		typedef ListNode<T> Node;
		typedef ListConstIterator<T> Self;

		Node* _node;
		ListConstIterator(Node* _node)
			:_node(_node)
		{}

		const T& operator*()
		{
			return _node->_data;
		}

		const T* operator->()
		{
			return &_node->_data;
		}

	};

但是這樣const迭代器與非const迭代器這兩個(gè)類的重合度非常高，僅僅是函數(shù)返回值前是否加用const修飾的區(qū)別，所以我們可以利用模板文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-852450.html

    typedef ListIterator<T,T&,T*> iterator;
    typedef ListIterator<T,const T&,const T*> const_iterator;
    ---------------------------------
    template<class T,class Ref,class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;

		Node* _node;
		ListIterator(Node* _node)
			:_node(_node)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}
		//前置++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(_node);
			_node = _node->_next;
			return tmp;
		}
	};

完整代碼：

#include<iostream>
using namespace std;
namespace zyq
{
	template<class T>
	struct ListNode
	{
		ListNode* _next;
		ListNode* _prev;
		T _data;

		ListNode(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

	//template<class T>
	//struct ListIterator
	//{
	//	typedef ListNode<T> Node;
	//	typedef ListIterator<T> Self;

	//	Node* _node;
	//	ListIterator(Node* _node)
	//		:_node(_node)
	//	{}

	//	T& operator*()
	//	{
	//		return _node->_data;
	//	}

	//     T* operator->()
	//	{
	//		return &_node->_data;
	//	}

	//	//前置++
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}

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

	//	bool operator!=(const Self& it)
	//	{
	//		return !(_node == it._node);
	//	}

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

	//};

	//template<class T>
	//struct ListConstIterator
	//{
	//	typedef ListNode<T> Node;
	//	typedef ListConstIterator<T> Self;

	//	Node* _node;
	//	ListConstIterator(Node* _node)
	//		:_node(_node)
	//	{}

	//	const T& operator*()
	//	{
	//		return _node->_data;
	//	}

	//	const T* operator->()
	//	{
	//		return &_node->_data;
	//	}

	//	//前置++
	//	 Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}

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

	//	bool operator!=(const Self& it)
	//	{
	//		return !(_node == it._node);
	//	}

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

	template<class T,class Ref,class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;

		Node* _node;
		ListIterator(Node* _node)
			:_node(_node)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}
		//前置++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(_node);
			_node = _node->_next;
			return tmp;
		}

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

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

	};
	template<class T>
	class list
	{
	public:
		typedef ListNode<T> Node;
		//typedef ListIterator<T> iterator;
		//typedef ListConstIterator<T> const_iterator;
		typedef ListIterator<T,T&,T*> iterator;
		typedef ListIterator<T,const T&,const T*> const_iterator;

		iterator begin()
		{
			//隱式類型轉(zhuǎn)換
			return _head->_next;
		}

		iterator end()
		{
			//隱式類型轉(zhuǎn)換
			return _head;
		}

		const_iterator begin() const
		{
			//隱式類型轉(zhuǎn)換
			return _head->_next;
		}

		const_iterator end() const
		{
			//隱式類型轉(zhuǎn)換
			return _head;
		}

		void Empty_Init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		//構(gòu)造函數(shù)
		list()
		{
			Empty_Init();
		}

		//拷貝構(gòu)造
		list(const list<T>& lt)
		{
			Empty_Init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

		void swap(list<T> lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		//賦值運(yùn)算符重載
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		~list()
		{
			iterator it = begin();
			while (it != end())
			{
				it=erase(it);
			}
			delete _head;
			_head = nullptr;
		}

		size_t size()
		{
			return _size;
		}

		/*void push_back(const T& x)
		{
			Node* newnode = new Node(x);
			Node* tail = _head->_prev;

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
			_size++;
		}*/

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

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

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

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

		void insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			_size++;
		}

		iterator erase(iterator pos)
		{
			Node* prev = pos._node->_prev;
			Node* next = pos._node->_next;
			prev->_next = next;
			next->_prev = prev;
			delete pos._node;
			_size--;
			return next;
		}

	private:
		Node* _head;
		size_t _size;
	};

	template<class T>
	void PrintList(const list<T>& clt)
	{
		typename list<T>::const_iterator it = clt.begin();
		while (it != clt.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}

	void testlist1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
		/*lt.push_back(9);
		lt.pop_front();*/
		PrintList(lt);
		list<int> lt1(lt);
		PrintList(lt1);
		list<int> lt2;
		lt2 = lt;
		PrintList(lt2);
	}

	struct A
	{
		int _a1;
		int _a2;
		A(int a1 = 0, int a2 = 0)
			:_a1(a1)
			, _a2(a2)
		{}
	};

	void testlist2()
	{
		list<A> lt;
		lt.push_back({ 1,2 });
		lt.push_back(A(1,2));
		list<A>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._a1 << " " << (*it)._a2 << " ";
			cout << it->_a1 << " " << it->_a2 << " ";
			it++;
		}
		cout << endl;
	}
}

到了這里，關(guān)于[STL-list]介紹、與vector的對(duì)比、模擬實(shí)現(xiàn)的迭代器問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！