list的使用与实现

1.list的使用

list本质上是一个带头双向循环链表，因此遍历的时候不支持下标随机访问[ ]

1.2.list的构造函数

list有四种默认构造函数

·无参构造

list<int> l1; //构造空的l1

·n个val值构造

list<int> l2 (4,100); //l2中构造4个值为100的数

迭代器构造

// 用l2的[begin(), end()）左闭右开的区间构造l3
list<int> l3 (l2.begin(), l2.end());

拷贝构造函数

list<int> l4 (l3); // 用l3拷贝构造l4

1.3.list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。但本质并不是一个指针，后面底层实现的时候就会知道

注意仔细看图中迭代器的指向

迭代器遍历

list<int> lt = { 1, 2, 3, 4, 5 };
list<int>::iterator it = lt.begin();
while (it!=lt.end())
{cout << *it << ' ';it++;
}

范围for遍历

for (auto e : lt)
{cout << e << ' ';
}

范围for本质上还是迭代器，在编译的时候会被替换成迭代器

1.4.list capapcity

1.5 list element access(元素访问)

1.6 list修改操作

这里只列举了经常使用的，其余的可以参考https://legacy.cplusplus.com/reference/list/list/?kw=list

头插、头删、尾插、尾删我就不再详细介绍；这些操作只能插入删除一个元素！

assign接口功能是新元素替换列表中的内容，它的功能我们完全可以使用list的构造函数替代，这里不再详细介绍；

insert

单个值插入

list<int> lt = {1, 2, 3, 4, 5};
list<int>::iterator it = mylist.begin();
it++; // 将迭代器it移动到第二个位置
lt.insert(it, 1); // 在it位置插入值为1的元素

插入多个相同的值

list<int> lt = {1, 2, 3, 4, 5};
list<int>::iterator it = mylist.begin();
it++; // 将迭代器it移动到第二个位置
lt.insert(it, 3，1); // 在it位置插入3个值为1的元素

迭代器区间插入

list<int> mylist = {1, 2, 3, 4, 5};
auto it = mylist.begin();
it++; // 将迭代器it移动到第二个位置
vector<int> vec = {7, 8, 9};
mylist.insert(it, vec.begin(), vec.end()); // 在it位置插入vector中的元素

erase

删除单个元素

list<int> mylist = {1, 2, 3, 4, 5};
auto it = mylist.begin();
it++; // 将迭代器it移动到第二个位置
mylist.erase(it); // 删除it位置的元素

删除范围内的元素

list<int> mylist = {1, 2, 3, 4, 5};
auto it1 = mylist.begin();
auto it2 = mylist.end();
mylist.erase(it1, it2); // 删除从it1到it2范围内的元素

swap

list<int> l1 = {1, 2, 3};
list<int> l2 = {4, 5, 6};
l1.swap(l2); // 交换l1和l2的元素

clear

list<int> lt = {1, 2, 3, 4, 5};
lt.clear(); // 清空lt的内容，lt现在为空

resize

list<int> lt = {1, 2, 3, 4, 5};
lt.resize(4); // 将lt的大小调整为4，删除多余的元素
lt.resize(6, 100); // 将lt的大小调整为5，多出的元素用100填充

1.7 list iterator迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

解决方法：在下一次指向被删除的节点时，必须先重新赋值

void TestListIterator()
{ list<int> l={1，3，5，6，7，8}；auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}

2.list的模拟实现

list整体实现需要完成三个部分的封装，__list_node(节点)，__list_iterator(迭代器)，list(链表)

__list_node

template <class T>
struct __list_node
{T _data;__list_node<T>* _next;__list_node<T>* _prev;__list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}
};

list是一个带头双向循环链表，因此节点中包含两个指针和数据

__list_iterator

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):_node(node){}
};

我们使用list的节点指针来初始化构造迭代器对象，以上便是迭代器的基本框架

同时迭代器应该还满足以下功能

T& operator*() //重载指针的解引用
{return _node->_data;
}
T* operator->()
{return *_node->_data;
}
//++it
Self& operator++()
{_node = _node->_next;return *this;
}
//it++
Self operator++(int)
{Self tmp = *this;_node = _node->_next;return tmp;
}Self& operator--()
{_node = _node->_prev;return *this;
}//it--//Self operator--(int)//{//	Self tmp = *this//	_node = _node->_prev;//	return tmp;//}
bool operator!=(const Self& it)
{return _node != it._node;
}

list

构造，析构,拷贝构造

list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}
~list()
{clear(); //clear函数不清除头节点delete _head;_head = nullptr;
}
list(const list<T>& lt) //拷贝构造
{_head = new Node;_head->_next = _head;_head->_prev = _head;for (auto e : lt)push_back(e);}

构造一个新的list时，里面只包含一个头节点，因此next指针和prev指针都指向自己

赋值

传统写法

list<T>& operator=(const list<T>& lt)
{if (this != &lt) //防止自己给自己赋值{clear(); //this指针调用clearfor (auto e : lt)push_back(e);}return *this;
}

现代写法

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

增删查改

void push_back(const T& x)
{Node* _tail = _head->_prev; //找到尾节点Node* newnode = new Node(x);_tail->_next = newnode;newnode->_prev = _tail;newnode->_next = _head;_head->_prev = newnode;
}
void insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prv = cur->_prev;Node* newnode = new Node(x);prv->_next = newnode;newnode->_prev = prv;newnode->_next = cur;cur->_prev = newnode;
}
void pop_back()
{erase(end()--);
}
void pop_front()
{erase(begin());
}
void push_front(const T& x)
{insert(begin(), x);
}