鹤壁建设网站推广渠道,企业网站建设有哪些书籍,国外建站企业,个体工商户可以搞网站建设1. list的介绍及使用 1.1 list的介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。
2. list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过指针指其前…1. list的介绍及使用 1.1 list的介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。
2. list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指其前一个元素和后一个元素。
3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。
4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
1.2 list的使用
list中的接口比较多此处类似只需要掌握如何正确的使用然后再去深入研究背后的原理已达到可扩展的能力。以下为list中一些常见的重要接口
1.2.1 list的构造 1.2.2 list iterator的使用
list迭代器可以理解成一个指针该指针指向list中的某个节点。实际它是指针的封装。 void testlist1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint::iterator it lt.begin();cout *it endl;while (it ! lt.end()){cout *it ;it;}cout endl;} 1.2.3 list capacity
1.2.4 list element access
int main()
{//listint lt(3);vectorint v{ 4,5 };vectorstring tokens{ 4,13,5,/, };coutevalRPN(tokens)endl;listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);//这里可以直接修改里面第一个元素的值lt.front() 10; for (auto e : lt){cout e ;}cout endl;return 0;
}
1.2.5 list modifiers
以下代码对部分接口进行测试 void testlist3(){listint lt;lt.push_front(1);lt.push_front(2);lt.push_front(3);lt.push_front(4);lt.push_front(5);for (auto e : lt){cout e ;}cout endl;listint lt1;lt1.push_front(10);lt1.push_front(20);lt1.push_front(30);lt1.push_front(40);lt.swap(lt1);for (auto e : lt){cout e ;}cout endl头删后endl;lt.erase(lt.begin());for (auto e : lt){cout e ;}cout endl;} 1.2.6 list的迭代器失效
迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。
删除list容器的所有值 正确写法
void TestListIterator()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));for (auto e : l){cout e ;}auto it l.begin();while (it ! l.end()){//此时it已经指向原来it的下一个迭代器位置l.erase(it); // it l.erase(it);//下面两行为错误写法//l.erase(it);//it;}for (auto e : l){cout e endl;}
}2. list的模拟实现
2.1 模拟实现list
要模拟实现list必须要熟悉list的底层结构以及其接口的含义通过上面的学习这些内容已基本掌握现在我们来模拟实现list。
namespace xwy {templatetypename Tstruct listNode{T _data;listNodeT* _pre;listNodeT* _next;//单参数构造函数listNode(const T val T()):_data(val),_pre(nullptr),_next(nullptr){}};templatetypename T, class Ref, class Ptrstruct _list_iterator{// 受类域的限制typedef listNodeT Node;typedef _list_iteratorT,Ref,Ptr self;Node* _node;_list_iterator(Node *nodenullptr):_node(node){}//操作符重载Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data);}self operator--(){_node _node-_pre;return *this;}self operator-(int a){Node* ptr _node;while (a--ptr){ptr ptr-_pre;}return ptr;}self operator(){_node _node-_next;return *this;}self operator(int){// self tmp(*this) 拷贝构造自己Node* tmp _node;_node _node-_next;return tmp;}bool operator!(const self node)const{return _node ! node._node;}};// 适配器 -- 复用templateclass Iterator, class Ref, class Ptrstruct Reverse_iterator{Iterator _it;typedef Reverse_iteratorIterator, Ref, Ptr self;Reverse_iterator(const Iterator it):_it(it){}//操作符重载Ref operator*(){return *_it;}self operator--(){_it;return *this;}Ptr operator-(){return (*_it);}self operator(){--_it;return *this;}self operator(int){// self tmp(*this) 拷贝构造自己Iterator it _it;--_it;return it;}bool operator!(const self lt) const //const和const比较 非const和const比较{return lt._it ! _it; //不支持那两种类型的比较是因为不存在那两种类型比较的重载}};templatetypename Tclass list{public:typedef listNodeT Node;typedef _list_iteratorT,T,T* iterator; typedef _list_iteratorT, const T, const T* const_iterator;typedef Reverse_iteratoriterator,T,T* reverse_iterator;typedef Reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;//无参构造函数list(){empty_init();}templateclass iteratorlist(iterator first,iterator last){empty_init();while (first ! last){push_back(*first);first;}}//拷贝构造list(const list lt){empty_init();auto it lt.begin();while (it ! lt.end()){push_back(*it);it;}}//迭代器的实现iterator begin() {return _head-_next;}iterator end() {return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}//反向迭代器reverse_iterator rbegin(){return --end();}reverse_iterator rend(){return --begin();}const_reverse_iterator rbegin() const{return --end();}const_reverse_iterator rend() const{return --begin();}void push_back(const T val){Node* newnode new Node(val);newnode-_next _head;_head-_pre-_next newnode;newnode-_pre _head-_pre;_head-_pre newnode;}iterator erase(iterator pos) //在pos位置删除{Node* cur pos._node;Node* prev cur-_pre;Node* next cur-_next;delete cur;prev-_next next;next-_pre prev;return next;}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){Node* cur pos._node;Node* newNode new Node(val);newNode-_next cur;newNode-_pre cur-_pre;cur-_pre-_next newNode;cur-_pre newNode;return pos;}/*void push_back(const T val){insert(_head, val);}*/void push_front(const T val){insert(_head-_next, val);}void swap(listT l){std::swap(l._head, _head);}void clear(){//清理数据,不清头节点iterator it begin();while (it ! end()){it erase(it);//it就是下一个位置}}~list(){clear();delete _head; // 只有节点是new出来需要delete但这个只delete 了一个节点}private:void empty_init(){_head new Node();_head-_next _head-_pre _head;}Node* _head; };
2.2 list的反向迭代器
反向迭代器的就是正向迭代器的--反向迭代器的--就是正向迭代器的因此反向迭代器的实现可以借助正向迭代器即反向迭代器内部可以包含一个正向迭代器对正向迭代器的接口进行包装即可.
templateclass Iterator
class ReverseListIterator
{// 注意此处typename的作用是明确告诉编译器Ref是Iterator类中的类型而不是静态成员变量// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:typedef typename Iterator::Ref Ref;typedef typename Iterator::Ptr Ptr;typedef ReverseListIteratorIterator Self;
public:
//// 构造ReverseListIterator(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(*this);
--_it;
return temp;
}
Self operator--(){
_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
_it;
return temp;
}
//
// 迭代器支持比较
bool operator!(const Self l)const{ return _it ! l._it;}
bool operator(const Self l)const{ return _it ! l._it;}
Iterator _it;
};
3. list与vector的对比
vector与list都是STL中非常重要的序列式容器由于两个容器的底层结构不同导致其特性以及应用场景不同其主要不同如下:
