做手机网站的好处,建筑设计资质加盟,农产品网站建设计划书,wordpress设置备份前言
各位读者朋友们大家好#xff01;上期我们讲了vector的使用以及底层的模拟实现#xff0c;这期我们来讲list。 目录 前言一. list的介绍及使用1.1 list的介绍1.2 list的使用1.2.1 list的构造1.2.2 list iterator的使用1.2.3 list capacity1.2.4 list element access1.…前言
各位读者朋友们大家好上期我们讲了vector的使用以及底层的模拟实现这期我们来讲list。 目录 前言一. list的介绍及使用1.1 list的介绍1.2 list的使用1.2.1 list的构造1.2.2 list iterator的使用1.2.3 list capacity1.2.4 list element access1.2.5 list modifiers 二. list的模拟实现2.1 list的底层结构2.2 普通迭代器2.3 const迭代器2.4 insert2.5 erase2.6 迭代器失效2.7 list的析构函数2.9 list的构造函数2.8 operator 三. 按需实例化四. initializer_list五. list.h结语 一. list的介绍及使用
1.1 list的介绍
list的文档 这里的list就是双向带头循环链表 1.2 list的使用
list的接口较多我们要先掌握如何正确的使用然后再去深入研究底层的原理以达到可扩展的能力。以下是list的一些常见的重要接口。
1.2.1 list的构造
构造函数(Constructor)接口说明list (size_type n, const value_type val value_type())构造的list中包含n个值为val的元素list()构造空的listlist(const list x)拷贝构造list(InputItetator first,InputIterator last)用一段迭代器区间构造list
list (size_type n, const value_type val value_type()) list() list(const list x) list(InputItetator first,InputIterator last)
1.2.2 list iterator的使用
这里我们暂时将list的迭代器理解为指针该指针指向list中的某一节点
函数声明接口说明begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的reverse_iterator即end位置的迭代器返回begin位置前一个位置的迭代器
可以看到这里的list的迭代器是双向的迭代器 如果想在某个位置插入元素就不能对迭代器进行运算了 这里我们在第三个位置之前插入1314要对begin进行三次自加而不能使用begin3
listint l(5, 520);
int k 3;
listint::iterator it l.begin();
while (k--)
{it;
}
l.insert(it, 1314);
for (auto a : l)
{cout a ;
}
cout endl;1.2.3 list capacity
函数声明接口说明empty检测list是否为空是返回true否则返回falsesize返回list的有效节点个数
void test_list2()
{listint l1,l2;if (l1.empty()){cout true endl;cout l1.size() endl;}else{cout false endl;cout l1.size() endl;}l2.push_back(1314);cout l2.size() endl;
}1.2.4 list element access
函数声明接口说明front返回list的第一个节点中的值的引用back返回list的最后一个节点中的值的引用
void test_list3()
{listint l;l.push_back(520);l.push_back(520);l.push_back(520);l.push_back(520);for (auto a : l){cout a ;}cout endl;l.front() 1314;l.back() 1314;for (auto a : l){cout a ;}
}将第一个和最后一个位置的值改为了1314
1.2.5 list modifiers
函数声明接口说明push_front在list首元素之前插入值为val的元素pop_front删除list的第一个元素push_back尾插值为val的元素emplace_back尾插一个元素pop_back将list的最后一个元素删除insert在pos位置插入值为val的元素erase删除pos位置的元素 push_front pop_front push_back 和 pop_back emplace_back emplace_back在功能上跟push_back类似。但是emplace_back支持直接构造不用再拷贝构造了在最后一种情况下emplace_back比push_back高效。 insert 和 erase splice 将一个链表插到另一个链表的指定位置
void test_list4()
{listint lt1,lt2;lt1.push_back(520);lt1.push_back(520);lt2.push_back(1314);lt2.push_back(1314);lt1.splice(lt1.begin(), lt2);for (auto a : lt1){cout a ;}cout endl;for (auto a : lt2){cout a ;}
}插入后lt2就被置空了。 这一接口也可以用来调整结点的顺序
merge 这一功能的实现的是有序链表的合并 将大的尾插到一个头节点后最后将头节点接到lt1上
上面就讲完了list常用接口的使用下面我们开始模拟实现list
二. list的模拟实现
2.1 list的底层结构
template class T// 链表的节点
struct list_node
{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr){}
};template class T
class list
{typedef list_nodeT Node;
public:
list()
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;
}
private:Node* _head;size_t _size;
};2.2 普通迭代器
因为list的节点在内存中不是连续存储的因此不能使用原生指针作为迭代器我们可以封装一个类来作为迭代器通过运算符重载来实现迭代器的功能。
template class T
struct list_iterator
{typedef list_nodeT Node;typedef list_iteratorT Self;Node* _node;list_iterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* operator - (){return _node-_data;}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 *this;}bool operator(const Self s) const{return _node s._node;}bool operator!(const Self s) const{return _node ! s._node;}
};2.3 const迭代器 但是这样要写成两个类而且两个类的方法只有两个不同很是冗余有没有方法能实现成一个类呢 我们看一下库里是如何实现的
template class T,class Ref,class Ptr
struct list_iterator
{typedef list_nodeT Node;typedef list_iteratorT,Ref,Ptr Self;Node* _node;list_iterator(Node* node):_node(node){}Ptr operator - (){return _node-_data;}Ref operator*(){return _node-_data;}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 *this;}bool operator(const Self s) const{return _node s._node;}bool operator!(const Self s) const{return _node ! s._node;}
};写一段程序来体现一下实例化的过程
2.4 insert iterator insert(iterator pos, const T x)
{Node* newnode new Node(x);Node* cur pos._node;Node* prev cur-_prev;// prev newnode curnewnode-_prev prev;newnode-_next cur;cur-_prev newnode;prev-_next newnode;_size;return newnode;
}有了insert我们可以服复用hinsert来实现push_back和push_front
void push_back(const T x)
{insert(end(), x);
}
void push_front(const T x)
{insert(begin(), x);
}2.5 erase
将pos节点的前节点和后节点相连然后将pos节点释放即可
iterator erase(iterator pos)
{assert(pos ! end());Node* next pos._node-_next;Node* prev pos._node-_prev;next-_prev prev;prev-_next next;delete pos._node;--_size;return next;
}有了erase就可以复用erase来实现pop_back和pop_front了
void pop_back()
{erase(--end());
}
void pop_front()
{erase(begin());
}2.6 迭代器失效 2.7 list的析构函数
~list()
{clear();delete _head;_head nullptr;
}
void clear()
{auto it begin();while (it ! end()){it erase(it);}
}将所有节点删除之后再将头结点释放
2.9 list的构造函数
void empty_init()
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;
}
list()
{empty_init();
}
list(const listT tmp)
{empty_init();for (auto a : tmp){push_back(a);}
}构造一个头节点将tmp的节点尾插到头节点后
2.8 operator listT operator(listT tmp){swap(tmp);return *this;}依旧是现代写法
三. 按需实例化
编译器在对模板进行实例化的时候使用哪些成员函数就实例化哪些成员函数不会全部实例化。
四. initializer_list
C11中支持下面的写法 不需要一直push_back数据这里是因为支持了initializer_list initializer_list底层是两个指针第一个指针指向第一个数据第二个指针指向最后一个数据的下一位置 我们写的list如果要支持这种写法需要写一个新的构造函数
list(initializer_listT il)
{empty_init();for (auto a : il){push_back(a);}
}跟普通的构造函数一样只是参数变了而已最正确的写法应该如下因为我们是构造函数 这样就是隐式类型转换了 所以就有了下面的玩法
五. list.h
namespace Yuey
{template class T// 链表的节点struct list_node{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr){}};template class T, class Ref, class Ptrstruct list_iterator{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr Self;Node* _node;list_iterator(Node* node):_node(node){}Ptr operator - (){return _node-_data;}Ref operator*(){return _node-_data;}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 *this;}bool operator(const Self s) const{return _node s._node;}bool operator!(const Self s) const{return _node ! s._node;}};struct AA{int _a1 520;int _a2 1314;};template class Tclass list{typedef list_nodeT Node;public:typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}list(){empty_init();}list(initializer_listT il){empty_init();for (auto a : il){push_back(a);}}list(const listT tmp){empty_init();for (auto a : tmp){push_back(a);}}~list(){clear();delete _head;_head nullptr;}void clear(){auto it begin();while (it ! end()){it erase(it);}}void swap(listT tmp){std::swap(_head, tmp._head);std::swap(_size, tmp._size);}listT operator(listT tmp){swap(tmp);return *this;}iterator begin(){return iterator(_head-_next);}iterator end(){return _head;}const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return _head;}iterator insert(iterator pos, const T x){Node* newnode new Node(x);Node* cur pos._node;Node* prev cur-_prev;// prev newnode curnewnode-_prev prev;newnode-_next cur;cur-_prev newnode;prev-_next newnode;_size;return newnode;}void push_back(const T x){insert(end(), x);}void push_front(const T x){insert(begin(), x);}iterator erase(iterator pos){assert(pos ! end());Node* next pos._node-_next;Node* prev pos._node-_prev;next-_prev prev;prev-_next next;delete pos._node;--_size;return next;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}private:Node* _head;size_t _size;};
}结语
以上我们就讲完了list的用法以及模拟实现希望对大家有所帮助感谢大家的阅读欢迎大家批评指正
