日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

利用C++模擬實(shí)現(xiàn)STL容器:list_C 語言

作者：蔣靈瑜的筆記本 ? 更新時(shí)間： 2023-01-03 編程語言

一、list的介紹

列表是一種順序容器，它允許在序列中的任何位置執(zhí)行常量時(shí)間插入和刪除操作，并允許在兩個(gè)方向上進(jìn)行迭代。

它的底層是一個(gè)帶頭雙向循環(huán)鏈表。附一篇博主用C語言寫的帶頭雙向循環(huán)鏈表：【數(shù)據(jù)結(jié)構(gòu)】帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

二、list的排序

list不能用算法庫的sort進(jìn)行排序。算法庫中的sort的底層是一個(gè)快排，需滿足三數(shù)取中，需要傳入隨機(jī)訪問迭代器，所以list并不適用。

當(dāng)然list中提供了一個(gè)自己的sort，它的底層是一個(gè)歸并排序。但是這個(gè)sort比vector使用算法庫的sort還慢，甚至比list的數(shù)據(jù)先push_back到vector到再用算法庫的sort還要慢。

三、迭代器

1、list的迭代器失效問題

insert，迭代器不失效

earse失效

2、迭代器的功能分類

1、單向迭代器：只能++，不能--。例如單鏈表，哈希表；

2、雙向迭代器：既能++也能--。例如雙向鏈表；

3、隨機(jī)訪問迭代器：能++--，也能+和-。例如vector和string。

迭代器是內(nèi)嵌類型（內(nèi)部類或定義在類里）

3、list迭代器的模擬實(shí)現(xiàn)

普通迭代器

迭代器的實(shí)現(xiàn)需要支持解引用（為了取數(shù)據(jù)），支持++--。

博主模擬實(shí)現(xiàn)string和vector時(shí)，直接將原生指針typedef成迭代器，是因?yàn)閿?shù)組的結(jié)構(gòu)正好滿足迭代器的行為（注：string和vector可以用原生指針實(shí)現(xiàn)，但是vs中采用自定義類型封裝的方式實(shí)現(xiàn)），但是list中的節(jié)點(diǎn)地址是不連續(xù)的，不能使用原生指針，需要使用類進(jìn)行封裝+運(yùn)算符重載實(shí)現(xiàn)。

//用類封裝迭代器
template <class T>
struct __list_iterator
{
    typedef list_node<T> node;
    //用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造
    __list_iterator(node* p)
        :_pnode(p)
    {}
    //迭代器運(yùn)算符的重載
    T& operator*()
    {
        return _pnode->_data;
    }
    __list_iterator<T>& operator++()//返回值不要寫成node* operator++()，因?yàn)榈?+肯定返回迭代器啊，你返回節(jié)點(diǎn)指針類型不對(duì)
    { 
        //return _pnode->_next;
        _pnode=_pnode->_next;
        return *this;//返回的是迭代器
    }
    bool operator!=(const __list_iterator<T>& it)
    {
        return _pnode != it._pnode;
    }
public:
    node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針
};

const迭代器

const迭代器的錯(cuò)誤寫法：

typedef __list_iterator<T> iterator;
const list<T>::iterator it=lt.begin();

因?yàn)閠ypedef后，const修飾的是迭代器it，只能調(diào)用operator*(),調(diào)不了operator++()。（重載operator++()為const operator++()也不行,因?yàn)閏onst版本++還是改變不了）

正確寫法：想實(shí)現(xiàn)const迭代器，不能在同一個(gè)類里面動(dòng)腦筋，需要再寫一個(gè)const版本迭代器的類。

//用類封裝const迭代器
template <class T>
struct __list_const_iterator
{
    typedef list_node<T> node;
    //用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造
    __list_const_iterator(node* p)
        :_pnode(p)
    {}
    //迭代器運(yùn)算符的重載
    const T& operator*()const
    {
        return _pnode->_data;
    }
    __list_const_iterator<T>& operator++()//返回值不要寫成node*，因?yàn)榈?+肯定返回迭代器啊，你返回節(jié)點(diǎn)指針類型不對(duì)
    {
        //return _pnode->_next;//返回類型錯(cuò)誤的
        _pnode = _pnode->_next;
        return *this;//返回的是迭代器
    }
    __list_const_iterator<T>& operator--()
    {
        _pnode = _pnode->_prev;
        return *this;
    }
    bool operator!=(const __list_const_iterator<T>& it)const
    {
        return _pnode != it._pnode;
    }
public:
    node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針
};
 
