【C++】list

简单了解

list 相关文档

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代
2. list的底层是带头双向****循环链表，链表中每个元素存储在独立的节点中，在节点中可以通过指针访问前后节点
3. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置插入、删除元素的效率较高
4. 与其他序列式容器相比，list最大的缺陷是不支持任意位置的随机访问，只能从已知的位置（通常都是头或尾）开始遍历，寻找要访问的元素

使用

构造

接口	接口说明
list(size_type n, const value_type& val = value_type ())	构造的 list 中包含 n 个值为 val 的元素
list()	构造空的 list
list(const list& x)	拷贝构造函数，用于创建一个与给定 list 相同的新 list
list(InputIterator first, InputIterator last)	用 [first, last) 区间中的元素构造 list。可以从其他容器或迭代器范围中初始化一个新的 list

迭代器

接口	接口说明
begin() + end()	分别返回第一个元素的迭代器和最后一个元素下一个位置的迭代器
rbegin() + rend()	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

反向迭代器这样定义是为了和正向迭代器对称，所以看着有点怪，后面在【Stack && Queue】会详细说明

Capacity

接口	接口说明
empty()	检测 list 是否为空，若是则返回 true，否则返回 false
size()	返回 list 中有效节点的个数

元素访问

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

增删查改

接口	接口说明
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 中的有效元素

迭代器失效

与vector、string等容器不同，list插入数据时，迭代器不会失效；数据删除时，才会发生迭代器失效

模拟实现

本次模拟实现主要目的是借助实现 list 的过程，加深对迭代器****以及类的封装的理解，所以主要是实现迭代器类，一些其他接口不写

节点类

链表是由一个个数据节点链接起来的，所以实现链表之前，我们需要封装一个节点类ListNode

节点有如下属性：

• ListNode* _next，指向下一个节点
• ListNode* _prev，指向前一个节点
• T _data，节点存储的数据，因为可能存储的数据类型可以有很多，所以使用模板

为了方便 list 对节点的管理，要把节点类中成员变量的访问权限设为 public；或者直接使用 struct，默认权限就是 public

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

有了基本的成员变量后，接下来写成员函数

构造函数当然是必不可少的，这里选择全缺省的默认构造函数，给一个T类型的匿名对象作为缺省值

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

没有涉及申请空间的操作，就不需要写析构函数了。到这里节点类就完成了

list的成员

list要对节点进行管理，那么如何管理呢？

• 只需要一个头节点即可。一个空的list对象，就只有一个头节点。如果要对空 list 对象插入数据，就 new 一个节点然后连接到头节点后面即可
• 还可以有一个 _size 来记录节点的个数

template <class T>
class list
{
        typedef ListNode<T> Node;
private:
        Node* _head;
        size_t _size;
};

迭代器类

list不支持随机访问，所以访问list中的数据，只能使用迭代器；而在任意位置插入删除数据也是用的迭代器。所以迭代器对list来说是很重要的。迭代器模拟的就是指针的功能

在 vector和string中，迭代器直接用的是原生指针。vector和string的底层存储都是数组，空间是连续的，原生指针支持 ++ -- + - *等操作，天然就可以当作迭代器来使用

在 list 中，数据 T 存储在节点 Node 中，想要访问不同的数据，就要访问不同的节点，所以如果要用原生指针实现迭代，应该使用Node*

但是仅仅用原生指针不能模拟 list 迭代器。因为各个节点的空间不一定连续，迭代器使用++操作到达的位置是未知的，并不一定是下一个节点；并且Node解引用得到的是Node类型数据，并不是我们需要的T类型数据*

正常情况下，迭代器的行为应该是这样的：

• 到下一个节点，应该使用 iterator = iterator->_next；到前一个结点，iterator = iterator->_prev
• 解引用，应该得到数据_data

所以为了使迭代器正常工作，需要对迭代器 Node* 进行运算符重载。如何做到呢？

将 Node* 封装为一个类，这样就可以自定义迭代器的行为了，如下：

template <class T>
struct ListIterator
{
        typedef ListNode<T> Node;
        Node* _node;
};

构造函数

我们使用迭代器时一定需要一个指针，所以构造函数的参数一定需要一个确定的 Node* node，直接将 node 赋值给 _node 即可

ListIterator(Node* node)
        :_node(node)
{}

operator*

迭代器解引用，应该获得节点的数据**_data的引用**，返回引用就可以修改_data

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

operator++

迭代器++，获得的应该是下一个节点的迭代器

• 返回值应该是一个迭代器****对象
• 可以使用 _node->next 指针构造一个迭代器
• 前置++返回更改后的迭代器，后置++返回更改前的迭代器

