利用C++模拟实现STL容器:list

目录
  • 一、list的介绍
  • 二、list的排序
  • 三、迭代器
    • 1、list的迭代器失效问题
    • 2、迭代器的功能分类
    • 3、list迭代器的模拟实现
    • 4、迭代器价值
    • 5、迭代器operator->的重载
  • 四、模拟实现时遇到的困惑及注意点
  • 五、vector和list的优缺点
    • 1、vector
    • 2、list
  • 六、模拟实现list整体代码

一、list的介绍

列表是一种顺序容器,它允许在序列中的任何位置执行常量时间插入和删除操作,并允许在两个方向上进行迭代。

它的底层是一个带头双向循环链表。附一篇博主用C语言写的带头双向循环链表:【数据结构】带头双向循环链表的实现

二、list的排序

list不能用算法库的sort进行排序。算法库中的sort的底层是一个快排,需满足三数取中,需要传入随机访问迭代器,所以list并不适用。

当然list中提供了一个自己的sort,它的底层是一个归并排序。但是这个sort比vector使用算法库的sort还慢,甚至比list的数据先push_back到vector到再用算法库的sort还要慢。

三、迭代器

1、list的迭代器失效问题

insert,迭代器不失效

earse失效

2、迭代器的功能分类

1、单向迭代器:只能++,不能--。例如单链表,哈希表;

2、双向迭代器:既能++也能--。例如双向链表;

3、随机访问迭代器:能++--,也能+和-。例如vector和string。

迭代器是内嵌类型(内部类或定义在类里)

3、list迭代器的模拟实现

普通迭代器

迭代器的实现需要支持解引用(为了取数据),支持++--。

博主模拟实现string和vector时,直接将原生指针typedef成迭代器,是因为数组的结构正好满足迭代器的行为(注:string和vector可以用原生指针实现,但是vs中采用自定义类型封装的方式实现),但是list中的节点地址是不连续的,不能使用原生指针,需要使用类进行封装+运算符重载实现。

//用类封装迭代器
template <class T>
struct __list_iterator
{
    typedef list_node<T> node;
    //用节点的指针进行构造
    __list_iterator(node* p)
        :_pnode(p)
    {}
    //迭代器运算符的重载
    T& operator*()
    {
        return _pnode->_data;
    }
    __list_iterator<T>& operator++()//返回值不要写成node* operator++(),因为迭代器++肯定返回迭代器啊,你返回节点指针类型不对
    {
        //return _pnode->_next;
        _pnode=_pnode->_next;
        return *this;//返回的是迭代器
    }
    bool operator!=(const __list_iterator<T>& it)
    {
        return _pnode != it._pnode;
    }
public:
    node* _pnode;//封装一个节点的指针
};

const迭代器

const迭代器的错误写法:

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

因为typedef后,const修饰的是迭代器it,只能调用operator*(),调不了operator++()。(重载operator++()为const operator++()也不行,因为const版本++还是改变不了)

正确写法:想实现const迭代器,不能在同一个类里面动脑筋,需要再写一个const版本迭代器的类。

