目录
List介绍：
list的接口：
构造：
析构：
赋值运算符重载：
迭代器：
容量相关：
元素访问相关：
修改相关：
1、assign&reserve3
2、头插和头删
3、尾插和尾删
4、任意位置的插入
5、任意位置的删除：
其他：
List容器的模拟实现：
List介绍：
list的接口： 构造：1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2、list的底层是带头结点双向循环链表结构，双向循环链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3、list和forwoed_list非常相似：最主要的不同在于forword链表是单链表，只能向前迭代，以让其更简单高效。
4、与其他的序列式容器相比（array, vector, deque），list通常在任意位置进行插入、移除元素的效率更好。
5、与其他序列式容器相比，list和forword_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第六个元素，必须从已知的位置迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关信息（对于存储类型较小元素的 list来说这可能是一个重要的因素）
析构：1、explicit list(const allocator_type&alloc = allocator_type())：默认构造函数，构造一个仅有空节点的空链表。
2、explicit list(size_type n, const value_type& val = value_type(),const allocator_type&alloc = allocator_type())：使用n个值为val的元素构造双向链表。
3、template
explicit list(InputIterator first, InputIterator last, const allocator_type&alloc = allocator_type())：用区间[first, last)之间的元素来构造双向链表。
4、list(const list& x)：拷贝构造函数
赋值运算符重载：~list()：用来释放资源，在对象使用完毕后会自动调用。
迭代器：list& operator=(const list& x)
容量相关：iterator begin() | const_iterator begin() const;
iterator end() | const_iterator end() const;
begin：返回链表的第一个元素的位置
end：返回链表的最后一个元素的下一个位置也就是头节点的位置。
reverse_iterator rbegin() | const_reverse_iterator rbegin() const;
reverse_iterator rend() | const_reverse_iterator rend() const;
可以看到此时it2调用的是下面的函数重载。
C++11:
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
const_reverse_iterator crbegin() const noexcept;
const_reverse_iterator crend() const noexcept;
注意：这两组接口的返回值指向的元素不可被修改
元素访问相关：bool empty() const：判空
size_type size() const：求链表有效元素个数
注意：list没有capacity和reserve方法
修改相关： 1、assign&reserve3reference front() | const_reference front() const：获取链表的第一个元素
reference back() | const_reference back() const：获取链表最后一个元素
注意：因为list是带头节点的双向循环链表，不支持随机访问，所以没有[]重载
将新内容分配给列表容器，替换当前内容，并相应地修改其大小。
2、头插和头删template
void assign (InputIterator first, InputIterator last)：使用区间[first, last)之间的元素重新构建新容器。
void assign (size_type n, const value_type& val)：使用n个值为val的元素重新构建新容器。
void resize(size_type n, value_type val = value_type())：将链表的有效元素调整为n个
n > oldsize：多出来的节点使用
n < oldsize：将链表的有效元素个数缩小为n
n == oldsize：不做任何 *** 作
3、尾插和尾删void push_front(const value_type& val)：头插一个值为val的元素，时间复杂度O(1)
void pop_front()：头删一个节点，O(1)
4、任意位置的插入void push_back(const value_type& val)：尾插一个值为val的元素
void pop_back()：尾删
5、任意位置的删除：iterator insert (iterator position, const value_type& val)：在position位置插入元素val
void insert(iterator position, size_type n, const value_type& val)：在position位置插入n个值为val的元素。
template
void insert (iterator position, InputIterator firet, InputIterator last)：在position位置插入区间[first, last)的内容
其他：iterator erase(iterator position)：删除pos位置的元素
iterator erase(iterator first, iterator last)：删除区间[first, last)之间的元素。
List容器的模拟实现：void swap(list& x)：交换两个链表
void clear()：清空链表
#include
using namespace std;
namespace DL {
//list的节点类
template
class ListNode {
public:
ListNode* prev;
ListNode* next;
T data;
ListNode(const T& value = T())
:prev(nullptr)
,next(nullptr)
,data(value){}
};
//正向迭代器
template
class ListIterator {
public:
typedef ListNode Node;
typedef Ref Reference;
typedef Ptr Pointer;
typedef ListIterator Self;
public:
ListIterator(Node* pNode = nullptr)
:_pNode(pNode){}
//解引用
Ref operator*() {
return _pNode->data;
}
//只有当T是自定义类型的时候才有意义
Ptr operator->() {
return &_pNode->data;
}
//前置++
Self operator++() {
_pNode = _pNode->next;
return *this;
}
//后置++
Self operator++(int) {
Self temp(*this);
_pNode = _pNode->next;
return temp;
}
Self operator--() {
_pNode = _pNode->prev;
return *this;
}
Self operator--(int) {
Self temp(*this);
_pNode = _pNode->prev;
return temp;
}
bool operator==(const Self& it) {
return _pNode == it._pNode;
}
bool operator!=(const Self& it) {
return _pNode != it._pNode;
}
public:
Node* _pNode;
};
//反向迭代器
template
class ListReverseIterator {
typedef typename Iterator::Reference Reference;
typedef typename Iterator::Pointer Pointer;
typedef ListReverseIterator Self;
public:
ListReverseIterator(Iterator it)
:_it(it){}
Reference operator*() {
auto temp = _it;
--temp;
return *temp;
}
Pointer 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& rit) {
return _it == rit._it;
}
bool operator!=(const Self& rit) {
return _it != rit._it;
}
public:
Iterator _it;
};
//list类
template
class List {
public:
typedef ListNode Node;
typedef ListIterator iterator;
typedef ListIterator const_iterator;
typedef ListReverseIterator reverse_iterator;
typedef ListReverseIterator const_reverse_iterator;
public:
//构造和析构
List() {
CreateHead(); //默认构造空的List
}
List(int n, const T& val = T()) {
CreateHead();
for (int i = 0; i < n; i++) {
push_back(val);
}
}
List(const List& L) {
CreateHead();
auto iter = L.cbegin();
while (iter != L.cend()) {
push_back(*iter);
++iter;
}
}
template
List(Iterator first, Iterator last) {
CreateHead();
auto it = first;
while (it != last) {
push_back(*it);
++it;
}
}
//析构
~List() {
clear();
delete(_head);
_head = nullptr;
}
//赋值运算符重载
List& operator=(List& L) {
if (this != &L) {
clear();//将this指向的元素清空
auto it = L.begin();
while (it != L.end()) {
push_back(*it);
++it;
}
}
return *this;
}
///
//迭代器
iterator begin() {
return iterator(_head->next);
}
iterator end() {
return iterator(_head);
}
const_iterator cbegin()const {
return const_iterator(_head->next);
}
const_iterator cend() const{
return const_iterator(_head);
}
//反向迭代器
reverse_iterator rbegin() {
return reverse_iterator(end());
}
reverse_iterator rend() {
return reverse_iterator(begin());
}
const_reverse_iterator crbegin() {
return const_reverse_iterator(cend());
}
reverse_iterator crend() {
return const_reverse_iterator(cbegin());
}
/
//容量相关
size_t size()const{
auto it = cbegin();
size_t count = 0;
while (it != cend()) {
++count;
++it;
}
return count;
}
bool empty()const {
return _head == _head->next;
}
//调整链表有效元素的个数
void resize(size_t newsize, const T& value = T()) {
size_t oldsize = size();
if (newsize <= oldsize) {
for (size_t i = newsize; i < oldsize; i++) {
pop_back();
}
}
else {
for (size_t i = oldsize; i < newsize; i++) {
push_back(value);
}
}
}
//访问元素
T& front() {
return *begin();
}
const T& front()const {
return *cbegin();
}
T& back() {
return *(--end());
}
const T& back()const {
return _head->prev->data;
}
//
//修改
//尾插
void push_back(const T& value) {
insert(end(), value);
}
void pop_back() {
if (empty()) {
return;
}
auto it = end();
--it;
erase(it);
}
//头插
void push_front(const T& value) {
insert(begin(), value);
}
void pop_front() {
erase(begin());
}
//任意位置插入
iterator insert(iterator InsertPos, const T& value) {
Node* newnode = new Node(value);
Node* pos = InsertPos._pNode;
newnode->next = pos;
newnode->prev = pos->prev;
newnode->prev->next = newnode;
pos->prev = newnode;
return iterator(newnode);
}
//任意位置的删除
iterator erase(iterator Erasepos) {
Node* pos = Erasepos._pNode;
if (Erasepos == end()) {
return end();
}
Node* nextPos = pos->next;
pos->prev->next = nextPos;
nextPos->prev = pos->prev;
delete pos;
return iterator(nextPos);
}
iterator erase(iterator first, iterator last) {
auto it = first;
while (it != last) {
it = erase(it);
}
return it;
}
/
void clear() {
erase(begin(), end());
}
void swap(List& L) {
std::swap(_head, L._head);
}
private:
//对于一个链表，即使是空链表也会有一个头节点，将它设置为私有
void CreateHead() {
_head = new Node;
_head->next = _head;
_head->prev = _head;
}
private:
Node* _head;
}; 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）