// ++it
ListIterator& operator++()
{
        _node = _node->_next;
        return *this;
}
// it++
ListIterator operator++(int)
{
        ListIterator tmp(_node);
        _node = _node->_next;
        return tmp;
}

operator–

// --it
ListIterator& operator--()
{
        _node = _node->_prev;
        return *this;
}
// it--
ListIterator operator--(int)
{
        ListIterator tmp(_node);
        _node = _node->prev;
        return tmp;
}

operator== 和 operator!=

判断两个迭代器相等，只需判断节点指针即可

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

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

搭一个简单的架子

迭代器的基本功能已经完成了，下面就把 list 简单写一写，搭个架子运行看看效果

无参的构造函数

一个空的 list 对象，虽然没有数据节点，但是有一个头节点，并且头节点的 _prev 和 _next 都是指向自己

所以无参构造函数只需 new 一个节点作为头节点，然后修改指针指向即可，顺便置零 _size

list()
{
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
        _size = 0;
}

push_back

void push_back (const value_type& val);

尾插数据，只需new一个新节点储存val，找到链表****的最后一个节点，然后修改链接关系即可。那么怎么定位到最后一个节点呢？

• 带头双向循环链表，头节点的前一个节点就是链表最后一个节点
• 修改最后一个节点和新插入节点的关系
• 修改新插入节点和头节点的关系

void push_back(const T& val)
{
        Node* tail = _head->_prev;
        Node* newnode = new Node(val);

        // tail newnode head
        tail->_next = newnode;
        newnode->_prev = tail;
        newnode->_next = _head;
        _head->_prev = newnode;
        ++_size;
}

迭代器

我们写的迭代器类是 ListIterator，在 list 类中使用时要进行 typedef

class list
{
public:
    typedef ListIterator<T> iterator;
}

在使用时我们不关心迭代器的底层是什么样的，只关心迭代器的用法。不同的容器可能实现迭代器的方法不同，可能是 VectorIterator 或者 StringIterator 等等，但这个和我们使用者无关，使用时是统一的 iterator。都支持 ++ -- **\***等操作

begin

iterator begin();

返回第一个元素的迭代器

• 通过 _head，可以获得第一个节点的指针
• 用指针构造出一个 iterator 匿名对象并返回

iterator begin()
{
        return iterator(_head->_next);
}

甚至还可以再简单一点，不用手动构造匿名对象，直接返回指针，中间会发生隐式类型转换，Node指针自动转为iterator对象

iterator begin()
{
        return _head->_next;
}

end

iterator end();

最后一个元素下一个位置的迭代器

• 最后一个位置的下一个位置就是头节点，直接返回头节点指针即可

iterator begin()
{
        return _head->_next;
}

iterator end()
{
        return _head;
}

测试

此时终于可以创建一个 list 对象，插入数据看看效果了

list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);

// 输出
list<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
        cout << *it << " ";
        ++it;
}
cout << endl;

Capacity

size

size_t size() const
{
        return _size;
}

empty

bool empty()
{
        return _size == 0;
}

增删查改

先实现 insert 和 erase 后，其他的插入删除操作就可以复用了

insert

iterator insert (iterator position, const value_type& val);

在 position 位置之前插入值为 val 的元素，插入成功后返回新插入的第一个元素的迭代器

• 记录 pos 位置的节点指针 cur，然后记录前一个节点的指针 prev
• new一个新节点 newcode
• 重新链接 prev newnode cur 三个节点
• _size加一

iterator insert(iterator pos, const T& val)
{
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* newnode = new Node(val);

        // prev newnode cur
        prev->_next = newnode;
        newnode->_prev = prev;
        newnode->_next = cur;
        cur->_prev = newnode;
        ++_size;

        // 返回新插入第一个元素的迭代器
        return newnode;
}

测试：

erase

iterator erase (iterator position);

删除 pos 位置的元素，成功后返回被删除元素的后一个元素的迭代器

• 记录 pos 位置的节点指针 cur，然后记录前一个节点的指针 prev 和后一个节点的指针 next
• 重新链接 prev next两个节点
• 释放 cur 节点的空间
• _size减一

iterator erase(iterator pos)
{
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* next = cur->_next;

        // pre next
        prev->_next = next;
        next->_prev = prev;
        delete cur;

        --_size;
        return next;
}

测试：

push_back

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

push_front

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

pop_back

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

pop_front

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

swap

两个链表的交换，只需要交换头节点的指针就可以

void swap(list<T>& lt)
{
        std::swap(_head, lt._head);
        std::swap(_size, lt._size);
}

