昆明网站建设哪家,如何在手机上学编程,深圳网站建设软件开发,建设网站开发公司快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《C语言》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 引言一、结点二、迭代器2.1 成员变量与默认成员函数2.2 operator*2.3 operator-2.4 operator2.5 operator- … 快乐的流畅个人主页 个人专栏《C语言》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 引言一、结点二、迭代器2.1 成员变量与默认成员函数2.2 operator*2.3 operator-2.4 operator2.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是带头双向循环链表提供全缺省的默认构造函数
templateclass T
struct __list_node
{__list_nodeT* _prev;__list_nodeT* _next;T _data;__list_node(const T x T()): _prev(nullptr), _next(nullptr), _data(x){}
};二、迭代器
由于list的每个结点物理空间不连续导致迭代器不能像之前string、vector那样简单的设计为指针而是设计为一个类进行封装以此完成*、-、、–等一系列操作。
2.1 成员变量与默认成员函数
细节
仍然使用struct标明公有属性成员变量是一个结点的指针提供带参构造函数其余的默认成员函数不用显式定义浅拷贝即可
templateclass T, class Ref, class Ptr
struct __list_iterator
{typedef __list_nodeT node;typedef __list_iteratorT, Ref, Ptr self;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指向哨兵位
templateclass T
class list
{
public:typedef __list_nodeT node;
private:node* _head;
};3.2 迭代器
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_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 class InputIterator
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 listT lt)
{empty_init();listT tmp(lt.begin(), lt.end());swap(tmp);
}3.3.4 operator
现代写法
细节
传参变成传值这样就会拷贝构造出一个临时对象再使用list中的swap交换*this和tmp的值完成赋值重载
listT operator(listT lt)
{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(listT lt)
{std::swap(_head, lt._head);
}总结
学习完list类对于STL中的精华——迭代器设计有了更深一步的了解。同时了解多参数模板的用途和方法极大提高代码复用程度。 真诚点赞手有余香
