快乐的流畅：个人主页
个人专栏：《C语言》《数据结构世界》《进击的C++》
远方有一堆篝火，在为久候之人燃烧！
文章目录
引言一、结点二、迭代器2.1 成员变量与默认成员函数2.2 operator*2.3 operator->2.4 operator++2.5 operator- -2.6 relational operators
三、list3.1 成员变量3.2 迭代器3.2.1 begin3.2.2 end
3.3 默认成员函数3.3.1 constructor3.3.2 destructor3.3.3 copy constructor3.3.4 operator=
3.4 修改3.4.1 insert3.4.2 push_front3.4.3 push_back3.4.4 erase3.4.5 pop_front3.4.6 pop_back3.4.7 clear3.4.8 swap
总结
引言
因为list结构的特殊性，所以拆分为结点、迭代器和list本身进行学习。
一、结点
细节：
使用struct，标明公有属性（这样从外部调用比较方便）list是带头双向循环链表提供全缺省的默认构造函数
template
struct __list_node
{
__list_node
__list_node
T _data;
__list_node(const T& x = T())
: _prev(nullptr)
, _next(nullptr)
, _data(x)
{}
};
二、迭代器
由于list的每个结点物理空间不连续，导致迭代器不能像之前string、vector那样简单的设计为指针，而是设计为一个类（进行封装），以此完成*、->、++、–等一系列操作。
2.1 成员变量与默认成员函数
细节：
仍然使用struct，标明公有属性成员变量是一个结点的指针提供带参构造函数（其余的默认成员函数不用显式定义，浅拷贝即可）
template
struct __list_iterator
{
typedef __list_node
typedef __list_iterator
node* _node;
__list_iterator(node* n)
: _node(n)
{}
};
此时的迭代器设计，可以说是list乃至STL的精华，天才般地运用了类的优势。
2.2 operator*
细节：
返回引用，为了区别普通迭代器和const迭代器
Ref operator*()
{
return _node->_data;
}
2.3 operator->
细节：
返回指针，为了区别普通迭代器和const迭代器
Ptr operator->()
{
return &_node->_data;
}
2.4 operator++
细节：
为了区分前置和后置，后置参数加上int（无实际意义，以示区分）前置传引用返回，后置传值返回
self& operator++()//前置++
{
_node = _node->_next;
return *this;
}
self operator++(int)//后置++
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
2.5 operator- -
细节：同上
self& operator--()//前置--
{
_node = _node->_prev;
return *this;
}
self operator--(int)//后置--
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
2.6 relational operators
bool operator!=(const self& s)
{
return _node != s._node;
}
bool operator==(const self& s)
{
return _node == s._node;
}
三、list
3.1 成员变量
list类包含了
_head（指向哨兵位）
template
class list
{
public:
typedef __list_node
private:
node* _head;
};
3.2 迭代器
typedef __list_iterator
typedef __list_iterator
3.2.1 begin
细节：
begin()在_head->next使用匿名对象
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
3.2.2 end
细节：
end()在_head使用匿名对象
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
3.3 默认成员函数
3.3.1 constructor
空初始化：创建哨兵位
void empty_init()
{
_head = new node;
_head->_prev = _head;
_head->_next = _head;
}
无参构造
list()
{
empty_init();
}
迭代器区间构造
细节：使用类模板，可以传任意类型的迭代器
template
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
3.3.2 destructor
~list()
{
clear();
delete _head;
_head = nullptr;
}
3.3.3 copy constructor
现代写法
细节：
用迭代器区间构造，构造出临时对象再使用list中的swap，交换*this和tmp的值，完成拷贝构造
list(const list
{
empty_init();
list
swap(tmp);
}
3.3.4 operator=
现代写法
细节：
传参变成传值，这样就会拷贝构造出一个临时对象再使用list中的swap，交换*this和tmp的值，完成赋值重载
list
{
swap(lt);
return *this;
}
3.4 修改
3.4.1 insert
指定位置插入
细节：
在pos之前插入迭代器不会失效
void insert(iterator pos, const T& x)
{
node* cur = pos._node;
node* prev = cur->_prev;
node* new_node = new node(x);
prev->_next = new_node;
new_node->_prev = prev;
cur->_prev = new_node;
new_node->_next = cur;
}
3.4.2 push_front
头插
void push_front(const T& x)
{
insert(begin(), x);
}
3.4.3 push_back
尾插
void push_back(const T& x)
{
insert(end(), x);
}
3.4.4 erase
指定位置删除
细节：
assert断言，防止删除哨兵位返回删除节点的下一位，防止迭代器失效
iterator erase(iterator pos)
{
assert(pos != end());
node* cur = pos._node;
node* prev = cur->_prev;
node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
3.4.5 pop_front
void pop_front()
{
erase(begin());
}
3.4.6 pop_back
void pop_back()
{
erase(--end());
}
3.4.7 clear
清除所有结点（除哨兵位以外）
void clear()
{
iterator it = begin();
while (it != end())
{
erase(it++);
}
}
3.4.8 swap
交换两个list类的值
细节：使用std库中的swap函数，交换各个成员变量的值
void swap(list
{
std::swap(_head, lt._head);
}
总结
学习完list类，对于STL中的精华——迭代器设计，有了更深一步的了解。同时，了解多参数模板的用途和方法，极大提高代码复用程度。
真诚点赞，手有余香
推荐阅读
发表评论