admin管理员组

文章数量:1794759

C++——list的模拟实现

文章目录

• 接口总览
• list结点的模拟实现
• list迭代器的模拟实现
• • 迭代器类的模板参数说明
  • 构造函数
  • ++运算符的重载
  • - - 运算符的重载
  • ==运算符的重载
  • !=运算符的重载
  • *运算符的重载
  • ->运算符的重载
• list的模拟实现
• • 默认成员函数
  • • 构造函数
    • 拷贝构造函数
    • 赋值运算符重载函数
    • 析构函数
  • 迭代器相关函数
  • 访问容器相关函数
  • 插入、删除函数
  • • insert
    • erase
    • push_front和push_back
    • pop_front和pop_back
  • 其他函数
  • • size
    • empty
    • clear
    • swap

接口总览

namespace NZB
{// 模拟实现list结点template<class T>struct _list_node{_list_node(const T& val = T()); // 构造结点//成员变量T _val;                 // 数据_list_node<T>* _next;   // 后向指针_list_node<T>* _prev;   // 前向指针};// 模拟实现list迭代器template<class T, class Ref, class Ptr>struct _list_iterator{typedef _list_node<T> node;// 重命名typedef _list_iterator<T, Ref, Ptr> self;_list_iterator(node* pnode);  // 构造函数// 运算符重载self operator++();self operator--();self operator++(int);self operator--(int);bool operator==(const self& s) const;bool operator!=(const self& s) const;Ref operator*();Ptr operator->();node* _pnode; // 指向结点的指针};// 模拟实现listtemplate<class T>class list{public:typedef _list_node<T> node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;// 默认成员函数list();list(const list<T>& lt);list<T>& operator=(const list<T>& lt);~list();// 迭代器相关函数iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;// 访问容器相关函数T& front();T& back();const T& front() const;const T& back() const;// 插入、删除函数void insert(iterator pos, const T& x);iterator erase(iterator pos);void push_back(const T& x);void pop_back();void push_front(const T& x);void pop_front();// 其他函数size_t size() const;void clear();bool empty() const;void swap(list<T>& lt);private:node* _head; //指向链表头结点的指针};
}

list结点的模拟实现

list底层实际上就是一个带头双向循环链表

实现list首先要实现它的结点类，从图中我们可以看出每个结点的成员变量为：存储数据的变量，指向前一个结点的指针和指向后一个结点的指针。

为了方便新结点的创建，还需要成员函数用于构造结点。

template<class T>
struct _list_node
{_list_node(const T& val = T()) // 构造结点:_next(nullptr), _prev(nullptr), _data(x){}//成员变量T _val;                 // 数据_list_node<T>* _next;   // 后向指针_list_node<T>* _prev;   // 前向指针
};

注意：当构造结点没有传入数据时，使用list默认构造函数构造出来的值

list迭代器的模拟实现

迭代器的作用是让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问。

list迭代器不同与string和vector迭代器，string类和vector类储存的数据是连续的，它们的迭代器类似指针，但是list类存储的数据是随机的，不能间单的用指针加减来进行访问。

为了使list满足迭代器的要求，我们对list结点进行封装，对结点指针的各种运算符操作进行重载。

迭代器类的模板参数说明

模板参数列表当中为什么有三个模板参数？

template<class T, class Ref, class Ptr>

在list的模拟实现当中，我们typedef了两个迭代器类型，普通迭代器和const迭代器。

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

迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。

当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。

构造函数

迭代器中成员变量就只有一个，那就是结点指针，构造时直接给指针构造一个迭代器对象即可

_list_iterator(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(*this);_node = _node->_prev;return tmp;
}

==运算符的重载

判断两个迭代器指针指向的结点是否相同即可
（这里不会对两个结点修改，最好用const迭代器）

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

!=运算符的重载

!=和==写法类似，一个是判断迭代器指针指向的结点是否不同，一个是判断迭代器指针指向的结点是否相同

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

*运算符的重载

这里类似指针的解应用操作，直接返回迭代器指针指向的结点，因为可能会对解引用的数据进行修改所以返回引用类型。

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

