C/C++ 入门(10)list类(STL)

个人主页:仍有未知等待探索-CSDN博客

专题分栏:C++

                                                        欢迎来指教!

目录

一、标准库中的list

1、了解

2、常用接口说明

a.常见的构造函数

 b.迭代器

c. Capacity​编辑

d.Element access

e.Modifiers

二、实现

1、框架 

a.节点

b.迭代器

c.链表

2、节点

3、迭代器 

 4、链表

三、反向迭代器

四、问题

1、迭代器中的箭头操作符为什么返回的是地址?


一、标准库中的list

1、了解

list:是一个双向带头循环链表,不支持随机访问(即下标访问),任意位置的插入删除效率高。

2、常用接口说明

a.常见的构造函数

list的构造函数
构造函数 接口说明
list(size_t n, const T& val = t()) 构造n个值为val的list
list() 构造空的list

list(const list& x)

拷贝构造
list(iterator first, iterator second) 用[first, second)构造list

 b.迭代器

迭代器可以看作是一个指向节点的指针。

(rbegin和rend是反向迭代器,rbegin是指向了链表的尾部,rend是指向了链表的头部)

注意:

 begin,进行++操作是往后面走。

rbegin,进行++操作是往前面走。

c. Capacity

d.Element access

e.Modifiers

二、实现

 老规矩,我们还是先对结构进行分析。 

链表:除了一些对链表的基本操作之外,还需要有迭代器和节点。

1、框架 

#include <cstring>
#include <iostream>
using namespace std;

// 开辟一个自己的命名空间
namespace my
{
	// 链表节点
	// 迭代器
	// 链表
}

a.节点

// 链表节点
template<class T>
struct ListNode
{
	ListNode<T>* _prev;
	ListNode<T>* _next;
	T val;

	// 缺省参数,如果没有传参的话,默认是T类型的无参构造
	// 这样做是为了防止T是一个自定义类型
	ListNode(const T& e = T())
		:_prev(nullptr)
		,_next(nullptr)
		,val(e)
	{}
};

b.迭代器

其实这样的迭代器是不完整的,我们在后面会对其进行扩展。

template<class T>
struct NodeIterator
{
    // 对于节点和迭代器的重命名,方便书写
	typedef ListNode<T> Node;// 节点	
	typedef NodeIterator<T> Self; // 迭代器

	Node* _node;
    
    // 迭代器是用节点的指针来进行构造的
	NodeIterator(Node* node)
		:_node(node)
	{}
};

c.链表

// 链表
// list是一个带头双向循环链表
template<class T>
class list
{
	typedef ListNode<T> Node;// 节点
public:
	typedef NodeIterator<T, T&, T*> iterator;// 迭代器
private:
	Node* _head;// 链表的头部
	size_t _size;// 链表的长度
};

2、节点

其实节点这部分没有什么可以讲解的。唯一一个要理解的就是这个(const T& e = T())。

//const T& e = T()
// 首先T()是一个匿名对象的写法
// 为什么我们需要用到一个匿名对象,而不是一个const T& e = 值?
// 1、我们不知道T是什么类型,不知道值可以设成一个什么类型的值
// 2、如果我们设置成一个内置类型,而T是一个自定义类型的话,类型不匹配
ListNode(const T& e = T())
		:_prev(nullptr)
		,_next(nullptr)
		,val(e)
	{}

3、迭代器 

 我之前框架里所写的就是老版本的迭代器。

新版本里面的迭代器主要添加了两个新的模板变量(Ref,Ptr),引入的这两个变量是对解引用和引用的重写。

思考题:怎么写const版本的迭代器呢?

答:新版本写法的迭代器可以直接这么写(以int为例):

NodeIterator<int, const int&, const int*>

思考题:反向迭代器怎么实现的?

标准库里面的begin()和end() 与 rbegin()和rend()采用的是对称法。

// 迭代器
// 新版本
// 链表迭代器:模仿指针的行为
// Ref:引用,Ptr指针
template<class T, class Ref, class Ptr>
struct NodeIterator
{
	typedef ListNode<T> Node;// 节点	
	typedef NodeIterator<T, Ref, Ptr> Self; // 迭代器

	Node* _node;

