list
- 1. 简单了解list
- 2. list的常见接口
- 3. 简单实现list
- 4. vector和list比较
1. 简单了解list
- list的底层是带头双向循环列表。
- 因此list支持任意位置的插入和删除，且效率较高。但其缺陷也很明显，由于各节点在物理空间是不连续的，所以不支持对任意位置的访问，效率低。
- list的迭代器底层不仅仅是指针这么简单，因为其迭代器支持前后双向迭代，而其空间又不连续，所以其底层是对指针的封装。（后面讲）
2. list的常见接口
- 构造
例子
- 普通迭代器
与其他容器的迭代器一样，只不过list的底层实现更加复杂，现在暂且将其看成指针。
例子
//迭代器
void test3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
auto it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
//运行结果：
//1 2 3 4
- 头插头删和尾插尾删
例子
void test2()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.pop_back();
lt.pop_back();
lt.pop_front();
lt.pop_front();
lt.push_front(4);
lt.push_front(3);
lt.push_front(2);
lt.push_front(1);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
//运行结果：
//1 2 3 4
//1 2 3 4
- 插入
例子
void test3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(3);
lt.push_back(4);
//想在第二个位置插入2，怎么做
//lt.insert(lt.begin()+1,2);//错误的，list的iterator没有重载+。这个等下讲原因。
auto it = lt.begin();
++it;
lt.insert(it, 2);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
//运行结果：
//1 2 3 4
这样确定插入位置太麻烦了，可以用find查找。
auto it = find(lt.begin(),lt.end(),3);
if (it != lt.end())
{
lt.insert(it,2);
}
- 删除
例子
//删除偶数
//删除后，迭代器还指向被删除空间，存在迭代器失效问题
//所以要重新赋值
it = lt.begin();
while (it != lt.end())
{
if (*it % 2 == 0)
{
it = lt.erase(it);
}
else
{
++it;
}
}
- front和back
例子
- 逆置和排序
例子
void test5()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.reverse();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.sort();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
//运行结果
//4 3 2 1
//1 2 3 4
拓展
（1）库里也有sort，为什么还要在list再写一个？C++库的sort不能用。
（2）这涉及到迭代器的分类。从功能上，由容器底层结构决定，迭代器有单项迭代器、双向迭代器和随机迭代器。单项迭代器只能++，向后迭代，例如forward_list/unordered_xxx的迭代器；双向迭代器能++/–，例如list/map/set；随机迭代器能+/-/++/–，例如string/vector/deque。
（3）有随机迭代器的容器能用随机的、双向的、单向的迭代器的库函数，有双向迭代器的容器能用双向的、单向的迭代器的库函数。
（4）list的迭代器类型是双向的，库函数sort的迭代器类型是随机的，所以list的数据排序不能用库函数sort。
- 归并
例子
void test6()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(3);
lt1.push_back(5);
lt1.push_back(7);
list<int>lt2;
lt2.push_back(2);
lt2.push_back(4);
lt2.push_back(6);
lt2.push_back(8);
lt1.merge(lt2);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
cout << "lt1的大小为：" << lt1.size() << endl;
cout << "lt2是否变为空：" << lt2.empty() << endl;
}
- unique
例子
list<int> lt1;
lt1.push_back(1);
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(2);
lt1.unique();
cout << "lt1的大小：" << lt1.size() << endl;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
- remove
list<int> lt1;
lt1.push_back(1);
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(2);
lt1.remove(1);//相当于find+erase
cout << "lt1的大小：" << lt1.size() << endl;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
remove不像erase，它的参数是值而不是迭代器，且remove如果要移除的值不存在，不会报错。
- splice
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
list<int> lt2;
lt2.push_back(5);
lt2.push_back(6);
lt2.push_back(7);
lt2.push_back(8);
lt1.splice(lt1.begin(), lt2);//将lt2的所有节点全部转移到lt1之前
lt1.splice(lt1.begin(), lt2,--lt2.end());//将lt2的最后一个元素转移到lt1之前
lt1.splice(lt1.begin(), lt2, ++lt2.begin(), lt2.end());//将迭代器区间的节点转移到lt1之前
lt1.splice(lt1.begin(), lt1, ++lt1.begin(), lt1.end());//将lt1第一个节点后面的节点转移到lt1之前
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
3. 简单实现list
#include<iostream>
using namespace std;
namespace zn
{
//节点
template<class T>
struct ListNode
{
ListNode<T>* _prev;
ListNode<T>* _next;
T _val;
ListNode(const T& val = T())
:_prev(nullptr)
, _next(nullptr)
, _val(val)
{}
};
//迭代器（双向迭代器）
//迭代器底层都是指针，但有些指针需要封装，例如节点的指针，不然不能满足++/--等操作
template<class T, class Ref, class Ptr>
//T == T, Ref == T&/const T&, Ptr == T*/const T*
struct __list_iterator
{
typedef ListNode<T>* iterator;
typedef __list_iterator<T, Ref, Ptr> This;
iterator _node;
//构造
__list_iterator(iterator node)
:_node(node)
{}
//*重载
Ref operator*()
{
return _node->_val;
}
//->重载
//如果T恰好是结构体类型，而迭代器又被看成指针，那么->就可以派上用场
Ptr operator->()
{
return &(_node->_val);
}
//++重载
This& operator++()
{
_node = _node->_next;
return *this;
}
This operator++(int)
{
This tmp(_node);
_node = _node->_next;
return tmp;
}
//--重载
This& operator--()
{
_node = _node->_prev;
return *this;
}
This operator--(int)
{
This tmp(_node);
_node = _node->_prev;
return tmp;
}
//==重载和!=重载
bool operator==(__list_iterator lit)const
{
return _node == lit._node;
}
bool operator!=(__list_iterator lit)const
{
return !(_node == lit._node);
}
};
//反向迭代器
//对正向迭代器的封装，从而得到我们想要的操作
template<class T,class Ref,class Ptr>
class ReverseIterator
{
typedef __list_iterator<T, Ref, Ptr> iterator;
typedef ReverseIterator<T, Ref, Ptr> reverse_iterator;
iterator _it;
ReverseIterator(iterator it)
:_it(it)
{}
public:
Ref operator*()
{
iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
reverse_iterator& operator++()
{
--_it;
return *this;
}
reverse_iterator operator++(int)
{
reverse_iterator tmp = *this;
--_it;
return tmp;
}
reverse_iterator& operator--()
{
++_it;
return *this;
}
reverse_iterator operator--(int)
{
reverse_iterator tmp = *this;
++_it;
return tmp;
}
bool operator!=(const reverse_iterator& rit)
{
return _it != rit._it;
}
bool operator==(const reverse_iterator& rit)
{
return _it == rit._it;
}
};
//list
template<class T>
class list
{
typedef ListNode<T> Node;
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
typedef ReverseIterator<T, T&, T*> reverse_iterator;
typedef ReverseIterator<T, const T&, const T*> const_reverse_iterator;
public:
//构造
list()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_size = 0;
}
//拷贝构造
list(const list<T>& lt)//list(const list& lt)
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
_size = 0;
for (auto& e : lt)
{
push_back(e);
}
_size = lt._size;
}
//交换
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//=重载
list<T> operator=(list<T> lt)
{
swap(lt);
return *this;
}
//析构
~list()
{
Node* cur = _head->_prev;
while (cur != _head)
{
Node* tmp = cur->_next;
delete cur;
cur = tmp;
}
delete _head;
_head = nullptr;
}
//迭代器
iterator begin()
{
return _head->_next;
}
const_iterator begin()const
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator end()const
{
return _head;
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin()const
{
return const_reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(begin());
}
//插入（默认在pos前插入）
iterator insert(iterator pos, const T& val)
{
Node* newnode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
cur->_prev = newnode;
newnode->_next = cur;
++_size;
//隐式类型转换
//返回指针类型，然后用类类型接收，会调用构造
return newnode;
}
//删除
iterator earse(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;
}
//尾插和尾删
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());
}
//大小
size_t size()
{
return _size;
}
//清理
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
private:
//指向头节点
Node* _head;
size_t _size;
};
void test_iterator()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
auto it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
}
4. vector和list比较
| vector | list | |
|---|---|---|
| 底层 | 顺序表，可扩容 | 双向循环链表，带头节点 |
| 效率 | 具有连续的空间，空间利用率高；访问元素效率高，支持随机访问；插入和删除元素效率低，需要挪动元素，时间复杂度为O(N) | 底层开辟节点，空间利用率低；访问元素效率低，不支持随机访问； 插入和删除元素效率高，时间复杂度为O(1) |
| 迭代器 | 是原生态指针；是随机迭代器，支持+/-等操作；无论是插入还是删除，都会导致迭代器失效（插入需要扩容，扩容后原来的迭代器失效） | 是对原生态指针的封装；是双向迭代器，不支持+/-等操作 ；删除会导致迭代器失效 |
| 应用 | 适用于插入和删除操作少，访问多的情况 | 适用于插入和删除操作多，访问少的情况 |
