真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

C++——模擬實現(xiàn)list-創(chuàng)新互聯(lián)

目錄

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比雜多網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式雜多網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋雜多地區(qū)。費用合理售后完善，10年實體公司更值得信賴。

1.鏈表節(jié)點的構(gòu)建

2.迭代器的初步實現(xiàn)

3.成員變量以及默認構(gòu)造

4.普通迭代器接口

5.插入接口

6.刪除與find接口

7.const迭代器實現(xiàn)與接口

8.范圍拷貝與拷貝構(gòu)造

9.如果實例化參數(shù)是自定義類型

10.析構(gòu)函數(shù)

11.完整代碼

1.鏈表節(jié)點的構(gòu)建

鏈表的節(jié)點有指針與和數(shù)據(jù)域，所以無法用任何一個內(nèi)置類型來表示它，我們需要自定義好節(jié)點的類型。list容器使用的是帶頭雙向循環(huán)鏈表。

templatestruct list_node		//節(jié)點類型
	{
		list_node* _next;
		list_node* _prev;
		T _val;
		list_node(const T& val = T()) 
			:_val(val)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
2.迭代器的初步實現(xiàn)

鏈表的節(jié)點所占用的內(nèi)存空間是不連續(xù)的，所以不能使用原生指針來代替迭代器。我們需要自定義迭代器的行為(例如++是從前一個節(jié)點移動到后一個節(jié)點)。

templatestruct list_iterator
	{
		typedef list_nodenode;
		node* pnode;
		
		list_iterator(node* p)
			:pnode(p)
		{}

		list_iterator& operator++()
		{
			pnode = pnode->_next;
			return *this;
		}

		bool operator!=(list_iterator& lt)
		{
			return pnode != lt.pnode;
		}
	};
3.成員變量以及默認構(gòu)造

定義空容器時，容器是存在頭節(jié)點(哨兵衛(wèi))的。

templateclass list
	{
	public:
		typedef list_nodenode;
		typedef list_iteratoriterator;

		void empty_init()
		{
			_head = new node(T());		//哨兵衛(wèi)
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();		//復(fù)用
		}

	private:
		node* _head;
		size_t size;		//記錄有節(jié)點個數(shù)(除哨兵衛(wèi))
	};
4.普通迭代器接口
iterator begin()
{
	return iterator(_head->_next);
}
iterator end()
{
	return iterator(_head);		//尾后迭代器
}
5.插入接口

插入有頭插、尾插、隨機插。我們重點實現(xiàn)隨機插，頭插和尾插復(fù)用隨機插。

void push_back(const T& val)
{
	insert(end(), val);		//在哨兵衛(wèi)頭插就是尾插
}

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

iterator insert(iterator pos, const T& val)
{
	node* newnode = new node(val);
	node* prev = pos.pnode->_prev;

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = pos.pnode;
	pos.pnode->_prev = newnode;
			
	++_size;
	return iterator(newnode);		//返回插入節(jié)點的位置(防止迭代器失效)
}
6.刪除與find接口

刪除有頭刪、尾刪、隨機刪。我們重點實現(xiàn)隨機刪，頭刪和尾刪復(fù)用隨機刪。

void pop_back()
{
	erase(end().pnode->_prev);
}
		
void pop_front()
{
	erase(begin());
}

iterator erase(iterator pos)
{
	assert(end() != pos);		//不能刪除哨兵衛(wèi)
			
	node* prev = pos.pnode->_prev;
	node* next = pos.pnode->_next;

	prev->_next = next;
	next->_prev = prev;

	delete pos.pnode;
	--_size;
	return iterator(next);		//返回刪除節(jié)點的下一個節(jié)點位置(防止迭代器失效)
			
}

iterator find(iterator first, iterator last, const T& val)
{
	assert(first != last);
	while (first != last)
	{
		if (*first == val) return first;
		++first;
	}
	return end();
}
7.const迭代器實現(xiàn)與接口

不能使用const成員函數(shù)重載，因為我們要的效果是底層const而非頂層const(即指向的內(nèi)容不可變，迭代器本身可變)。所以我們有兩套方案，一是再構(gòu)建一個迭代器類模板；二是在原來的迭代器模板基礎(chǔ)上添加一個模板參數(shù)。再構(gòu)建一個迭代器的方案與原模板的唯一區(qū)別就是返回值不同。所以否決第一套設(shè)計方案。

現(xiàn)在先統(tǒng)一一下迭代器接口：

typedef list_iteratoriterator;
typedef list_iteratorconst_iterator;

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

迭代器設(shè)計：

template//多使用一個模板參數(shù)
struct list_iterator
{
	typedef list_nodenode;
	typedef list_iteratorself;		//為了方便
	node* pnode;
		
	list_iterator(node* p)
		:pnode(p)
	{}

	ref operator*()
	{
		return pnode->_val;
	}

	self& operator++()
	{
		pnode = pnode->_next;
		return *this;
	}

	bool operator!=(self& lt)
	{
		return pnode != lt.pnode;
	}
};
8.范圍拷貝與拷貝構(gòu)造

我們實現(xiàn)更加全面的構(gòu)造接口。

templatelist(InputIterator first, InputIterator last)		//范圍拷貝
{
	empty_init();
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}
		
void swap(list& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}
list(const list& lt)		//拷貝構(gòu)造現(xiàn)代寫法
{
	empty_init();
	listtmp(lt.begin(), lt.end());
	swap(tmp);
}

list& operator=(listlt)		//賦值運算符重載現(xiàn)代寫法
{
	swap(lt);
	return *this;
}
9.如果實例化參數(shù)是自定義類型

如果鏈表的節(jié)點是一個自定義類型，那么使用 * 將無法讀取自定義類型的數(shù)據(jù)。所以我們需要完善訪問自定義類型成員的功能，即 ->運算符重載。此重載函數(shù)的返回值是實例化參數(shù)類型的指針，這個指針也有const與非const之分，并且調(diào)用此重載的對象可能是const或非const對象，也就是說迭代器可能是const迭代器與非const迭代器。那么我們依然為迭代器模板添加一個參數(shù)，并且完善迭代器的功能。

別忘了對迭代器的重命名需要更新一下：

typedef list_iteratoriterator;
typedef list_iteratorconst_iterator;
template//多使用一個模板參數(shù)
struct list_iterator
{
	typedef list_nodenode;
	typedef list_iteratorself;		
	node* pnode;
		
	list_iterator(node* p)
		:pnode(p)
	{}

	ref operator*()
	{
		return pnode->_val;
	}

	ptr operator->()
	{
		return &pnode->_val;
	}

	self& operator++()
	{
		pnode = pnode->_next;
		return *this;
	}

	self operator++(int)		//后置++
	{
		node* tmp(pnode);
		pnode = pnode->_next;
		return tmp;
	}

	self& operator--()
	{
		pnode = pnode->_prev;
		return *this;
	}

	self operator--(int)		//后置--
	{
		node* tmp(pnode);
		pnode = pnode->_prev;
		return tmp;
	}

	bool operator!=(const self& lt)
	{
		return pnode != lt.pnode;
	}

	bool operator==(const self& lt)
	{
		return pnode == lt.pnode;
	}
};
10.析構(gòu)函數(shù)

釋放分為兩個部分，一是不釋放哨兵衛(wèi)，將有效節(jié)點釋放；而是全部釋放。我們實現(xiàn)一個clear接口，讓析構(gòu)復(fù)用此接口。

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

void clear()
{
	auto it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
11.完整代碼

這里只實現(xiàn)了list容器常用的接口，并沒有完全依照標準庫1：1模擬實現(xiàn)。代碼會有很多細節(jié)沒有處理好，并不是會報錯，而是有些地方顯得不夠嚴謹。

#include 
#include 
namespace ly
{
	templatestruct list_node		//節(jié)點類型
	{
		list_node* _next;
		list_node* _prev;
		T _val;
		list_node(const T& val = T()) 
			:_val(val)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};

template//多使用一個模板參數(shù)
struct list_iterator
{
	typedef list_nodenode;
	typedef list_iteratorself;		
	node* pnode;
		
	list_iterator(node* p)
		:pnode(p)
	{}

	ref operator*()
	{
		return pnode->_val;
	}

	ptr operator->()
	{
		return &pnode->_val;
	}

	self& operator++()
	{
		pnode = pnode->_next;
		return *this;
	}

	self operator++(int)		//后置++
	{
		node* tmp(pnode);
		pnode = pnode->_next;
		return tmp;
	}

	self& operator--()
	{
		pnode = pnode->_prev;
		return *this;
	}

	self operator--(int)		//后置--
	{
		node* tmp(pnode);
		pnode = pnode->_prev;
		return tmp;
	}

	bool operator!=(const self& lt)
	{
		return pnode != lt.pnode;
	}

	bool operator==(const self& lt)
	{
		return pnode == lt.pnode;
	}
};

	templateclass list
	{
	public:
		typedef list_nodenode;
		typedef list_iteratoriterator;
		typedef list_iteratorconst_iterator;

		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);		//尾后迭代器
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}

		void empty_init()
		{
			_head = new node(T());		//哨兵衛(wèi)
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();		//復(fù)用
		}

		templatelist(InputIterator first, InputIterator last)		//范圍拷貝
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		
		void swap(list& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list(const list& lt)		//拷貝構(gòu)造現(xiàn)代寫法
		{
			empty_init();
			listtmp(lt.begin(), lt.end());
			swap(tmp);
		}

		list& operator=(listlt)		//賦值運算符重載現(xiàn)代寫法
		{
			swap(lt);
			return *this;
		}


		void pop_back()
		{
			erase(end().pnode->_prev);
		}
		
		void pop_front()
		{
			erase(begin());
		}

		iterator erase(iterator pos)
		{
			assert(end() != pos);		//不能刪除哨兵衛(wèi)
			
			node* prev = pos.pnode->_prev;
			node* next = pos.pnode->_next;

			prev->_next = next;
			next->_prev = prev;

            delete pos.pnode;
			--_size;
			return iterator(next);		//返回刪除節(jié)點的下一個節(jié)點位置(防止迭代器失效)
			
		}

		iterator find(iterator first, iterator last, const T& val)
		{
			assert(first != last);
			while (first != last)
			{
				if (*first == val) return first;
				++first;
			}
			return end();
		}


		void push_back(const T& val)
		{
			insert(end(), val);		//在哨兵衛(wèi)頭插就是尾插
		}

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

		iterator insert(iterator pos, const T& val)
		{
			node* newnode = new node(val);
			node* prev = pos.pnode->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = pos.pnode;
			pos.pnode->_prev = newnode;
			
			++_size;
			return iterator(newnode);		//返回插入節(jié)點的位置(防止迭代器失效)
		}



	private:
		node* _head;
		size_t _size;		//記錄有節(jié)點個數(shù)(除哨兵衛(wèi))
	};
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧


當前名稱：C++——模擬實現(xiàn)list-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://weahome.cn/article/pcioh.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部