测试：

clear

清空 list 中的有效元素，但是留下头节点

• 使用迭代器与erase，把 list 中的元素删除即可
• 注意：节点删除后，迭代器****就会失效，需要更新迭代器
• 新的迭代器由 erase 返回

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

测试：

完善迭代器类

operator->

如果list中存储的元素是自定义类型，如下：

struct A
{
        A(int a1 = 0, int a2 = 0)
                :_a1(a1)
                ,_a2(a2)
        {}

        int _a1;
        int _a2;
};

现在我们创建一个存储 A 类对象的 list，并插入元素

list<A> lt1;
A aa1(1, 1);
lt1.push_back(aa1); // 有名对象
lt1.push_back(A(2, 2)); // 匿名对象
lt1.push_back({3, 3}); // 多参数的构造函数的隐式类型转换
lt1.push_back({4, 4}); // 多参数的构造函数的隐式类型转换

现在链表的节点存的元素都是 A 类对象

那我们该怎么访问链表中 A 类对象的元素呢？访问节点中的元素可以使用迭代器iterator

迭代器模拟的是原生指针，在这里就是模拟 A*，指针访问指向对象中的数据有两种方法

1. p-> 这种方法应该是最常用的，但是我们的迭代器并未重载->，只重载了解引用
2. (*p). 先解引用，再通过.访问数据，我们暂时先用这种

将链表中的数据输出：

// 输出
list<A>::iterator it = lt1.begin();
while (it != lt1.end())
{
        cout << (*it)._a1 << ":" << (*it)._a2 << endl;
        ++it;
}

测试：

下面来重载->

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

返回的数据是 T*，在这里就是 A*，下面是用法

it->_a1

怎么看怎么怪，明明it->返回的是 A* 指针，怎么后面就直接是数据了？其实完整的语句是这样的：

it.operator->()->_a1
it.operator->()`返回一个 A* 指针，指针再通过`->`访问数据。经过编译器的省略，就变成了`it->_a1

测试：

const迭代器

之前只写了非 const 的迭代器，这里完善 const迭代器

像这样单纯地把迭代器改为 const 版本行不行呢？

class list
{
        typedef ListNode<T> Node;
public:
        typedef ListIterator<T> iterator;

        iterator begin()
        {
                return _head->_next;
        }
        
        iterator end()
        {
                return _head;
        }
        // const迭代器
        const iterator begin() const
        {
                return _head->_next;
        }
        
        const iterator end() const
        {
                return _head;
        }
}

测试一下：

void PrintList(const list<int>& lt) // 常引用，不可修改
{
        // 输出
        list<int>::iterator it = lt.begin();
        while (it != lt.end())
        {
                cout << *it << " ";
                ++it;
        }
        cout << endl;
}

void test6()
{
        list<int> lt1;
        lt1.push_back(1);
        lt1.push_back(2);
        lt1.push_back(3);
        lt1.push_back(4);
        PrintList(lt1);
}

这样看还是可以的，可如果尝试对 list 进行修改呢？

void PrintList(const list<int>& lt) // 常引用，不可修改
{
        // 输出
        list<int>::iterator it = lt.begin();
        while (it != lt.end())
        {
                (*it) += 10; // 修改
                cout << *it << " ";
                ++it;
        }
        cout << endl;
}

运行结果：

数据被修改了，这是怎么回事呢？问题出在这里：

const iterator begin() const
const iterator end() const

const iterator表达的意思和我们需要的不同

• const 修饰的是 iterator 对象，意思是iterator对象本身不可修改
• 而我们需要的const迭代器，需要的是iterator****指向的对象不可修改

iterator指向的对象可不可以被修改，是由 operator* 和 operator-> 返回的数据类型决定的。需要我们对迭代器****类做出修改，在原来迭代器类的基础上，copy一份修改修改就可以了

template <class T>
struct ListConstIterator // const迭代器
{
        typedef ListNode<T> Node;

        ListConstIterator(Node* node)
                :_node(node)
        {}
        
        // 常引用
        const T& operator*()
        {
                return _node->_data;
        }
        // 常量指针
        const T* operator->()
        {
                return &(_node->_data);
        }
        // ......
}

template <class T>
class list
{
        typedef ListNode<T> Node;
public:
        typedef ListIterator<T> iterator;
        // const迭代器
        typedef ListConstIterator<T> const_iterator;

        iterator begin()
        {
                return _head->_next;
        }
        
        iterator end()
        {
                return _head;
        }
        // const迭代器
        const_iterator begin() const
        {
                return _head->_next;
        }
        
        const_iterator end() const
        {
                return _head;
        }
}

