欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)

 更新時(shí)間:2022年05月20日 09:16:40   作者:莓關(guān)系  
list相較于vector來(lái)說(shuō)會(huì)顯得復(fù)雜,它的好處是在任意位置插入,刪除都是一個(gè)O(1)的時(shí)間復(fù)雜度,下面這篇文章主要給大家介紹了關(guān)于C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下

一、list的介紹以及使用

1.1 list的介紹

1、list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器,并且該容器可以前后雙向迭代(所謂的常熟范圍內(nèi),就是時(shí)間復(fù)雜度為O(1))

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ī)訪問(wèn),比如:要訪問(wèn)list的第6個(gè)元素,必須從已知的位置(比如頭部或者尾部)迭代到該位置,在這段位置上迭代需要線性的時(shí)間開(kāi)銷(xiāo);list還需要一些額外的空間,以保存每個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)信息(對(duì)于存儲(chǔ)類(lèi)型較小元素的大list來(lái)說(shuō)這可能是一個(gè)重要的因素) 

這一段關(guān)于list的特性,需要能夠與vector對(duì)比理解。

1.2 list的使用

1.2.1 list的構(gòu)造

構(gòu)造函數(shù)( (constructor))接口說(shuō)明
list()構(gòu)造空的list
list (size_type n, const value_type& val = value_type())構(gòu)造的list中包含n個(gè)值為val的元素
list (const list& x)拷貝構(gòu)造函數(shù)
list (InputIterator first, InputIterator last)用[first, last)區(qū)間中的元素構(gòu)造list
#include <iostream>
#include <list>
using namespace std;
int main()
{
    std::list<int> l1; // 構(gòu)造空的l1
    std::list<int> l2(4, 100); // l2中放4個(gè)值為100的元素
    std::list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end())左閉右開(kāi)的區(qū)間構(gòu)造l3
    std::list<int> l4(l3); // 用l3拷貝構(gòu)造l4
    // 以數(shù)組為迭代器區(qū)間構(gòu)造l5
    int array[] = { 16,2,77,29 };
    std::list<int> l5(array, array + sizeof(array) / sizeof(int));
    // 用迭代器方式打印l5中的元素
    for (std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)
        std::cout << *it << " ";
    std::cout << endl;
    // C++11范圍for的方式遍歷
    for (auto& e : l5)
    {
        std::cout << e << " ";
    }
    std::cout << endl;
    return 0;
}

1.2.2 list iterator的使用

函數(shù)聲明接口說(shuō)明
begin +
end
返回第一個(gè)元素的迭代器+返回最后一個(gè)元素下一個(gè)位置的迭代器
rbegin +
rend
返回第一個(gè)元素的reverse_iterator,即end位置,返回最后一個(gè)元素下一個(gè)位置的reverse_iterator,即begin位置

注意:

1、begin與end為正向迭代器,對(duì)迭代器執(zhí)行++操作,迭代器向后移動(dòng)

2、rbegin(end)與rend(begin)為反向迭代器,對(duì)迭代器執(zhí)行++操作,迭代器向前移動(dòng)

#include <iostream>
#include <list>
using namespace std;
void print_list(const list<int>& l)
{
    // 注意這里調(diào)用的是list的 begin() const,返回list的const_iterator對(duì)象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
        // *it = 10; 編譯不通過(guò)
    }
    cout << endl;
}
int main()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
    // 使用反向迭代器逆向打印list中的元素
    for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

1.2.3 list capacity

函數(shù)聲明接口說(shuō)明
empty檢測(cè)list是否為空,是返回true,否則返回false
size返回list中有效節(jié)點(diǎn)的個(gè)數(shù)

1.2.4 list element access

函數(shù)聲明接口說(shuō)明
front返回list的第一個(gè)節(jié)點(diǎn)中值的引用
back返回list的最后一個(gè)節(jié)點(diǎn)中值的引用

1.2.5 list modifiers

函數(shù)聲明接口說(shuō)明
push_front在list首元素前插入值為val的元素
pop_front刪除list中第一個(gè)元素
push_back在list尾部插入值為val的元素
pop_back刪除list中最后一個(gè)元素
insert在list position 位置中插入值為val的元素
erase刪除list position位置的元素
swap交換兩個(gè)list中的元素
clear清空l(shuí)ist中的有效元素

