STL之list

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

list模拟实现

一. list的基本框架

template<class T>
struct list_node
{
	list_node<T>* _prev;
	T _data;
	list_node<T>* _next;
};

template<class T>
class list
{
    typedef list_node<T> Node;
private:
    Node* _head;
}

使用库中的list类需要包含头文件#inlcude<list>,并且使用std::命名空间

STL之list

list是一个带头结点的双向循环链表

_head:指向其头结点

二. list_node类

1.构造函数

list_node(const T& val= T())
	:_data(val)
	,_prev(nullptr)
	,_next(nullptr)
{}

每一个结点,创建时_data = val,并将 _prev_next置空(nullptr)。

其中如果没有传val参数,则使用缺省值T():T类型的匿名对象(内置类型,如:int() = 0)

2.其他函数

其他成员函数使用编译器默认生成的函数就行,如:析构函数、拷贝构造、赋值运算符重载……

因为,如

  1. 拷贝构造:内置类型是按照字节方式直接拷贝的;自定义类型是调用其拷贝构造函数完成拷贝的
  2. 析构函数:无动态申请空间需要释放

三. 迭代器(iterator)

和string与vector的顺序存储不同,list存储是链式的。

所以list::iterator不能直接定义为元素指针,因为++、*(解引用)等对指针的操作在这里会出现问题

我们可以来封装原生指针(节点指针)成一个类,在类中完成运算符重载(operator 运算符),使++、*(解引用)等能完成其功能。此时iterator就变成像指针一样的对象了。

1.结构

template<class T, class Refence, class Pointer>
struct _list_iterator
{
    typedef list_node<T> Node;
	Node* _node;
};

2. 构造函数

_list_iterator(Node* node = nullptr)
	:_node(node)
{}

3. 运算符重载

//为书写方便,typedf
typedef _list_iterator<T, Refence, Pointer> iterator;
bool operator!=(const iterator& it)
{
    return _node != it._node;
}

bool operator==(const iterator& it)
{
    return _node == it._node;
}

Refence operator*()
{
    //返回节点的数据的引用
    return _node->_data;
}


Pointer operator->()
{ 
    //返回数据元素的指针
    return &(operator*());
}

// ++it
iterator& operator++()
{
    //自增1位
    _node = _node->_next;
    return *this;
}

// it++
//临时变量不能传引用
iterator operator++(int)
{
    //后置++,返回+1前的值
    iterator tmp(*this);
    _node = _node->_next;
    return tmp;
}

// --it
iterator& operator--()
{
    _node = _node->_prev;
    return *this;
}

// it--
//临时变量不能传引用
iterator operator--(int)
{
    iterator tmp(*this);
    _node = _node->_prev;
    return tmp;
}
operator->

STL之list


->操作符:类对象指针访问其publibc成员
STL之list

四.反向迭代器

反向迭代器与正向迭代器的区别主要是:移动方向不同。如:反向迭代器的++操作是向前走的

因此反向迭代器也需要重载运算符(operator 运算符),我们可以沿用正向迭代器的实现方法:将反向迭代器封装成一个类

同时我们可以使用正向迭代器来适配反向迭代器,即复用正向迭代器的代码

反向迭代器设计时,可以规定和正向迭代器相反
STL之list

因此*rbegin的操作应该是先让rbegin向前移动1位再 *(解引用)

1.结构

template<class Iterator, class Refence, class Pointer>
struct _reverse_iterator
{
    Iterator _rit;
}

反向迭代器类的成员变量是一个正向迭代器的对象(适配)

2.构造函数

_reverse_iterator(const Iterator& it = Iterator())
		:_it(it)
	{}

3.运算符重载

//为书写方便,typedf
typedef _reverse_iterator<Iterator, Refence, Pointer> Self;
Refence operator*()
{
    Iterator tmp = _it;
    return *(--tmp);
}

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

Self& operator++()
{
    --_it;
    return *this;
}

