C++ - 列表功能和用法
最编程
2024-05-07 10:10:21
...
list的特性
STL中的list是指带头双向循环列表,list每个元素的存储相互独立,因为其节点存储位置独立不连续,其插入和删除不需要挪动其他元素效率比起vector更高。但也因为存储空间不连续的问题,不能做到和vector一样的随机访问。
list的模拟实现
template<class T>
struct ListNode
{
ListNode(const T& val = T())
:_pPre(nullptr)
,_pNext(nullptr)
,_val(val)
{
}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
//List的迭代器类
template<class T, class Ref, class Ptr>
class ListIterator
{
typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;
public:
ListIterator(PNode pNode = nullptr)
:_pNode(pNode)
{}
ListIterator(const Self& l)
{
_pNode = l.getpNode();
}
//T& operator*();
Ref operator*()
{
return _pNode->_val;
}
//T* operator->();
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.getpNode();
}
bool operator==(const Self& l)
{
return _pNode == l.getpNode();
}
PNode getpNode()const
{
return _pNode;
}
private:
PNode _pNode;
};
//list类
template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* PNode;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T&> const_iterator;
public:
///
// List的构造
list()
{
CreateHead();
}
list(int n, const T& value = T())
{
_size += n;
CreateHead();
PNode cur = _pHead;
while (n--)
{
PNode newnode = new Node(value);
cur->_pNext = newnode;
newnode->_pPre = cur;
newnode->_pNext = _pHead;
_pHead->_pPre = newnode;
cur = cur->_pNext;
}
}
template <class Iterator>
list(Iterator first, Iterator last)
{
Iterator cur = first;
while (cur != last)
{
push_back(cur.getpNode()->_val);
cur++;
}
}
list(const list<T>& l)
{
CreateHead();
for (auto& a : l)
{
push_back(a);
}
}
list<T>& operator=(const list<T> l)
{
list<T> tmp(l);
swap(tmp);
}
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
///
// 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
{
return _size;
}
bool empty()const
{
return _size == 0;
}
// List Access
T& front()
{
return _pHead->_pNext->_val;
}
const T& front()const
{
return _pHead->_pNext->_val;
}
T& back()
{
return _pHead->_pPre->_val;
}
const T& back()const
{
return _pHead->_pPre->_val;
}
// List Modify
void push_back(const T& val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const T& val) { insert(begin(), val); }
void pop_front() { erase(begin()); }
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
PNode newnode = new Node(val);
PNode cur = pos.getpNode();
PNode prev = cur->_pPre;
newnode->_pNext = cur;
cur->_pPre = newnode;
prev->_pNext = newnode;
newnode->_pPre = prev;
_size++;
return iterator(newnode);
}
// 删除pos位置的节点,返回该节点的下一个位置
iterator erase(iterator pos)
{
PNode cur = pos.getpNode();
PNode prev = cur->_pPre;
PNode next = cur->_pNext;
prev->_pNext = next;
next->_pPre = prev;
delete cur;
_size--;
return iterator(next);
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void swap(list<T>& l)
{
std::swap(_pHead, l.getpHead());
std::swap(_size, l.size());
}
PNode getpHead()const
{
return _pHead;
}
private:
void CreateHead()
{
_pHead = new Node;
_pHead->_pNext = _pHead;
_pHead->_pPre = _pHead;
_size = 0;
}
PNode _pHead;
size_t _size;
};
迭代器失效问题
与vector不同,list插入时迭代器不会失效,因为节点相互独立的原因,所以list的插入不会改变其节点存储位置,如此一来迭代器的指向也不会有影响。
不过删除时仍会出现迭代器失效,迭代器指向的节点被删除时该迭代器失效(指向的节点失效,迭代器自然也就失效了),其余不受影响。
list与vector的区别
vector | list | |
插入与删除 | 插入与删除都可能需要挪动部分元素,时间复杂度为O(n),插入还往往伴随着扩容,又因为其需要连续的存储空间还可能出现开辟新空间,拷贝数据,释放旧空间的操作,整体效率低下。 | 插入与删除的时间复杂度均为O(1),存储空间的独立使其不需要扩容,需要新节点时才进行申请,并且不需要挪动数据。 |
随机访问 | 存储空间连续,支持随机访问,查找的时间复杂度为O(1) | 不支持随机访问,查找的时间复杂度为O(n) |
迭代器 | 使用原生指针 | 使用被封装的原生指针 |
空间利用率 | 因其内存连续,不易造成内存碎片,空间利用率高,但缓存利用率高 | 因其节点是动态开辟而来,且相互独立。容易造成内存碎片,空间利用率低,但缓存利用率低 |
总结:如果需要高效存储、需要随机访问且不关心插入删除效率则使用vector。反之需要大量插入删除查找,不关心随机访问则使用list。
推荐阅读
-
C++ - 列表功能和用法
-
深入了解 C++ lambda 表达式:用法、特性和最佳实践
-
ES6、ES7、ES8、ES9 和 ES10 中的新功能列表
-
枚举在 C++ 和 Java 中的用法
-
C++] 手搓列表容器-3 功能实现
-
谈API网关和应用网关--从技术选型谈起:API网关的性能是第一指标,一般会选择Kong、Apisix等基于OpenResty+Lua的高性能网关(得益于Ngnix基于C++的高性能无阻塞网络IO模型),应用网关一般是结合自身业务的技术栈来选择,比如SpringCloud Gateway、Zuul等。当然,这也不是绝对的,如果你对 Kong 非常熟悉,用它来做应用网关也不是不可能。 一些开源网关项目的例子: Kong Apisix 特使 Traefik SpringCloud 网关 Zuul / Zuul2 接下来,我们将重点介绍应用网关。在网格中,应用网关侧重于以下功能(与 API 网关不同) 动态路由 服务发现 服务聚合/协调 可观察性 如果您使用的是 Sping 技术栈,使用 SpringCloud Gateway 和 Zuul 可以轻松重用现有类库,如集成您的注册表,使用 Hystrix、resilience4j 完成熔断和限流功能等,快速完成一个生产级可用应用网关,如果引入新的复杂技术栈 成本将直线上升。根据使用场景的不同,性能有时并不是第一指标,但通常我们很容易陷入性能误区。
-
C++:列表使用和模拟实施
-
深入分析 C++ 中的虚拟函数和虚拟继承:实现多态性和继承关系的高级功能
-
C++] 虚拟函数指针和虚拟函数列表
-
C++ 虚拟函数的概念和用法(基础)