10.list的模拟实现(普通迭代器和const迭代器的类模板)
1. list的介绍及使用
1.1 list的介绍
list的文档介绍
-
list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
-
list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
-
list
与forward_list
非常相似:最主要的不同在于forward_list
是单链表,只能朝前迭代,已让其更简单高效。 -
与其他的序列式容器相比(
array,vector,deque
),list
通常在任意位置进行插入、移除元素的执行效率更好。 -
与其他序列式容器相比,
lis
t和forward_list
最大的缺陷是不支持任意位置的随机访问,比如:要访问list
的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
1.2 list的使用
头插、尾插、尾删、头删
#include <vector>
#include <algorithm>
#include <time.h>
#include <set>
using namespace std;#include "List.h"void test_list1()
{// 尾插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()){cout << *it << " ";++it;}cout << endl;// 头插lt.push_front(10);lt.push_front(20);lt.push_front(30);lt.push_front(40);for (auto e : lt){cout << e << " ";}cout << endl;// 尾删lt.pop_back();lt.pop_back();// 头删lt.pop_front();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();//lt.pop_back();for (auto e : lt){cout << e << " ";}cout << endl;
}
insert的用法
void test_list2()
{list<int> lt;// 尾插lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto pos = find(lt.begin(), lt.end(), 3);if (pos != lt.end()){// insert就是在pos位置前插入一个节点// insert以后pos是否失效呢?(此处不存在失效)// 在vector中,扩容后,pos的形参发生改变,但是实参不会发生改变// 但是list是用链表结构,就算扩容,也不会使pos的形参发生变化lt.insert(pos, 30);}// 下面两个代码的测试可以发现,pos并不会失效cout << *pos << endl;(*pos)++;for (auto e : lt){cout << e << " ";}cout << endl;// 此处pos失效,因为pos指向的节点都被释放了,那么再访问pos指向的空间,就会造成野指针lt.erase(pos);//cout << *pos << endl;for (auto e : lt){cout << e << " ";}cout << endl;
}
remove的用法
void test_list3()
{list<int> lt;lt.push_back(10);lt.push_back(2);lt.push_back(5);lt.push_back(3);lt.push_back(4);lt.push_back(4);lt.push_back(6);lt.push_back(4);lt.push_back(3);for (auto e : lt){cout << e << " ";}cout << endl;// 打印结果为:10 2 5 3 4 4 6 4 3// void remove (const value_type& val);// 从容器中删除所有与 val 相等的元素。这将调用这些对象的析构函数,并按删除的元素数减小容器大小。// 因此,会将链表中val值为3的节点全部删除,并缩小容器的大小lt.remove(3);for (auto e : lt){cout << e << " ";}cout << endl;// 打印结果为:10 2 5 4 4 6 4lt.remove(30);for (auto e : lt){cout << e << " ";}cout << endl;// 打印结果为:10 2 5 4 4 6 4lt.sort(); // 链表自带的排序功能/*sort(lt.begin(), lt.end()); // 库里面自带的排序功能,参数为迭代器的起始和结束位置*/for (auto e : lt){cout << e << " ";}cout << endl;// 先排序,才能实现去重/*void unique();没有参数的版本从容器中每个连续的相等元素组中删除除第一个元素之外的所有元素。请注意,只有当元素与紧接其前面的元素相等时,才会从列表容器中删除该元素。因此,此函数对于排序列表特别有用。*/lt.unique();for (auto e : lt){cout << e << " ";}cout << endl;
}
vector和list排序速度的比较
void test_op()
{srand(time(0));const int N = 100000;// 创建一个vector对象,并提前预留足够大的空间vector<int> v;v.reserve(N);// 创建两个list对象list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){// 将生成的随机数,尾插到两个链表中auto e = rand();//v.push_back(e);lt1.push_back(e);lt2.push_back(e);}// 将链表lt1中的数据,拷贝到vector对象v中int begin1 = clock();for (auto e : lt1){v.push_back(e);}// 使用std::sort对vector对象v中的数据进行排序sort(v.begin(), v.end());size_t i = 0;for (auto& e : lt1){// e是lt1数据的引用// 所以对e进行赋值,就是拷贝v中的数据到lt1中e = v[i++];}int end1 = clock();// 直接使用链表中自带的排序函数,对链表2中的数据进行排序int begin2 = clock();// sort(lt.begin(), lt.end());lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);/*// 打印结果为:vector sort : 246list sort : 118*/// 综上可知,vector的排序速度是远大于list的排序速度的
}
2. list的模拟实现
list的私有成员变量
private:node* _head; // 链表的头节点size_t _size; // 链表的大小
list_node(节点的类)
// 此处的T和list<T>是同一个模板参数
template<class T>
struct list_node
{// _next指向下一个节点list_node<T>* _next;// _prev指向前一个节点list_node<T>* _prev;// 该节点存放的数据T _data;// 节点的构造函数list_node(const T& x) :_next(nullptr) , _prev(nullptr), _data(x){}
};
__list_iterator(迭代器的类)
迭代器的价值:
1.封装底层实现,不暴露底层实现的细节。
2.提供统一的访问方式,降低使用成本。
// 迭代器的类类型就是__list_iterator<T>
// 类名就是__list_iterator
template<class T>
struct __list_iterator
{// list_node<T> 就是节点的类类型,将节点的类类型定义为nodetypedef list_node<T> node;// 定义了一个节点指针,但是并没有进行初始化node* _pnode; // 迭代器的构造函数__list_iterator(node* p) :_pnode(p) // 使用传递的节点p来初始化_pnode{}// 迭代器的解引用// it为迭代器,(*it)++ 其实就是对_pnode->_data进行++, 因为是传引用返回// T会根据_pnode->_data的类型,实例化对应的类型T& operator*() // 解引用,就是返回 _pnode->data{return _pnode->_data;}// 迭代器++// ++ 也就是返回_pnode->next指向节点的地址// 此处是传引用返回,因为_pnode->_next指向的节点存在于主函数中,// 所以传引用返回后依旧可以进行读写操作// __list_iterator<T>& 就是对迭代器对象的引用// __list_iterator<T>是迭代器的类型__list_iterator<T>& operator++() {// 修改迭代器成员变量_pnode指向的节点_pnode = _pnode->_next;// this就是迭代器对象的指针// 返回*this,就是返回迭代器对象return *this; }bool operator!=(const __list_iterator<T>& it){// 判断是否相等,也就是判断两个迭代器的_pnode是否相等,比较地址是否相等return _pnode != it._pnode; }
};
__list_const_iterator(const迭代器的类)
// 跟普通迭代器的区别:遍历,不能用*it修改数据
// it就是迭代器对象,*it就是迭代器指向的节点的数据,
// 对于const迭代器,const修饰的是*it,因此对于*it只能读,不能够进行修改/*
1.const T* p1; // const在*左侧,修饰的是*p1
2.T* const p2; // const在*右侧,修饰的是p2
// const迭代器类似于第一种情况,保护指向的对象不被修改,但是迭代器本身是可以修改的注:普通迭代器前加const可不是const迭代器,如下:
const list<int>::iterator cit = lt.begin();
// 这里的const修饰的是cit,也就是保护迭代器本身不可以进行修改,那么就不可以对cit进行++,或者--的操作,这不符合迭代器的行为
*/
template<class T>
struct __list_const_iterator
{// list_node<T> 就是节点的类类型,将节点的类类型定义为nodetypedef list_node<T> node;// 定义了一个节点指针,但是并没有进行初始化node* _pnode;// const迭代器的构造函数__list_const_iterator( node* p):_pnode(p){}// const迭代器的解引用const T& operator*() {// 会根据_pnode->_data类型,来实例化const T& 的类型// const修饰的是返回值,因此返回值无法进行修改// 之所以可以进行引用返回,是因为_pnode->_data不会随着函数而结束自身的生命周期return _pnode->_data;}// const迭代器++// __list_const_iterator<T>是const迭代器的类型// __list_const_iterator<T>& 是对const迭代器对象的引用// 此处的返回值,可以被传引用返回__list_const_iterator<T>& operator++(){// 更新const迭代器对象的成员变量_pnode指向的节点_pnode = _pnode->_next;// 返回迭代器对象return *this;}// const迭代器--__list_const_iterator<T>& operator--(){_pnode = _pnode->_prev;return *this;}// const迭代器判断是否相等bool operator!=(const __list_const_iterator<T>& it){return _pnode != it._pnode;}
};
对普通迭代器和const迭代器的合并
// 我们发现迭代器和const迭代器,有大量的冗余代码,因此做出合并
/*
Ref 是reference的缩写
ref就是引用,ptr就是指针
template<class T, class Ref, class Ptr>同一个类模板实例化出的两个类型,
Ref可以被实例化为T&,也可以被实例化为const T&
Ptr可以被实例化为T*,也可以被实例化为const T*
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;如果是节点类型为 list<int>
则template<class T, class Ref, class Ptr>将被实例化为下面两种类类型
也就是将一个迭代器类模板,实例化为了两个类,一个普通迭代器的类,一个const迭代器的类
typedef __list_iterator<int, int&, int*> iterator;
typedef __list_iterator<int, const int&, const int*> const_iterator;
*/
template<class T, class Ref, class Ptr>
struct __list_iterator
{// 将节点的类类型定义为nodetypedef list_node<T> node;// 将迭代器的类类型定义为Selftypedef __list_iterator<T, Ref, Ptr> Self;// 定义了一个节点指针,但是并没有进行初始化node* _pnode;// 迭代器的构造函数__list_iterator(node* p):_pnode(p){}// 迭代器的->操作// 通过指针访问节点对象的成员变量data// 在主函数中,如果创建const迭代器,也就是 const_iterator cit(head->next)// 因为typedef __list_iterator<T, const T&, const T*> const_iterator;// template<class T, class Ref, class Ptr>// 所以Ptr对应的类型是const int*,// 如果链表的类类型是list<int>// 那么Ptr的类型是const int*,Ptr operator->(){ // _pnode是链表节点的指针// _pnode->_data,可以拿到链表节点存放的数据// &_pnode->_data,也就是取链表节点存放的数据的地址return &_pnode->_data;}/*// (详细看test_list5)下面这两种方法是等价的cout << it->_row << ":" << it->_col << endl;cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;// it-> 是一个函数调用,即it.operator->()// it.operator->() 的返回对象类类型是pos*,所以再次使用-> ,返回pos类型的成员变量row的值// 本来面貌:it->->_row,编译器为了可读性,做了特殊处理,省略了一个->*/// 同上,Ref的类型应该是const int&Ref operator*(){return _pnode->_data;}// ++it 前置// 因为typedef __list_iterator<T, Ref, Ptr> Self;所以Self就是一个迭代器的类类型Self& operator++(){_pnode = _pnode->_next;// 返回一个迭代器对象(++之后的迭代器对象)return *this;}// it++ 后置:括号中的int为占位符Self operator++(int){// 使用this指针指向的迭代器对象构造一个临时的迭代器对象Self tmp(*this);_pnode = _pnode->_next; // 返回++之前的迭代器对象,这个对象是一个临时对象,因此不可以进行传引用返回return tmp;}// 前置Self& operator--(){_pnode = _pnode->_prev;return *this;}// 后置:括号中的int为占位符Self operator--(int){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}
};
反向迭代器的类模板
// reverse_iterator.h
// 如果要使用反向迭代器,必须要使用反向迭代器的头文件
// 给我不同容器的正向迭代器,适配出对应的这个容器需要的反向迭代器
template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{typedef ReverseIterator<Iterator, Ref, Ptr> Self;public:// 构造函数ReverseIterator(Iterator it):_it(it){}// 以list为例// begin() 对应的是 rend() ; begin() 指向首个元素 --> rend() 指向首个元素// end() 对应的是 rbegin() ; end() 指向的是哨兵位 --> rbegin() 指向的是哨兵位/*end() begin()哨兵位 1 2 3 4rbegin() rend()rend() rbegin() 进行--操作之后的位置*/// 因此 解引用指向的元素时,必须 --tmp// 因为begin() 进行--操作之后,与rbegin()对应的节点是一致的// 如 return reverse_iterator(begin()); 使用正向迭代器的开始迭代器 构造 反向迭代器的结束迭代器// 如果要进行解引用,--正向迭代器之后才是其正确的位置Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){// 反向迭代器的++对应正常迭代器的----_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!= (const Self& s) const{return _it != s._it;}private:Iterator _it;
};
list双向链表的构造函数
/*
// 节点的构造函数
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
*//*
list()
{// T()就是构造节点所需要的参数const T& x// T():也就是调用x的默认构造函数去初始化这个参数x // T():类型为x的一个匿名对象_head = new node(T()); _head->_next = _head;_head->_prev = _head;
}
*/void empty_initialize()
{_head = new node(T());_head->_next = _head;_head->_prev = _head;
}// 双向链表的无参构造函数
list()
{empty_initialize();
}
list::push_back, push_front, pop_front, pop_back
//尾插
void push_back(const T& x)
{// 方法一/*// 先创建一个新节点node* newnode = new node(x); // _head->prev中存放的是tail节点的地址node* tail = _head->_prev; // _head newnode tail// 将上面三个节点按顺序双向链接起来tail->_next = newnode; newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/// 方法二// 当我们实现insert()之后,我们就可以通过insert()来实现 push_back// 也就是在end()位置前插入insert(end(), x);
}
// 头插
void push_front(const T& x)
{// 头插就是在begin()位置前插入insert(begin(), x);
}// 头删
void pop_front()
{// 头删就是删除begin()位置的节点erase(begin());
}// 尾删
void pop_back()
{// 尾删就是删除end()位置前的节点// --end() 会调用operator--erase(--end());
}
list的拷贝构造函数的传统写法
void empty_initialize()
{_head = new node(T());_head->_next = _head;_head->_prev = _head;
}// lt3(lt1)
list(const list<T>& lt)
{// 初始化这个对象,也就是初始化lt3empty_initialize();// 将迭代器节点指向数据尾插到新对象中// lt是lt1的引用,也就是将lt1的数据尾插到lt3// 这样就实现了lt1到lt3的拷贝for (const auto& e : lt){push_back(e);}
}
list拷贝函数的现代写法
// 类名 类型
// 普通类 类名 等价于 类型
// 类模板 类名 不等价于 类型
// 如:list模板 类名是list 类型是list<T>
// 类模板里面可以用类名代表类型,但是建议不要那么用// 构造函数(使用迭代器来构造对象)
// tmp(lt)
template <class InputIterator>
list(InputIterator first, InputIterator last)
{// 初始化这个对象,也就是初始化tmpempty_initialize();// first就是链表lt起始位置的迭代器对象// last就是链表lt结束位置的迭代器对象while (first != last){// 将迭代器的数据,尾插到新的链表tmp中push_back(*first);++first;}
}void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}// 现代写法
// lt3(lt1)
list(const list<T>& lt)
{// 初始化这个对象,也就是初始化lt3empty_initialize();// 用it的迭代区间数据创建一个list的临时对象list<T> tmp(lt.begin(), lt.end()); // 再将临时对象与目标对象的_head,_size进行交换// 出了当前函数的作用域之后,tmp就会被销毁// 但是构造给tmp的资源都已经交给了lt3swap(tmp);
}
list对象的赋值重载
void clear()
{iterator it = begin();while (it != end()){// erase()会返回被删除节点的下一个节点的迭代器// 最后it就是end()位置的迭代器,那么就会跳出循环// end()位置的迭代器,也就是_head哨兵位节点的迭代器it = erase(it); }
}// 传统写法
// lt2 = lt1
list<T>& operator=(const list<T>& lt)
{// lt就是lt1的传引用// this就是lt2的地址// this != < 就是判断lt2的地址是否与lt1的地址相等if (this != <) {// 使用clear()清空双向循环链表中,除哨兵位的所有节点clear();for (const auto& e : lt) // 此处使用传引用,就可以减少拷贝{// 将lt的数据,全部插入到lt2中push_back(e);}}// 返回lt2的迭代器对象return *this;
}// 现代写法
// lt3 = lt1
list<T>& operator=(list<T> lt)
//list& operator=(list lt) // 不建议
{swap(lt);return *this;
}
list::insert
// 在pos迭代器的节点位置前插入新节点
iterator insert(iterator pos, const T& x)
{node* newnode = new node(x);node* cur = pos._pnode; // pos迭代器位置处的节点为 pos._pnodenode* prev = cur->_prev; // 再找到cur的前一个节点// prev newnode cur 将这三个节点双向链接起来prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;// 使用newnode构建一个迭代器,并返回这个迭代器对象return iterator(newnode);
}
list::erase
iterator erase(iterator pos)
{assert(pos != end()); // 保证链表不为空node* prev = pos._pnode->_prev; // prev 为pos._pnode前一个节点的地址node* next = pos._pnode->_next; // next 为pos._pnode后一个节点的地址// 将prev next双向链接起来prev->_next = next;next->_prev = prev;delete pos._pnode; // 释放 pos._pnode节点// 返回 pos._pnode节点下一个节点的迭代器// 也就是返回,next节点构建的迭代器return iterator(next);
}
list的析构函数
void clear()
{iterator it = begin();while (it != end()){// erase()会返回被删除节点的下一个节点的迭代器// 最后it就是end()位置的迭代器,那么就会跳出循环// end()位置的迭代器,也就是_head哨兵位节点的迭代器it = erase(it); }
}~list()
{clear();delete _head;_head = nullptr;
}
list类的完整实现
template<class T>
class list
{typedef list_node<T> node;
public:// 迭代器的老版本// typedef __list_iterator<T> iterator;// typedef __list_const_iterator<T> const_iterator;// 迭代器的改良版本// typedef __list_iterator<T, T&> iterator;// typedef __list_iterator<T, const T&> const_iterator;// 再次改良迭代器// 此处的T和list<T>是同一个模板参数typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;// 反向迭代器typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}// 右侧的const修饰的是this指针const_iterator begin() const{// head是带头双向循环链表的哨兵位// _head->_next是双向链表的头节点// 使用头节点的指针构造一个迭代器的对象return const_iterator(_head->_next);}const_iterator end() const{// _head->next 是带头双向循环链表头节点// _head->prev 是带头双向循环链表的尾节点// end()是只迭代器的末尾位置,end是尾节点的下一个位置,也就是tail->next// tail->next就是哨兵位,也就是_headreturn const_iterator(_head);}iterator begin(){return iterator(_head->_next);}iterator end(){// iterator it(_head);// return it;return iterator(_head); // 返回迭代器的匿名对象}void empty_initialize(){// 这里只能使用T的默认构造来对node进行构造// 因为此时,并不能确定T是什么类型// 如果T是int类型,那么T的默认构造,T()就是0_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}// 链表的构造函数list(){empty_initialize();}// 传统的拷贝函数// lt2(lt1) /*list(const list<T>& lt){empty_initialize();for (const auto& e : lt){push_back(e);}}*/// 传统的赋值重载函数// lt1 = lt3//list<T>& operator=(const list<T>& lt)//{// if (this != <)// {// clear();// for (const auto& e : lt)// {// push_back(e);// }// }// return *this;//}// 构造函数,通过迭代器来构造template <class InputIterator> list(InputIterator first, InputIterator last){empty_initialize();while (first != last){push_back(*first);++first;}}// 自己写的交换函数void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// 拷贝函数的现代写法// 普通类 类名 等价于 类型// 类模板 类名 不等价于 类型// 如:list模板 类名list 类型list<T> // 类模板里面(也就是类模板内部)可以用类名代表类型,但是建议不要那么用// 拷贝函数// lt2(lt1)list(const list<T>& lt)//list(const list& lt) // 不建议这么写,最好将类型写为list<T> {empty_initialize();list<T> tmp(lt.begin(), lt.end());swap(tmp);}// 赋值重载的现代写法// lt3 = lt1list<T>& operator=(list<T> lt)//list& operator=(list lt) // 不建议这么写,最好将类型写为list<T> {swap(lt);return *this;}size_t size() const{return _size;}bool empty() const{return _size == 0;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){//node* newnode = new node(x);//node* tail = _head->_prev; _head tail newnode//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_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& x){node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());node* prev = pos._pnode->_prev;node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;
};
3.测试
测试迭代器(test1)
void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);// iterator是类里面的类型,那么有如下两种情况// 1、内嵌类型 // 2、迭代器的行为是像指针一样// 对于vector的迭代器类型:typedef int* iterator; // 迭代器++,跳过4个字节// 对于string的迭代器类型:typedef char* iterator; // 迭代器++,跳过1个字节// vector和string的迭代器++,或者--之后,都可以找到对应的数据,因为其存储空间是连续的// 但是对于list却不能够像vector和list一样,因为每个节点的空间都是独立的,因此对于list的迭代器// 需要专门实现一个迭代器的类list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;
}
test_list5
struct Pos
{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}
};void print_list(const list<Pos>& lt)
{// it就是链表的初始位置的迭代器// 在list类里面的定义:typedef __list_iterator<T, const T&, const T*> const_iterator;list<Pos>::const_iterator it = lt.begin();while (it != lt.end()){/*it-> 是一个函数调用,即it.operator->()it.operator->() 的返回对象类类型是const pos*,所以拿到的类型为pos的对象的值是不可以被修改的,因此const在*左侧,这个对象被const修饰再次使用-> ,返回pos类型的成员变量row的值本来面貌:it->->_row,编译器为了可读性,做了特殊处理,省略了一个->*/// 那么下面这行代码的使用就是错误的// it->_row++;cout << it->_row << ":" << it->_col << endl;++it;}cout << endl;
}void test_list5()
{// 创建一个链表对象,模版类型被实例化为pos类型list<Pos> lt;// 创建一个pos对象Pos p1(1, 1);// 将pos对象p1尾插到链表中lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);// 构建一个匿名的pos对象,并将其尾插到链表中// 这个匿名的pos的生命周期,只在当前这一行,除了这一行,这个匿名对象就会被销毁lt.push_back(Pos(2,2));lt.push_back(Pos(3,3));// int* p : *p 可以通过解引用找到p指针所指向的数据// Pos* p : p-> 可以通过-> 找到pos指针所指向的数据list<Pos>::iterator it = lt.begin();while (it != lt.end()){// pos为一个类,_row,_col为pos类的成员变量// 因为pos对象存放在链表中,所以*it 解引用就可以拿到类类型为pos的对象// 在通过这个对象来访问其成员变量cout << (*it)._row << ":" << (*it)._col << endl;// 当我们写了 ->的重载函数后// 使用-> 打印pos类中数据的三种方法/*cout << (&(*it))->_row << ":" << (*it)._col << endl;// *it 是pos; &(*it) 也就是pos*, 在通过pos*进行->操作找到_row的数据*//*// 下面这两种方法是等价的cout << it->_row << ":" << it->_col << endl;cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;// it-> 是一个函数调用,即it.operator->()// it.operator->() 的返回对象类类型是pos*,所以再次使用-> ,返回pos类型的成员变量row的值// 本来面貌:it->->_row,编译器为了可读性,做了特殊处理,省略了一个->*/++it;}cout << endl;print_list(lt);
}
4.完整的模拟实现,并测试
namespace qwy
{// 链表的节点的类模板template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x):_next(nullptr), _prev(nullptr), _data(x){}};// 迭代器的类模板// 同一个类模板实例化出的两个类,分别是普通迭代器的类和const迭代器的类// typedef __list_iterator<T, T&, T*> iterator;// typedef __list_iterator<T, const T&, const T*> const_iterator;template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> Self;node* _pnode;__list_iterator(node* p):_pnode(p){}Ptr operator->(){return &_pnode->_data;}Ref operator*(){return _pnode->_data;}Self& operator++(){_pnode = _pnode->_next;return *this;}Self operator++(int){Self tmp(*this);_pnode = _pnode->_next; return tmp;}Self& operator--(){_pnode = _pnode->_prev;return *this;}Self operator--(int){Self tmp(*this);_pnode = _pnode->_prev;return tmp;}bool operator!=(const Self& it) const{return _pnode != it._pnode;}bool operator==(const Self& it) const{return _pnode == it._pnode;}};// 带头双向循环链表的类模板template<class T>class list{typedef list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}void empty_initialize(){_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_initialize();}template <class InputIterator> list(InputIterator first, InputIterator last){empty_initialize();while (first != last){push_back(*first);++first;}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// 拷贝构造的现代写法// lt2(lt1)list(const list<T>& lt){empty_initialize();list<T> tmp(lt.begin(), lt.end());swap(tmp);}// 负值重载的现代写法// lt3 = lt1list<T>& operator=(list<T> lt){swap(lt);return *this;}size_t size() const{return _size;}bool empty() const{return _size == 0;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){//node* newnode = new node(x);//node* tail = _head->_prev; _head tail newnode//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_front(){erase(begin());}void pop_back(){erase(--end());}iterator insert(iterator pos, const T& x){node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());node* prev = pos._pnode->_prev;node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;};void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);// iterator 1、内嵌类型 2、行为像指针一样 list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list2(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_back();lt.pop_front();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);for (auto e : lt){cout << e << " ";}cout << endl;cout << lt.size() << endl;list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);cout << lt2.size() << endl;lt = lt2;for (auto e : lt){cout << e << " ";}cout << endl;}void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){// (*it) += 2; // 不能写cout << *it << " ";++it;}cout << endl;}void test_list4(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int>::iterator it = lt1.begin();while (it != lt1.end()){(*it) += 2; // 可以写cout << *it << " ";++it;}cout << endl;print_list(lt1);}struct Pos{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}};void print_list(const list<Pos>& lt){list<Pos>::const_iterator it = lt.begin();while (it != lt.end()){//it->_row++;cout << it->_row << ":" << it->_col << endl;++it;}cout << endl;}void test_list5(){list<Pos> lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2,2));lt.push_back(Pos(3,3));// int* p -> *p// Pos* p -> p->list<Pos>::iterator it = lt.begin();//list<Pos>::iterator it2 = it;while (it != lt.end()){it->_row++;//cout << (&(*it))->_row << ":" << (*it)._col << endl;cout << it->_row << ":" << it->_col << endl;//cout << it.operator->()->_row << ":" << it->_col << endl;++it;}cout << endl;print_list(lt);}
}
5.vector和list的对比
vector优点:1.下标随机访问2.尾插尾删效率高3.CPU高速缓存命中高缺点:1.前面部分插入删除数据低2.扩容有消耗,还存在一定空间浪费list优点:1.按需申请释放,无需扩容2.任意位置插入删除,时间复杂度为O(1)缺点:1.不支持随机访问2.CPU高速缓存命中低迭代器失效:vector: insert/eraselist: earsestring: insert/erase(和vector类似,但是string一般不关注失效,因为string的insert/erase 重用接口函数都是下标支持的,迭代器支持用得很少)
相关文章:
10.list的模拟实现(普通迭代器和const迭代器的类模板)
1. list的介绍及使用 1.1 list的介绍 list的文档介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过…...
【电控笔记5】电流环速度环三环参数整定
旋转坐标系下的电压方程,由id和iq计算出ud和uq Lq:q轴电感 Ld:d轴电感 输入是电流,输出是电压? 内嵌式pmsm(ipmsm)模型建立: 其中: λf是转子磁场在定子绕组所产生的磁通链,为一常数,在psms中转子磁场非常稳定几乎不变。 ipmsm转矩方程式: 对永磁同步马达而言,使…...
AI克隆语音(基于GPT-SoVITS)
概述 使用GPT-SoVITS训练声音模型,实现文本转语音功能。可以模拟出语气,语速。如果数据质量足够高,可以达到非常相似的结果。相比于So-VITS-SVC需要的显卡配置更低,数据集更小(我的笔记本NVIDIA GeForce RTX 4050 Lap…...
小蚕爬树问题
小蚕爬树问题 问题描述: 编写一个函数 int day(int k,int m,int n),其功能是:返回小蚕需要多少天才能爬到树顶(树高 k 厘米,小蚕每天白天向上爬 m 厘米,每天晚上下滑 n 厘米,爬到树顶后不再下滑࿰…...
科研学习|科研软件——如何使用SmartPLS软件进行结构方程建模
SmartPLS是一种用于结构方程建模(SEM)的软件,它可以用于定量研究,尤其是在商业和社会科学领域中,如市场研究、管理研究、心理学研究等。 一、准备数据 在使用SmartPLS之前,您需要准备一个符合要求的数据集。…...
实用工具系列-ADB使用方式
作者持续关注 WPS二次开发专题系列,持续为大家带来更多有价值的WPS开发技术细节,如果能够帮助到您,请帮忙来个一键三连,更多问题请联系我(WPS二次开发QQ群:250325397),摸鱼吹牛嗨起来࿰…...
计算机网络书籍--《网络是怎样连接的》阅读笔记
第一章 浏览器生成信息 1.1 生成HTTP请求信息 1.1.1 URL Uniform Resource Locator, 统一资源定位符。就是网址。 不同的URL能够用来判断使用哪种功能来访问相应的数据,比如访问Web服务器就要用”http:”,而访问FTP服务器用”ftp:”。 FTPÿ…...
antd+vue——datepicker日期控件——禁用日期功能
需求:今天之前的日期禁用 <a-date-pickerv-model.trim"formNE.deliveryTime":disabled-date"disabledDate"valueFormat"YYYY-MM-DD"allowClearstyle"width: 100%" />禁用日期的范围: //时间范围 disab…...
技术分享 | Appium 用例录制
下载及安装 下载地址: github.com/appium/appi… 下载对应系统的 Appium 版本,安装完成之后,点击 “Start Server”,就启动了 Appium Server。 在启动成功页面点击右上角的放大镜,进入到创建 Session 页面。配置好…...
[蓝桥杯 2018 省 A] 付账问题
【蓝桥杯】付账问题 [蓝桥杯 2018 省 A] 付账问题 题目描述 几个人一起出去吃饭是常有的事。但在结帐的时候,常常会出现一些争执。 现在有 n n n 个人出去吃饭,他们总共消费了 S S S 元。其中第 i i i 个人带了 a i a_i ai 元。幸运的是&#…...
设计模式|装饰器模式(Decorator Pattern)
文章目录 结构优缺点优点缺点适用场景示例装饰器模式(Decorator Pattern)是一种结构型设计模式,它允许在不改变原始对象的基础上,动态地给对象添加新的功能或责任。这种模式是通过创建一个包装对象,也就是装饰器,来包裹真实的对象,然后在装饰器中添加新的行为或功能。这…...
发作性睡病有性别差异吗?
发作性睡病是一种特殊的睡眠障碍,以不可控制的嗜睡、猝倒发作、睡眠瘫痪、入睡前幻觉以及夜间睡眠紊乱为主要临床特点。关于发作性睡病是否存在性别差异,不同的研究和报道给出了不同的结论。 一方面,从生理角度来看,男性和女性在…...
ppt从零基础到高手【办公】
第一章:文字排版篇01演示文稿内容基密02文字操作规范03文字排版处理04复习&作业解析第二章:图形图片图表篇05图形化表达06图片艺术化07轻松玩转图表08高效工具&母版统一管理09复习&作业解析10轻松一刻-文字图形小技巧速学第三章:…...
文件上传下载
文章目录 文件上传下载文件上传文件下载 文件上传下载 HTTP请求会包含一个请求头,其中"Content-Type"字段告诉服务器正在发送什么类型的数据。根据发送的数据类型,浏览器和服务器会采取适应的处理方式。 "multipart/form-data"是一…...
C++11 新特性:新增算法
C11 在标准库中引入了一系列新的算法,这些新增的算法使我们的代码写起来更简洁方便。 下面是 C11 中新增加的一些重要算法的简要描述和使用方法: 1、非修改序列操作 std::all_of:检查范围内的所有元素是否都满足指定的谓词。std::any_of&a…...
c/c++普通for循环学习
学习一下 for 循环的几种不同方式,了解一下原理及差异 完整的测试代码参考 GitHub :for 循环测试代码 1 常用形态 对于 for 循环来说,最常用的形态如下 for (表达式1; 表达式2; 表达式3) {// code }流程图如下: 编写测试代码…...
操作系统组成部分
从1946年诞生第一台电子计算机。 冯诺依曼结构 冯诺依曼是:数字计算机的数制采用二进制;计算机应该按照程序顺序执行。 常见的操作系统有三种类型 单用户单任务操作系统:只支持一个用户和一个任务的执行,如DOS;单用…...
深入理解DES算法:原理、实现与应用
title: 深入理解DES算法:原理、实现与应用 date: 2024/4/14 21:30:21 updated: 2024/4/14 21:30:21 tags: DES加密对称加密分组密码密钥管理S盒P盒安全性分析替代算法 DES算法简介 历史 DES(Data Encryption Standard)算法是由IBM研发&…...
# 达梦sql查询 Sql 优化
达梦sql查询 Sql 优化 文章目录 达梦sql查询 Sql 优化注意点测试数据单表查询 Sort 语句优化优化过程 多表关联SORT 优化函数索引的使用 注意点 关于优化过程中工具的选用,推荐使用自带的DM Manage,其它工具在查看执行计划等时候不明确在执行计划中命中…...
Linux下SPI驱动:SPI设备驱动简介
一. 简介 Linux下的SPI 驱动框架和 I2C 很类似,都分为主机控制器驱动和设备驱动,主机控制器也就是 SOC的 SPI 控制器接口,SPI设备驱动也就是所操作的SPI设备的驱动。 本文来学习一下Linux下SPI设备驱动。 二. Linux下SPI驱动:SP…...
【简明图文教程】Node.js的下载、安装、环境配置及测试
文章目录 前言下载Node.js安装Node.js配置Node.js配置环境变量测试后言 前言 本教程适用于小白第一次从零开始进行Node.js的下载、安装、环境配置及测试。 如果你之前已经安装过了Node.js或删除掉了Node.js想重新安装,需要先参考以下博客进行处理后,再根…...
共模电感饱和与哪些参数有关?这些参数是如何影响共模电感的?
在做一个变频器项目,遇到一个问题,在30Hz重载超过一定1小时,CE测试结果超出限制,查找原因最终发现EMI filter内的共模电感加热,fail现象可以复现。最终增大Y电容把问题解决了。由此问题引申出一个问题,到底…...
儿童护眼台灯怎么选?五款必选的高口碑护眼台灯推荐
儿童台灯,想必大家都不会陌生了,是一种学生频繁使用的小灯具,一般指放在桌面用的有底座的电灯。随着近年来儿童青少年的视力急速下滑,很多家长都会选择给孩子选择一款合适的护眼台灯,以便孩子夜晚学习能有个好的照明环…...
前端小技巧之轮播图
文章目录 功能htmlcssjavaScript图片 设置了一点小难度,不理解的话,是不能套用的哦!!! (下方的圆圈与图片数量不统一,而且宽度是固定的) 下次写一些直接套用的,不整这些麻…...
手动实现简易版RPC(上)
手动实现简易版RPC(上) 前言 什么是RPC?它的原理是什么?它有什么特点?如果让你实现一个RPC框架,你会如何是实现?带着这些问题,开始今天的学习。 本文主要介绍RPC概述以及一些关于RPC的知识,为…...
大语言模型总结整理(不定期更新)
《【快捷部署】016_Ollama(CPU only版)》 介绍了如何一键快捷部署Ollama,今天就来看一下受欢迎的模型。 模型简介gemmaGemma是由谷歌及其DeepMind团队开发的一个新的开放模型。参数:2B(1.6GB)、7Bÿ…...
关于npm和yarn的使用(自己的问题记录)
目录 一 npm 和 yarn 的区别 二 npm 和 yarn 常用命令对比 1. 初始化项目 2. 安装所有依赖包 3. 安装某个依赖包 4.安装某个版本的依赖包 5. 更新依赖包 5. 移除依赖包 三 package.json中 devDependencies 和 dependencies 的区别。 四 npm安装包时,…...
Web端Excel的导入导出Demo
📚目录 📚简介:✨代码的构建:💭Web端接口Excel操作🚀下载接口🚀导入读取数据接口 🏡本地Excel文件操作⚡导出数据🌈导入读取数据 📚简介: 使用阿里巴巴开源组件Easy Exce…...
Java日期正则表达式(附Demo)
目录 前言1. 基本知识2. Demo 前言 对于正则匹配,在项目实战中运用比较广泛 原先写过一版Python相关的:ip和端口号的正则表达式 1. 基本知识 对于日期的正则相对比较简单 以下是一些常见的日期格式及其对应的正则表达式示例: 年-月-日&a…...
基于LabVIEW的CAN通信系统开发案例
基于LabVIEW的CAN通信系统开发案例 介绍了基于LabVIEW开发的CAN通信系统,该系统主要用于汽车行业的数据监控与分析。通过对CAN通信协议的有效应用,实现了车辆控制系统的高效信息交换与实时数据处理,从而提升了车辆性能的检测与优化能力。 项…...
扶风做企业网站/郑州优化公司有哪些
关于设置多个折线图时,y轴的数据对不上问题还原问题解析解决方案博主微信欢迎交流问题还原 问题解析 我们可以看到三条线的数据是10,30,20但是y轴的数据跟显示的对不上 解决方案 把stack注释掉即可 博主微信欢迎交流...
怎么让自己做的网站让别人看到/安卓优化大师老版本
推理引擎示例推理引擎示例应用是简单的控制台应用,显示了如何在应用中利用特定的推理引擎功能,帮助开发人员执行特定的任务,例如加载模型、运行推理、查询特定的设备功能等。安装英特尔OpenVINO™工具套件分发版后,С、C和Python …...
wordpress内容/seo营销培训咨询
一、深入浅出理解索引结构 实际上,您可以把索引理解为一种特殊的目录。微软的SQL SERVER提供了两种索引:聚集索引(clustered index,也称聚类索引、簇集索引)和非聚集索引(nonclustered index,…...
上市公司网站建设/百度seo优化教程
1. 线程优先级 现代操作系统中基本上使用时间分片的方式调度线程,通过设置线程优先级,使优先级高的线程获得时间片的次数多于优先级低的线程。 在java 线程中,通过一个整形变量prority来控制优先级,优先级的范围从1~10…...
免费开源网站/国外搜索引擎排行榜
csc.exe使用来编译*.cs文件的,但必须要在安装目录下使用。所以需要设置一下环境变量。 C#的环境变量设置 1.“winR” 打开运行窗口,并输入 “cmd”; 2.运行“set path%path%;C:\Windows\Microsoft.NET\Framework\v4.0.30319”(不包含“”)。后…...
开一个网站建设公司需要什么软件/东莞做好网络推广
mysql连接池的实现前言池化技术数据库连接池什么是数据库连接池为什么使用数据库连接池不使用连接池的执行过程使用连接池的执行过程数据库连接池运行机制连接池和线程池的关系线程池设计与代码实现线程池设计要点构造函数初始化获取连接池内的连接归还连接至连接池析构函数连接…...