Self& operator--()
{
    ++_it;
    return *this;
}

bool operator!=(const Self& s)
{
    return _it != s._it;
}

五. list常用方法及实现

1. 默认构造函数

a.empty_init
void empty_init()
{
    // 创建并初始化哨兵位头结点
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
}
list()
{
    empty_init();
}

2.迭代器

//正向迭代器
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
//反向迭代器
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

反向迭代器第一个模板参数传入的正向迭代器的类 类型

a. begin
iterator begin()
{
    //返回迭代器对象
    return iterator(_head->_next);
}
const_iterator begin() const
{
    return const_iterator(_head->_next);
}

返回首元素的位置(_head的下一个元素)

b. end
iterator end()
{
    return iterator(_head);
}
const_iterator end() const
{
    return const_iterator(_head);
}

end()返回,尾元素的下一个位置(即 _head)

c.rbegin
reverse_iterator rbegin()
{
    return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
    return const_reverse_iterator(cend());
}
d.rend
reverse_iterator rend()
{
    return reverse_iterator(begin());
}
const_reverse_iterator rend() const
{
    return const_reverse_iterator(cbegin());
}

3.数据访问

a. size
size_t size() const
{
	size_t count = 0;
	iterator cur = begin();
    
	while (cur != end())
	{
		++count;
	}
    
	return count;
}

遍历计数

b. empty
void empty() const
{
    return begin() == end();
}
c. front
T& front()
{
    return *begin();
}
const T& front() const
{
    return *begin();
}

返回首元素的引用

d. back
T& back()
{
    return *(--end());
}
const T& back() const
{
    return *(--end());
}

返回尾元素的引用

4.增删操作

a. insert
iterator insert(iterator pos, const T& val)
{
    //断言处理,避免pos指向一个空指针
    assert(pos._node);
	Node* cur = pos._node;

    Node* newnode = new Node(val);
    Node* prev = cur->_prev;
    Node* next = cur;
    
    //|prev| |newnode| |next|
    newnode->_prev = prev;
    prev->_next = newnode;
    newnode->_next = next;
    next->_prev = newnode;

    return iterator(newnode);
}

在pos前 插入一个值为val的结点

b. push_back
void push_back(const T& val)
{
    insert(end(), val);
}

在尾元素的下一个位置前,插入值为val的结点

c. push_front
void push_front(const T& val)
{
    insert(begin(), val);
}

在首元素的位置前,插入值为val的结点

d. erase
iterator erase(iterator pos)
{
    assert(pos._node);//pos指向的非空指针
    assert(pos != end());//删除的不是尾元素的下一个位置
    
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    
 	//|prev| |cur| |next|
    prev->_next = next;
    next->_prev = prev;
    delete cur;

    return iterator(next);
}

删除pos指向的元素,并返回删除位置的下一个位置的迭代器

e. pop_front
void pop_front()
{
    erase(begin());
}

删除首元素

f. pop_back
void pop_back()
{
    erase(--end());
}

删除尾元素

g.clear
void clear()
{
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);
    }
}

迭代释放所有节点空间(除头节点外)

5.初始化和清理

a. 析构函数
~list()
{
    clear();
    delete _head;
    _head = nullptr;
}

释放所有节点空间

b. n个val的构造
list(size_t n, const T& val = T())
{
    empty_init();

    for (size_t i = 0; i < n; ++i)
        push_back(val);
}
c. 迭代器区间构造
template <class InputIterator>  
list(InputIterator first, InputIterator last)
{
    empty_init();//创建头结点

    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}
d. swap
void swap(list<T>& lt)
{
    std::swap(_head, lt._head);
}
e. 拷贝构造

传统写法:

list(const list<T>& lt)
{
    empty_init();//创建头结点
    
    for (const auto& e : lt)
    {
        push_back(e);
   	}
}

现代写法:

通过一个局部对象,和swap来完成

list(const list<T>& lt)
{
    empty_init();//创建头结点
    
    list<T> temp(lt.begin(), lt.end());
    swap(temp);
}

