目录
一、list的介绍
二、list的深度剖析与模拟实现
1、list图解
2、list增删查改模拟实现
三、list与vector的对比
一、list的介绍
STL中的list指的是带头双向循环链表。list是可以在常数范围内任意位置进行插入和删除的序列式容器，并且可以前后双向迭代。list中每个元素的存储相互独立，通过每个节点中的指针指向其前一个元素和后一个元素。list因为每个节点的存储位置相互独立而是的插入和删除元素不需要移动其他元素让其效率更高，但是list也因此不能支持任意位置的随机访问，不能随机访问是它最大的缺陷。
二、list的深度剖析与模拟实现
1、list图解
list的节点中有三个成员变量（哨兵位头节点除外），分别是：有效数据date、指向下一个节点的指针变量next、指向前一个节点的指针变量pre，哨兵位头节点不存储有效数据，只有两个指针变量。
2、list增删查改模拟实现
#pragma once
#include<iostream>
using namespace std;
namespace lbj
{
// List的节点类
template<class T>
struct ListNode
{
ListNode(const T& val = T())
:_val(val)
,_pPre(nullptr)
,_pNext(nullptr)
{}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
//List的迭代器类
template<class T, class Ref, class Ptr> //Ref是T类型的引用；Ptr是指向T类型数据的指针
class ListIterator
{
typedef ListNode<T> Node;
typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;
public:
ListIterator(PNode pNode = nullptr)
:_pNode(pNode)
{}
ListIterator(const Self& l);
Ref operator*()
{
return _pNode->_val;
}
Ptr 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;
};
//list类
template<class T>
class list
{
typedef ListNode<T> Node;
typedef ListNode<T>* PNode;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
public:
// List Iterator
iterator begin()
{
return _pHead->_pNext;
}
iterator end()
{
return _pHead;
}
const_iterator begin() const
{
return _pHead->_pNext;
}
const_iterator end() const
{
return _pHead;
}
// List Capacity
size_t size()const;
bool empty()const;
// List Access
T& front();
const T& front()const;
T& back();
const T& back()const;
// List Modify
iterator insert(iterator pos, const T& val)// 在pos位置前插入值为val的节点,返回新插入元素的迭代器
{
PNode cur = pos._pNode;
PNode pre = cur->_pPre;
PNode NewNode = new Node(val);
pre->_pNext = NewNode;
NewNode->_pPre = pre;
NewNode->_pNext = cur;
cur->_pPre = NewNode;
return iterator(NewNode); //返回新插入元素的迭代器
}
iterator erase(iterator pos)// 删除pos位置的节点，返回该节点的下一个位置
{
PNode cur = pos;
PNode pre = cur->_pPre;
PNode next = cur->_pNext;
pre->_pNext = next;
next->_pPre = pre;
delete cur;
return iterator(next); //返回该节点的下一个位置
}
void push_back(const T& val) //{ insert(end(), val); }
{
//insert(end(), val);
PNode tail = _pHead->_pPre;
PNode NewNode = new Node(val);
tail->_pNext = NewNode;
NewNode->_pPre = tail;
NewNode->_pNext = _pHead;
_pHead->_pPre = NewNode;
}
void pop_back()
{
erase(--end());
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_front()
{
erase(begin());
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void swap(list<T>& l)
{
std::swap(_pHead, l._pHead);
}
// List的构造
void empty_init()
{
_pHead = new Node;
_pHead->_pPre = _pHead;
_pHead->_pNext = _pHead;
}
list()
{
empty_init();
}
list(int n, const T& value = T());
template <class Iterator>
list(Iterator first, Iterator last);
list(const list<T>& l)
{
empty_init();
for (auto L_N : l)
{
push_back(L_N);
}
}
list<T>& operator=(const list<T> l)
{
//if (this != &l)
//{
// clear();
// for (auto L_N : l)
// {
// push_back(L_N);
// }
//}
swap(l);
return *this;
}
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
private:
void CreateHead();
PNode _pHead;
};
};三、list与vector的对比
| vector | list | |
| 地 层 结 构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随 机 访 问 | 支持随机访问，访问某个元素的效率是O(1) | 不支持随机访问，访问某个元素的效率是O(n) |
| 插 入 和 删 除 | 任意位置插入和删除效率低，需要移动部分元素，时间复杂度是O(n)，插入元素可能需要扩容，开辟新空间、拷贝元素、释放旧空间，这些操作导致效率低下 | 任意位置插入和删除效率高，不需要 移动其他元素，时间复杂度是O(1) |
| 空 间 利 用 率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点是动态开辟出来的，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭 代 器 | 原生态指针 | 被封装的原生态指针（节点指针） |
| 迭 代 器 失 效 | 在插入元素时，要给所有迭代器重新赋值，因为插入元素有可能导致扩容，使得原来迭代器失效，删除时，当前迭代器也需要重新赋值 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使 用 场 景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
