C++ STL学习之【list的模拟实现】

这篇具有很好参考价值的文章主要介绍了C++ STL学习之【list的模拟实现】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

✨个人主页: 北 海
🎉所属专栏: C++修行之路
🎊每篇一句: 图片来源

  • A year from now you may wish you had started today.
    • 明年今日,你会希望此时此刻的自己已经开始行动了。

C++ STL学习之【list的模拟实现】



🌇前言

STL 中的 list 是一个双向带头循环链表,作为链表的终极形态,各项操作性能都很优秀,尤其是 list 中迭代器的设计更是让人拍案叫绝,如此优秀的容器究竟是如何实现的?本文将带你共同揭晓

C++ STL学习之【list的模拟实现】
出自书籍《STL源码剖析》 侯捷著

本文重点:迭代器类的设计


🏙️正文

注意:本文实现的只是部分基础函数,更多函数将会在后续进行更新

1、基本框架

list 由三个类构建而成:

  • 节点类:每个节点必须的三部分(指向前一个节点的指针、指向后一个节点的指针、当前节点存储的数据)
  • 迭代器类:此时的迭代器为双向迭代器,比较特殊,需要对其进行封装,如 it++ 并非使迭代器单纯向后移动,而是让其指向下一个节点
  • 链表类:实现链表各项功能的类,为主要部分

C++ STL学习之【list的模拟实现】

1.1、节点类

节点类在设计时,需要确定三个成员和构造函数,用来生成类

//节点类
template<class T>
struct __list_node
{
	__list_node(const T& data = T())
		:_prev(nullptr)
		,_next(nullptr)
		,_data(data)
	{}

	__list_node<T>* _prev;	//指向前一个节点
	__list_node<T>* _next;	//指向后一个节点
	T _data;	//存储相应数据
};

注意:节点的创建与销毁,不在 节点类 中进行,因此不需要写析构函数

1.2、迭代器类

迭代器类中的成员为节点类指针,指向单个节点,同样的,迭代器类也需要提供构造函数

//迭代器类
template<class T>
struct __list_iterator
{
	typedef __list_node<T>* link_type;	//对节点类的指针,进行重命名

	__list_iterator(link_type node)
		:_node(node)
	{}

	link_type _node;
};

注意:迭代器只是一个辅助工具,指向的是节点,同样不需要提供析构函数,析构相关事宜交给链表类处理就好

1.3、链表类

链表类中也只用有一个成员变量:哨兵位节点(头节点)

//list本类
template<class T>
class list
{
	typedef __list_node<T> node;	//节点
	typedef T value_type;	//模板参数值
	typedef T& refence;	//引用
	typedef const T& const_refence;	//const 引用

private:
	node* _head;	//哨兵位节点(头节点)
};

为了避免变量名过长,这里用到了很多的 typedef


2、默认成员函数

默认成员函数中包含了 默认构造、带参构造、拷贝构造、赋值重载和析构函数
析构函数负责 释放链表中的节点,而其他默认成员函数负责 构造/构建出其他对象

因为有很多构造函数中都需要对创建出头节点,所以此时 需要先构建出一个空初始化函数 empty_init(),这个函数只能在类中使用,因此设为 private

private:
	//初始化出头节点
	void empty_init()
	{
		_head = new node;
		_head->_prev = _head->_tail = _head;
	}

其他构造函数在构造对象前,可以先调用此函数

比如 默认构造函数, 构成出一个空对象

//默认构造函数
list() { empty_init(); }

对于带参构造函数,在构造对象前,仍需要调用 empty_init() 构建头节点
参数:

  • size_t n 对象中包含 n 个数据
  • const_reference val 数据值

为了避免与后续的迭代器区间构造起冲突,这里需要再额外提供一个 int n 版本

//带参构造函数(size_t)
list(size_t n, const_refence val = value_type())
{
	empty_init();
	while (n--) push_back(val);
}
//为了避免与迭代器区间构造函数冲突,提供额外版本(int)
list(int n, const_refence val = value_type())
{
	empty_init();
	while (n--) push_back(val);
}

在实际创建 list 对象时,多使用迭代器区间进行构造,因为是创建新对象,所以可以直接调用尾插进行创建

//迭代器区间构造
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
	empty_init();
	while (first != last) push_back(*first++);
}

关于拷贝构造和赋值重载,可以使用现代写法【交换】

