C++—list类的使用及模拟实现

1、list的介绍

2、list常用接口函数

2.1 几个构造函数

2.1.1 构造函数的模拟实现

2.2 迭代器

2.2.1 迭代器的模拟实现

2.3 容量相关的函数

3、list的增删查改

3.1 插入insert

3.2 删除erase

3.3 头插、头删、尾插、尾删

4、list需要注意的点及功能完善

4.1 list迭代器失效问题

4.2 list的sort排序

1、list的介绍

list在底层是双向链表，能够进行动态内存分配，与其他容器相比，list的插入删除要更高效。

list的特性

1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2、list的底层是带头双向循环链表结构，在节点中通过指针指向其前一个元素和后一个元素。

3、与其他的序列式容器相比(array，vector，deque等)，list通常在任意位置进行插入、移除元素的效率更高。

list的缺陷

list最大的缺陷是不支持任意位置的随机访问

list和vector一样也是类模板。

2、list常用接口函数

2.1 几个构造函数

函数声明	函数说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造list 注意：这里的区间是左闭右开

//无参构造
list<int> l1;
//用10个6初始化链表
list<int> l2(10, 6);
//拷贝构造
list<int> ll2(l2);vector<int> v{ 1,2,3,4 };
//用迭代器区间初始化链表
list<int> l3(v.begin(), v.end());

2.1.1 构造函数的模拟实现

无参构造

void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}list()
{empty_init();
}

拷贝构造

list(const list<T>& lt)
{empty_init();for (const auto& e : lt){push_back(e);}
}

赋值构造

void swap(const list<T>& tmp)
{std::swap(_head, tmp._head);
}list<T>& operator=(const list<T> lt)
{swap(lt);return *this;
}

析构

void clear()
{iterator it = begin();while (it != end()){it = erase(it);}
}~list()
{clear();delete _head;_head = nullptr;
}

2.2 迭代器

可以暂时将迭代器理解成指针，这个指针指向list中的某个节点。

函数声明	接口说明
begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

vector<int> v1{ 5,3,10,26,9,22,12,24 };
list<int> l(v1.begin(), v1.end());auto it = l.begin();
while (it != l.end())
{cout << *it << " ";it++;
}

反向迭代

2.2.1 迭代器的模拟实现

与vector不同，list的迭代器不是一个原生指针，而是封装节点指针的类，因为用户只需要得到节点中的数据而不是整个节点。

vector随机访问可以支持像it+5，it[6]这样的形式，而list不能随机访问也就不能使用operator []来访问节点，仅支持++和--操作，这个++和--也不是指针的++和--，所以要把迭代器也封装成一个类，通过重载++、--和解引用等运算符来满足需求。

//先要封装一个结点类
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}
};
//封装一个迭代器类
template<class T>
struct __list_iterator
{typedef ListNode<T> Node;typedef __list_iterator<T> self;Node* _node;__list_iterator(Node* x):_node(x){}self& operator++(){_node = _node->_next;return *this;}self operator++(int){//相当于__list_iterator<T> tmp(*this);self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int);//解引用重载T& operator*(){return _node->_data;}//T operator->(){return &_node->_data;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s);
};

迭代器的实现

const_iterator begin()const
{//这里是单参数类型支持隐式类型转换//return const_iterator(_head->_next);return _head->_next;
}const_iterator end()const
{return _head;
}iterator begin()
{return _head->_next;
}iterator end()
{return _head;
}

2.3 容量相关的函数

函数	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

这里个函数我们学会使用即可。

3、list的增删查改

访问头部和尾部数据

函数	功能
front()	取到头节点数据的引用
back()	返回尾节点数据的引用

3.1 插入insert

iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;//这里是为了管理_sizereturn newnode;
}

3.2 删除erase

将待删除的节点的前后节点先保存起来，再删除pos出节点，将前后节点连接起来。

iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;
}

3.3 头插、头删、尾插、尾删

//尾插
void push_back(const T& x)
{insert(end(), x);
}
//头插
void push_front(const T& x)
{insert(begin(), x);
}//尾删
void pop_back()
{erase(--end());
}//头删
void pop_front()
{erase(begin());
}