测试一下：

void PrintList(const list<int>& lt)
{
        // 输出
        list<int>::const_iterator it = lt.begin(); // const迭代器
        while (it != lt.end())
        {
                (*it) += 10;
                cout << *it << " ";
                ++it;
        }
        cout << endl;
}

运行结果：

使用模板改造迭代器类

虽然上面的做法可以达到目的，但是代码冗余了很多。两个版本的迭代器类的代码几乎是相同的，只有两个函数的返回值类型不同。到这里，很容易想到使用模板来解决，模板最擅长解决这种问题了

使用模板可以将两份代码合并为一份：

• 将引用类型和指针类型作为模板参数

template <class T, class Ref, class Ptr>
struct ListIterator
{
        typedef ListNode<T> Node;

        ListIterator(Node* node)
                :_node(node)
        {}

        // 引用
        Ref operator*()
        {
                return _node->_data;
        }
        // 指针
        Ptr operator->()
        {
                return &(_node->_data);
        }
}

template <class T>
class list
{
        typedef ListNode<T> Node;
public:
        // 两种不同迭代器
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
}

虽然代码合并为了一份，但是本质上还是有两个类，只不过实例化不同类的工作交给了编译器

测试：

完善其他接口

拷贝构造

list (const list& x);

使用已经存在的对象构造一个新的对象

• 这里采用现代写法：不用自己手动进行开空间，拷贝数据等操作，而是使用已经存在的接口自动完成
• 先开一个头节点。由于构造函数也需要开头节点，所以直接把相关操作封装为一个接口，这样构造和拷贝构造都可以用
• 使用范围 for 遍历 x，把 x 的数据插入到新开的头节点

// 开头节点
void empty_init()
{
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
        _size = 0;
}
// 构造
list()
{
        empty_init();
}
// 拷贝构造
list(const list& x)
{
        empty_init();
        for (auto& e : x)
                push_back(e);
}

测试：

赋值拷贝

list& operator= (const list& x);

将已经存在的对象赋值给另一个已存在对象

• 同样是借助现代写法
• 现代写法是传值传参，而不是传引用
• 通过传值传参，拷贝构造出一个临时变量tmp
• 调用 this 的 swap 来与临时变量 tmp 交换数据

list& operator=(list tmp) // 传值传参
{
        swap(tmp);
        return *this;
}

测试：

析构函数

• 首先需要清空有效节点，调用 clear 即可
• 将头节点释放

~list()
{
        clear();
        delete _head;
}

代码

#pragma once

#include <iostream>
using namespace std;

namespace ns1
{
        template <class T>
        struct ListNode
        {
                ListNode(const T& val = T())
                        :_next(nullptr)
                        ,_prev(nullptr)
                        ,_data(val)
                {}
                ListNode* _next;
                ListNode* _prev;
                T _data;
        };

        //template <class T>
        //struct ListIterator
        //{
        //        typedef ListNode<T> Node;

        //        ListIterator(Node* node)
        //                :_node(node)
        //        {}

        //        T& operator*()
        //        {
        //                return _node->_data;
        //        }

        //        T* operator->()
        //        {
        //                return &(_node->_data);
        //        }

        //        // ++it
        //        ListIterator& operator++()
        //        {
        //                _node = _node->_next;
        //                return *this;
        //        }
        //        // it++
        //        ListIterator operator++(int)
        //        {
        //                ListIterator tmp(_node);
        //                _node = _node->_next;
        //                return tmp;
        //        }

        //        // --it
        //        ListIterator& operator--()
        //        {
        //                _node = _node->_prev;
        //                return *this;
        //        }
        //        // it--
        //        ListIterator operator--(int)
        //        {
        //                ListIterator tmp(_node);
        //                _node = _node->prev;
        //                return tmp;
        //        }

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

        //        bool operator!=(const ListIterator& it)
        //        {
        //                return _node != it._node;
        //        }

        //        Node* _node;
        //};
        //
        //template <class T>
        //struct ListConstIterator
        //{
        //        typedef ListNode<T> Node;

        //        ListConstIterator(Node* node)
        //                :_node(node)
        //        {}

        //        const T& operator*()
        //        {
        //                return _node->_data;
        //        }

        //        const T* operator->()
        //        {
        //                return &(_node->_data);
        //        }

        //        // ++it
        //        ListConstIterator& operator++()
        //        {
        //                _node = _node->_next;
        //                return *this;
        //        }
        //        // it++
        //        ListConstIterator operator++(int)
        //        {
        //                ListIterator tmp(_node);
        //                _node = _node->_next;
        //                return tmp;
        //        }