//拷贝构造---现代写法
list(const list<T>& x)
{
	empty_init();
	list<T> tmp(x.begin(), x.end());
	swap(tmp);
}
//赋值重载---现代写法
list<T>& operator=(list<T> tmp)
{
	swap(tmp);
	return *this;
}

注意:

  • 以上几种构造函数都是在创建新对象,因此在构建前,需要先调用 empty_init() 初始化出头节点
  • 为了避免 list(int, int) 匹配上迭代器区间构造,可以再额外提供一个 int 版的带参构造函数
  • 拷贝构造的参数必须使用引用,否则会造成 无穷递归 问题

至于 析构函数 的实现就很简单了,直接使用函数 clear() 释放节点,最后再释放头节点即可

//析构函数
~list()
{
	clear();	//后续会对这个函数的实现进行讲解
	delete _head;
	_head = nullptr;
}

对上述函数进行使用
C++ STL学习之【list的模拟实现】


3、迭代器设计

迭代器设计是本文的重难点

它是一个单独存在的类

//迭代器类
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef __list_node<T>* link_type;
	typedef __list_iterator<T, Ref, Ptr> self;

	__list_iterator(link_type node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	self& operator++()
	{
		_node = _node->_next;

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

		return *this;
	}

	self operator++(int)
	{
		self tmp(_node);
		
		//++_node;	//谨防错误写法
		//_node = _node->_next;	//正确写法1
		++(*this);	//正确写法2
		return tmp;
	}

	self operator--(int)
	{
		self tmp(_node);

		//--_node;	//谨防错误写法
		//_node = _node->_prev;	//正确写法1
		--(*this);	//正确写法2
		return tmp;
	}

	bool operator==(const self& tar)
	{
		return tar._node == _node;
	}

	bool operator!=(const self& tar)
	{
		return tar._node != _node;
	}

	link_type _node;
};

注意:节点类及迭代器类都是使用 struct 定义的,目的是为了开放其中的成员

list 类中的迭代器相关函数也有两种:普通版本与 const 版本

规定:

  • begin()list 的头节点的下一个节点
  • end()list 的头节点
  • 返回类型都为迭代器对象,因此可以使用匿名对象进行构造
//=====迭代器设计=====
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_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); }

3.1、双向迭代器

list 中的迭代器只支持双向操作,在进行随机移动时会报错
以下是 std::list 中对迭代器进行随机移动的情况

void TestStdList()
{
	std::list<int> slt = { 1, 2, 3 };
	std::list<int>::iterator it = slt.begin();
	it++;	//单向移动,支持
	it--;	//双向移动,支持
	it + 10;	//随机移动,不支持
}

C++ STL学习之【list的模拟实现】

虽然我们可以通过某些手段实现随机移动(比如 operator+(int n)),但为了更好的符合链表及标准库规定,这里设计为双向移动的迭代器即可

迭代器分类:

  • 单向迭代器:支持 ++-- 其中一种移动方式
  • 双向迭代器:支持 ++-- 两种移动方式
  • 随机迭代器:不仅支持 ++--,还支持迭代器 +n-n,只有随机迭代器才能使用 std::sort 进行快速排序

目标:实现前置 ++/-- 及后置 ++/--

self& operator++();	//前置++

self& operator--();	//前置--

self operator++(int);	//后置++

self operator--(int);	//后置--

注:具体代码实现在上面

3.2、特殊移动策略

