权重7以上的网站,品牌设计需要学什么,dz论坛怎么做视频网站,金乡网站建设多少钱文章目录 1、list的介绍与使用1.1 list的介绍1.2 list的使用 2、list迭代器3、list的构造4、list常用接口的实现4.1 list capacity4.2 插入删除、交换、清理4.2.1 insert任意位置插入4.2.2 push_front头插4.2.3 push_back尾插4.2.4 erase任意位置删除4.2.5 pop_front头删4.2.6 … 文章目录 1、list的介绍与使用1.1 list的介绍1.2 list的使用 2、list迭代器3、list的构造4、list常用接口的实现4.1 list capacity4.2 插入删除、交换、清理4.2.1 insert任意位置插入4.2.2 push_front头插4.2.3 push_back尾插4.2.4 erase任意位置删除4.2.5 pop_front头删4.2.6 pop_back尾删4.2.7 swap()4.2.8 clear 5、list迭代器失效问题6、list与vector对比 1、list的介绍与使用
1.1 list的介绍
list文档介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) 1.2 list的使用
list中的接口比较多此处类似只需要掌握如何正确的使用然后再去深入研究背后的原理已达到可扩展的能力。
2、list迭代器
此处我们可暂时将迭代器理解成一个指针该指针指向list中的某个节点。 list我们都知道它不是连续的空间是我们将下一个位置的地址保存起来通过地址走到下一个因此我们需要重载一些运算符。 后移的前置后置 前移的 --前置后置 解引用的*- 相等判断的 !
这里我们为list节点创建一个类后面直接使用这个类就可以了再写一个缺省的构造函数为后面开节点提供便利。
// List的节点类
templateclass T
struct ListNode
{ListNode(const T val T()):_pPre(nullptr),_pNext(nullptr),_val(val){}ListNodeT* _pPre;ListNodeT* _pNext;T _val;
};//List的迭代器类
templateclass T, class Ref, class Ptr
class ListIterator
{typedef ListNodeT* PNode;typedef ListIteratorT, Ref, Ptr Self;
public:ListIterator(PNode pNode nullptr):_pNode(pNode){}ListIterator(const Self l){_pNode l._pNode;}T operator*(){return _pNode-_val;}T* operator-(){return _pNode-_val;}Self operator(){_pNode _pNode-_pNext;return *this;}Self operator(int){Self tmp(*this);_pNode _pNode-_pNext;return tmp;}Self operator--(){_pNode _pNode-_pPre;return *this;}Self operator--(int){Self tmp(*this);_pNode _pNode-_pPre;return tmp;}bool operator!(const Self l){return _pNode ! l._pNode;}bool operator(const Self l){return _pNode l._pNode;}//private:PNode _pNode;
};3、list的构造
构造函数constructor接口说明list (size_type n, const value_type val value_type())构造的list中包含n个值为val的元素list()构造空的listlist(const list x)拷贝构造函数list(InputIterator first, InputIterator last)用[first, last)区间中的元素构造list
构造我们已经写了太多了对于这些接口直接秒杀。 空参构造list
list()
{_pHead new Node;_pHead-_pNext _pHead;_pHead-_pPre _pHead;
}拷贝构造list
list(const listT l)
{_pHead new Node;_pHead-_pNext _pHead;_pHead-_pPre _pHead;for (auto e : l){push_back(e);}
}n个值为val的构造
list(int n, const T value T())
{_pHead new Node;_pHead-_pNext _pHead;_pHead-_pPre _pHead;for (int i 0; i n; i){push_back(value);}
}迭代器区间构造
template class Iterator
list(Iterator first, Iterator last)
{CreateHead();while (first ! last){push_back(*first);first;}
}4、list常用接口的实现
我们实现的是双向带头循环的list因此结构为
我们先将得到头尾的接口实现一下
iterator begin()
{return _pHead-_pNext;
}
iterator end()
{return _pHead;
}
const_iterator begin() const
{return _pHead-_pNext;
}
const_iterator end() const
{return _pHead;
}4.1 list capacity
函数声明接口说明empty检测list是否为空是返回true否则返回falsesize返回list中有效节点的个数
这里两个接口都比较简单我们直接秒杀。
size_t size() const
{int count 0;const_iterator it begin();while (it ! end()){count;it;}return count;
}
bool empty() const
{return _pHead _pHead-_pNext;
}4.2 插入删除、交换、清理
函数声明接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在list position 位置中插入值为val的元素erase删除list position位置的元素swap交换两个list中的元素clear清空list中的有效元素
4.2.1 insert任意位置插入 思路 1、我们先new一个节点newnode并赋值为x这里就会去调用list节点类里面的构造函数 2、记下pos位置前一个节点prev将newnode, prev, pos三个节点连接起来 3、返回newnode的迭代器。
代码实现
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T val)
{PNode cur pos._pNode;PNode prev cur-_pPre;PNode newnode new Node(val);prev-_pNext newnode;newnode-_pPre prev;newnode-_pNext cur;cur-_pPre newnode;return newnode;
}4.2.2 push_front头插 对于头插来说我们直接复用插入的代码就可以。 头插就是在链表的头部插入一个元素因此就是 insert(begin(), x);
void push_front(const T val) { insert(begin(), val); }4.2.3 push_back尾插 对于尾插也是一样的直接复用insert代码。 因为我们list是双向带头循环链表尾插 insert(end(), x) 直接在尾部前插入即可。end()返回的就是头结点头结点是哨兵位节点因此在end()前插就是尾插。
void push_back(const T val) { insert(end(), val); }4.2.4 erase任意位置删除 思路 1、分别记下pos前后位置的节点prevnext 2、将prev与next连接起来释放pos位置节点 3、饭后pos下一个位置的节点。
// 删除pos位置的节点返回该节点的下一个位置
iterator erase(iterator pos)
{PNode cur pos._pNode;PNode prev cur-_pPre;PNode next cur-_pNext;delete cur;prev-_pNext next;next-_pPre prev;return next;
}4.2.5 pop_front头删 对于头删来说我们直接复用erase代码就可以了。 头删直接删除掉头部就可以了erase(begin())。
void pop_front() { erase(begin()); }4.2.6 pop_back尾删 尾删也是复用erase代码就是删掉列表的最后一个节点erase(–end())。
void pop_back() { erase(--end()); }这里为什么–end()这里end()返回的是头结点因为要删除尾结点所以需要–end()才是真正的尾结点。
4.2.7 swap() list的swap交换只要交换两个链表的头结点就可以因为是链式存储的更换头指针即可。库中提供的交换直接复用就可以。
void swap(listT l) { std::swap(_pHead, l._pHead); }4.2.8 clear
对于链表的clear我们需要释放掉每一个有效节点因此我们遍历一遍并复用erase。
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}5、list迭代器失效问题 前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。 int main()
{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();while (it ! lt.end()){//这里如果先删掉了再去更新迭代器已经被失效影响了lt.erase(it);it;}return 0;
}改正
int main()
{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();while (it ! lt.end()){//这里如果先删掉了再去更新迭代器已经被失效影响了lt.erase(it);}return 0;
}6、list与vector对比
vector与list都是STL中非常重要的序列式容器由于两个容器的底层结构不同导致其特性以及应用场景不同其主要不同如下
vectorlist底 层 结 构动态顺序表一段连续空间带头结点的双向循环链表随 机 访 问支持随机访问访问某个元素效率O(1)不支持随机访问访问某个元素效率O(N)插 入 和 删 除任意位置插入和删除效率低需要搬移元素时间复杂度为O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为O(1)空 间 利 用 率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭 代 器原生态指针对原生态指针(节点指针)进行封装迭 代 器 失 效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使 用 场 景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问
