STL_List与萃取

这篇具有很好参考价值的文章主要介绍了STL_List与萃取。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

List

参考文章: https://blog.csdn.net/weixin_45389639/article/details/121618243

List源码

STL_List与萃取,c++,开发语言,stl

List中节点的定义:
list是双向列表,所以其中节点需要包含指向前一节点和后一节点的指针, data是节点中存储的数据类型

template <class _Tp>
struct _List_node {
  typedef void* _Void_pointer;
  _Void_pointer _M_next;
  _Void_pointer _M_prev;
  _Tp _M_data;
};

List列表的定义

template<class T,class Alloc=alloc>
class list
{
protected:
	typedef __list_node<T> list_node;
public:
	typedef list_node* link_type;
    typedef __list_iterator<T,T&,T*>iterator;
protected:
    link_type node;
...
}

list(双向链表),在GNU2.9源码中,list类中维护了node这个属性,这个属性就是一个包含两个指针prev、next和当前data的结构体。基于容器都要满足前闭后开的原则,在list的头部会添加一个灰部地带,begin()获得灰部地带下一个节点,end()获得灰部地带。

STL_List与萃取,c++,开发语言,stl

List迭代器

list_iterator其中定义了5种参数,这五种参数是为了Iterator traits做准备
在STL的算法中,需要传入容器的迭代器,然后根据推断判断出迭代器的类型。

  • bidirectional_iterator_tag :指明迭代器类别,双向列表指针迭代器、单向列表指针迭代器、任意方向链表指针迭代器
  • T(value_type):迭代器指向的数据类型
  • ptrdiff_t(difference_type) 两个迭代器之间的距离,用什么type表现
  • ptr(pointer) 后两个,在此版本中没有使用
  • Ref(reference)

迭代器源码

// __list_iterator源码
template<class T,class Ref,class Ptr>
struct __list_iterator
{
	typedef __list_iterator<T,Ref,Ptr> self;
	typedef bidirectional_iterator_tag iterator_category;
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef __list_node<T>* link_type;
	typedef ptrdiff_t difference_type;

	link_type node;

	reference operator*()const{return *(node).data;}
	pointer operator->()const{return &(operator*());}
	self& operator++(){
		node = (link_type)(*node).next;
		return *this;
	}
	self operator++(int){
		self temp = *this;
		++*this;
		return temp;
	}
	...
};

迭代器萃取机Iterator traits

template<typename _ForwardIterator>
inline void rotate(_ForwardIterator __first,_ForwardIterator __middle,_ForwardIterator __last){
	...
	std::__rotate(__first,__middle,__last,std::__iterator_category(__first));
}


template<typename _Iter>
inline typename iterator_traits<_Iter>::iterator_category __iterator_category(const _Iter&){
	return typename iterator_traits<_Iter>::iterator_category();
}

迭代器是算法和容器的桥梁
算法执行,需要获取迭代器包含的5种类型的参数
如上述所示为算法rotate的部分代码,可知算法内部还需要做Iterator类型获取操作
STL_List与萃取,c++,开发语言,stl

​同时为了考虑兼容性的问题,就在迭代器和算法之间加了一中间层"萃取机"(traits),同时也是为了用它来辨别iteratorclass类型还是non-class(指针)类型

那么问题来了,traits是如何分辨class和non-class类型的iterator呢?答案是partial specialization(模板的偏特化)。

// iterator为class类型,直接取默认泛型
template<class I>
struct iterator_traits {
    typedef typename I::iterator_category 	iterator_category;
    typedef typename I::value_type 			value_type;
    typedef typename I::difference_type 	difference_type;
    typedef typename I::pointer 			pointer;
    typedef typename I::reference 			reference;
};

// iterator为指针
template<class T>
struct iterator_traits<T *> {
    typedef random_access_iterator_tag 		iterator_category;
    typedef T 								value_type;
    typedef ptrdiff_t 						difference_type;
    typedef T*								pointer;
    typedef T&								reference;
};

// iterator为常量指针
template<class T>
struct iterator_traits<const T *> {
    typedef random_access_iterator_tag 		iterator_category;
    typedef T 								value_type;	
    typedef ptrdiff_t 						difference_type;
    typedef const T*						pointer;
    typedef const T&						reference;
};

​ 其中value_type的主要目的是用来声明变量,而声名一个无法被赋值的变量没什么用,所以iterator(即使是const iterator)的value_type不应加上const文章来源地址https://www.toymoban.com/news/detail-861353.html

到了这里,关于STL_List与萃取的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • [STL]list使用介绍

    注:本文测试环境是visual studio2019。 list是可以在常量时间内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 list与

    2024年02月15日
    浏览(65)
  • STL list基本用法

    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 构造函数和前面的容器用法相同 赋值

    2024年02月11日
    浏览(47)
  • STL——list

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

    2024年01月21日
    浏览(45)
  • STL——list详解

    1.1 初始化 在C++11之前,std::list容器没有提供初始化列表的构造函数,因此需要使用push_back或push_front函数向列表中添加元素。以下是一些常见的std::list初始化方式: 使用默认构造函数创建空列表 使用列表初始化语法创建列表 使用指定大小和默认值创建列表 使用迭代器创建列

    2024年02月06日
    浏览(43)
  • STL——list用法

    1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 2、list就是一个带头双向循环链表, list通常在任意位置进行插入、移除元素的执行效率更好。 3、 list最大的缺陷是不支持任意位置的随机访问。 有了前面使用string和vector的

    2024年02月12日
    浏览(46)
  • STL之list

    使用库中的list类需要包含头文件 #inlcudelist ,并且使用 std:: 命名空间 list是一个 带头结点的双向循环链表 _head :指向其头结点 1.构造函数 每一个结点,创建时 _data = val,并将 _prev 和 _next 置空(nullptr)。 其中如果没有传val参数,则 使用缺省值T() :T类型的匿名对象(内置类型

    2024年02月09日
    浏览(39)
  • 【STL】:list用法详解

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关list的使用,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 C + + 专 栏   : C++ Linux 专 栏 

    2024年02月06日
    浏览(39)
  • 【C++】STL---list

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

    2024年02月11日
    浏览(41)
  • C++ STL list

    ✅1主页:我的代码爱吃辣 📃2知识讲解:C++之 STL list介绍和模拟实现 ☂️3开发环境:Visual Studio 2022 💬4前言:上次我们详细的介绍了vector,今天我们继续来介绍一下TSTL中的另外一个容器list。list在基础的功能和结构上就是一个双向带头的循环链表,实现起来基本不难,但是

    2024年02月13日
    浏览(38)
  • 【STL】list的使用

    学习C++途中自然绕不过STL,在这个系列文章之中 我们讲了string的使用和string的模拟实现,以及vector的使用、vector的模拟实现。 感兴趣的可以翻翻看。 目录 系列文章 前言 默认成员函数 构造函数 拷贝构造 赋值重载 迭代器 容量查询 数据访问 数据修改 assign 头插头删尾插尾删

    2024年02月06日
    浏览(88)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包