❤️前言
大家好!,今天为大家带来的一篇博客是关于STL中的list,内容主要包括list的介绍使用、list的模拟实现。以及list与vector的对比。
正文
list的介绍和使用
首先,让我们看看list的文档介绍:
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
- list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
- 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
官方网站list的文档介绍如下:
list - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/list/list/?kw=list list的简单使用在我们学会了vector的使用之后只要多看看list的文档并多加使用就可以很熟悉,因此在这里就不多讲了。
需要提一提的是,由于存储在其中的元素的内存并不是连续的,list并不支持随机访问,也没有提供重载方括号。并且因此它并不适合算法库中的sort()和reverse(),于是在我们想要对list进行排序或者逆置的时候,应该使用list自带的接口,它们的名字与算法库中的一样。
除此之外,使用list时也可能遇到迭代器失效的问题,这时候我们需要重新为迭代器赋值来解决这个问题。
list的模拟实现
list的模拟实现分为三个部分,分别为:list的节点、list的迭代器、list本体。
list_node的模拟实现
首先我们模拟实现list的节点,双向链表需要节点具有前后两个指针:
template<typename T>
struct list_node
{
// 我们初学类模板时常常会忘记写<T>
// 这里需要注意,模板名带上尖括号之后才会成为类型名
list_node<T>* _prev;
list_node<T>* _next;
T _val;
list_node<T>(const T& x = T())
:_prev(nullptr)
,_next(nullptr)
,_val(x)
{}
};
list迭代器的模拟实现
然后我们要接着模拟实现list的迭代器,这里我们有一个很重要的设计,就是设置多个模板参数,对应数据类型,数据的引用类型,数据的指针类型。
设计的思路:当我们设计迭代器类的时候,不仅要考虑普通的迭代器,还要考虑const迭代器,它并不是简单的在迭代器类声明对象前加上const关键字就可以。因为我们的const迭代器并不意味着我们不能改动这个迭代器对象本身,而是我们不能改动此迭代器所指向的数据。因此我们需要对迭代器类的一些接口的返回值类型做改动,也就是 * 号和 -> ,原因是这两个重载运算符会提供操作数据的方式。这种设计很好的减少了代码的冗余,使我们不用再另写一份const迭代器。
除此之外,迭代器实现中比较独特的一点就是->运算符的重载,我们可以看到这里的运算符重载返回值为节点值的地址,那么我们获得了节点数据的地址之后继续要访问节点值的成员,应该要再使用一次->运算符,那么在具体应用中我们就需要使用两个箭头,也就是 iterator->->member ,但是这不符合我们使用->运算符的习惯,于是编译器就为我们简化了一下,只要使用一次箭头,编译器自己会正确识别这样的写法。
template<typename T, typename Ref, typename Ptr>
struct _list_iterator
{
typedef list_node<T> Node;
typedef _list_iterator<T, Ref, Ptr> self;
Node* _node;
_list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &_node->_val;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
_node = _node->_next;
return _node->_prev;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
_node = _node->_prev;
return _node->_next;
}
bool operator!=(const self& it) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
};
除了正向迭代器之外,我们还有一个反向迭代器,反向迭代器的使用规则与正向迭代器完全相反,如果我们直接重新定义一个反向迭代器的类模板,那么我们就需要为每一种迭代器都再写一份反向迭代器,这样代码会非常的冗余。于是这里就引出了一个新的概念——适配器模式。
由于反向迭代器的规则与迭代器完全相反,反向迭代器的许多地方其实是可以复用对应正向迭代器本身的接口。那么我们就将迭代器类型作为一个模板参数传入,然后在反向迭代器内部创建一个正向迭代器,之后就可以直接对其进行相反的操作,这样我们就得到了一个可以复用的反向迭代器模板。代码如下:
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
typedef Reverse_iterator<Iterator, Ref, Ptr> self;
Reverse_iterator(Iterator it)
:_it(it)
{}
Ref operator*()
{
return *_it;
}
Ptr operator->()
{
return &_it->_node->_val;
}
self& operator++()
{
return --_it;
}
self operator++(int)
{
return _it--;
}
self& operator--()
{
return ++_it;
}
self operator--(int)
{
return _it++;
}
bool operator!=(const self& rit) const
{
return _it != rit._it;
}
bool operator==(const self& rit) const
{
return _it == rit._it;
}
private:
Iterator _it;
};
list本身的实现
list本身的实现非常简单,我们之前在数据结构时期已经学过了链表的相关知识,写个双向循环链表应该是不在话下。简单代码如下:
template<typename 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;
reverse_iterator rbegin()
{
return (iterator)_head->_prev;
}
reverse_iterator rend()
{
return (iterator)_head;
}
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
list<T>()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list<T>(const list<T>& lt)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
for (auto& x : lt)
{
push_back(x);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
// 复用insert的代码
void push_back(const T& x)
{
//Node* tail = _head->_prev;
//Node* newnode = new Node(x);
//newnode->_next = tail->_next;
//newnode->_prev = tail;
//tail->_next = newnode;
//_head->_prev = newnode;
//_size++;
insert(end(), x);
}
// 复用erase的代码
void pop_back()
{
//Node* tail = _head->_prev;
//Node* nexttail = tail->_prev;
//_head->_prev = nexttail;
//nexttail->_next = _head;
//delete tail;
//_size--;
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
// pos之前位置插入
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
newnode->_prev = prev;
newnode->_next = cur;
prev->_next = newnode;
cur->_prev = newnode;
_size++;
return newnode;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return next;
}
size_t size()
{
return _size;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
~list<T>()
{
clear();
delete _head;
_head = nullptr;
}
private:
Node* _head;
size_t _size = 0;
};
list和vector的对比
list和vector的底层数据结构分别是链表和数组,它们的区别也就是链表与数组的区别。它们之间的不同点如下:
- list的迭代器不支持随机访问和加减等操作,但是vector的迭代器支持
- list的内存空间不是连续的,而vector的内存空间是连续的
- list在中间和开头插入删除的效率要比vector高得多
- list的查询效率较低
总的来说,这两种容器各有优缺点,我们要根据使用场景进行灵活选择。文章来源:https://www.toymoban.com/news/detail-691992.html
🍀结语
ok,那么这篇拖了许久的博客也终于是写完了,临近开学,希望大家开学快乐呀!文章来源地址https://www.toymoban.com/news/detail-691992.html
到了这里,关于【C++】学习STL中的list的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!