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 != <) //防止自己给自己赋值{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);
}