河南经贸一站式服务平台,佛山网站制作好处,wordpress需要付费才能看某些页面,龙岩做网站开发哪家做的好目录
一.核心特性
1.双向循环链表结构
2.头文件#xff1a;#include 3.时间复杂度
4.内存特性
二.构造函数
三.list iterator的使用
1.学习list iterator之前我们要知道iterator的区分
编辑 2.begin()end()
3.rbegin()rend() 四.list关键接口
1.empty()
2. size…目录
一.核心特性
1.双向循环链表结构
2.头文件#include
3.时间复杂度
4.内存特性
二.构造函数
三.list iterator的使用
1.学习list iterator之前我们要知道iterator的区分
编辑 2.begin()end()
3.rbegin()rend() 四.list关键接口
1.empty()
2. size()
3.front()
4. back()
5.push_front()
6. pop_front()
7.push_back()
8. pop_back()
9.insert ()
10.erase()
11.swap()
12.clear()
五.list的迭代器失效
六.模拟实现list
1.List.h
2.test.cpp 七.list与vector的对比 一.核心特性 1.双向循环链表结构
每个节点包含前驱和后继指针 2.头文件#include list
3.时间复杂度
任意位置插入/删除O(1)
随机访问O(n)
排序O(n log n)
4.内存特性
非连续内存存储
每个元素需要额外存储两个指针前驱后继
内存占用 ≈ sizeof(T)2 2指针大小 二.构造函数 int main()
{listT lst1; // 空链表listT lst2(n); // n个默认初始化元素listT lst3(n, value); // n个value副本listT lst4(begin, end);// 迭代器范围构造listT lst5(init_list); // 初始化列表 C11listT lst6(lst4); // 拷贝构造
} 三.list iterator的使用 1.学习list iterator之前我们要知道iterator的区分 功能上区分 iterator普通迭代器reverse_iterator反向迭代器const_iterator只读迭代器const_reverse_iterator只读反向迭代器 性质上区分 名称代表容器支持操作单向迭代器ForwardIteratorForward_list(单链表)unordered_map双向迭代器BidirectionalIteratorlist(链表)mapset/--随机迭代器RandomAccessIteratorvectorstringdeque/--//- 通过底层结构决定可以实现哪些算法 比如算法库里的sort要求使用随机迭代器list就无法使用这个算法 对于算法库里的reverse和find可以正常使用 可以得知功能是向上兼容得 此处大家可暂时将迭代器理解成一个指针该指针指向list中的某个节点 2.begin()end() 返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器 3.rbegin()rend() 返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的reverse_iterator,即begin位置 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto it lt.rbegin();while (it ! lt.rend()){cout *it ; //4 3 2 1it;}cout endl; begin与end为正向迭代器对迭代器执行操作迭代器向后移动rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动 四.list关键接口 1.empty() 检测list是否为空是返回true否则返回false listint lt;coutlt.empty()endl; //1lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout lt.empty(); //0 2. size() 返回list中有效节点的个数 listint lt;coutlt.size()endl; //0lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout lt.size(); //4 3.front() 返回list的第一个节点中值的引用 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout lt.front(); //1 4. back() 返回list的最后一个节点中值的引用 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout lt.back(); //4 5.push_front() 在list首元素前插入值为val的元素 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5); //5 1 2 3 4 6. pop_front() 删除list中第一个元素 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.pop_front(); //2 3 4 7.push_back() 在list尾部插入值为val的元素 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5); //1 2 3 4 5 8. pop_back() 删除list中最后一个元素 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.pop_back(); //1 2 3 9.insert () 在list position 位置中插入值为val的元素 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);std::listint::iterator it;itlt.begin();int k 3;while (k--){it;}lt.insert(it, 30); 1 2 3 30 4 10.erase() 删除list position位置的元素 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);std::listint::iterator it;itlt.begin();int k 2;while (k--){it;}lt.erase(it); //1 2 4 11.swap() 交换两个list中的元素 std::listint first(3, 100); // 100 100 100std::listint second(5, 200); // 200 200 200 200 200first.swap(second); // 200 200 200 200 200 12.clear() 清空list中的有效元素 std::listint mylist;mylist.push_back(1101); //1101mylist.clear();mylist.push_back(2202); //2202return 0; 五.list的迭代器失效 前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响
void TestListIterator1() {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 TestListIterator() {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()) {l.erase(it); // it l.erase(it);}
}
六.模拟实现list 1.List.h
#pragma once // 防止头文件重复包含
#includeassert.h // 断言检查// 实现双向链表及相关迭代器
class bit
{// 链表节点结构体模板templateclass Tstruct list_node{T _data; // 节点存储的数据list_nodeT* _next; // 后继指针list_nodeT* _prev; // 前驱指针// 节点构造函数默认构造空对象list_node(const T data T()):_data(data), _next(nullptr), _prev(nullptr){}};// 链表迭代器结构体模板支持普通/const迭代器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) {}// 解引用操作符返回数据引用Ref operator*() { return _node-_data; }// 成员访问操作符返回数据指针// 使得 it-member 等价于 (it-)_data-memberPtr 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;return tmp;}// 后置--同上self operator--(int) {self tmp(*this);_node _node-_prev;return tmp;}// 比较操作符重载bool operator!(const self s) const { return _node ! s._node; }bool operator(const self s) const { return _node s._node; }};// 链表类模板template class Tclass list{typedef list_nodeT Node; // 节点类型简写public:/*typedef list_iteratorT iterator;typedef list_const_iteratorT const_iterator;*/ //两个代码相似度太高所以通过增加模板参数实现// 迭代器类型定义通过模板参数实现const重载typedef list_iteratorT, T, T* iterator; // 普通迭代器typedef list_iteratorT, const T, const T* const_iterator; // const迭代器// 获取起始迭代器指向第一个有效节点iterator begin() { return _head-_next; }// 获取结束迭代器哨兵节点iterator end() { return _head; }// const版本迭代器const_iterator begin() const { return _head-_next; }const_iterator end() const { return _head; }// 初始化哨兵节点构建空链表void empty_init() {_head new Node; // 申请头节点_head-_next _head; // 初始状态自环_head-_prev _head;_size 0; // 大小置零}// 默认构造函数list() { empty_init(); }// 初始化列表构造支持花括号初始化list(std::initializer_listT il) {empty_init();for (auto e : il) { // 遍历列表插入元素push_back(e);}}// 拷贝构造函数深拷贝list(const listT lt) {empty_init();for (auto e : lt) { // 遍历插入每个元素push_back(e);}}// 赋值运算符拷贝交换惯用法listT operator(listT lt) {swap(lt); // 交换资源return *this;}// 析构函数清理节点~list() {clear(); // 删除所有数据节点delete _head; // 释放哨兵节点_head nullptr;}// 清空链表保留哨兵节点void clear() {auto it begin();while (it ! end()) { // 逐个删除节点it erase(it);}}// 交换两个链表内容void swap(listT lt) {std::swap(_head, lt._head); // 交换头指针std::swap(_size, lt._size); // 交换大小}// 尾插复用insert实现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); //直接调用insert}// 头插void push_front(const T x) { insert(begin(), x); }// 在pos位置前插入新节点iterator insert(iterator pos, const T x) {Node* cur pos._node; // 当前节点Node* prev cur-_prev; // 前驱节点Node* newnode new Node(x); // 创建新节点// 调整指针链接newnode-_next cur;cur-_prev newnode;newnode-_prev prev;prev-_next newnode;_size; // 更新大小return newnode; // 返回新节点位置}// 尾删void pop_back() { erase(--end()); }// 头删void pop_front() { erase(begin()); }// 删除pos位置节点注意原代码此处返回类型应为iteratoriterator erase(iterator pos) {assert(pos ! end()); // 不能删除哨兵节点Node* prev pos._node-_prev; // 前驱节点Node* next pos._node-_next; // 后继节点// 调整链接关系prev-_next next;next-_prev prev;delete pos._node; // 释放节点--_size; // 更新大小return next; // 返回下一位置的迭代器}// 获取元素数量size_t size() const { return _size; }// 判断是否为空bool empty() const { return _size 0; }private:Node* _head; // 哨兵头节点size_t _size; // 元素个数};
};// 打印容器内容泛型模板
templateclass Container
void print_container(const Container con) {// 使用const迭代器遍历保证内容不被修改// const iterator - 迭代器本身不能修改// const_iterator - 指向内容不能修改typename Container::const_iterator it con.begin(); // typename指明依赖类型//auto it con.begin();或者使用autowhile (it ! con.end()) {std::cout *it ;it;}std::cout std::endl;// 范围for遍历C11特性for (auto e : con) {std::cout e ;}std::cout std::endl;
}
2.test.cpp
#include iostream
#include list
#includealgorithmusing namespace std;
#includelist.hvoid test_list1()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl;/*it lt.begin();lt.erase(it 3);*/// 不支持要求随机迭代器//sort(lt.begin(), lt.end());string s(dadawdfadsa);cout s endl;sort(s.begin(), s.end());cout s endl;
}
void test_list3()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);for (auto e : lt){cout e ;}cout endl;auto it lt.begin();int k 3;while (k--){it;}lt.insert(it, 30);for (auto e : lt){cout e ;}cout endl;int x 0;cin x;it find(lt.begin(), lt.end(), x);if (it ! lt.end()){lt.erase(it);}for (auto e : lt){cout e ;}cout endl;
}
void test_list4()
{// 直接构造listint lt0({ 1,2,3,4,5,6 });// 隐式类型转换listint lt1 { 1,2,3,4,5,6,7,8 };const listint lt3 { 1,2,3,4,5,6,7,8 };print_container(lt1);
}int main()
{//test_list3();//test_list4();test_list1();}七.list与vector的对比
vectorlist底 层 结 构动态顺序表一段连续空间带头结点的双向循环链表随 机 访 问支持随机访问访问某个元素效率O(1)不支持随机访问访问某个元素效率O(N)插 入 和 删 除任意位置插入和删除效率低需要搬移元素时间复杂度为O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更 低任意位置插入和删除效率高不需要搬移元素时间复杂度为O(1)空 间 利 用 率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭 代 器原生态指针对原生态指针(节点指针)进行封装 迭 代 器 失 效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使 用 场 景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问 学到C11时需要补充一些新的接口。
