C++中list的使用与模拟实现

目录
  • 一、list的介绍以及使用
    • 1.1 list的介绍
    • 1.2 list的使用
      • 1.2.1 list的构造
      • 1.2.2 list iterator的使用
      • 1.2.3 list capacity
      • 1.2.4 list element access
      • 1.2.5 list modifiers
      • 1.2.6 list的迭代器失效
  • 二、list的模拟实现
    • 2.1 模拟实现list
  • 总结

一、list的介绍以及使用

1.1 list的介绍

1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代(所谓的常熟范围内,就是时间复杂度为O(1))

2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。

4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

这一段关于list的特性,需要能够与vector对比理解。

1.2 list的使用

1.2.1 list的构造

构造函数( (constructor)) 接口说明
list() 构造空的list
list (size_type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素
list (const list& x) 拷贝构造函数
list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list
#include <iostream>
#include <list>
using namespace std;
int main()
{
    std::list<int> l1; // 构造空的l1
    std::list<int> l2(4, 100); // l2中放4个值为100的元素
    std::list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end())左闭右开的区间构造l3
    std::list<int> l4(l3); // 用l3拷贝构造l4
    // 以数组为迭代器区间构造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的使用

函数声明 接口说明
begin +
end
返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin +
rend
返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的reverse_iterator,即begin位置

注意:

1、begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动

2、rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

#include <iostream>
#include <list>
using namespace std;
void print_list(const list<int>& l)
{
    // 注意这里调用的是list的 begin() const,返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
        // *it = 10; 编译不通过
    }
    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

函数声明 接口说明
empty 检测list是否为空,是返回true,否则返回false
size 返回list中有效节点的个数

1.2.4 list element access

函数声明 接口说明
front 返回list的第一个节点中值的引用
back 返回list的最后一个节点中值的引用

1.2.5 list modifiers

函数声明 接口说明
push_front 在list首元素前插入值为val的元素
pop_front 删除list中第一个元素
push_back 在list尾部插入值为val的元素
pop_back 删除list中最后一个元素
insert 在list position 位置中插入值为val的元素
erase 删除list position位置的元素
swap 交换两个list中的元素
clear 清空list中的有效元素

这里就不用代码的形式展示了

1.2.6 list的迭代器失效

前面说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响

#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()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给其赋值
		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的模拟实现

2.1 模拟实现list

这是本章的重中之重。

#include <iostream>
#include <assert.h>
using std::cout;
using std::endl;
namespace zjx
{
	// List的节点类
	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的迭代器类
	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类
	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的构造

		list()
		{
			_pHead = new Node();
			_pHead->_pNext = _pHead;
			_pHead->_pPre = _pHead;
		}
		//构造函数
		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++;
			}
		}

		//拷贝构造函数
		list(const list<T>& l)
		{
			//用迭代器先构造出来一个
			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//这个函数右边的const是用来限定this指针的。原本的this指针,不可以改变指向,可以改变所知的内容。
						  //但若要对所指向的内容加以限定的话,那就在函数的右边加上const,表示此函数的隐藏的参数,也就是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的节点

		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位置的节点,返回该节点的下一个位置

		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的元素的个数 = " << 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;
}

函数右边的const是用来限定this指针的。原本的this指针,不可以改变指向,可以改变所知的内容。

但若要对所指向的内容加以限定的话,那就在函数的右边加上const,表示此函数的隐藏的参数,也就是this指针,被加以const限定。

vector缺陷:

连续的物理空间,是优势,也是劣势。优势:支持高效随机访问。

劣势:

1、空间不够要增容,增容代价比较大。

2、可能存在一定空间浪费。按需申请,会导致频繁增容,所以一般都会2倍左右扩容。

3、头部或者中部插入删除需要挪动数据,效率低下list很好的解决vector的以上问题:

1、按需申请释放空间。

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

const对象会自动找到const修饰的函数

总结

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

(0)