list 中的双向迭代器在进行移动时也比较特殊,不像之前的 stringvector 是连续空间(移动直接调用内置 ++/--list非连续空间,迭代器在移动时为前后节点间的移动,使用内置 ++/-- 会引发严重的迭代器越界问题

因此才需要将迭代器单独封装为一个类,实现我们想要的效果

C++ STL学习之【list的模拟实现】

如何实现不同区域间节点的移动?

  • 首先需要先构建出迭代器对象
  • 当使用前置 ++ 时,会去调用迭代器类中的 operator++() 重载函数,将迭代器指向当前节点的下一个节点(_node = _node->_next
  • 使用后置 -- 时也是如此,调用 operator--() 即可(_node = _node->_prev
  • 至于后置 ++/--,可以先构造出当前节点的迭代器对象,再复用前置 ++/-- 即可
self& operator++()
{
	_node = _node->_next;

	return *this;
}

self& operator--()
{
	_node = _node->_prev;

	return *this;
}

self operator++(int)
{
	self tmp(_node);

	//++_node;	//谨防错误写法
	//_node = _node->_next;	//正确写法1
	++(*this);	//正确写法2
	return tmp;
}

self operator--(int)
{
	self tmp(_node);

	//--_node;	//谨防错误写法
	//_node = _node->_prev;	//正确写法1
	--(*this);	//正确写法2
	return tmp;
}

注意:_node 是迭代器中的节点指针,包含在迭代器对象中

在这里分享一个我在模拟迭代器类时遇到的小问题:根据一个 list 对象构造出另一个 list 对象,调用后置 ++/-- 并解引用后,出现内存问题(越界访问)

C++ STL学习之【list的模拟实现】

原因分析:调用后置 ++ 后,因 operator++(int) 编写不当,导致当前节点指针没有正确指向下一个节点,而是指向当前位置的下一块空间(非法空间),导致迭代器失联,引发后续的越界访问

//以下是后置++的错误写法
self operator++(int)
{
	self tmp(_node);

	++_node;	//错误写法
	return tmp;
}

根本原因:_node 是一个节点指针,非迭代器对象,++_node 不是在调用 operator++(),而是在调用内置的前置 ++ (节点指针没有像迭代器一样进行重载),直接 ++ 就指向了非法空间

C++ STL学习之【list的模拟实现】
解决方案:

  1. 手动实现节点的移动:_node = _node->_next
  2. 调用迭代器类的前置 ++++(*this)

两种解决方法都可以,推荐使用第二种(库中的解决方案)

self operator++(int)
{
	self tmp(_node);

	//++_node;	//谨防错误写法
	//_node = _node->_next;	//正确写法1
	++(*this);	//正确写法2
	return tmp;
}

补充:假设构造对象为内置的数组或其他库中的容器,++_node 不会出错,因为此时会调用正确的移动方法;而当构造对象为自己模拟实现的 list 时,会出现上述的报错问题

3.3、多参数模板

list 的模拟实现精华在于迭代器类的设计,而迭代器类中的精华在于多参数模板,这种传多模板参数的方法,巧妙的解决了 正常对象 与 const 对象的冗余设计问题

迭代器分为 iteratorconst_iterator,不同的对象调用不同的迭代器类型,假设不使用多参数模板,就需要实现两份相差不大的迭代器类(完全没有必要)

优雅、巧妙的解决方案 多参数模板

  • T:节点中值的普通类型
  • Ref:节点中值的引用类型(可为 const)
  • Ptr:节点中值的指针类型(可为 const)
//迭代器类
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef __list_node<T>* link_type;
	typedef __list_iterator<T, Ref, Ptr> self;

	//……

	link_type _node;
};

//=====迭代器设计=====(list 类中)
typedef __list_iterator<T, T&, T*> iterator;	//声明两种不同的迭代器
typedef __list_iterator<T, const T&, const T*> const_iterator;

迭代器类中的模板参数是一对二的

C++ STL学习之【list的模拟实现】
多参数模板的使用,使得 list 的迭代器设计更加优雅,下面是实际使用演示(在 operator*() 中添加信息区分)

Ref operator*()
{
	cout << "当前的模板参数为: " << typeid(*this).name() << endl;
	return _node->_data;
}
void TestList()
{
	int arr[] = { 1,2,3,4,5 };
	list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));	//普通对象
	const list<int> rlt(arr, arr + sizeof(arr) / sizeof(arr[0]));	//const 对象

	auto it = lt.begin();
	auto rit = rlt.begin();

	cout << *it << endl;

	cout << *++rit << endl;
}

C++ STL学习之【list的模拟实现】

使用不同的迭代器类型,可以使迭代器类中的模板参数变为对应类型
这正是 泛型编程 思想之一

3.4、其他功能

关于迭代器类中的其他功能:

  • 解引用 operator*()
  • 取当前节点指针 operator->()
  • 迭代器比较 operator==()operator!=()

详细实现代码可以查看本文的 章节3 开头

这里简单说一下 operator->()

适用场景:list 中的对象为自定义类型时,想直接通过 it-> 访问其中的成员

struct A
{
	A(int a = int(), double b = double(), char c = char())
		:_a(a)
		,_b(b)
		,_c(c)
	{}

	int _a;
	double _b;
	char _c;
};

void TestList()
{
	list<A> lt;
	lt.push_back(A(1, 2.2, 'A'));
	
	auto it = lt.begin();
	cout << (*it)._a << endl;	//不使用 operator->() 比较别扭
	cout << it.operator->()->_b << endl;	//这种写法是真实调用情况
	cout << it->_c << endl;	//编译器直接优化为 it->
}

