list
C++的list是标准模板库中的一个容器，用于存储和管理元素的双向链表。提供了一系列访问和修改数据的函数；
使用时需要包含头文件
#include< list >
下面演示下它的一些基础功能
使用list
list的遍历
int main() { list<int> lt; lt.push_back(1);//尾插 lt.push_back(2); lt.push_back(3); lt.push_back(4); list<int>::iterator it = lt.begin(); while (it != lt.end()) { *it += 10; cout << *it << " "; it++; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; lt.reverse();//倒置 for (auto e : lt) { cout << e << " "; } cout << endl; }
对于list的遍历，常用迭代器来进行访问遍历，list没有vector的[]访问符，也就不通过下标来进行访问；
去重复值
int main() { list<int> lt; lt.push_back(1); lt.push_back(1); lt.push_back(2); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(4); lt.push_back(4); lt.unique();//去重复值 for (auto e : lt) { cout << e << " "; } cout << endl; }
splice
int main() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); for (auto e : lt) { cout << e << " "; } cout << endl; lt.splice(lt.end(), lt, find(lt.begin(), lt.end(), 2)); for (auto e : lt) { cout << e << " "; } cout << endl; }
自我实现list
初始化
push_back()
list的迭代器
list提供了迭代器，用来遍历列表中的元素。可以通过解引用来进行访问元素。
测试1结果： 
insert和erase
析构、拷贝构造、赋值
当时为什么要将初始化empty_init()单独分离出来，就是因为也要让拷贝构造也要初始化，如果拷贝构造没有初始化，将会报错；
赋值还是利用了创建一个临时对象，该对象拷贝实参对象的内容，然后让临时对象与*this进行交换,就完成了赋值；
#pragma once #include<assert.h> #include"reverse_iterator.h" namespace fnc { //链表结构 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, class Ref, class Ptr> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; __list_iterator(Node* x) :_node(x) {} //前置++ self& operator++() { _node = _node->_next; return *this; } //后置++ self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self& operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } Ref operator*() { return _node->_Data; } Ptr operator->() { return &_node->_Data; } bool operator!=(const self& s) { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } }; template <class T> class list { typedef ListNode<T> Node; public: //typedef __list_iterator<T, T&, T*> iterator; //typedef __list_iterator<T, const T&, const T*> const_iterator; //typedef ReverseIterator<iterator, T&, T*> RIterator; //typedef ReverseIterator<const_iterator, const T&, const T*> const_RIterator; iterator begin() { //return iterator(_head_next); return _head->_next;//隐式类型转换 } iterator end() { return _head; } void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } list() { empty_init(); } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } ~list() { clear(); delete _head; _head = nullptr; } //拷贝构造 list(list<T>& lt) { empty_init(); for (const auto& e : lt) { push_back(e); } } void swap(list<T>& tmp) { std::swap(_head, tmp._head); } //赋值 list<T>& operator=(list<T> lt)//? { swap(lt); return *this; } 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;*/ insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } //在pos位置前插入 iterator insert(iterator pos, const T& x) { Node* newnode = new Node(x); Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return newnode; } //删除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; return next; } void func() { //内置类型 Node* it1 = _head->_next; //自定义类型 iterator it2 = _head->_next; *it1; it1++; *it2; it2++; } private: Node* _head; }; void print_list(const list<int>& lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; it++; } cout << endl; } void test_list3() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); cout << "原链表:"; for (auto e : lt) { cout << e << " "; } cout << endl; lt.push_back(66); lt.push_front(44); cout << "前插后插："; for (auto e : lt) { cout << e << " "; } cout << endl; list<int> lt2; lt2.push_back(12); lt2.push_back(23); lt2.push_back(34); lt2.push_back(45); lt = lt2; cout << "lt赋值之后:"; for (auto e : lt) { cout << e << " "; } cout << endl; list<int> lt3(lt); cout << "lt3拷贝构造"; for (auto e : lt3) { cout << e << " "; } cout << endl; } }
const迭代器
运算符->
解释：
原始指针与迭代器
反向迭代器
反向迭代器是一种特殊类型的迭代器，用于逆序遍历容器中的元素。
#pragma once namespace fnc { template <class iterator, class Ref, class Ptr> struct ReverseIterator { typedef ReverseIterator<iterator,Ref,Ptr> Self; iterator cur; ReverseIterator(iterator it) :cur(it) {} Self& operator++() { --cur; return *this; } Self& operator++(int) { Self tmp = *this; --cur; return tmp; } Ref operator*() { iterator tmp = cur; return *--tmp; } Ptr operator->() { iterator tmp = cur; return &(*--tmp); } bool operator!=(const Self& s) { return cur != s.cur; } bool operator==(const Self& s) { return cur == s.cur; } }; }
