如何学建设网站,app服务器搭建教程,推广联盟,关于加强内网网站建设的通知目录
1.模拟实现list
2.节点模板讲解
3.迭代器模板讲解
3.1为什么template 有三个类型参数
(1).class T
(2).class ref
(3).class ptr
3.2 *重载
3.3 -重载
3.4 前置和后置的重载
3.5 前置--和--后置的重载
3.6 和!的重载
4. list模板讲解
4.1 begin()函数 … 目录
1.模拟实现list
2.节点模板讲解
3.迭代器模板讲解
3.1为什么template 有三个类型参数
(1).class T
(2).class ref
(3).class ptr
3.2 *重载
3.3 -重载
3.4 前置和后置的重载
3.5 前置--和--后置的重载
3.6 和!的重载
4. list模板讲解
4.1 begin()函数
4.2 end()函数
4.3 空初始化函数
4.4 深拷贝函数
4.5 交换函数
4.6 赋值运算符operator的实现
4.7 析构函数和clear()函数
4.8 push_back函数
4.9 插入函数
4.10 push_front函数
4.11 erase函数
4.12 头删和尾删
4.13 size函数
3.14 empty函数 1.模拟实现list 分别定义了三个类模板
分别是节点模板迭代器模板list模板
template class T
class list_node
{
public:T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T data T()): _data(data), _next(nullptr), _prev(nullptr){}
};
template class T, class ref, class ptr
struct list_iterator
{typedef list_nodeT Node;typedef list_iteratorT, ref, ptr self;Node* _node;
};
template class T
class list
{typedef list_nodeT Node;public:private:Node* _head;size_t _size;
}; 2.节点模板讲解
源码
template class T
class list_node
{
public:T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T data T()): _data(data), _next(nullptr), _prev(nullptr){}
}; (1).定义值域_data用于存放数值在定义指向下一个节点和上一个节点的指针。 (2).默认构造函数可用于初始化赋值等等。 3.迭代器模板讲解
源码
template class 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 operator*(){return _node-_data;}ptr* operator-(){return _node-_data;}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;}bool operator!(const self s) const{return _node ! s._node;}bool operator(const self s) const{return _node s._node;}
}; 3.1为什么template class T, class ref, class ptr有三个类型参数
(1).class T
T通常用于表示迭代器所指的数据类型。在list中T是链表节点中存储的数据类型。例如如果此链表用于存储整数那么T就是int如果链表用于存储字符串则T就是string。 (2).class ref
ref用于定义解引用迭代器时返回的类型这允许迭代器解引用时的行为。
在这个代码中ref被用作operator*()的返回类型他返回_node-_data的一个引用。这意味着ref应该是对T类型的引用类型通常是T。 (3).class ptr
ptr用于定义迭代器箭头操作符operator-()的返回类型。他返回_node-_data的地址这意味着ptr应该是一个指针类型通常是T*。 这三个类型参数Trefptr提供了对迭代器行为的精细度控制使得迭代器模板能够更加灵活和通用地应对不同场景和数据类型。 3.2 *重载
ref operator*()
{return _node-_data;
} (1).*为解引用要获取值则返回这个值的引用即可。(ref被用作operator*()的返回类型) 3.3 -重载
ptr* operator-()
{return _node-_data;
} (1). -为获取地址获取地址就返回地址即可。(ref被用作operator*()的返回类型) 3.4 前置和后置的重载
self operator()
{_node _node-_next;return *this;
}self operator(int)
{self tmp(*this);_node _node-_next;return tmp;
} (1).前置中由于是先自加再赋值所以直接将_node_node-_next即可然后返回*this。 (1).后置中由于是先赋值再自加所以要先把改变之前的值保持在tmp中再对_node作改变最后返回的是tmp。 3.5 前置--和--后置的重载
self operator--()
{_node _node-_prev;return *this;
}
self operator--(int)
{self tmp(*this);_node _node-_prev;return tmp;
} (1).前置--中由于是先自减再赋值所以直接将_node_node-_prev即可然后返回*this。 (2).--后置中由于是先赋值再自减所以要先把改变之前的值保持在tmp中再对_node作改变最后返回的是tmp。 3.6 和!的重载
bool operator!(const self s) const
{return _node ! s._node;
}
bool operator(const self s) const
{return _node s._node;
} (1) 和!中直接判断s与_node 是否相等即可。 (2)注意 这两个运算符通常应该一起被重载以保持它们之间的一致性。 它们被声明为const成员函数因为它们不修改_node成员。 4. list模板讲解
源码
template class T
class list
{typedef list_nodeT Node;public:// typedef list_iteratorT iterator;// typedef list_const_iteratorT const_iterator;typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;iterator begin(){iterator it(_head-_next);return it;}iterator end(){iterator it(_head);return it;}const_iterator begin() const{iterator it(_head-_next);return it;}const_iterator end() const{iterator it(_head);return it;}void empty_init(){_head new Node(T());_head-_next _head;_head-_prev _head;_size 0;}list(){empty_init();}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(listint lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}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;_size;// insert(end(),x);}void push_front(const T x){insert(begin(), x);}// 在pos之前插入void 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;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator 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(){return _size 0;}private:Node* _head;size_t _size;
}; 重命名
typedef list_iteratorT, T, T* iterator;
typedef list_iteratorT, const T, const T* const_iterator; 4.1 begin()函数
iterator begin()
{iterator it(_head-_next);return it;
} (1).begin()是一个迭代器其作用是返回第一个有效数值的地址。 (2)._head是一个指向链表头节点的指针这里的头节点并不存储有效数据而是作为一个哨兵节点的存在。 (3)._head_next是头节点的下一个节点即链表中第一个存储有效数据的节点。 (4).iterator it(_head_next) 创建了一个迭代器it他初始化为指向链表的第一个有效元素。 4.2 end()函数
iterator end()
{iterator it(_head);return it;
} (1).end()是一个迭代器其作用是返回最后一个有效节点的下一个位置也就是哨兵节点。 4.3 空初始化函数
void empty_init()
{_head new Node(T());_head-_next _head;_head-_prev _head;_size 0;
} void empty_init()函数在list类中有着重要作用其作用为初始化链表为空状态的作用这个函数的主要目的是创建一个哑节点(哨兵节点)并设置链表的初始状态使链表在逻辑上是空的。 4.4 深拷贝函数
list(const listT lt) // 深拷贝
{empty_init(); // 初始化for (auto e : lt){push_back(e);}
} list(const listT lt)是一个拷贝构造函数它用于创建一个新的list对象该对象是另一个已存在list对象的深拷贝。这个拷贝构造函数通过遍历it并使用其元素来填充新创建的list从而实现了深拷贝。 4.5 交换函数
void swap(listint lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
} 实现了交换两个list的功能 4.6 赋值运算符operator的实现
listT operator(listT lt)
{swap(lt);return *this;
} 注意是传值传参只是一个拷贝在调用operator时会创建一个listT的副本这个副本是通过调用list的拷贝构造函数实现的。 在swap调用后*this获得了it的原始资源而it获得了*this的原始资源。 4.7 析构函数和clear()函数
void clear()
{auto it begin();while (it ! end()){it erase(it); // 返回下一个的迭代器}
}~list()
{clear();delete _head;_head nullptr;
} void clear()函数中,通过遍历整个list再通过erase来销毁list。 析构函数中直接调用了clear()函数。 4.8 push_back函数
void push_back(const T x)
{Node* newnode new Node(x);Node* tail _head-_prev;//尾节点tail-_next newnode;//更新尾节点的_next指针newnode-_prev tail;//更新新节点的_prev指针newnode-_next _head;//新节点的_next指向哨兵节点_head-_prev newnode;//哨兵节点的_prev指向新节点_size;//更新链表大小// insert(end(),x);
} 这个函数接受一个类型为constT的参数x即要插入的新元素的一个常量引用。使用常量引用是为了避免不必要的元素复制同时保证传递给函数的对象不会被修改。 4.9 插入函数
void insert(iterator pos, const T x)
{Node* cur pos._node;//cur指向迭代器pos当前指向的节点Node* prev cur-_prev;//prev指向cur的前一个节点Node* newnode new Node(x);//创建一个新的节点newnode并初始化为xnewnode-_next cur;//将新结点的_next指针指向cur。cur-_prev newnode;//将当前位置的_prev指针更新为指向新节点以保持双向链接newnode-_prev prev;//将新节点_prev指针指向prev即前一个节点prev-_next newnode;//将前一个结点的_next指针更新为新结点完成插入。_size;//链表大小加一因为插入了新数据
} 用于在链表的指定位置pos之前插入一个新的元素x。这个函数展示了如何在双向链表中高效的插入元素。 4.10 push_front函数
void push_front(const T x)
{insert(begin(), x);
} 直接利用insert函数即可将插入位置定为begin()。 4.11 erase函数
iterator erase(iterator pos)
{assert(pos ! end());Node* prev pos._node-_prev;//获得删除结点的前驱Node* next pos._node-_next;//获得删除结点的后继prev-_next next;//将前驱结点的_next指针指向后继结点next-_prev prev;//将后继节点的_prev指针指向前驱结点delete pos._node;//删除pos位置的节点的内存_size--;//将链表大小减一return next;//返回被删除元素之后元素的迭代器
} 用于从双向链表中删除指定位置的元素并返回指向被删除元素之后元素的迭代器。 4.12 头删和尾删
void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
} 直接调用erase即可 4.13 size函数
size_t size() const
{return _size;
} 直接返回_size的大小即可 3.14 empty函数 bool empty(){return _size 0;} 直接返回_size是否等于0即可。 本篇完