C++ STL学习之【list的模拟实现】

operator->() 存在的意义:使得 迭代器 访问自定义类型中的成员时更加方便
如果没有这个函数,只能通过 (*迭代器).成员 的方式进行成员访问,很不方便

注意:编译器将 迭代器.operator->()->成员 直接优化为 迭代器->成员


4、容量相关

list 中的容量访问有:判空和大小

实现判空:判断当前的 begin()end() 是否相同
统计大小:利用迭代器将整个 list 遍历一遍,计数统计即可

//=====容量相关=====
bool empty() const { return begin() == end(); }
size_t size() const 
{
	int cnt = 0;
	auto it = begin();	//使用 auto 自动推导迭代器类型
	while (it != end())
		++it, ++cnt;

	return cnt;
}

C++ STL学习之【list的模拟实现】


5、数据访问

STL 库中给 list 提供了两种数据访问方式:访问首个数据和访问最后一个数据

//=====数据访问=====
refence front() { return *begin(); }
const_refence front() const { return *begin(); }

refence back() { return *(--end()); }
const_refence back() const { return *(--end()); }

C++ STL学习之【list的模拟实现】


6、数据修改相关

数据修改是 list 的拿手好戏(双向循环链表),只需要找到对应节点的位置,插入/删除 本质上就是在进行前后节点的链接关系修改

C++ STL学习之【list的模拟实现】
出自《STL源码剖析》

6.1、头尾插删

头尾插删是在对 begin()--end() 所指向的节点进行操作,尾部插入/头部删除 逻辑一致,尾部删除/头部删除 逻辑一致,学会其中一个就够用了

尾部插入步骤:

  • 根据传入的数值,构建出新尾节点 new_back
  • 找到原链表中的尾节点 old_back
  • old_backnew_back_head 间建立链接关系即可
  • 头部插入逻辑与尾部插入基本一致,不过找的是 old_front 头节点
//尾插
void push_back(const_refence val)
{
	node* new_back = new node(val);

	node* old_back = _head->_prev;

	old_back->_next = new_back;	//原尾节点的 _next 指向新尾节点
	new_back->_prev = old_back;	//新尾节点的 _prev 指向原尾节点

	new_back->_next = _head;	//新尾节点的 _next 指向头节点
	_head->_prev = new_back;	//头节点的 _prev 指向新尾节点
}

尾部删除步骤:

  • 断言当前 list 不为空,如果为空,就报错
  • 选择原来的尾节点 old_back->_head->_prev
  • 确定新的尾节点 new_back->old_back->prev
  • new_back_head 之间建立链接关系
  • 最后在释放原来的尾节点 old_back
  • 头删时,逻辑基本一致,不过选择的是 old_frontnew_front
//尾删
void pop_back()
{
	assert(!empty());

	node* old_back = _head->_prev;	//选择原尾节点
	node* new_back = old_back->_prev;	//确定新尾节点

	new_back->_next = _head;	//新尾节点的 _next 指向头节点
	_head->_prev = new_back;	//头节点的 _prev 指向新尾节点

	delete old_back;
}

C++ STL学习之【list的模拟实现】

类似于 push_back() 还有一个函数 assign() 分配,相当于构造函数构造出对象,不过此时是赋值的方式

//=====数据修改=====
//赋值
void assign(size_t n, const_refence val)
{
	clear();
	while (n--) push_back(val);
}
void assign(int n, const_refence val)
{
	assign((size_t)n, val);
}
template<class InputIterator>
void assign(InputIterator first, InputIterator last)
{
	list<T> tmp(first, last);
	swap(tmp);
}

C++ STL学习之【list的模拟实现】
注意:

  • 为了避免 assign(int, int)assign(first, last) 起冲突,需要再额外提供一个 assign(int n, const_refence val) 版本
  • assign 行为类似于创建出一个新的对象,因此在赋值(分配)前需要先清空 clear()
  • assign 本质上是在调用 push_back

6.2、任意位置插删

任意位置插入就是在插入操作的基础上添加了迭代器 pos 进行定位

  • 约定:在 pos 位置前插入
  • 根据传入值,创建出新节点 new_node
  • 确定当前 pos 位置的节点 pos_cur
  • 确定当前 pos 位置的上一个节点 pos_prev
  • pos_prevnew_nodepos_cur 间建立链接关系
  • 最后返回当前插入新节点的位置