->运算符的重载

当结点储存为自定义类型时，例如结点储存也为结构体，这时再用*运算符就不太合适了，为了更好访问结点储存这里我们引入了->运算符。

->返回结点中所存储数据的地址即可

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

list的模拟实现

默认成员函数

构造函数

list是一个带头双向循环链表，构造时创建一个头结点，让其前向指针和后向都指向自己

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

拷贝构造函数

新建一个结点，让其前向指针和后向指针都指向自己，再将要拷贝的数据遍历尾插到该结点中。

list(const list<T>& it)
{_head = new Node;_head->_next = _head;_head->_prev = _head;for (const auto& e : it){push_back(e);}
}

赋值运算符重载函数

传统写法

先用clear函数清理原链表留下头结点，再将新数据遍历尾插

list<T>& operator=(const list<T>& lt)
{if (this != &lt){clear();for (const auto& e : lt){push_back(e);}}return *this;
}

现代写法

现代写法的代码量较少，首先利用编译器机制，故意不使用引用接收参数，通过编译器自动调用list的拷贝构造函数构造出来一个list对象，然后调用swap函数将原容器与该list对象进行交换，出程序后临时拷贝出的list被销毁。

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

析构函数

先调用clear函数清理结点留下头结点，再将头结点释放并置空

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

迭代器相关函数

begin和end

从string和vector类中我们知道，begin函数返回的是第一个数据的迭代器，end函数返回的是最后一个数据的下一个位置的迭代器，在list类中，begin函数返回的是头指针的下一个结点的迭代器，end函数返回的是头结点的迭代器（最后一个结点的下一个结点就是头结点）

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

我们还需要构造一对用于const对象的迭代器

const_iterator begin() const
{return const_iterator(_head->_next);
}const_iterator end() const
{return const_iterator(_head);
}

访问容器相关函数

front和back函数分别用于获取第一个有效数据和最后一个有效数据，返回第一个有效数据和最后一个有效数据即可

T& front()
{return *begin(); 
}
T& back()
{return *(--end()); 
}

不要忘了再写一份const版本用于const类型链表

const T& front() const
{return *begin(); 
}
const T& back() const
{return *(--end());
}

插入、删除函数

insert

作用：在指定位置插入数据。
实现思路：先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，接着根据所给数据x构造一个待插入结点，之后再建立新结点与cur，prev之间的双向关系。

iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);// 建立新结点与cur，prev之间的双向关系prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}

erase

作用：删除指定位置的数据。
实现思路：先根据所给迭代器得到该位置处的结点指针cur，然后通过cur指针找到前一个位置的结点指针prev，以及后一个位置的结点指针next，紧接着释放cur结点，最后建立prev和next之间的双向关系。

iterator erase(iterator pos)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;// 建立next，prev之间的双向关系prev->_next = next;next->_prev = prev;return iterator(next);
}

push_front和push_back

作用：头插，尾插
实现思路：套用先前实现的insert函数，利用迭代器相关函数begin和end进行头插和尾插

void push_front(const T& x)
{insert(begin(), x);
}void push_back(const T& x)
{insert(end(), x);
}

pop_front和pop_back

作用：头删，尾删
实现思路：套用先前实现的erase函数，利用迭代器相关函数begin和end进行头删和尾删（注意：尾删是删除最后一个数据，用end迭代器时需要它的前一个结点）。

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

其他函数

size

作用：获取当前容器有效数据的个数
实现思路：设置变量，遍历容器，记录有效数据的个数

size_t size()
{int n = 0;iterator it = begin();// 遍历容器while (it != begin()){++it;++n;}return n;
}

empty

作用：判断容器是否为空
实现思路：判断它的begin和end迭代器是否指向同一块空间

bool empty()
{return begin() == end();
}

clear

作用：清空容器
实现思路：遍历删除结点只保留头结点

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

swap

作用：交换链表
实现思路：list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换即可。

void swap(list<T>& lt)
{::swap(_head, lt._head);//交换两个容器当中的头指针
}

本文标签： Clist的模拟实现