C++初阶（list容器+模拟实现）
list介绍
list的本质是一个带头的双向循环链表。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另 一个是存储下一个结点地址的指针域。
相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就只配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准， 一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。
List和vector是两个最常被使用的容器。 List容器是一个双向链表。
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
- 链表灵活，但是空间和时间额外耗费较大
- list有一个重要的性质，插入和删除操作都不会造成原有的list迭代器失效
概述
list容器
- 数据结构：双向循环链表
- 迭代器：双向迭代器
- 常用API
- 构造
- 数据元素的插入和删除
- 容器大小操作
- 赋值操作
- 数据的存取
- 反转和排序
- 动态存储分配（链表的插入和删除）
- 注意：list容器不能使用常用的sort，只能使用自己的sort
- list容器插入和删除很方便，但是不支持任意位置的随机访问
list常见的接口
list的构造函数
list<T> lstT;//list采用采用模板类实现,对象的默认构造形式
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身
list(n,elem);//构造函数将n个elem拷贝给本身
list(const list &lst);//拷贝构造函数
void test
{
list<int> lt1;// 无参构造
list<int> lt2(10, 5);// 用n个val构造一个list对象
list<int> lt3(lt2);// 拷贝构造
list<int> lt4(lt2.begin , lt2.end );// 用一段区间的元素构造list
}
list中的迭代器
- begin + end： 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator(最后一个数据的下一个位置就是第一个数据的位置)
- rbegin + rend： 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator（第一个数据的前一个位置就是最后一个数据的位置）
- list容器是一个双向的循环链表
list的迭代器遍历
1.迭代器遍历正向遍历
void test01
{
list<int> lt;
//尾插
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
//头插
lt.push_front(0);
lt.push_front(-1);
lt.push_front(-2);
list<int>::iterator it = lt.begin ;
while (it != lt.end )
{
cout << *it << " ";
++it;
}
cout << endl;
}
2.范围for
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
3.迭代器反向遍历
list<int>::reverse_iterator rit = lt.rbegin ;
while (rit != lt.rend )
{
cout << *rit << " ";
++rit;
}
cout << endl;
}
输出结果如下：
list的增删改查
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身
assign(n, elem);//将n个elem拷贝赋值给本身
push_back(elem);//在容器尾部加入一个元素
pop_back ;//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front ;//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值
clear ;//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置
erase(pos);//删除pos位置的数据，返回下一个数据的位置
remove(elem);//删除容器中所有与elem值匹配的元素
swap(lst);//将lst与本身的元素互换
list<int> mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
mylist.push_front(100);
mylist.push_front(200);
mylist.push_front(300);
mylist.push_front(400);
vector<int> v;
v.push_back(1000);
v.push_back(2000);
v.push_back(3000);
mylist.insert(mylist.begin , v.begin , v.end );
printList(mylist);
mylist.remove(300);
//删除大于300的数据
mylist.remove_if(myfunc);
list的大小和头尾元素的读取
size ;//返回容器中元素的个数
empty ;//判断容器是否为空
resize(num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除
resize(num, elem);//重新指定容器的长度为num，若容器变长，则以值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除
list迭代器失效
迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
第一种情况：插入
list<int> mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
list<int>::iterator it = mylist.begin ;
mylist.insert(it,3);
运行结果没有问题，不会报错
第二种情况：删除
list<int> mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
list<int>::iterator it = mylist.begin ;
while( it! = mylist.end )
{
mylist.erase(it);
++it;
}
总结：插入数据不会导致迭代器失效，删除数据会导致迭代器失效。相比vector容器，vector容器插入数据是会导致迭代器失效，因为vector涉及增容问题，而list却不存在增容问题，所以迭代器指向的位置是有效的。删除数据会导致迭代器指向的位置是无效的，所以迭代器会失效。
解决方法：和vector一样，对迭代器进行赋值
list<int> mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
list<int>::iterator it = mylist.begin ;
while( it! = mylist.end )
{
it = mylist.erase(it);//erase 返回值是指向被删元素的下一元素的指针(也就是迭代器)
}
list模拟实现
list整体框架
list是由节点组成，所以定义一个节点的类，然后list的类中成员只需要一个头结点的指针即可。
template<class T>
struct __list_node
{
__list_node<T>* _prev;
__list_node<T>* _next;
T _data;
__list_node(const T& x = T )
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
template<class T>
class list
{
typedef __list_node<T> Node;
public:
private:
Node* _head;
};
list的构造函数
构造函数要做的任务就是开一个头结点，所以我们可以封装出一个具体的函数来实现创建头结点的这个过程
创建头结点：
void CreatHead
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
构造函数的实现：
list
{
CreatHead ;
}
list迭代器的实现
list相比vector的迭代器而言，不再是一个简单的指针，它相对而言更复杂一些，list的迭代器为了实现一些简单的功能，我们把它封装成了一个类。看下面源码实现：
我们自己来模拟实现一下简单的。
迭代器的小框架（里面有一个成员变量——节点指针）
struct __list_iterator
{
typedef __list_node<T> Node;
__list_iterator(Node* node = nullptr)
:_node(node)
{}
Node* _node;
}
由于迭代器分普通迭代器和const 迭代器，为了不造成代码冗余，我们设计出来三个模板参数，根据传入的模板参数确定是那种迭代器。
// __list_iterator<T, T&, T*> -> 普通迭代器
// __list_iterator<T, const T&, const T*> -> const迭代器
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef __list_node<T> Node;
typedef __list_iterator<T, Ref, Ptr> Self;
Node* _node;
__list_iterator(Node* node = nullptr)
:_node(node)
{}
__list_iterator(const Self& l)
:_node(l._node)
{}
// *it T&
Ref operator*
{
return _node->_data;
}
// it-> T*
Ptr operator->
{
return &_node->_data;
}
Self& operator++
{
_node = _node->_next;
return *this;
}
Self& operator--
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
//_node = _node->_next;
++(*this);
return tmp;
}
Self operator--(int)
{
Self tmp(*this);
//_node = _node->_prev;
--(*this);
return tmp;
}
Self operator+(int count)
{
Self tmp(*this);
while (count--)
{
++tmp;
}
return tmp;
}
Self operator-(int count)
{
Self tmp(*this);
while (count--)
{
--tmp;
}
return tmp;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
};
我们还要在list里面做这样一个操作（堆两种迭代器进行重命名，方便我们认识）：
typedef list_iterator<T, T&, T*> iterator;// 普通迭代器
typedef list_iterator<T, const T&, const T*> const_iterator;// const迭代器
list内部begin 和end 的实现（普通迭代器调用前两个，const迭代器调用后两个）
iterator begin
{
return iterator(_head->_next);
}
iterator end
{
return iterator(_head);
}
const_iterator begin const
{
return const_iterator(_head->_next);
}
const_iterator end const
{
return const_iterator(_head);
}
list的增删查改的实现
void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void pop_back
{
assert(head != head->_next);
Node* tail = head->_prev;
Node* prevTail = tail->_prev;
delete tail;
tail = prevTail;
tail->_next = head;
head->_prev = tail;
}
void push_front(const T& x)
{
Node* newnode = new Node(x);
Node* firstNode = head->_next;
head->_next = newnode;
newnode->_prev = head;
newnode->_next = firstNode;
firstNode->_prev = newnode;
}
void pop_front
{
assert(head->_next != head);
Node* firstNode = head->_next;
Node* secondNode = firstNode->_next;
delete firstNode;
firstNode = nullptr;
head->_next = secondNode;
secondNode->_prev = head;
}
void 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;
}
iterator erase(iterator pos)
{
assert(head->_next != head);
assert(pos != end );
Node* node = pos._node;
Node* prev = node->_prev;
Node* next = node->_next;
delete node;
node = nullptr;
prev->_next = next;
next->_prev = prev;
return iterator(next);
}
T front
{
assert(head->_next != head);
return head->_next->data;
}
T back
{
assert(head->_next != head);
return head->_prev->data;
}
list中的析构函数和clear
1.clear 通过迭代器遍历，一个一个的删除节点
void clear
{
iterator it = begin ;
while (it != end )
{
it = erase(it);
}
}
2.析构函数 可以先调用clear函数清理空间，然后再delete掉头结点
~list
{
clear ;
delete head;
head = nullptr;
}
拷贝构造和operator=赋值重载
1.拷贝构造
list(const list<T>& lt)
{
CreatHead ;
/*const_iterator it = lt.begin ;
while (it != lt.end )
{
push_back(*it);
++it;
}*/
for (auto e : lt)
push_back(e);
}
2.operator= 直接利用swap和形参交换，形参会自己调用析构函数清理空间
list<T>& operator=(list<T> lt)
{
if (this != <)// 防止自己给自己赋值
{
swap(lt);
}
return *this;
}
swap函数实现如下：
void swap(list<T>& lt)
{
::swap(head, lt.head);
}