//任意位置插入
iterator insert(iterator pos, const_refence val)
{
	node* new_node = new node(val);	//创建新节点

	node* pos_cur = pos._node;	//当前 pos 位置的节点
	node* pos_prev = pos_cur->_prev;	//pos 的前一个节点

	pos_prev->_next = new_node;	
	new_node->_prev = pos_prev;

	new_node->_next = pos_cur;
	pos_cur->_prev = new_node;

	return iterator(new_node);	//最后返回的是一个迭代器对象
}

任意位置删除逻辑与 尾删/头删 基本一致

  • 首先断言 list 是否为空
  • 分别确定当前节点 pos_cur,上一个节点 pos_prev,下一个节点 pos_next
  • 在上下节点 pos_prevpos_next 间建立链接关系
  • 删除当前节点 pos_cur
  • 返回已删除节点下一个节点,即 pos_next
//任意位置删除
iterator erase(iterator pos)
{
	assert(!empty());

	node* pos_cur = pos._node;

	node* pos_prev = pos_cur->_prev;
	node* pos_next = pos_cur->_next;

	pos_prev->_next = pos_next;
	pos_next->_prev = pos_prev;

	delete pos_cur;

	return iterator(pos_next);
}

注意:list 的插入操作没有迭代器失效问题,删除操作也仅仅是影响被删除节点的迭代器,返回值是为了更好的进行操作

之前提到的 尾部插入/删除头部插入/删除 可以复用 任意位置插入/删除

//尾插
void push_back(const_refence val)
{
	insert(end(), val);
}

//尾删
void pop_back()
{
	erase(--end());
}

//头插
void push_front(const_refence val)
{
	insert(begin(), val);
}

//头删
void pop_front()
{
	erase(begin());
}

复用后,之前的代码也能正常运行

C++ STL学习之【list的模拟实现】

6.3、交换、调整、清理

接下来是一些比较简单函数实现

  • 交换 swap:不同于 std::swaplist::swap 是直接交换两个链表的头节点,效率是极高的
  • 调整 resize:传入 n 及值 val,对 list 进行大小调整,只有 n > size() 才进行大小调整,具体调整就是 push_back() 尾插 n - size()
  • 清理 clear:通过迭代器对 list 进行遍历, erase 除头节点外的所有节点
//交换
void swap(list<T>& tmp)
{
	std::swap(_head, tmp._head);
}

//大小调整
void resize(size_t n, const_refence val = value_type())
{
	if (n > size())
	{
		while (size() < n)
			push_back(val);
	}
}

//清理
void clear()
{
	iterator it = begin();
	while (it != end())
		it = erase(it);
}

简单写一个小 demo 测试一下这些函数

void Print(list<int>& lt1, list<int>& lt2)
{
	cout << "lt1:" << "empty():" << lt1.empty() << "   size():" << lt1.size() << endl;
	for (auto e : lt1)
		cout << e << " ";
	cout << endl;

	cout << "lt2:" << "empty():" << lt2.empty() << "   size():" << lt2.size() << endl;
	for (auto e : lt2)
		cout << e << " ";
	cout << endl;
	
	cout << "============================" << endl;
}

void TestList()
{
	int arr[] = { 1,2,3,4,5 };
	list<int> lt1(arr, arr + sizeof(arr) / sizeof(arr[0]));
	list<int> lt2(3, 1);

	cout << "original" << endl;
	Print(lt1, lt2);

	cout << "swap(lt1, lt2)" << endl;
	lt1.swap(lt2);
	Print(lt1, lt2);

	cout << "lt1 resize()" << endl;
	lt1.resize(10, 2);
	Print(lt1, lt2);

	cout << "clear()" << endl;
	lt1.clear();
	lt2.clear();
	Print(lt1, lt2);
}

C++ STL学习之【list的模拟实现】


7、源码

关于本文中涉及到的所有代码都在这个仓库中 《list_4_8》

C++ STL学习之【list的模拟实现】


🌆总结

以上就是本次关于 STL 学习之 list 的模拟实现的全部内容了,对于本文来说,最核心的内容莫过于迭代器类的设计,而其中的精华在于多参数模板的使用,只要把迭代器类设计好了,list 中的其他部分都不成问题

如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!

如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正


C++ STL学习之【list的模拟实现】

相关文章推荐

STL 之 list 类

C++ STL学习之【list的使用】

===============

STL 之 vector 类

C++ STL学习之【vector的模拟实现】

C++ STL学习之【vector的使用】

===============