	NodeIterator(Node* node)
		:_node(node)
	{}
	// 前置++
	Self& operator++()
	{
		_node = _node->_next;
		return *this;   
	}
	// 后置++
	Self& operator++(int)
	{
		Self tmp(*this);
		_node = _node->_next;
		return tmp; 
	}
	// 前置--
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	// 后置--
	Self& operator--(int)
	{
		Self tmp(_node);
		_node = _node->_prev;
		return tmp;
	}
	// 解引用
	Ref operator*()
	{
		return _node->val;
	}
	// -> 
	Ptr operator->()
	{
		return &_node->val;
	}
	// ==
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
	// !=
	bool operator!=(const Self& s)
	{
		return !(*this == s); 
	}
};
 老版本:缺点:无法实现const的迭代器
 链表迭代器:模仿指针的行为
//template<class T>
//struct NodeIterator
//{
//	typedef ListNode<T> Node;// 节点
//	typedef NodeIterator<T> Self; // 迭代器
//
//	Node* _node;
//
//	NodeIterator(Node* node)
//		:_node(node)
//	{}
//	// 前置++
//	Self& operator++()
//	{
//		_node = _node->_next;
//		return *this;   
//	}
//	// 后置++
//	Self& operator++(int)
//	{
//		Self tmp(*this);
//		_node = _node->_next;
//		return tmp; 
//	}
//	// 前置--
//	Self& operator--()
//	{
//		_node = _node->_prev;
//		return *this;
//	}
//	// 后置--
//	Self& operator--(int)
//	{
//		Self tmp(_node);
//		_node = _node->_prev;
//		return tmp;
//	}
//	// 解引用
//	T& operator*()
//	{
//		return _node->val;
//	}
//	// ==
//	bool operator==(const Self& s)
//	{
//		return _node == s._node;
//	}
//	// !=
//	bool operator!=(const Self& s)
//	{
//		return !(*this == s); 
//	}
//
//	// -> 
//	T* operator->()
//	{
//		return &_node->val;
//	}
//};

// 反向迭代器
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
	typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
	Iterator _it;

	Reverse_iterator(Iterator it)
		:_it(it)
	{}

	Ref operator*()
	{
		Iterator tmp(_it);
		return *( -- tmp);
	}
	Ptr operator->()
	{
		//return &_it.operator->();
		return &(_it.operator*());
	}
	Self& operator++()
	{
		_it -- ;
		return *this;
	}
	Self& operator--()
	{
		_it ++;
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _it != s._it;
	}
};

 4、链表

// 链表
template<class T>
class list
{
	typedef ListNode<T> Node;
public:
	typedef NodeIterator<T, T&, T*> iterator;
	typedef NodeIterator<T, const T&, const T*> const_iterator;
	// 构造函数
	list ()
		:_size(0)
	{
		_head = new Node;
		_head -> _next = _head;
		_head -> _prev = _head;
	}
	list (size_t n, const T& val = T())
		:_size(0)
	{
		_head = new Node;
		_head -> _next = _head;
		_head -> _prev = _head;

		for (size_t i = 0; i < n; i ++ )
		{
			push_back(val);
		}
	}
	list (list<T>& x)
		:_size(0)
	{
		_head = new Node;
		_head -> _next = _head;
		_head -> _prev = _head;

		iterator it = x.begin();
		while (it != x.end())
		{
			push_back(*it);
			it ++ ;
		}
	}
	list (iterator first, iterator last)
		:_size(0)
	{
		_head = new Node;
		_head -> _next = _head;
		_head -> _prev = _head;
		iterator it = first;
		while (it != last)
		{
			insert(end(), *it);
			it ++ ;
		}
	}
	~list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
	// 访问
	// const版本的迭代器,迭代器的指向的内容不能被修改
	// 1、自己单独实现一个const版本的迭代器
	// 2、将const和非const合成一个,通过模板参数进行控制
	const_iterator begin() const
	{
		return _head->_next;
	}
	const_iterator end() const
	{
		return _head;
	}
	iterator begin()
	{
		return iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}
	// list capacity
	bool empty()
	{
		return _size == 0;
	}
	size_t size()
	{
		return _size;
	}
	// list element access
	T& front()
	{
		return *begin();
	}
	T& back()
	{
		return *end();
	}
	// list modifiers
	/*void push_back(const T& val)
	{
	Node* tmp = new Node;
	tmp -> val = val;

	Node* tail = _head -> _prev;
	tmp->_next = tail->_next;
	tail->_next = tmp;
	tmp->_prev = tail;
	_head->_prev = tmp;

	_size ++ ;
	}*/
	void push_back(const T& val)
	{
		insert(end(), val);
	}
	void push_front(const T& val)
	{
		insert(begin(), val);
	}
	iterator insert (iterator position, const T& val)
	{
		Node* tmp = new Node(val);
		tmp->_next = position._node;
		tmp->_prev = position._node->_prev;
		position._node->_prev->_next = tmp;
		position._node->_prev = tmp;

		_size ++ ;
		return iterator(tmp);
	}
	void pop_back()
	{
		erase( -- end());
	}
	void pop_front()
	{
		erase(begin());
	}
	iterator erase (iterator position)
	{
		iterator tmp(position._node->_next);
		position._node->_prev->_next = position._node->_next;
		position._node->_next->_prev = position._node->_prev;
		delete position._node;

		_size -- ;

		return tmp;
	}
	void clear()
	{
		while (_size)
		{
			erase(begin());
		}
	}
	void swap(list& l)
	{
		std::swap(_head, l._head);
		std::swap(_size, l._size);
	}

private:
	Node* _head;
	size_t _size;
};