這里就不用代碼的形式展示了

1.2.6 list的迭代器失效

前面說(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ì)受到影響

#include <iostream>
#include <list>
using namespace std;
void TestListIterator1()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函數(shù)執(zhí)行后,it所指向的節(jié)點(diǎn)已被刪除,因此it無(wú)效,在下一次使用it時(shí),必須先給其賦值
		l.erase(it);
		++it;
	}
}
// 改正
void TestListIterator()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++); // it = l.erase(it);
	}
}

二、list的模擬實(shí)現(xiàn)

2.1 模擬實(shí)現(xiàn)list

這是本章的重中之重。

#include <iostream>
#include <assert.h>
using std::cout;
using std::endl;
namespace zjx
{
	// 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>
	struct ListIterator
	{
		typedef ListNode<T>* PNode;
		typedef ListIterator<T, Ref, Ptr> Self;
	public:
		ListIterator(PNode pNode = nullptr)
		{
			_pNode = pNode;
		}
		//ListIterator(const Self& l);
 
		Ref operator*()
		{
			return _pNode->_val;
		}
 
		Ptr 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;
		}
 
	public:
		PNode _pNode;
	};
 
	//list類(lèi)
	template<class T>
	class list
	{
		typedef ListNode<T> Node;
 
		typedef Node* PNode;
 
	public:
 
		typedef ListIterator<T, T&, T*> iterator;
 
		typedef ListIterator<T, const T&, const T*> const_iterator;
 
	public:
 
		// List的構(gòu)造
 
		list()
		{
			_pHead = new Node();
			_pHead->_pNext = _pHead;
			_pHead->_pPre = _pHead;
		}
		//構(gòu)造函數(shù)
		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);
			}
		}
 
		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			_pHead = new Node();
			_pHead->_pNext = _pHead;
			_pHead->_pPre = _pHead;
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
 
		//拷貝構(gòu)造函數(shù)
		list(const list<T>& l)
		{
			//用迭代器先構(gòu)造出來(lái)一個(gè)
			list tmp(l.begin(), l.end());
			_pHead = new Node();
			_pHead->_pNext = _pHead;
			_pHead->_pPre = _pHead;
			std::swap(_pHead, tmp._pHead);
		}
 
		list<T>& operator=(list<T> l)
		{
			std::swap(_pHead, l._pHead);
			return *this;
		}
 
		~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 Capacity
		size_t size()const//這個(gè)函數(shù)右邊的const是用來(lái)限定this指針的。原本的this指針,不可以改變指向,可以改變所知的內(nèi)容。
						  //但若要對(duì)所指向的內(nèi)容加以限定的話,那就在函數(shù)的右邊加上const,表示此函數(shù)的隱藏的參數(shù),也就是this指針,被加以const限定。
		{
			size_t count = 0;
			const_iterator cur = begin();
			while (cur != end())
			{
				count++;
				cur++;
			}
			return count;
		}
		//list為空返回1,否則返回0
		bool empty()const
		{
			return size() == 0;
		}
 
		// List Access
 
		T& front()
		{
			return begin()._pNode->_val;
		}
 
		const T& front()const
		{
			return begin()._pNode->_val;
		}
 
		T& back()
		{
			return _pHead->_pPre->_val;
		}
 
		const T& back()const
		{
			return _pHead->_pPre->_val;
		}
 
		// List Modify
 
		//void push_back(const T& val) 
		//{ 
		//    insert(begin(), val); 
		//}
		void push_back(const T& val)
		{
			Node* tail = _pHead->_pPre;
			Node* newnode = new Node(val);
			tail->_pNext = newnode;
			newnode->_pPre = tail;
			newnode->_pNext = _pHead;
			_pHead->_pPre = newnode;
		}
 
		void pop_back()
		{
			erase(--end());
		}
 
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
 
		void pop_front()
		{
			erase(begin());
		}
 
		 在pos位置前插入值為val的節(jié)點(diǎn)
 
		iterator insert(iterator pos, const T& val)
		{
			PNode next = pos._pNode;
			PNode prev = next->_pPre;
			PNode newnode = new Node(val);
			newnode->_pNext = next;
			newnode->_pPre = prev;
			prev->_pNext = newnode;
			next->_pPre = newnode;
			return iterator(newnode);
		}
 
		 刪除pos位置的節(jié)點(diǎn),返回該節(jié)點(diǎn)的下一個(gè)位置
 
		iterator erase(iterator pos)
		{
			assert(pos != end());
			PNode next = pos._pNode->_pNext;
			PNode prev = pos._pNode->_pPre;
			delete pos._pNode;
			prev->_pNext = next;
			next->_pPre = prev;
			return iterator(next);
		}
 
		void clear()
		{
			iterator cur = begin();
			while (cur != end())
			{
				erase(cur++);
			}
			_pHead->_pNext = _pHead;
			_pHead->_pPre = _pHead;
		}
 
		//void swap(list<T>& l);
 
	private:
 
		void CreateHead()
		{
			_pHead = new Node();
			_pHead->_pNext = _pHead;
			_pHead->_pPre = _pHead;
		}
		PNode _pHead;
	};
 
};
class Date
{
private:
	int _year;
	int _month;
	int _day;
public:
	Date(int year = 0, int month = 0, int day = 0)
		:_year(year),
		_month(month),
		_day(day)
	{
	}
	void print()
	{
		std::cout << _year << " " << _month << " " << _day << std::endl;
	}
};
int main()
{
	using namespace zjx;
	list<Date> it;
	it.push_back(Date(2022, 5, 16));
	it.push_back(Date(2022, 5, 17));
	it.push_back(Date(2022, 5, 18));
	it.push_back(Date(2022, 5, 19));
	it.push_back(Date(2022, 5, 20));
	for (auto e : it)
	{
		e.print();
	}
	cout << endl;
	list<int> a1(5, 2);
	for (auto e : a1)
	{
		cout << e << " ";
	}
	cout << endl;
	list<Date> a2(it);
	for (auto e : a2)
	{
		e.print();
	}
	cout << endl;
	int arr[] = { 1,2,3,4,5,6,7,8,9 };
	list<int> a3(arr, arr + 9);
	for (auto e : a3)
	{
		cout << e << " ";
	}
	cout << endl;
	a1 = a3;
	for (auto e : a1)
	{
		cout << e << " ";
	}
	cout << endl;
 
	cout << "a3的元素的個(gè)數(shù) = " << a3.size() << endl;
 
	list<int> a4;
	cout << a4.empty() << endl;
	const auto ans1 = a3.front();
	auto ans2 = a3.back();
	cout << "ans1 = " << ans1 << " " << "ans2 = " << ans2 << endl;
	a3.push_front(30);
	a3.pop_back();
	a3.pop_front();
	a3.pop_front();
	for (auto e : a3)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

函數(shù)右邊的const是用來(lái)限定this指針的。原本的this指針,不可以改變指向,可以改變所知的內(nèi)容。

但若要對(duì)所指向的內(nèi)容加以限定的話,那就在函數(shù)的右邊加上const,表示此函數(shù)的隱藏的參數(shù),也就是this指針,被加以const限定。

vector缺陷:

連續(xù)的物理空間,是優(yōu)勢(shì),也是劣勢(shì)。優(yōu)勢(shì):支持高效隨機(jī)訪問(wèn)。

劣勢(shì):

1、空間不夠要增容,增容代價(jià)比較大。

2、可能存在一定空間浪費(fèi)。按需申請(qǐng),會(huì)導(dǎo)致頻繁增容,所以一般都會(huì)2倍左右擴(kuò)容。

3、頭部或者中部插入刪除需要挪動(dòng)數(shù)據(jù),效率低下list很好的解決vector的以上問(wèn)題:

1、按需申請(qǐng)釋放空間。

2、list任意位置支持O(1)插入刪除。

const對(duì)象會(huì)自動(dòng)找到const修飾的函數(shù)

總結(jié)

到此這篇關(guān)于C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ list講解內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++數(shù)據(jù)結(jié)構(gòu)之并查集詳解

    C++數(shù)據(jù)結(jié)構(gòu)之并查集詳解

    這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)之并查集詳解,并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相交集合的合并及查詢(xún)問(wèn)題,并查集的思想是用一個(gè)數(shù)組表示了整片森林,需要的朋友可以參考下
    2023-08-08
  • C++實(shí)現(xiàn)LeetCode(312.打氣球游戲)

    C++實(shí)現(xiàn)LeetCode(312.打氣球游戲)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(312.打氣球游戲),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C++多線程編程詳解

    C++多線程編程詳解

    這篇文章主要介紹了c語(yǔ)言多線程編程使用示例,小編覺(jué)得這篇文章寫(xiě)的還不錯(cuò),需要的朋友可以參考下,希望能夠給你帶來(lái)幫助
    2021-09-09
  • C++類(lèi)型轉(zhuǎn)換運(yùn)算符詳解

    C++類(lèi)型轉(zhuǎn)換運(yùn)算符詳解

    這篇文章主要介紹了C++類(lèi)型轉(zhuǎn)換運(yùn)算符的相關(guān)資料,希望通過(guò)本文大家能夠掌握這部分內(nèi)容,需要的朋友可以參考下,希望能夠給你帶來(lái)幫助
    2021-10-10
  • C語(yǔ)言三子棋一步步實(shí)現(xiàn)詳程

    C語(yǔ)言三子棋一步步實(shí)現(xiàn)詳程

    三子棋是一種民間傳統(tǒng)游戲,又叫九宮棋、圈圈叉叉、一條龍、井字棋等。將正方形對(duì)角線連起來(lái),相對(duì)兩邊依次擺上三個(gè)雙方棋子,只要將自己的三個(gè)棋子走成一條線,對(duì)方就算輸了,想用c語(yǔ)言做出這個(gè)游戲,事實(shí)上也是比較簡(jiǎn)單的,下面通過(guò)c語(yǔ)言進(jìn)行對(duì)五子棋的分析
    2022-02-02
  • C語(yǔ)言庫(kù)函數(shù)qsort的使用及模擬實(shí)現(xiàn)

    C語(yǔ)言庫(kù)函數(shù)qsort的使用及模擬實(shí)現(xiàn)

    這篇文章主要介紹了C語(yǔ)言庫(kù)函數(shù)qsort的使用及模擬實(shí)現(xiàn),文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的小伙伴可以參考一下
    2022-08-08
  • Qt實(shí)現(xiàn)字符串生成二維碼功能

    Qt實(shí)現(xiàn)字符串生成二維碼功能

    這篇文章主要介紹了如何利用Qt實(shí)現(xiàn)字符串生成二維碼功能,文中的實(shí)現(xiàn)過(guò)程講解詳細(xì),對(duì)我們學(xué)習(xí)Qt有一定的幫助,需要的可以參考一下
    2022-01-01
  • C語(yǔ)言編程動(dòng)態(tài)內(nèi)存分配常見(jiàn)錯(cuò)誤全面分析

    C語(yǔ)言編程動(dòng)態(tài)內(nèi)存分配常見(jiàn)錯(cuò)誤全面分析

    這篇文章主要介紹了C語(yǔ)言編程中動(dòng)態(tài)內(nèi)存分配的常見(jiàn)錯(cuò)誤全面分析講解,同樣遇到過(guò)C語(yǔ)言動(dòng)態(tài)內(nèi)存分配各種問(wèn)題的同學(xué)可以借鑒參考下,希望能夠有所幫助
    2021-10-10
  • C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之單鏈表操作詳解

    C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之單鏈表操作詳解

    鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文將和大家一起聊聊C語(yǔ)言中單鏈表的常用操作,感興趣的可以學(xué)習(xí)一下
    2022-07-07
  • QT5連接MySQL實(shí)現(xiàn)增刪改查

    QT5連接MySQL實(shí)現(xiàn)增刪改查

    這篇文章主要為大家詳細(xì)介紹了QT5如何連接MySQL實(shí)現(xiàn)增刪改查功能,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,感興趣的可以了解一下
    2022-12-12

最新評(píng)論