//用类封装const迭代器
template <class T>
struct __list_const_iterator
{
    typedef list_node<T> node;
    //用节点的指针进行构造
    __list_const_iterator(node* p)
        :_pnode(p)
    {}
    //迭代器运算符的重载
    const T& operator*()const
    {
        return _pnode->_data;
    }
    __list_const_iterator<T>& operator++()//返回值不要写成node*,因为迭代器++肯定返回迭代器啊,你返回节点指针类型不对
    {
        //return _pnode->_next;//返回类型错误的
        _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;//封装一个节点的指针
};

typedef __list_const_iterator<T> const_iterator;

当然,这样写__list_iterator和__list_const_iterator这两个类会出现代码重复。STL库中是通过类模板多给一个参数来实现,这样,同一份类模板就可以生成两种不同的类型的迭代器(以下为仿STL库的模拟实现):

//用类封装普通/const迭代器
template <class T,class Ref>
struct __list_iterator
{
    typedef list_node<T> node;
    typedef __list_iterator<T,Ref> Self;
    //用节点的指针进行构造
    __list_iterator(node* p)
        :_pnode(p)
    {}
    //迭代器运算符的重载
    Ref operator*()
    {
        return _pnode->_data;
    }
    Self& operator++()//返回值不要写成node*,因为迭代器++肯定返回迭代器啊,你返回节点指针类型不对
    {
        //return _pnode->_next;//返回类型错误的
        _pnode=_pnode->_next;
        return *this;//返回的是迭代器
    }
    Self& operator--()
    {
        _pnode = _pnode->_prev;
        return *this;
    }
    bool operator!=(const Self& it)
    {
        return _pnode != it._pnode;
    }
public:
    node* _pnode;//封装一个节点的指针
};

typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;

4、迭代器价值

1、封装底层实现,不暴露底层实现的细节;

2、多种容器提供统一的访问方式,降低使用成本;

C语言没有运算符重载和引用等语法,是实现不了迭代器的。

5、迭代器operator->的重载

迭代器的用法就是模拟指针的行为,如果现在有一个指向结构的指针,那么就需要用到->来解引用。

//*的重载:返回节点的数据
Ref operator*()
{
    return _pnode->_data;
}
//->的重载:返回数据的指针
T* operator->()
{
    return &_pnode->_data;
}

但是operator->使用T*做返回值类型,这样无论是普通迭代器和const迭代器都能修改,所以operator->的返回值类型应该改为泛型:

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;

四、模拟实现时遇到的困惑及注意点

1、调用拷贝构造时,链表内节点数据为什么已经是深拷贝了?

2、类名和类型的区别

普通类:类名等于类型

类模板:类名不等价于类型,例如list类模板类名是list,类型list<int>等。

所以我们平常写函数形参和返回值时,总会带上形参和返回值的类型:

// 赋值运算符重载写法2(赋值运算符重载都可以这么干)
list<T>& operator=(list<T> lt)
{
    swap(lt);
    return *this;
}

但是C++在类模板里面可以用类名代替类型:

// 赋值运算符重载写法2(赋值运算符重载都可以这么干)
list& operator=(list lt)
{
    swap(lt);
    return *this;
}

建议写代码的时候严格区分类型和类名,让自己和别人能够看的很明白。(了解下C++有这种坑语法即可)

五、vector和list的优缺点

vector和list像左右手一样,是互补关系,缺一不可。vector的优点正是list的缺点,list的优点也是vector的缺点,实际选用容器时,按照需求择优选用。

1、vector

vector的优点(结构厉害):

1、支持下标的随机访问;

2、尾插尾删效率高(当然扩容的那一次尾插尾删会较慢);

3、CPU高速缓存命中高(数据从缓存加载至CPU中,会加载连续的一段数据,vector因为结构连续,高速缓存命中高)。

vector的缺点:

1、非尾插尾删效率低;

2、扩容有消耗,并存在一定的空间浪费。

vector迭代器失效问题:

insert/erase均失效。(如果string的insert和erase形参是迭代器,那么也会失效,但是大部分接口是下标传参,不考虑失效问题,只有几个接口是迭代器传参,需要注意迭代器失效问题)

2、list

list的优点:

1、按需申请释放,无需扩容;

2、任意位置插入删除时间O(1);(这里说的是插入删除,不要加上查找的时间)

list的缺点:

1、不支持下标的随机访问;

2、CPU高速缓存命中率低;

3、每一个节点除了存储数据外,还需要额外存储两个指针。

list迭代器失效问题:

insert不失效,erase失效。

六、模拟实现list整体代码

#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <vector>
using std::cout;
using std::endl;
namespace jly
{
	//链表节点的类
	template <class T>
	struct list_node
	{
		list_node(const T& x = T())//给一个缺省值,变成默认构造函数
			:_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;
		//用节点的指针进行构造
		__list_iterator(node* p)
			:_pnode(p)
		{}
		//迭代器运算符的重载
		Ref operator*()
		{
			return _pnode->_data;
		}
		Ptr operator->()
		{
			return &_pnode->_data;
		}
		Self& operator++()//返回值不要写成node*,因为迭代器++肯定返回迭代器啊,你返回节点指针类型不对
		{
			//return _pnode->_next;//返回类型错误的
			_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;//封装一个节点的指针
	};
	//用类封装const迭代器
	//template <class T>
	//struct __list_const_iterator
	//{
	//	typedef list_node<T> node;
	//	//用节点的指针进行构造
	//	__list_const_iterator(node* p)
	//		:_pnode(p)
	//	{}
	//	//迭代器运算符的重载
	//	const T& operator*()const
	//	{
	//		return _pnode->_data;
	//	}
	//	__list_const_iterator<T>& operator++()//返回值不要写成node*,因为迭代器++肯定返回迭代器啊,你返回节点指针类型不对
	//	{
	//		//return _pnode->_next;//返回类型错误的
	//		_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;//封装一个节点的指针
	//};