三、反向迭代器

通过前面例子知道,反向迭代器的++就是正向迭代器的--,反向迭代器的--就是正向迭代器的++,因此反向迭代器的实现可以借助正向迭代器,即:反向迭代器内部可以包含一个正向迭代器,对正向迭代器的接口进行包装即可。

四、问题

1、迭代器中的箭头操作符为什么返回的是地址?

 答:其实是编译器省略了一个箭头,例如:Iterator it;

正常的调用是:it.operator->()->val; 省略了一个箭头是为了提高代码的可读性。

相关推荐

  1. <span style='color:red;'>STL</span>_<span style='color:red;'>list</span>

    STL_list

    2024-05-12 13:02:01      29 阅读
  2. STL - list

    2024-05-12 13:02:01       23 阅读
  3. stl-list

    2024-05-12 13:02:01       12 阅读
  4. STL - list

    2024-05-12 13:02:01       6 阅读

最近更新

  1. .Net Core WebAPI参数的传递方式

    2024-05-12 13:02:01       0 阅读
  2. QT--气泡框的实现

    2024-05-12 13:02:01       1 阅读
  3. LeetCode 968.监控二叉树 (hard)

    2024-05-12 13:02:01       0 阅读
  4. leetcode热题100.完全平方数(动态规划进阶)

    2024-05-12 13:02:01       0 阅读
  5. leetcode328-Odd Even Linked List

    2024-05-12 13:02:01       0 阅读
  6. C 语言设计模式(结构型)

    2024-05-12 13:02:01       0 阅读
  7. v-if 与 v-show(vue3条件渲染)

    2024-05-12 13:02:01       0 阅读
  8. kafka防止消息丢失配置

    2024-05-12 13:02:01       0 阅读

热门阅读

  1. 关于python内置inspect

    2024-05-12 13:02:01       4 阅读
  2. iOS 生成SSH Key

    2024-05-12 13:02:01       4 阅读
  3. 记录一个git无法push的问题

    2024-05-12 13:02:01       3 阅读
  4. linux命令

    2024-05-12 13:02:01       3 阅读
  5. 整除C++

    整除C++

    2024-05-12 13:02:01      3 阅读
  6. 【AMBA Bus ACE 总线 9 -- Non-cache IO device】

    2024-05-12 13:02:01       2 阅读
  7. 编译OpenResty遇到找不到OpenSSL的解决办法

    2024-05-12 13:02:01       3 阅读
  8. 汇编个位数求和实验

    2024-05-12 13:02:01       3 阅读
  9. Python梯度下降算法

    2024-05-12 13:02:01       2 阅读
  10. pat乙1030

    2024-05-12 13:02:01       2 阅读