网站分为几部分,设计软件排行,月饼营销软文,自己做免费手机网站吗目录#xff08;文章中节点和结点是同一个意思#xff09;
1. list的介绍及使用
1.1 list的介绍
1.2 list的使用
1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity
1.2.4 list element access 1.2.5 list modifiers 1.2.6 list…目录文章中节点和结点是同一个意思
1. list的介绍及使用
1.1 list的介绍
1.2 list的使用
1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity
1.2.4 list element access 1.2.5 list modifiers 1.2.6 list的迭代器失效 2. list的模拟实现
2.1 list_node结点 2.2 list_iterator迭代器 2.2.1 运算符重载!
2.2.2 运算符重载 2.2.3 运算符重载前置 2.2.4 运算符重载后置 2.2.5 运算符重载前置-- 2.2.6 运算符重载后置-- 2.2.7 运算符重载* 2.2.8 运算符重载- 2.3 list类
2.3.1 构造函数
2.3.1.1默认构造函数list 2.3.1.2 拷贝构造
2.3.1.3 list(std::initializer_list lt) 2.3.2 析构函数
2.3.3 赋值运算符重载 2.3.4 front和back
2.3.5 size和begin和end
2.3.6 insert插入和erase删除
2.3.6.1 insert插入 2.3.6.2 erase删除
2.3.7 头插push_front头删pop_front尾插push_back尾删pop_back
2.4 整体代码 1. list的介绍及使用
1.1 list的介绍
std::list是 C 标准模板库STL中的一个容器类底层实现为双向链表适用于需要频繁插入和删除操作的场景。
1.2 list的使用
以下为list中一些常见的重要接口。
1.2.1 list的构造
构造函数 (constructor)接口说明list (size_type n, const value_type val value_type())构造的list中包含n个值为val的元素list()构造空的listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造 list
使用演示 void test1()
{listint l1(10, 5);listint l2;listint l3(l1);listint l4(l1.begin(),l1.end());for (auto e : l1){cout e ;}cout endl;for (auto e : l2){cout e ;}cout endl;for (auto e : l3){cout e ;}cout endl; for (auto e : l4){cout e ;}cout endl;
} 结果 1.2.2 list iterator的使用
这里可以暂时将迭代器理解成一个指针该指针指向list中的某个节点。其实底层实现时迭代器是一个封装的对象
函数声明接口说明begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位 置的reverse_iterator,即begin位置
1. begin与end为正向迭代器对迭代器执行操作迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动
使用演示 void test2()
{listint l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);listint::reverse_iterator rit l.rbegin();while (rit ! l.rend()){cout *rit ;rit;}cout endl;listint::iterator it l.begin();while (it ! l.end()){cout *it ;it;}cout endl;
} 结果 1.2.3 list capacity
函数声明接口说明empty检测list是否为空是返回true否则返回falsesize返回list中有效节点的个数
使用演示 void test3()
{listint l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);if(!l.empty()){cout 该链表非空 endl;}cout 有效节点个数 l.size() endl;
} 结果 1.2.4 list element access
函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用 使用演示 void test4()
{listint l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);cout l.front() endl;cout l.back() endl;
} 结果 1.2.5 list modifiers
函数声明接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在list position 位置中插入值为val的元素erase删除list position位置的元素swap交换两个list中的元素clear清空list中的有效元素
使用演示 push_front和pop_front使用: void test5()
{listint l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);for (auto e : l){cout e ;}cout endl;l.push_front(10);cout 头插后:;for (auto e : l){cout e ;}cout endl;l.pop_front();cout 头删后:;for (auto e : l){cout e ;}cout endl;
} 结果 push_back和pop_back: void test6()
{listint l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);for (auto e : l){cout e ;}cout endl;l.push_back(6);cout 尾插后:;for (auto e : l){cout e ;}cout endl;l.pop_back();cout 尾删后:;for (auto e : l){cout e ;}cout endl;
} 结果 insert和erase: void test7()
{listint l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);for (auto e : l){cout e ;}cout endl;l.insert(l.begin(), 30);cout 插入后:;for (auto e : l){cout e ;}cout endl;l.erase(--l.end());cout 删除后:;for (auto e : l){cout e ;}cout endl;
} 结果 swap: void test8()
{listint l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);listint l2(5, 5);cout 交换前 endl;cout l1:;for (auto e : l1){cout e ;}cout endl;cout l2:;for (auto e : l2){cout e ;}cout endl;cout 交换后 endl;l1.swap(l2);cout l1:;for (auto e : l1){cout e ;}cout endl;cout l2:;for (auto e : l2){cout e ;}cout endl;
}结果 clear void test9()
{listint l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);cout 清空前 endl;cout 有效元素个数 l1.size() endl;for (auto e : l1){cout e ;}cout endl;l1.clear();cout 清空后 endl;cout 有效元素个数 l1.size() endl;for (auto e : l1){cout e ;}cout endl;
} 结果 1.2.6 list的迭代器失效
小编前面文章里面“vector迭代器失效”提到只要使用erase或者insert之后迭代器就直接失效但是对于list有所不同迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。 举例删除所有结点 void test10()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));auto it l.begin();while (it ! l.end()){// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给其赋值l.erase(it);it;}
} 结果 可以看到这里报段错误迭代器失效了。 改进后 void test10()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));auto it l.begin();while (it ! l.end()){itl.erase(it);}
} 因为erase函数删除后会返回删除结点的下一个节点迭代器it接收返回值相当于更新了迭代器。 2. list的模拟实现
这里利用双向带头链表实现因为链表的物理空间并不是连续的所以这里的迭代器不能使用指针这里对迭代器进行了封装实现一个对象。还有这里为了和原本库里list区分将自己写的list封装在命名空间里作者的是iu
2.1 list_node结点
templateclass T
struct list_node
{list_nodeT* _prev;list_nodeT* _next;T _value;list_node(const T x T()):_prev(nullptr),_next(nullptr),_value(x){}
}; 双向带头链表所以成员有前驱结点和后继结点和元素对象。 2.2 list_iterator迭代器
templateclass T,class REF,class PTR
struct list_iterator
{typedef list_nodeT Node;typedef list_iteratorT, REF, PTR Self;Node* _node;list_iterator(Node* node):_node(node){}}; 这里模版为什么会有REF和PTR其实是解决范围for迭代器访问时会有const修饰的对象如果直接确定的写只有普通对象可以所以这里多给两个参数模版让编译器自己去判断是const修饰的对象还是普通对象。 2.2.1 运算符重载!
bool operator!(const Self it)
{return _node!it._node;
}
2.2.2 运算符重载
bool operator(const Self it)
{return _node it._node;
} 2.2.3 运算符重载前置
Self operator()
{_node _node-_next;return *this;
} 结点的指向直接向后移动一位。 2.2.4 运算符重载后置
Self operator(int)
{Self tmp(*this);_node _node-_next;return tmp;
} 创建一个临时对象节点的指向向后移动一位返回临时对象。 2.2.5 运算符重载前置--
Self operator--()
{_node _node-_prev;return *this;
} 结点的指向直接向前移动一位。 2.2.6 运算符重载后置--
Self operator(int)
{Self tmp(*this);_node _node-_next;return tmp;
} 创建一个临时对象节点的指向向前移动一位返回临时对象。 2.2.7 运算符重载*
REF operator*()
{return _node-_value;
} 解引用就是返回对象的值。 2.2.8 运算符重载-
PTR operator-()
{return _node-_value;
} 这里为什么是取值的地址通过下面的例子来讲解 void test2()
{struct A{A(int a 0,int b0):_a(a),_b(b){}int _a;int _b;};iu::listAl2;l2.push_back({1,1});l2.push_back({2,2});l2.push_back({3,3});l2.push_back({4,4});iu::listA::iterator it l2.begin();while (it ! l2.end()){cout (*it)._a : it-_b endl;it;}
} 这里可以利用解引用在去访问A类中的成员这是一种访问方式而这个it-b是如何访问的前面实现的是返回A的地址拿到A对象的地址和成员_b之间也没有运算符那有怎么样才能访问到_b呢其实这里省略了一个-,这里其实应该是it--_b所以先拿到A对象的地址再利用结构体-这种方式。解引用访问里面的成员。 结果 2.3 list类 templateclass Tclass list{typedef list_nodeT Node;public:typedef list_iteratorT,T,T* iterator;typedef list_iteratorT, const T, const T* const_iterator;private:Node* _head;size_t _size;};
} 成员有头结点和元素个数。 2.3.1 构造函数
2.3.1.1默认构造函数list
void empty_init()
{_head new Node;_head-_prev _head;_head-_next _head;_size 0;
}list()
{empty_init();
} 这里利用empty_init函数进行初始化是为了方便后面几个构造函数先初始化再尾插的操作。 2.3.1.2 拷贝构造
list(const listT lt)
{empty_init();for (auto e : lt){push_back(e);}
} 初始化再遍历一遍lt进行尾插依次插入。 2.3.1.3 list(std::initializer_listT lt)
list(std::initializer_listT lt)
{empty_init();for (auto e : lt){push_back(e);}
} 和上面同理。 这里举一个例子 void test8()
{iu::listintl1 { 1,2,3,4,5,6,7 };for (auto e : l1){cout e ;}cout endl;
} 结果 这个initializer_listT类型是一个类似于数组的类型可以理解成一种类似数组初始化的方式。 2.3.2 析构函数
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}~list()
{clear();delete _head;_head nullptr;
} 先在clear函数里面将数据全部清除再将头结点释放掉置为空。 2.3.3 赋值运算符重载
void swap(listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}listT operator(listT lt)
{swap(lt);return *this;
} 利用std中的交换函数将临时对象与this指向的对象进行交换临时对象出了作用域会自然销毁也不会影响实参这样就相当于实现了赋值操作。 2.3.4 front和back
T front()
{return _head-_next-_value;
}const T front()const
{return _head-_next-_value;
}
T back()
{return _head-_prev-_value;
}
const T back()const
{return _head-_prev-_value;
} 这里利用的是双向带头链表所以头部front元素就是头结点的下一个尾结点back就是头结点的前一个。这里还重载了const修饰的对象当对象元素是不可改变的const时也可以使用。 2.3.5 size和begin和end
size_t size()
{return _size;
}iterator begin()
{return _head-_next;
}iterator end()
{return _head;
}const_iterator begin() const
{return _head-_next;
}const_iterator end() const
{return _head;
} size函数直接返回成员_size大小即可。 begin()返回头结点的下一个结点的迭代器end()返回最后一个元素的下一个结点的迭代器所以就是头结点head这里也是重载了const修饰的对象当对象元素是不可改变的const时也可以使用。 2.3.6 insert插入和erase删除
2.3.6.1 insert插入
void 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;_size;
} 首先创建一个新的结点再进行插入操作插入时先找到pos位置的结点和pos位置的前一个结点再改变前后指针指向即可最后_size再加1。 2.3.6.2 erase删除
iterator erase(iterator pos)
{assert(pos ! end());Node* del pos._node;Node* prev del-_prev;Node* next del-_next;prev-_next next;next-_prev prev;delete del;--_size;return iterator(next);
} 首先找到pos位置的结点再确定pos前一个结点和后一个结点的位置最后改变指针指向再删除pos位置的节点_size再减1最后还要返回删除节点的下一个位置的结点返回匿名对象即可。 2.3.7 头插push_front头删pop_front尾插push_back尾删pop_back
void push_back(const T x)
{insert(end(), x);
}
void push_front(const T x)
{insert(begin(), x);
}
void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
} 这里直接复用insert和erase函数实现只是要注意尾结点的位置是end()的前一个位置。 例子 void test4()
{iu::listintl1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.insert(l1.begin(), 10);l1.insert(l1.begin(), 20);for (auto e : l1){cout e ;}cout endl;l1.pop_back();l1.pop_back();l1.pop_front();l1.pop_front();for (auto e : l1){cout e ;}cout endl;
} 结果 2.4 整体代码
#includeassert.h
#includealgorithm
#include initializer_listnamespace iu
{templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _value;list_node(const T x T()):_prev(nullptr),_next(nullptr),_value(x){}};templateclass T,class REF,class PTRstruct list_iterator{typedef list_nodeT Node;typedef list_iteratorT, REF, PTR Self;Node* _node;list_iterator(Node* node):_node(node){}bool operator!(const Self it){return _node!it._node;}bool operator(const Self it){return _node it._node;}REF operator*(){return _node-_value;}PTR operator-(){return _node-_value;}Self operator(){_node _node-_next;return *this;}Self operator--(){_node _node-_prev;return *this;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef list_iteratorT,T,T* iterator;typedef list_iteratorT, const T, const T* const_iterator;void empty_init(){_head new Node;_head-_prev _head;_head-_next _head;_size 0;}list(){empty_init();}void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}listT operator(listT lt){swap(lt);return *this;}list(std::initializer_listT lt){empty_init();for (auto e : lt){push_back(e);}}list(const listT lt)//拷贝构造{empty_init();for (auto e : lt){push_back(e);}}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}T front(){return _head-_next-_value;}const T front()const{return _head-_next-_value;}T back(){return _head-_prev-_value;}const T back()const{return _head-_prev-_value;}size_t size(){return _size;}iterator begin(){return _head-_next;}iterator end(){return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}void push_back(const T x){//Node* newnode new Node(x);//Node* tail _head-_prev;//newnode-_prev tail;//tail-_next newnode;//newnode-_next _head;//_head-_prev newnode;insert(end(), x);}void push_front(const T x){insert(begin(), x);}void 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;_size;}iterator erase(iterator pos){assert(pos ! end());Node* del pos._node;Node* prev del-_prev;Node* next del-_next;prev-_next next;next-_prev prev;delete del;--_size;return iterator(next);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}private:Node* _head;size_t _size;};
}