typedef __list_const_iterator<T> const_iterator;

當(dāng)然，這樣寫__list_iterator和__list_const_iterator這兩個(gè)類會(huì)出現(xiàn)代碼重復(fù)。STL庫中是通過類模板多給一個(gè)參數(shù)來實(shí)現(xiàn)，這樣，同一份類模板就可以生成兩種不同的類型的迭代器（以下為仿STL庫的模擬實(shí)現(xiàn)）：?

//用類封裝普通/const迭代器
template <class T,class Ref>
struct __list_iterator
{
    typedef list_node<T> node;
    typedef __list_iterator<T,Ref> Self;
    //用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造
    __list_iterator(node* p)
        :_pnode(p)
    {}
    //迭代器運(yùn)算符的重載
    Ref operator*()
    {
        return _pnode->_data;
    }
    Self& operator++()//返回值不要寫成node*，因?yàn)榈?+肯定返回迭代器啊，你返回節(jié)點(diǎn)指針類型不對(duì)
    { 
        //return _pnode->_next;//返回類型錯(cuò)誤的
        _pnode=_pnode->_next;
        return *this;//返回的是迭代器
    }
    Self& operator--()
    {
        _pnode = _pnode->_prev;
        return *this;
    }
    bool operator!=(const Self& it)
    {
        return _pnode != it._pnode;
    }
public:
    node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針
};
 
typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;

4、迭代器價(jià)值

1、封裝底層實(shí)現(xiàn)，不暴露底層實(shí)現(xiàn)的細(xì)節(jié)；

2、多種容器提供統(tǒng)一的訪問方式，降低使用成本；

C語言沒有運(yùn)算符重載和引用等語法，是實(shí)現(xiàn)不了迭代器的。

5、迭代器operator->的重載

迭代器的用法就是模擬指針的行為，如果現(xiàn)在有一個(gè)指向結(jié)構(gòu)的指針，那么就需要用到->來解引用。

//*的重載：返回節(jié)點(diǎn)的數(shù)據(jù)
Ref operator*()
{
    return _pnode->_data;
}
//->的重載：返回?cái)?shù)據(jù)的指針
T* operator->()
{
    return &_pnode->_data;
}

但是operator->使用T*做返回值類型，這樣無論是普通迭代器和const迭代器都能修改，所以operator->的返回值類型應(yīng)該改為泛型：

template <class T, class Ref,class Ptr>
Ptr operator->()
{
    return &_pnode->_data;
}
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

四、模擬實(shí)現(xiàn)時(shí)遇到的困惑及注意點(diǎn)

1、調(diào)用拷貝構(gòu)造時(shí)，鏈表內(nèi)節(jié)點(diǎn)數(shù)據(jù)為什么已經(jīng)是深拷貝了？

2、類名和類型的區(qū)別

普通類：類名等于類型

類模板：類名不等價(jià)于類型，例如list類模板類名是list,類型list<int>等。

所以我們平常寫函數(shù)形參和返回值時(shí)，總會(huì)帶上形參和返回值的類型：

// 賦值運(yùn)算符重載寫法2(賦值運(yùn)算符重載都可以這么干)
list<T>& operator=(list<T> lt)
{
    swap(lt);
    return *this;
}

但是C++在類模板里面可以用類名代替類型：?

// 賦值運(yùn)算符重載寫法2(賦值運(yùn)算符重載都可以這么干)
list& operator=(list lt)
{
    swap(lt);
    return *this;
}

建議寫代碼的時(shí)候嚴(yán)格區(qū)分類型和類名，讓自己和別人能夠看的很明白。（了解下C++有這種坑語法即可）

五、vector和list的優(yōu)缺點(diǎn)

vector和list像左右手一樣，是互補(bǔ)關(guān)系，缺一不可。vector的優(yōu)點(diǎn)正是list的缺點(diǎn)，list的優(yōu)點(diǎn)也是vector的缺點(diǎn)，實(shí)際選用容器時(shí)，按照需求擇優(yōu)選用。

1、vector

vector的優(yōu)點(diǎn)（結(jié)構(gòu)厲害）：

1、支持下標(biāo)的隨機(jī)訪問；

2、尾插尾刪效率高（當(dāng)然擴(kuò)容的那一次尾插尾刪會(huì)較慢）；

3、CPU高速緩存命中高（數(shù)據(jù)從緩存加載至CPU中，會(huì)加載連續(xù)的一段數(shù)據(jù)，vector因?yàn)榻Y(jié)構(gòu)連續(xù)，高速緩存命中高）。