	//链表类(控制哨兵位)
	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;
		//构造函数
		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)//迭代器区间构造
		{
			empty_initialize();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//析构函数
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		//拷贝构造
		list(const list<T>& lt)
		{
			先初始化*this
			//empty_initialize();
			//for (const auto& e : lt)//取lt的数据给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);
		}
		赋值运算符重载写法1
		//list<T>& operator=(const list<T>& lt)
		//{
		//	//防止自己给自己赋值
		//	if (this != &lt)
		//	{
		//		clear();
		//		for (const auto& e : lt)
		//		{
		//			push_back(e);
		//		}
		//	}
		//	return *this;
		//}
		// 赋值运算符重载写法2(赋值运算符重载都可以这么干)
		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返回删除元素的下一个
			}
		}
		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;//用于统计节点个数,空间换时间
		//不加这个私有变量,统计节点个数时间O(N),有这个私有变量,时间O(1),但是每个节点的体积变大
	};

	//测试函数
	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取数据,再取地址、解引用得到_row,多此一举
			cout << it->_row;//同第三种写法,编译器为了可读性,省略了一个->
			cout << it.operator->()->_row;//it.operator->()是显示调用,->_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();
	}
}

到此这篇关于利用C++模拟实现STL容器:list的文章就介绍到这了,更多相关C++ STL容器list内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • c++ STL容器总结之:vertor与list的应用

    STL提供六大组件,彼此可以组合套用 1.容器(containers):各种数据结构,如vertor,list,deque,set,map.从实现的角度来看,STL容器是一种class template 2.算法(algorithms):各种算法如sort,search,copy,earse.STL算法是一种 function template. 3.迭代器(iterators):扮演容器与算法之间的胶合剂,是所谓的"泛型指针".所有STL容器都有自己的专属的迭代器. 4.仿函数(fu

  • C++语言 STL容器list总结

    在使用std::list<>链表时,难免会对数据进行添加删除操作.而遍历链表则有两种方式:通过索引访问,象数组一样处理:通过std::list<>::iterator链表遍历器进行访问 STL 中的list 就是一 双向链表,可高效地进行插入删除元素. list不支持随机访问.所以没有 at(pos)和operator[]. list 对象list1, list2 分别有元素list1(1,2,3),list2(4,5,6) .list< int>::iterator

  • C++ STL入门教程(2) list双向链表使用方法(附程序代码)

    一.简介 "Unlike other standard sequence containers, list and forward_list objects are specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence." Lists将元素按顺序储存在链表中.与向量(vector)相比, 它允许快速

  • C++中 STL list详解及简单实例

    C++中 STL list详解 1.List: 内部实现是一个双向链表,可以高效的进行插入删除,但不能够进行随机访问 2..示例程序: #include "stdafx.h" #include <iostream> #include <list> #include <iterator> #include <algorithm> using namespace std; const int num[5] = {1,3,2,4,5}; boo

  • 利用C++模拟实现STL容器:list

    目录 一.list的介绍 二.list的排序 三.迭代器 1.list的迭代器失效问题 2.迭代器的功能分类 3.list迭代器的模拟实现 4.迭代器价值 5.迭代器operator->的重载 四.模拟实现时遇到的困惑及注意点 五.vector和list的优缺点 1.vector 2.list 六.模拟实现list整体代码 一.list的介绍 列表是一种顺序容器,它允许在序列中的任何位置执行常量时间插入和删除操作,并允许在两个方向上进行迭代. 它的底层是一个带头双向循环链表.附一篇博主用C语言写

  • C++模拟实现STL容器vector的示例代码

    目录 一.vector迭代器失效问题 二.模拟实现构造函数调用不明确 1.问题描述 2.解决调用不明确的方法 三.reserve中的深浅拷贝问题 1.reserve中浅拷贝发生原因 2.浅拷贝发生的图解 3.解决方法 四.模拟实现vector整体代码 一.vector迭代器失效问题 1.Visual Studio和g++对迭代器失效问题的表现 int main(){ std::vector<int>v{1,2,3,4}; std::vector<int>::iterator it

  • C++ STL容器详解之红黑树部分模拟实现

    目录 一.红黑树的概念 二.红黑树的性质 三.红黑树节点的定义 四.红黑树结构  五. 红黑树的插入操作 六.代码 总结 一.红黑树的概念 红黑树(Red Black Tree),是在计算机科学中用到的一种数据结构,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的. 二.红黑树的性质 1. 每个结点不是红色就是黑色: 2. 根节点是黑色的:

  • C++ STL容器适配器使用指南

    目录 适配器 stack容器适配器 ️stack的介绍 ️stack的使用 ️stack的模拟实现 queue ️queue的介绍 ️queue的使用 ️queue的模拟实现 deque容器 priority-queue ️priority-queue的使用 ️priority-queue的模拟实现 适配器 适配器是一种设计模式(设计模式是一套被反复使用的.多数人知晓的.经过分类编目的.代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口.例如: 容器适配器让一种已存在的容

  • 利用python模拟实现POST请求提交图片的方法

    本文主要给大家介绍的是关于利用python模拟实现POST请求提交图片的方法,分享出来供大家参考学习,下面来一看看详细的介绍: 使用requests来模拟HTTP请求本来是一件非常轻松的事情,比如上传图片来说,简单的几行代码即可: import requests files = {'attachment_file': ('1.png', open('1.png', 'rb'), 'image/png', {})} values = {'next':"http://www.xxxx.com/xxx

  • 利用Python模拟登录pastebin.com的实现方法

    任务 在https://pastebin.com网站注册一个账号,利用python实现用户的自动登录和创建paste.该任务需要分成如下两步利用python实现: 1.账号的自动登录 2.paste的自动创建 模拟账号登录 模拟登录,需要知道登录的URL是什么,那么登录URL怎么去看呢. 进入https://pastebin.com/之后,发现是以访客的身份进入的,点击身份图像的下拉中的LOGIN,进入登录页面,打开Chrome开发工具,选择Network,勾选Preserve log: 输入用

  • 使用Java注解模拟spring ioc容器过程解析

    使用注解,简单模拟spring ioc容器.通过注解给对象属性注入值. 项目结构 annotation 包,用于存放自定义注解 Component 注解表示该类为组件类,并需要声明名字 package priv.haidnor.annotation; import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy;

  • 利用JavaScript模拟京东按键输入功能

    在看到这个功能的时候我也很惊讶,京东竟然做了这样的一个功能.在京东商城网页版,无论你在什么位置,只需要按下S键,就可以将光标定位到搜索栏进行搜索.虽然说这是一个很不错的功能,但是貌似没有几个人知道. 程序实现很简单,在s键上升的时候搜索框获得焦点就可以了. <!DOCTYPE html> <html lang="zh-CN"> <head> <meta charset="UTF-8"> <meta name=&q

  • 利用Python模拟谷歌的小恐龙游戏

    目录 前言 开发工具 环境搭建 先睹为快 代码介绍 前言 本文的文字及图片来源于网络,仅供学习.交流使用,不具有任何商业用途,如有问题请及时联系我们以作处理. PS:如有需要Python学习资料的小伙伴可以加点击下方链接自行获取 谷歌流量器中有个很有名的彩蛋:当你网络出现问题时,就会出现一个"小恐龙游戏". (如果想要直接进行游戏,可以在地址栏输入:chrome://dino) 今天我们就来给大家演示下,用Python来自己做一个仿制的"小恐龙游戏"! 废话不多说,

随机推荐