通过empty_init,对成员变量_head进行初始化,然后和经迭代器区间构造函数得到的temp对象进行交换内容,完成拷贝构造。该函数执行结束,局部对象temp会自动调用析构函数,并销毁。

f. operator=

传统写法:

list<T>& operator=(const list<T> lt)
{
    //如果是自己给自己赋值则不操作
    if (lt != this)
    {
        clear();
        for (const auto& e : lt)
        {
            push_back(e);
        }
    }
    return *this;
}

现代写法:

list<T>& operator=(list<T> lt)
{
    swap(lt);
    return *this;
}

传参时,会调用拷贝构造函数完成对局部对象lt的初始化,然后交换*this和lt的内容,完成对自身对象的赋值。

六.小结

1.代码结构

可以将模拟实现的代码放在自己的命名空间中,避免冲突

#include <iostream>
#include <assert.h>

namespace yyjs
{
    template<class T>
	struct list_node
    {};
    
    template<class T, class Refence, class Pointer>
	struct _list_iterator
    {};
    
    template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
    {};
    
    
template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:

		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
          
    };
}

2.迭代器失效

插入元素时不会导致迭代器失效

iterator insert(iterator pos, const T& x);

在pos结点前插入一个元素,pos指向并未改变。

删除时迭代器会失效

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

对于上例中clear()函数中,每次进行删除操作后,it就是失效的迭代器(原先指向的空间被释放了),所以需要重新对it进行赋值(erase函数返回的是下一个位置的迭代器)。

3. 反向迭代器

由于list底层是一个双向链表,因此可以实现反向遍历等操作(–),所有可以实现其反向迭代器。

关于迭代器可以发现,对于客户(使用者)而言,不需要过多的了解使用的某个容器的底层实现原理,对于如string、vector与list,都提供了一个迭代器(iterator),我们甚至不需要考虑iterator具体是什么:是一个指针还是一个类?

在使用时,auto it = lti.begin(),然后就可以遍历容器的元素,并且他们的操作方法都相同,如it++、*it……


    🦀🦀观看~~文章来源地址https://www.toymoban.com/news/detail-488731.html

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

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

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

相关文章

  • STL——list用法

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

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

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

    2024年02月11日
    浏览(37)
  • STL之list

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

    2024年02月09日
    浏览(33)
  • [STL]list使用介绍

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

    2024年02月15日
    浏览(45)
  • STL——list

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

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

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

    2024年02月06日
    浏览(38)
  • 【STL】:list的模拟实现

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

    2024年02月05日
    浏览(38)
  • stl中的list模拟实现

    首先我们要清楚list是一个带头双向循环的链表。 在下面代码中我们用到了 模板 ,并且用的是 struct 没有用 class ,这是因为我们使用struct时相当于 这一个类是公开的 ,当然我们也可以使用class但是得使用友元函数比较麻烦。 我们可以查看stl的源码进行查看,如下: 我们可以

    2024年02月02日
    浏览(41)
  • 【STL】list的模拟实现

    目录 前言 结构解析 默认成员函数 构造函数 拷贝构造 赋值重载 析构函数 迭代器 const迭代器 数据修改 insert erase 尾插尾删头插头删 容量查询 源码  🍉list之所以摆脱了单链表尾插麻烦,只能单向访问等缺点,正是因为其在结构上升级成了带头双向循环链表。不仅如此,lis

    2024年02月06日
    浏览(39)
  • 【STL】模拟实现简易 list

    目录 1. 读源码 2. 框架搭建  3. list 的迭代器 4. list 的拷贝构造与赋值重载 拷贝构造 赋值重载 5. list 的常见重要接口实现 operator--()  insert 接口 erase 接口 push_back 接口 push_front 接口 pop_back 接口 pop_front 接口 size 接口 clear 接口 别忘了析构函数 源码分享 写在最后: 读源码千万

    2024年02月16日
    浏览(32)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包