        //        // --it
        //        ListConstIterator& operator--()
        //        {
        //                _node = _node->_prev;
        //                return *this;
        //        }
        //        // it--
        //        ListConstIterator operator--(int)
        //        {
        //                ListIterator tmp(_node);
        //                _node = _node->prev;
        //                return tmp;
        //        }

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

        //        bool operator!=(const ListConstIterator& it)
        //        {
        //                return _node != it._node;
        //        }

        //        Node* _node;
        //};

        template <class T, class Ref, class Ptr>
        struct ListIterator
        {
                typedef ListNode<T> Node;

                ListIterator(Node* node)
                        :_node(node)
                {}

                // 引用
                Ref operator*()
                {
                        return _node->_data;
                }
                // 指针
                Ptr operator->()
                {
                        return &(_node->_data);
                }

                // ++it
                ListIterator& operator++()
                {
                        _node = _node->_next;
                        return *this;
                }
                // it++
                ListIterator operator++(int)
                {
                        ListIterator tmp(_node);
                        _node = _node->_next;
                        return tmp;
                }

                // --it
                ListIterator& operator--()
                {
                        _node = _node->_prev;
                        return *this;
                }
                // it--
                ListIterator operator--(int)
                {
                        ListIterator tmp(_node);
                        _node = _node->prev;
                        return tmp;
                }

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

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

                Node* _node;
        };

        template <class T>
        class list
        {
                typedef ListNode<T> Node;
        public:
                typedef ListIterator<T, T&, T*> iterator;
                typedef ListIterator<T, const T&, const T*> const_iterator;

                iterator begin()
                {
                        return _head->_next;
                }
                
                iterator end()
                {
                        return _head;
                }
                // const迭代器
                const_iterator begin() const
                {
                        return _head->_next;
                }
                
                const_iterator end() const
                {
                        return _head;
                }

                // 开头节点
                void empty_init()
                {
                        _head = new Node;
                        _head->_next = _head;
                        _head->_prev = _head;
                        _size = 0;
                }
                // 构造
                list()
                {
                        empty_init();
                }
                ~list()
                {
                        clear();
                        delete _head;
                }

                // 拷贝构造
                list(const list& x)
                {
                        empty_init();
                        for (auto& e : x)
                                push_back(e);
                }

                list& operator=(list tmp) // 传值传参
                {
                        swap(tmp);
                        return *this;
                }

                size_t size() const
                {
                        return _size;
                }

                bool empty()
                {
                        return _size == 0;
                }

                iterator insert(iterator pos, const T& val)
                {
                        Node* cur = pos._node;
                        Node* prev = cur->_prev;
                        Node* newnode = new Node(val);

                        // prev newnode cur
                        prev->_next = newnode;
                        newnode->_prev = prev;
                        newnode->_next = cur;
                        cur->_prev = newnode;
                        ++_size;

                        // 返回新插入第一个元素的迭代器
                        return newnode;
                }

                iterator erase(iterator pos)
                {
                        Node* cur = pos._node;
                        Node* prev = cur->_prev;
                        Node* next = cur->_next;

                        // pre next
                        prev->_next = next;
                        next->_prev = prev;
                        delete cur;

                        --_size;
                        return next;
                }

                void push_back(const T& val)
                {
                        insert(end(), val);
                }
                void push_front(const T& val)
                {
                        insert(begin(), val);
                }
                
                void pop_back()
                {
                        erase(--end());
                }
                void pop_front()
                {
                        erase(begin());
                }

                void swap(list<T>& lt)
                {
                        std::swap(_head, lt._head);
                        std::swap(_size, lt._size);
                }

                void clear()
                {
                        iterator it = begin();
                        while (it != end())
                        {
                                it = erase(it);
                        }
                }
        private:
                Node* _head;
                size_t _size;
        };
}
xt
                        prev->_next = next;
                        next->_prev = prev;
                        delete cur;

                        --_size;
                        return next;
                }

                void push_back(const T& val)
                {
                        insert(end(), val);
                }
                void push_front(const T& val)
                {
                        insert(begin(), val);
                }
                
                void pop_back()
                {
                        erase(--end());
                }
                void pop_front()
                {
                        erase(begin());
                }

                void swap(list<T>& lt)
                {
                        std::swap(_head, lt._head);
                        std::swap(_size, lt._size);
                }

                void clear()
                {
                        iterator it = begin();
                        while (it != end())
                        {
                                it = erase(it);
                        }
                }
        private:
                Node* _head;
                size_t _size;
        };
}

原文地址：https://blog.csdn.net/2301_77578940/article/details/143028888

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！