十档行情免费网站,已经有了域名怎么做网站,专业的佛山网站设计,网站iis7.5配置1、基本框架
list 由三个类构建而成:
节点类:每个节点必须的三部分(指向前一个节点的指针、指向后一个节点的指针、当前节点存储的数据)
迭代器类:此时的迭代器为双向迭代器#xff0c;比较特殊#xff0c;需要对其进行封装#xff0c;如 it并非使迭代器单纯向后移动比较特殊需要对其进行封装如 it并非使迭代器单纯向后移动而是让其指向下一个节点
链表类:实现链表各项功能的类为主要部分 1.1、节点类
节点类在设计时需要确定三个成员和构造函数用来生成类
//节点类
templateclass T
struct __list_node
{__list_node(const T data T()):_prev(nullptr),_next(nullptr),_data(data){}__list_nodeT* _prev; //指向前一个节点__list_nodeT* _next; //指向后一个节点T _data; //存储相应数据
};注意: 节点的创建与销毁不在节点类中进行因此不需要写析构函数
1.2、迭代器类
迭代器类中的成员为节点类指针指向单个节点同样的选代器类也需要提供构造函数
//迭代器类
templateclass T
struct __list_iterator
{typedef __list_nodeT* link_type; //对节点类的指针进行重命名__list_iterator(link_type node):_node(node){}link_type _node;
};注意: 迭代器只是一个辅助工具指向的是节点同样不需要提供析构函数析构相关事宜交给链表类处理就好
1.3链表类
链表类中也只用有一个成员变量:哨兵位节点(头节点)
//list本类
templateclass T
class list
{typedef __list_nodeT node; //节点typedef T value_type; //模板参数值typedef T refence; //引用typedef const T const_refence; //const 引用private:node* _head; //哨兵位节点头节点
};2、默认成员函数
默认成员函数中包含了默认构造、带参构造、拷贝构造、赋值重载和析构函数
析构函数只负责释放链表中的节点而其他默认成员函数负责 构造/构建出其他对象
因为有很多构造函数中都需要对创建出头节点所以此时 需要先构建出一个空初始化函数empty init()这个函数只能在类中使用
因此设为 private
private://初始化出头节点void empty_init(){_head new node;_head-_prev _head-_tail _head;}其他构造函数在构造对象前可以先调用此函数
比如默认构造函数 构成出一个空对象
//默认构造函数
list() { empty_init(); }对于带参构造函数在构造对象前仍需要调用 empty_init()构建头节点 参数:
size_t n 对象中包含 n 个数据 const reference val 数据值
为了避免与后续的迭代器区间构造起冲突这里需要再额外提供一个 int版本
//带参构造函数(value_type)此处的value_type指的就是就是模版参数T
list(value_type n, const_refence val value_type())
{empty_init();while (n--) push_back(val);
}
//为了避免与迭代器区间构造函数冲突提供额外版本(int)
list(int n, const_refence val value_type())
{empty_init();while (n--) push_back(val);
}在实际创建 list 对象时多使用迭代器区间进行构造因为是创建新对象所以可以直接调用尾插进行创建
//迭代器区间构造
templateclass InputIterator
list(InputIterator first, InputIterator last)
{empty_init();while (first ! last) push_back(*first);
}关于拷贝构造和赋值重载可以使用现代写法
//交换
void swap(listT tmp)
{std::swap(_head, tmp._head);
}
//拷贝构造---现代写法
list(const listT x)
{empty_init();listT tmp(x.begin(), x.end());swap(tmp);
}
//赋值重载---现代写法
listT operator(listT tmp)
{swap(tmp);return *this;
}注意:
以上几种构造函数都是在创建新对象因此在构建前需要先调用 empty_init()初始化出头节点
为了避免 list(intint)匹配上迭代器区间构造可以再额外提供一个int版的带参构造函数。
拷贝构造的参数必须使用引用否则会造成无穷递归问题
至于析构函数的实现就很简单了直接使用函数 clear()释放节点最后再释放头节点即可
//析构函数
~list()
{clear(); //后续会对这个函数的实现进行讲解delete _head;_head nullptr;
}3、迭代器设计 3.1、多参数模板
list 的模拟实现精华在于迭代器类的设计而迭代器类中的精华在于多参数模板这种传多模板参数的方法巧妙的解决了正常对象与const 对象的冗余设计问题
选代器分为 iterator 和 const iterator不同的对象调用不同的迭代器类型假设不使用多参数模板就需要实现两份相差不大的迭代器类(完全没有必要)
T:节点中值的普通类型
Ref :节点中值的引用类型(可为const
Ptr:节点中值的指针类型(可为const
//迭代器类
templateclass T, class Ref, class Ptr
struct __list_iterator
{typedef __list_nodeT* link_type;typedef __list_iteratorT, Ref, Ptr self;__list_iterator(link_type node):_node(node){}link_type _node;
};//迭代器设计list 类中
typedef __list_iteratorT, T, T* iterator; //声明两种不同的迭代器
typedef __list_iteratorT, const T, const T* const_iterator;他是一个要单独存在的类
注意: 节点类及迭代器类都是使用 struct 定义的目的是为了开放其中的成员 list 类中的迭代器相关函数也有两种:
普通版本与 const 版本
规定:
begin()为 list 的头节点的下一个节点
end()是 list 的头节点
返回类型都为迭代器对象因此可以使用匿名对象进行构造
//迭代器设计
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;iterator begin() { return iterator(_head-_next); }
iterator end() { return iterator(_head); }const_iterator begin() const { return const_iterator(_head-_next); }
const_iterator end() const { return const_iterator(_head); }迭代器分类:
单向迭代器:支持或--其中一种移动方式 双向迭代器:支持及--两种移动方式 随机迭代器:不仅支持 和 -还支持迭代器 n、-n
只有随机选代器才能使用 std::sort 进行快速排序
3.2双向迭代器
对于双向链表我们要实现双向迭代器
self operator(); //前置self operator--(); //前置--self operator(int); //后置self operator--(int); //后置--list 中的双向迭代器在进行移动时也比较特殊不像之前的 string 和 vector 是连续空间(移动直接调用内置 /--) list 为非连续空间迭代器在移动时为前后节点间的移动使用内置 /-- 会引发严重的迭代器越界问题 因此才需要将迭代器单独封装为一个类实现我们想要的效果 实现代码
self operator()
{_node _node-_next;return *this;
}self operator--()
{_node _node-_prev;return *this;
}self operator(int)
{self tmp(_node);//_node; //谨防错误写法//_node _node-_next; //正确写法1(*this); //正确写法2return tmp;
}self operator--(int)
{self tmp(_node);//--_node; //谨防错误写法//_node _node-_prev; //正确写法1--(*this); //正确写法2return tmp;
}注意
//以下是后置的错误写法
self operator(int)
{self tmp(_node);_node; //错误写法return tmp;
}node 是一个节点指针非迭代器对象 node 不是在调用 operator()而是在调用内置的前置 (节点指针没有像迭代器一样进行重载)直接就指向了非法空间 解决方案:
1.手动实现节点的移动: node node- next
2.调用迭代器类的前置 : (*this)
3.3指向结构体成员功能 Ptr operator-(){return _node-_val;}
运用场景
当 list 中的对象为自定义类型时想直接通过 it-访问其中的成员
struct A
{A(int a int(), double b double(), char c char()):_a(a),_b(b),_c(c){}int _a;double _b;char _c;
};void TestList()
{listA lt;lt.push_back(A(1, 2.2, A));auto it lt.begin();cout (*it)._a endl; //不使用 operator-() 比较别扭cout it--_b endl; //这种写法是真实调用情况cout it-_c endl; //编译器直接优化为 it-
}3.4迭代器总代码
//迭代器类
templateclass T, class Ref, class Ptr
struct __list_iterator
{typedef __list_nodeT* link_type;typedef __list_iteratorT, Ref, Ptr self;__list_iterator(link_type node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return (operator*());}self operator(){_node _node-_next;return *this;}self operator--(){_node _node-_prev;return *this;}self operator(int){self tmp(_node);//_node; //谨防错误写法//_node _node-_next; //正确写法1(*this); //正确写法2return tmp;}self operator--(int){self tmp(_node);//--_node; //谨防错误写法//_node _node-_prev; //正确写法1--(*this); //正确写法2return tmp;}bool operator(const self tar){return tar._node _node;}bool operator!(const self tar){return tar._node ! _node;}link_type _node;
};4.容量
list 中的容量访问有:判空和大小 实现判空:判断当前的 begin()与 end()是否相同 统计大小:利用迭代器将整个 list 遍历一遍计数统计即可
//容量相关
bool empty() const { return begin() end(); }
size_t size() const
{int cnt 0;auto it begin(); //使用 auto 自动推导迭代器类型while (it ! end())it, cnt;return cnt;
}5、数据访问
STL 库中给 list 提供了两种数据访问方式:访问首个数据和访问最后一个数据
//数据访问
refence front() { return *begin(); }
const_refence front() const { return *begin(); }refence back() { return *(--end()); }
const_refence back() const { return *(--end()); }6、数据修改相关
只需要找到对应节点的位置插入/删除本质上就是在进行前后节点的链接关系修改
6.1、头尾插删
头尾插删是在对 begin()和 --end()所指向的节点进行操作尾部插入/头部删除逻辑一致尾部删除/头部删除 逻辑一致学会其中一个就够用了
尾部插入步骤:
根据传入的数值构建出新尾节点 new_back 找到原链表中的尾节点 old_back 在 old back、new back、 head 间建立链接关系即可
头部插入逻辑与尾部插入基本一致不过找的是 old_front 头节点
//尾插
void push_back(const_refence val)
{node* new_back new node(val);node* old_back _head-_prev;old_back-_next new_back; //原尾节点的 _next 指向新尾节点new_back-_prev old_back; //新尾节点的 _prev 指向原尾节点new_back-_next _head; //新尾节点的 _next 指向头节点_head-_prev new_back; //头节点的 _prev 指向新尾节点
}尾部删除步骤
断言当前 list 不为空如果为空就报错
选择原来的尾节点 old_back- head- prev
确定新的尾节点 new back-old back-prev
在 new_back 与 head 之间建立链接关系
最后在释放原来的尾节点 old back
头删时逻辑基本一致不过选择的是old_front与 new_front
//尾删
void pop_back()
{assert(!empty());node* old_back _head-_prev; //选择原尾节点node* new_back old_back-_prev; //确定新尾节点new_back-_next _head; //新尾节点的 _next 指向头节点_head-_prev new_back; //头节点的 _prev 指向新尾节点delete old_back;
}6.2、任意位置插删
任意位置插入就是在插入操作的基础上添加了迭代器pos进行定位
在 pos位置前插入
根据传入值创建出新节点 new_node
确定当前 pos 位置的节点 pos_cur
确定当前 pos 位置的上一个节点 pos_prev
在 pos_prev、new_node、pos_cur 间建立链接关系
最后返回当前插入新节点的位置
//任意位置插入
iterator insert(iterator pos, const_refence val)
{node* new_node new node(val); //创建新节点node* pos_cur pos._node; //当前 pos 位置的节点node* pos_prev pos_cur-_prev; //pos 的前一个节点pos_prev-_next new_node; new_node-_prev pos_prev;new_node-_next pos_cur;pos_cur-_prev new_node;return iterator(new_node); //最后返回的是一个迭代器对象
}任意位置删除逻辑与 尾删/头删 基本一致 首先断言 list 是否为空 分别确定当前节点 pos_cur上一个节点 pos_prev 下一个节点 pos_next 在上下节点 pos_prev 和 pos_next 间建立链接关系 删除当前节点 pos_cur 返回己删除节点下一个节点即pos_next
//任意位置删除
iterator erase(iterator pos)
{assert(!empty());node* pos_cur pos._node;node* pos_prev pos_cur-_prev;node* pos_next pos_cur-_next;pos_prev-_next pos_next;pos_next-_prev pos_prev;delete pos_cur;return iterator(pos_next);
}list 的插入操作没有迭代器失效问题删除操作也仅仅是影响被删除节点的迭代器返回值是为了更好的进行操作 注意: 之前提到的 尾部插入/删除、头部插入/删除 可以复用任意位置插入/删除
//尾插
void push_back(const_refence val)
{insert(end(), val);
}//尾删
void pop_back()
{erase(--end());
}//头插
void push_front(const_refence val)
{insert(begin(), val);
}//头删
void pop_front()
{erase(begin());
}