相关推荐

  • C++模拟实现List迭代器详解

    目录 概念 迭代器使用 迭代器模拟实现 迭代器的大体结构 构造函数 解引用重载 重载 自增实现 自减实现 运算符重载 迭代器失效 模拟List 概念 迭代器是一种抽象的设计概念,其定义为:提供一种方法,使他能够按顺序遍历某个聚合体(容器)所包含的所有元素,但又不需要暴露该容器的内部表现方式. 迭代器是一种行为类似智能指针的对象, 而指针最常见的行为就是内 容提领和成员 访问. 因此迭代器最重要的行为就是对operator*和operator->进行重载. STL的中心思想在于: 将数据容器和算法

  • C++入门之list的使用详解

    目录 前言 构造的使用 1 构造空list 2 构造含n个值为val的元素 3 拷贝构造 4 用迭代区间 迭代器接口 1 正常迭代接口 2 逆向迭代接口 容量接口 元素访问 数据修改 头插 头删 尾插 尾删 pos位置插入 erase擦除pos位置 交换两个链表元素 总结 前言 今天我们终于来到了C++的list章节,在讲解之前,先回顾一下前面的vector和string吧. vector和string的底层都是用的顺序表,因此其空间在物理结构上连续的.而今天的list却不一样,它在物理上是散乱

  • C++深入探究list的模拟实现

    目录 迭代器 正向迭代器类 反向迭代器类 push_back尾插函数 push_front头插函数 insert插入函数 erase删除函数 pop_front函数 pop_back函数 构造函数 析构函数 list拷贝构造函数 list赋值重载函数 其他函数 示意图: 迭代器 正向迭代器类 我们之前所理解的是:迭代器理解为像指针一样的东西,但是在list中有些不同 // 迭代器逻辑 while(it!=l.end()) { *it; // 解引用取数据 ++it;// 自加到达下一个位置 }

  • C++初阶之list的模拟实现过程详解

    list的介绍 list的优点: list头部.中间插入不再需要挪动数据,O(1)效率高 list插入数据是新增节点,不需要增容 list的缺点: 不支持随机访问,访问某个元素效率O(N) 底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低. 今天来模拟实现list 我们先来看看官方文档中对于list的描述 我们先大致了解一下list的遍历 迭代器 对于迭代器我们可以用while循环+begin()end().同时还可以用迭代器区间. 当然迭代器区间的方式只适用于内存连续的结构

  • C++中list的用法实例讲解

    目录 前言 一.list的节点 二.list的迭代器 2.1.模板参数为什么是三个 2.3 修改方法 二.美中不足 三.迭代器的分类 3.x std::find的一个报错 总结 前言 list相较于vector来说会显得复杂,它的好处是在任意位置插入,删除都是一个O(1)的时间复杂度. 一.list的节点 template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; void_poi

  • C++数据结构之list详解

    目录 前言 一.list的节点 二.list的迭代器 2.1 const 迭代器 2.2 修改方法 二.美中不足 三.迭代器的分类 3.x std::find的一个报错 总结 前言 list相较于vector来说会显得复杂,它的好处是在任意位置插入,删除都是一个O(1)的时间复杂度. 一.list的节点 template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; void_poin

  • C++ 超详细示例讲解list的使用

    目录 一.list的介绍 list的介绍 二.list的使用 2.1 list的构造函数 2.2 list迭代器的使用 2.3 list相关的容量大小相关的函数 2.4 list数据的访问相关的函数 2.5 list的数据调整相关的函数 2.6 list中其他函数操作 一.list的介绍 list的介绍 list是可以以O(1)的时间复杂度任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针

  • c++中vector的使用和模拟实现

    一.接口介绍 1.插入数据 void push_back(const T& x) 在当前vector尾部插入x,如果容量不够扩大二倍. iterator insert(iterator pos, const T& x) 在POS位置插入元素x 2.容量相关 size_t capacity() 返回当前vector的容量(size+剩余容量) size_t size() 返回当前vector的元素个数 void resize(size_t n, const T& val = T())

  • C语言中关于库函数 qsort 的模拟实现过程

    目录 前言 一.qsort函数 二.qsort函数实现思路 1. 底层原理 2. 函数传参 1). 第一个参数 2). 第二个参数 3). 第三个参数 4). 第四个参数 三.局部函数实现 四.全部代码汇集 五.总结 前言 我们在上一篇博客讲解了库函数qsort的使用,今天我为大家带来qsort的模拟实现.上一篇博客这个库函数的阅读链接:C语言中关于库函数 qsort 快排的用法 其实有人会问,我明明已经掌握了库函数qsort的使用方法,为何还要去写模拟实现,其实啊,学好一个东西,不仅仅只是会用

  • C++中priority_queue的使用与模拟实现

    目录 priority_queue的使用 priority_queue简介 priority_queue的使用 priority_queue的模拟实现 priority_queue的使用 priority_queue文档介绍 priority_queue简介 优先队列是一种容器适配器,有严格的排序标准,它的第一个元素总是它所包含的元素中最大的(或最小的). 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆(或 最小堆)元素(优先队列中位于顶部的元素). 默认情况下,如果没有为特定的p

  • C++中list的使用与模拟实现

    目录 一.list的介绍以及使用 1.1 list的介绍 1.2 list的使用 1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity 1.2.4 list element access 1.2.5 list modifiers 1.2.6 list的迭代器失效 二.list的模拟实现 2.1 模拟实现list 总结 一.list的介绍以及使用 1.1 list的介绍 1.list是可以在常数范围内在任意位置进行插入和删除的序列式容器,

  • 详解C++中vector的理解以及模拟实现

    目录 vector介绍 vector常见函数介绍 vector模拟实现及迭代器失效讲解 vector介绍 vector文档 1.vector是表示可变大小数组的序列容器. 2.就像数组一样,vector也采用的连续存储空间来存储元素.也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效.但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理. 3.本质讲,vector使用动态分配数组来存储它的元素.当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间.其做

  • 仅Firefox中链接A无法实现模拟点击以触发其默认行为

    而标准的事件触发可以使用dispatchEvent方法.但现在FF5无法触发了A的默认行为了.如下 复制代码 代码如下: <!doctype html> <html> <head> <meta charset="utf-8"> <title>Firefox5链接A无法实现模拟点击bug</title> </head> <body> <a id="a1" href=&

  • DSP中浮点转定点运算--定点数模拟浮点数运算及常见的策略

    4.定点数模拟浮点数运算及常见的策略 相信大家到现在已经大致明白了浮点数转换成定点数运算的概貌.其实,原理讲起来很简单,真正应用到实际的项目中,可能会遇到各种各样的问题.具我的经验,常见的策略有如下几条: 1)除法转换为乘法或移位运算 我们知道,不管硬件平台如果变换,除法运算所需要的时钟周期都远远多于乘法运算和加减移位运算,尤其是在嵌入式应用中,"效率"显得尤为重要.以笔者的经验,其实,项目中的很大一部分除法运算是可以转换成乘法和移位运算,效率还是有很大提升空间的. 2)查表计算 有些

  • 一篇文章带你实现C语言中常用库函数的模拟

    目录 前言 函数介绍 strlen(求字符串长度) strcpy(字符串拷贝) strcat(字符串追加) strcmp(字符串比较) strstr(找子字符串) memcpy(内存拷贝) memmove(内存移动) 总结 前言 C语言中对字符和字符串的处理很是频繁,但是C语言本身是没有字符串类型的,字符串通常放在常量字符串中或者字符数组中. 字符串常量适用于那些对它不做修改的字符串函数. 函数介绍 strlen(求字符串长度) size_t strlen ( const char * str

  • vue-cli项目如何使用vue-resource获取本地的json数据(模拟服务端返回数据)

    最近使用vue-cli做了一个小小的项目,在项目中需要使用vue-resource来与后台进行数据交互,所以我使用了本地json数据来模仿后台获取数据的流程. 至于vue-resource的安装和json的准备我就不赘述了... 下面是操作方法: 1.首先介绍一下项目的结构:将本地的json文件放在最外层和index.html在一起,姑且叫做data.json. 我的json数据文件大概如此: { "seller": { "name": "粥品香坊(回龙观

  • 使用正则表达式替换报表名称中的特殊字符(推荐)

    正则表达式,又称规则表达式.(英语:Regular Expression,在代码中常简写为regex.regexp或RE),计算机科学的一个概念.正则表通常被用来检索.替换那些符合某个模式(规则)的文本. 许多程序设计语言都支持利用正则表达式进行字符串操作.例如,在Perl中就内建了一个功能强大的正则表达式引擎,还有java语言自带的.正则表达式这个概念最初是由Unix中的工具软件(例如sed和grep)普及开的.正则表达式通常缩写成"regex",单数有regexp.regex,复数

随机推荐