STL-list类
list的介绍和使用
list的介绍
list是双向循环链表
list的使用
构造
list(size_t n,const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
|---|---|
list() | 构造空list |
lis(const list& x) | 拷贝构造函数 |
list(inputlerator first,inputlterator last) | 用[first,list)的区间中元素构造list |
int main()
{
list<int> A;
list<int> B(5,1);
list<int> C(B);
list<int> D(C.begin(),C.end());
return 0;
}迭代器
begin | 返回第一个元素的迭代器 |
|---|---|
end | 返回最后一个元素的下一个位置的迭代器 |
rbegin | 返回最后一个元素的迭代器 |
rend | 返回第一个元素的上一个位置的迭代器 |
begin与end是一组的正向地迭代器 ++向后移动 rbegin与rend是反向迭代器 ++向前移动
int main()
{
int num[10] = { 1,2,3,4,5,6,7,8,9,10 };
list<int> a(num,num+10);
for (auto it = a.begin(); it != a.end(); it++)
{
cout << *it << ' ';
}
cout << endl;
for (auto rit = a.rbegin(); rit != a.rend(); rit++)
{
cout << *rit << ' ';
}
cout << endl;
for (auto ait : a)
{
cout << ait;
}
return 0;
}empty | 检测list是否为空 |
|---|---|
size | 返回list中有效节点数 |
front | 返回list地第一个节点中值的引用 |
|---|---|
back | 返回list最后一个节点中值的引用 |
push_front | 头插 |
|---|---|
pop_front | 头删 |
push_back | 尾插 |
pop_back | 尾删 |
insert | 在pos位置插入 |
erase | 删除pos位置元素 |
swap | 交换元素 |
clear | 清空有效元素 |
int main()
{
list<int> a;
a.push_back(1);
a.push_front(0);
for (auto it : a)
cout << it;
a.pop_front();
for (auto it : a)
cout << it;
a.push_front(3);
swap(a.front(),a.back());
for (auto it : a)
cout << it;
swap(a.front(), a.back());
for (auto it : a)
cout << it;
a.clear();
cout << a.size();
return 0;
}迭代器失效
只有删除某个节点后，迭代器的位置还指向被删除节点时候才失效
模拟实现
#include<iostream>
using namespace std;
namespace mylist
{
template<class T>
struct ListNode
{
ListNode(const T& val = T()):_val(val),_pPre(nullptr),_pNext(nullptr){}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
template<class T, class Ref, class Ptr>
class ListIterator
{
typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;
public:
PNode node()
{
return _pNode;
}
ListIterator(PNode pNode = nullptr):_pNode(pNode){}
ListIterator(const Self& l):_pNode(l._pNode){}
T& operator*()
{
return _pNode->_val;
}
T* operator->()
{
return _pNode;
}
Self& operator++()
{
_pNode = _pNode->_pNext;
return *this;
}
Self operator++(int)
{
Self p = *this;
_pNode = _pNode->_pNext;
return Self(p);
}
Self& operator--()
{
_pNode = _pNode->_pPre;
return *this;
}
Self& operator--(int)
{
Self p = *this;
_pNode = _pNode->_pPre;
return Self(p);
}
bool operator!=(const Self& l) const
{
return _pNode != l._pNode;
}
bool operator==(const Self& l) const
{
return _pNode == l._pNode;
}
private:
PNode _pNode;
};
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
Reverse_iterator(Iterator it):_it(it){}
Ref operator*()
{
Iterator t(_it);
return *t;
}
Ptr operator->()
{
return &(operator*());
}
//
// 迭代器支持移动
Self& operator++()
{
Self temp(*this);
--_it;
return temp;
}
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;
};
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;
typedef Reverse_iterator<iterator, const T&, const T*> const_Reverse_iterator;
typedef Reverse_iterator<iterator,T&,T*> Reverse_iterator;
public:
list()
{
CreateHead();
}
list(int n, const T& value = T())
{
CreateHead();
while(n--)
push_front(value);
}
template <class Iterator>
list(Iterator first, Iterator last)
{
CreateHead();
while (first != last)
{
push_back(*first);
first++;
}
}
list(const list<T>& l)
{
CreateHead();
for (auto it : l)
{
push_back(it);
}
}
list<T>& operator=(const list<T>& l)
{
list(l);
}
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
///
// List Iterator
iterator begin() { return iterator(_pHead->_pNext); }
iterator end() {return iterator(_pHead);};
const_iterator begin() const { return const_iterator(_pHead->_pNext); }
const_iterator end() const { return const_iterator(_pHead); }
Reverse_iterator rbegin()
{
return Reverse_iterator(--end());
}
Reverse_iterator rend()
{
return Reverse_iterator(--begin());
}
const_Reverse_iterator rbegin()const
{
return const_Reverse_iterator(--end());
}
const_Reverse_iterator rend()const
{
return const_Reverse_iterator(--begin());
}
///
// List Capacity
size_t size()const
{
size_t s = 0;
const_iterator it = this->begin();
while (it != this->end())
{
it++;
s++;
}
return s;
}
bool empty()const
{
return _pHead == _pHead->_pNext;
}
// 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 tmp = new Node(val);
tmp->_pNext = pos.node();
tmp->_pPre = pos.node()->_pPre;
pos.node()->_pPre->_pNext = tmp;
pos.node()->_pPre = tmp;
return iterator(tmp);
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
PNode it = pos.node()->_pNext;
PNode p = pos.node();
p->_pNext->_pPre = p->_pPre;
p->_pPre->_pNext = p->_pNext;
delete p;
return iterator(it);
}
void clear()
{
while (_pHead != _pHead->_pNext)
{
pop_front();
}
}
void swap(list<T>& l)
{
PNode tmp = l._pHead;
l._pHead = _pHead;
_pHead = tmp;
}
private:
void CreateHead()
{
_pHead = new Node;
_pHead->_pNext = _pHead;
_pHead->_pPre = _pHead;
}
PNode _pHead;
};
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-01-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
