文章目录
前言
C++list类的常见函数及其模拟实现
list的底层是一个双向循环链表。每个元素存储在互不相关的独立节点中，在节点中通过指针来访问前一个元素和后一个元素。与其他序列式容器相比(array,vector,deque)，list可以在任意位置以O(1)的效率进行插入与删除，但其本身不可随机访问(因此不需要去重载[ ]符号)。
接下来我们将依次介绍list的模拟实现。
一、list内部成员有什么？
首先定义了一个命名空间jjw
接着在jjw内首先定义了一个双向链表的数据结构，并完成它的默认构造。
随后定义了一个Node* 类型的_head指针，指向这个链表的头结点。并且定义了一个_size表示链表结点的数量。
最后定义了一个Create_node函数，这个函数来为_head开辟一份空间,并让其_next,_pre指向其本身完成初始化。
namespace jjw
{
template<class T>
struct ListNode{
ListNode(const T& val=T())
{
_pre = nullptr;
_next = nullptr;
_val = val;
}
ListNode<T>* _pre;
ListNode<T>* _next;
T _val;
};
template<class T>
class list
{
typedef ListNode<T> Node;
public:
// 一系列函数
private:
void Create_node()
{
_head = new Node;
_head->_next = _head;
_head->_pre = _head;
_size = 0;
}
Node* _head;
size_t _size;
};
}
二、构造函数以及析构函数
1.默认构造
直接调用Create_node函数即可。
list()
{
Create_node();
}
2.传参构造
传入两个参数，int n表示该链表的结点数目，val表示每个结点的值。
首先调用Create_node完成_head的初始化。
然后创建一个变量p用来表示每次链尾的元素。
最后通过for循坏依次插入元素，注意插入后需要将_size++。（后面我们可以直接调用push_back完成）
list(int n, const T& val = T())
{
Create_node();
Node* p = _head;
for (int i = 0; i < n; i++)
{
Node* temp = new Node;
temp->_val = val;
temp->_next = p->_next;
temp->_pre = p;
p->_next = temp;
_head->_pre = temp;
p = temp;
_size++;
//push_back(val);
}
}
3.迭代器构造
首先定义了一个迭代器模板，不管什么类型的迭代器都可以进行初始化。
然后就和上诉基本一样，循环遍历区间，依次在链表末尾插入元素。
template<class Iterator>
list(Iterator start,Iterator finish)
{
Create_node();
while (start != finish)
{
push_back(*start);
++start;
}
}
4.深拷贝以及运算符=的重载
1.深拷贝
和上述实现差不多，依次遍历lt，插入到链表的末端。
list(const list<T>& lt)
{
Create_node();
for (auto e : lt)
{
push_back(e);
}
}
2.=的重载
首先通过lt创建了一个临时变量temp，然后将temp变量和this交换。
最后返回this。（注意这里函数返回值类型不可以加引用）
list operator=(list<T>& lt)
{
list temp(lt);
swap(lt);
return *this;
}
5.析构函数
首先调用clear函数清除每个结点（后面会介绍clear函数）。
然后释放_head 头结点指针完成析构。
~list()
{
clear();
delete _head;
_head = nullptr;
}
三、迭代器的模拟实现
1.正向迭代器
首先定义了三个模板 T表示链表中元素的类型，Ref表示T&，Ptr表示T*(重载->运算符需要)。
然后在List_Iterator内定义了Node* _node,并且定义了其默认构造。
接着对迭代器一系列的操作进行了重载，来实现正向迭代器。
在List类中，begin返回第一个元素的位置，即_head->_next。
end返回最后一个元素的下一个位置，即_head。
list不同与string和vector，它需要通过一个类来封装实现迭代器。
namespace jjw
{
template<class T,class Ref,class Ptr>
struct List_Iterator{
typedef ListNode<T> Node;
typedef List_Iterator<T, Ref, Ptr> self;
typedef Ref Ref; //反向迭代器要用到
typedef Ptr Ptr; //反向迭代器要用到
List_Iterator(Node* node=nullptr)
{
_node = node;
}
bool operator!=(const self it)
{
return _node != it._node;
}
bool operator==(const self it)
{
return _node == it._node;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self temp(_node);
_node = _node->_next;
return temp;
}
self& operator--()
{
_node = _node->_pre;
return *this;
}
self operator--(int)
{
self temp(_node);
_node = _node->_pre;
return temp;
}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &(_node->_val);
}
Node* _node;
};
template<class T>
class list{
public:
typedef ListNode<T> Node;
typedef List_Iterator<T, T&, T*> iterator;
typedef List_Iterator<T, const T&,const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return _head;
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
};
}
2.反向迭代器
反向迭代器通过封装正向迭代器来实现。
rbegin返回end()的位置，rend返回begin()的位置。
++去- -，- -去++。
注意这里的解引用操作，先 - - 再解引用。
template<class Iterator>
struct Reverse_Iterator
{
typedef Reverse_Iterator<Iterator> self;
typedef typename Iterator::Ref Ref;//typename表示取出的Ref和Ptr是Iterator中的一个类型
typedef typename Iterator::Ptr Ptr;//而不是一个静态成员变量。
Reverse_Iterator(Iterator it)
{
_it = it;
}
Ref operator*() //返回前一个位置的元素值
{
Iterator temp(_it);
--temp;
return *temp;
}
Ptr operator->()
{
return &(operator*());
}
self& operator++()
{
--_it;
return *this;
}
self operator++(int)
{
self temp(_it);
--_it;
return temp;
}
self& operator--()
{
++_it;
return *this;
}
self operator--(int)
{
self temp(_it);
++_it;
return temp;
}
bool operator!=(const self l)
{
return _it != l._it;
}
bool operator==(const self l)
{
return _it == l._it;
}
Iterator _it;
};
template<class T>
class list{
public:
typedef ListNode<T> Node;
typedef Reverse_Iterator<iterator> reverse_iterator;
typedef Reverse_Iterator<const_iterator> const_reverse_iterator;
reverse_iterator rbegin()
{
return reverse_iterator(_head->_pre);
}
reverse_iterator rend()
{
return reverse_iterator(_head->_next);
}
const_reverse_iterator rbegin()const
{
return const_reverse_iterator(_head->_pre);
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(_head->_next);
}
};
四、常见函数及其实现
1.insert函数
在pos位置前插入一个值为val的结点。
最后更新_size
注意插入完返回插入后结点的迭代器，防止出现迭代器失效问题。
iterator insert(iterator pos,const T& val)
{
Node* temp = new Node;
temp->_val = val;
temp->_pre = pos._node->_pre;
pos._node->_pre->_next = temp;
temp->_next = pos._node;
pos._node->_pre = temp;
_size++;
return iterator(temp);
}
2.erase函数
删除pos当前位置的结点，并释放它的空间。
最后更新_size
注意：返回pos的下一个结点的迭代器，否则会出现迭代器失效。
iterator erase(iterator pos)
{
Node* p = pos._node->_next;
p->_pre = pos._node->_pre;
pos._node->_pre->_next = p;
delete pos._node;
pos = nullptr;
_size--;
return iterator(p);
}
3.clear函数
依次遍历删除每一个结点，并释放它们的空间。
最后重置一下_head的_next和_pre指针，防止出错。
void clear()
{
Node* p = _head->_next;
while (p != _head)
{
_head->_next = p->_next;
p->_next->_pre = _head;
delete p;
p = _head->_next;
_size--;
}
_head->_next = _head;
_head->_pre = _head;
}
4.push_back和push_front函数
直接调用insert函数即可。
void push_back(const T& val)
{
insert(end(), val);
}
void push_front(const T& val)
{
insert(begin(), val);
}
5.pop_back和pop_front 函数
直接调用erase函数即可。
注意pop_back应传入最后一个元素的迭代器，即_head->_pre。
void pop_back()
{
erase(end()._node->_pre);
}
void pop_front()
{
erase(begin());
}
6.resize函数
1.若newsize小于_size,则直接pop_back
2. 若newsize大于_size,则直接push_back
直到newsize==size
void resize(size_t newsize, const T& val=T())
{
if (newsize < _size)
{
while (newsize != _size)
pop_back();
}
else
{
while (newsize != _size)
push_back(val);
}
}
7.front和back函数
因为链表不支持随机访问，但其访问首元素和尾元素的效率很高。
front返回首元素的值，back返回尾元素的值。
T& front()
{
return _head->_next->_val;
}
const T& front()const
{
return _head->_next->_val;
}
T& back()
{
return _head->_prev->_val;
}
const T& back()const
{
return _head->_prev->_val;
}
8.swap,empty和size函数
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
size_t size()
{
return _size;
}
bool empty()
{
return _size == 0;
}
总结
以上就是list的常用函数以及模拟实现（本人小白一枚，若有错误还望各位指正）
完整的代码存放在gitee上：https://gitee.com/jj-wen/c-beginner/blob/master/06.21%EF%BC%88list%EF%BC%89/06.21%EF%BC%88list%EF%BC%89/list.h
学习任重而道远，希望自己可以坚持下去。