STL 之 string 类

C++ STL学习之【string类的模拟实现】

C++ STL 学习之【string】

C++ STL学习之【list的模拟实现】文章来源地址https://www.toymoban.com/news/detail-440128.html

到了这里,关于C++ STL学习之【list的模拟实现】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [ C++ ] STL---list的模拟实现

    目录 结点类的模拟实现 迭代器类的模拟实现 构造函数 前置++与后置++ 前置- -与后置 - - == 与 !=运算符重载 * 运算符重载 - 运算符重载 普通迭代器总体实现代码 list类的实现 list类的成员变量 构造函数 迭代器 insert() erase() push_front/push_back/pop_front/pop_back front/back clear() empty()

    2024年04月09日
    浏览(58)
  • C++ ——STL容器【list】模拟实现

    代码仓库: list模拟实现 list源码 数据结构——双向链表 源码的list是双向带头循环链表,所以我们定义两个节点,一个指向下一个,一个指向前一个 list类包含一个 _head 头节点,然后为了方便查出当前有多少个节点,还能多定义一个 _size 源码的迭代器设置了三个模板参数:

    2024年02月15日
    浏览(44)
  • 【C++】STL---list的模拟实现

    上次模拟实现了一个vector容器,那么我们这次来实现一个list(链表)容器,链表在实际的开发中并不常见。但是也是一种很重要的数据结构,下面给大家介绍一下链表(list) 和 vector(顺序表)的区别。 list 和 vector 一样,是一个存储容器。不同的是vector在内存中是连续存储的,而

    2024年01月22日
    浏览(51)
  • 【C++】STL之list容器的模拟实现

    个人主页:🍝在肯德基吃麻辣烫 分享一句喜欢的话:热烈的火焰,冰封在最沉默的火山深处。 本文章进入C++STL之list的模拟实现。 在STL标准库实现的list中,这个链表是一个== 双向带头循环链表==。 说明: list是一个类,成员变量为_head 节点类node,是每一个节点。 list的迭代

    2024年02月17日
    浏览(52)
  • 【C++】STL——list深度剖析 及 模拟实现

    这篇文章我们来继续STL的学习,今天我们要学习的是list,也是STL中容器的一员。 和之前一样,我们还是先学习它的使用,然后再对它进行一个深度剖析和模拟实现。 1.1 list的介绍 list的文档介绍 list的底层实现其实就是我们之前数据结构学过的带头双向循环链表: 1.2 list的使

    2024年02月05日
    浏览(41)
  • C++ stl容器list的底层模拟实现

    目录 前言: 1.创建节点 2.普通迭代器的封装 3.反向迭代器的封装 为什么要对正向迭代器进行封装? 4.const迭代器 5.构造函数 6.拷贝构造 7.赋值重载 8.insert 9.erase 10.析构 11.头插头删,尾插尾删 12.完整代码+简单测试 总结: 1.创建节点 注意给缺省值,这样全缺省就会被当做默认

    2024年04月23日
    浏览(44)
  • C++ STL之list的使用及模拟实现

    英文解释: 也就是说: list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常

    2024年01月24日
    浏览(68)
  • 【C++】STL之list深度剖析及模拟实现

    目录 前言 一、list 的使用  1、构造函数 2、迭代器 3、增删查改 4、其他函数使用 二、list 的模拟实现  1、节点的创建  2、push_back 和 push_front  3、普通迭代器  4、const 迭代器  5、增删查改(insert、erase、pop_back、pop_front)  6、构造函数和析构函数   6.1、默认构造   6.2、构造

    2024年02月07日
    浏览(43)
  • C++ STL库详解:list的详细模拟实现

    在详细学习并学习c++后,我们对stl库的例如vector、list、string都有了详细的了解,对模板的使用以及类和对象都有了熟练的掌握,而实践才是检验真理的唯一标准,在此片博客中,将利用先前学过的各模块知识来对list这个在数据结构中令许多初学者摸不到北,在c++中出场率不

    2024年01月24日
    浏览(46)
  • C++:stl:list的常用接口及其模拟实现

    本文主要介绍c++:stl中list常用接口的功能及使用方法,比较list与vector的区别,并对list的常用接口进行模拟实现。 目录 一、list的介绍和使用 1.list介绍 2.list使用 1.list的构造 2.list iterator的使用 3.list 容量相关 4.list元素访问 5.list修改 6.list的迭代器失效 二、list的模拟实现 1.l

    2024年02月07日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包