vector的缺點(diǎn)：

1、非尾插尾刪效率低；

2、擴(kuò)容有消耗，并存在一定的空間浪費(fèi)。

vector迭代器失效問題：

insert/erase均失效。（如果string的insert和erase形參是迭代器，那么也會(huì)失效，但是大部分接口是下標(biāo)傳參，不考慮失效問題，只有幾個(gè)接口是迭代器傳參，需要注意迭代器失效問題）

2、list

list的優(yōu)點(diǎn)：

1、按需申請(qǐng)釋放，無需擴(kuò)容；

2、任意位置插入刪除時(shí)間O(1)；（這里說的是插入刪除，不要加上查找的時(shí)間）

list的缺點(diǎn)：

1、不支持下標(biāo)的隨機(jī)訪問；

2、CPU高速緩存命中率低；

3、每一個(gè)節(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外，還需要額外存儲(chǔ)兩個(gè)指針。

list迭代器失效問題：

insert不失效，erase失效。

六、模擬實(shí)現(xiàn)list整體代碼

#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <vector>
using std::cout;
using std::endl;
namespace jly
{
	//鏈表節(jié)點(diǎn)的類
	template <class T>
	struct list_node
	{
		list_node(const T& x = T())//給一個(gè)缺省值，變成默認(rèn)構(gòu)造函數(shù)
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
 
		list_node* _next;
		list_node* _prev;
		T _data;
	};
	//用類封裝普通/const迭代器
	template <class T, class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T, Ref,Ptr> Self;
		//用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造
		__list_iterator(node* p)
			:_pnode(p)
		{}
		//迭代器運(yùn)算符的重載
		Ref operator*()
		{
			return _pnode->_data;
		}
		Ptr operator->()
		{
			return &_pnode->_data;
		}
		Self& operator++()//返回值不要寫成node*，因?yàn)榈?+肯定返回迭代器啊，你返回節(jié)點(diǎn)指針類型不對(duì)
		{
			//return _pnode->_next;//返回類型錯(cuò)誤的
			_pnode = _pnode->_next;
			return *this;//返回的是迭代器
		}
		Self operator++(int)//后置++
		{
			_pnode = _pnode->_next;
			return Self(_pnode->_next);
		}
		Self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		Self operator--(int)//后置--
		{
			_pnode = _pnode->_prev;
			return Self(_pnode->_prev);
		}
		bool operator!=(const Self& it)const
		{
			return _pnode != it._pnode;
		}
		bool operator==(const Self& it)const
		{
			return _pnode == it._pnode;
		}
	public:
		node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針
	};
	//用類封裝const迭代器
	//template <class T>
	//struct __list_const_iterator
	//{
	//	typedef list_node<T> node;
	//	//用節(jié)點(diǎn)的指針進(jìn)行構(gòu)造
	//	__list_const_iterator(node* p)
	//		:_pnode(p)
	//	{}
	//	//迭代器運(yùn)算符的重載
	//	const T& operator*()const
	//	{
	//		return _pnode->_data;
	//	}
	//	__list_const_iterator<T>& operator++()//返回值不要寫成node*，因?yàn)榈?+肯定返回迭代器啊，你返回節(jié)點(diǎn)指針類型不對(duì)
	//	{
	//		//return _pnode->_next;//返回類型錯(cuò)誤的
	//		_pnode = _pnode->_next;
	//		return *this;//返回的是迭代器
	//	}
	//	__list_const_iterator<T>& operator--()
	//	{
	//		_pnode = _pnode->_prev;
	//		return *this;
	//	}
	//	bool operator!=(const __list_const_iterator<T>& it)const
	//	{
	//		return _pnode != it._pnode;
	//	}
	//public:
	//	node* _pnode;//封裝一個(gè)節(jié)點(diǎn)的指針
	//};
 
	//鏈表類（控制哨兵位）
	template <class T>
	class list
	{
	public:
		typedef list_node<T> node;
		typedef __list_iterator<T, T&,T*> iterator;
		typedef __list_iterator<T, const T&,const T*> const_iterator;
		//typedef __list_const_iterator<T> const_iterator;
		//構(gòu)造函數(shù)
		void empty_initialize()//用于初始化哨兵位
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_initialize();
		}
		template <class InputIterator>
		list(InputIterator first, InputIterator last)//迭代器區(qū)間構(gòu)造
		{
			empty_initialize();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//析構(gòu)函數(shù)
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		//拷貝構(gòu)造
		list(const list<T>& lt)
		{
			先初始化*this
			//empty_initialize();
			//for (const auto& e : lt)//取lt的數(shù)據(jù)給e
			//{
			//	push_back(e);
			//}
 
			//工具人寫法
			list<T> tmp(lt.begin(),lt.end());
			empty_initialize();
			swap(tmp);
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);//交換頭指針
			std::swap(_size,lt._size);
		}
		賦值運(yùn)算符重載寫法1
		//list<T>& operator=(const list<T>& lt)
		//{
		//	//防止自己給自己賦值
		//	if (this != &lt)
		//	{
		//		clear();
		//		for (const auto& e : lt)
		//		{
		//			push_back(e);
		//		}
		//	}
		//	return *this;
		//}
		// 賦值運(yùn)算符重載寫法2(賦值運(yùn)算符重載都可以這么干)
		list<T>& operator=(list<T> lt)
		{
			swap(lt);//直接交換
			return *this;
		}
		//插入刪除
		void push_back(const T& x)
		{
			/*node* newNode = new node(x);
			node* tail = _head->_prev;
			newNode->_prev = tail;
			newNode->_next = _head;
			tail->_next = newNode;
			_head->_prev = newNode;*/
			insert(end(), x);
		}
		void pop_back()
		{
			erase(--end());
		}
		void push_front(const T& x)//頭插
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}
		iterator insert(iterator pos, const T& x)
		{
			node* newNode = new node(x);
			node* prev = pos._pnode->_prev;
			node* cur = pos._pnode;
			newNode->_prev = prev;
			newNode->_next = cur;
			prev->_next = newNode;
			cur->_prev = newNode;
			//return iterator(newNode);
			pos._pnode = newNode;
			++_size;
			return pos;
		}
		iterator erase(iterator pos)
		{
			assert(!empty());
			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;
			prev->_next = next;
			next->_prev = prev;
			delete pos._pnode;
			--_size;
			//return iterator(next);
			pos._pnode = next;
			return pos;
		}
		//鏈表小接口
		bool empty()const
		{
			return _head->_next == _head;
		}
		void clear()
		{
			/*assert(!empty);
			node* cur = _head->_next;
			while (cur != _head)
			{
				node* next = cur->_next;
				delete cur;
				cur = next;
			}*/
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);//erase返回刪除元素的下一個(gè)
			}
		}
		size_t size()const
		{
			return _size;
		}
		//普通begin(),end()迭代器
		iterator begin()
		{
			//return iterator(_head->_next);
			return __list_iterator<T, T&,T*>(_head->_next);
		}
		iterator end()
		{
			return __list_iterator<T, T&,T*>(_head);
		}
		//const begin(),end()迭代器
		const_iterator begin()const
		{
			//return const_iterator(_head->_next);
			return __list_iterator<T, const T&,const T*>(_head->_next);
		}
		const_iterator end()const
		{
			return __list_iterator<T, const T&,const T*>(_head);
		}
	private:
		node* _head;//哨兵位
		size_t _size;//用于統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)，空間換時(shí)間
		//不加這個(gè)私有變量，統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)時(shí)間O(N),有這個(gè)私有變量，時(shí)間O(1),但是每個(gè)節(jié)點(diǎn)的體積變大
	};
 
 
	//測(cè)試函數(shù)
	struct Pos
	{
		int _row;
		int _col;
 
		Pos(int row = 0, int col = 0)
			:_row(row)
			, _col(col)
		{}
	};
	void test()
	{
		list<Pos> i;
		i.push_back(Pos(1, 2));
		i.push_back(Pos(2, 5));
		i.push_back(Pos(4, 3));
		list<Pos>::iterator it = i.begin();
		while (it != i.end())
		{
			cout << (&( * it))->_row;//*it取數(shù)據(jù)，再取地址、解引用得到_row,多此一舉
			cout << it->_row;//同第三種寫法，編譯器為了可讀性，省略了一個(gè)->
			cout << it.operator->()->_row;//it.operator->()是顯示調(diào)用，->_row是解引用得到_row
			it++;
		}
	}
	void test1()
	{
		list<std::vector<int>> i;
		std::vector<int> v1(1, 2);
		std::vector<int> v2(2, 4);
		std::vector<int> v3(3, 5);
		i.push_back(v1);
		i.push_back(v2);
		i.push_back(v3);
		list<std::vector<int>> m(i);
		i = m;
		cout << m.size();
	}
}

原文鏈接：https://blog.csdn.net/gfdxx/article/details/128195342

欄目分類
最近更新