漳州 外贸网站建设 SEO,wordpress post编辑,温州网凝科技有限公司,专做外贸的网站有哪些资料目录
类及其成员函数接口总览
结点类的模拟实现 构造函数
迭代器类的模拟实现 迭代器类存在的意义 迭代器类的模板参数说明 构造函数 运算符的重载 --运算符的重载 运算符的重载 !运算符的重载 *运算符的重载 -运算符的重载
list的模拟实现 默认成员函数 构造函数 拷贝…目录
类及其成员函数接口总览
结点类的模拟实现 构造函数
迭代器类的模拟实现 迭代器类存在的意义 迭代器类的模板参数说明 构造函数 运算符的重载 --运算符的重载 运算符的重载 !运算符的重载 *运算符的重载 -运算符的重载
list的模拟实现 默认成员函数 构造函数 拷贝构造函数 赋值运算符重载函数 析构函数 迭代器相关函数 begin和end 访问容器相关函数 front和back 插入、删除函数 insert erase push_back和pop_back push_front和pop_front 其他函数 size resize clear empty swap 类及其成员函数接口总览
namespace RussLeo
{// 模拟实现 list 当中的结点类templateclass Tstruct _list_node{// 构造函数_list_node(const T val T()); // 默认构造函数初始化数据域// 成员变量T _val; // **数据域**存储节点的值_list_nodeT* _next; // **后继指针**指向下一个节点_list_nodeT* _prev; // **前驱指针**指向前一个节点};// 模拟实现 list 迭代器templateclass T, class Ref, class Ptrstruct _list_iterator{typedef _list_nodeT node; // 节点类型别名typedef _list_iteratorT, Ref, Ptr self; // 迭代器自身类型别名// 构造函数_list_iterator(node* pnode); // 初始化迭代器指向节点// 各种运算符重载函数self operator(); // 前置递增self operator--(); // 前置递减self operator(int); // 后置递增self operator--(int); // 后置递减bool operator(const self s) const; // 相等比较bool operator!(const self s) const; // 不等比较Ref operator*(); // 解引用Ptr operator-(); // 成员访问// 成员变量node* _pnode; // **一个指向结点的指针**用于迭代};// 模拟实现 listtemplateclass Tclass list{public:typedef _list_nodeT node; // 节点类型别名typedef _list_iteratorT, T, T* iterator; // 迭代器类型别名typedef _list_iteratorT, const T, const T* const_iterator; // 常量迭代器类型别名// 默认成员函数list(); // 默认构造函数list(const listT lt); // 拷贝构造函数listT operator(const listT lt); // 拷贝赋值操作符~list(); // 析构函数// 迭代器相关函数iterator begin(); // 返回指向头部的迭代器iterator end(); // 返回指向尾部的迭代器const_iterator begin() const; // 返回常量迭代器指向头部const_iterator end() const; // 返回常量迭代器指向尾部// 访问容器相关函数T front(); // 返回容器第一个元素的引用T back(); // 返回容器最后一个元素的引用const T front() const; // 返回容器第一个元素的常量引用const T back() const; // 返回容器最后一个元素的常量引用// 插入、删除函数void insert(iterator pos, const T x); // 在指定位置插入元素iterator erase(iterator pos); // 删除指定位置的元素void push_back(const T x); // 在末尾添加元素void pop_back(); // 删除末尾元素void push_front(const T x); // 在头部添加元素void pop_front(); // 删除头部元素// 其他函数size_t size() const; // 返回容器中元素的个数void resize(size_t n, const T val T()); // 调整容器大小void clear(); // 清空容器bool empty() const; // 判断容器是否为空void swap(listT lt); // 交换两个容器的内容private:node* _head; // **指向链表头结点的指针**};
}结点类的模拟实现 list 类在底层实现时确实是一个链表更确切地说它通常是一个带有头结点的双向循环链表。因此要实现 list首先需要实现一个结点类。 一个链表结点需要存储的信息包括数据、前一个结点的地址 和 后一个结点的地址。因此该结点类的成员变量就包括了数据、前驱指针和后继指针。 对于结点类的成员函数我们只需要实现一个 构造函数。这个构造函数用于根据给定的数据初始化结点。结点的释放则由 list 类的析构函数负责处理。 构造函数 结点类的构造函数 直接根据所提供的数据来创建一个结点。构造出来的结点将具有以下特点 数据域存储传入的数据。前驱指针 和 后继指针均初始化为空指针 (nullptr)。 // 构造函数
_list_node(const T val T()): _val(val) // 初始化数据域为传入的值, _prev(nullptr) // 初始化前驱指针为空, _next(nullptr) // 初始化后继指针为空
{} 注意:若构造结点时未传入数据则构造函数会使用 list 容器存储类型的默认构造函数 构造出的值作为传入数据。 迭代器类的模拟实现 迭代器类存在的意义 当我们模拟实现 string 和 vector 时并没有提到需要实现一个迭代器类这是因为 string 和 vector 的数据都存储在连续的内存空间中。我们可以通过原生指针来实现迭代器的功能指针支持自增、自减和解引用等操作因此可以直接用于访问和操作数据。 然而对于 list 类而言它的内部结构与 string 和 vector 不同。list 通常采用链表结构来存储数据这意味着每个元素并不是存储在一个连续的内存块中而是通过指针链接在一起。因此原生指针无法直接用于链表中的迭代因为在链表中元素的存储位置并不连续。 为了能够遍历和操作链表中的元素我们需要实现一个专门的迭代器类该类需要管理链表节点的连接关系并支持类似于指针的操作如自增、自减和解引用。 迭代器的意义在于让使用者能够以统一的方式访问容器中的数据而无需关心底层实现。 对于 list 类它的节点指针行为不符合标准迭代器的定义。为了使 list 的迭代器能够像 string 和 vector 的迭代器一样使用我们需要对节点指针进行封装。通过重载节点指针的各种运算符我们可以实现与原生指针类似的操作。例如当使用 list 的迭代器进行自增操作时实际上执行的是 p p-next但用户不需要知道底层的具体实现细节。 总结 list 迭代器类本质上是对节点指针的封装通过重载运算符使得节点指针的行为看起来像普通指针一样。例如节点指针自增操作能够指向下一个节点。 迭代器类的模板参数说明 我们所实现的迭代器类的模板参数列表当中为什么有三个模板参数
templateclass T, class Ref, class Ptr这里的模板参数 Ref 和 Ptr 分别代表了引用类型和指针类型。在 list 的模拟实现中我们定义了两个迭代器类型
typedef _list_iteratorT, T, T* iterator;
typedef _list_iteratorT, const T, const T* const_iterator;这表明迭代器类的模板参数 Ref 和 Ptr 用于区分普通迭代器和 const 迭代器。具体来说
普通迭代器iterator使用 T 作为引用类型T* 作为指针类型。const 迭代器const_iterator使用 const T 作为引用类型const T* 作为指针类型。 总结 迭代器类的三个模板参数T、Ref 和 Ptr使得迭代器能够适应不同的引用和指针类型从而可以很好地区分普通迭代器和 const 迭代器。如果只设计两个模板参数无法实现对普通迭代器和 const 迭代器的有效区分。因此使用三个模板参数可以确保迭代器在不同的使用场景下具有正确的行为和类型。 构造函数 迭代器类实际上是对节点指针的封装它的主要成员变量就是一个节点指针。迭代器的构造函数直接使用传入的节点指针来初始化迭代器对象。
// 构造函数
_list_iterator(node* pnode): _pnode(pnode) // 初始化节点指针
{}说明 self 是当前迭代器对象的类型
typedef _list_iteratorT, Ref, Ptr self;运算符的重载 前置自增 的作用是将迭代器指向下一个节点并返回自增后的迭代器对象。实现如下
// 前置自增
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 s) const
{return _pnode s._pnode; // 判断两个节点指针是否相同
}!运算符的重载 ! 运算符 的作用是判断两个迭代器是否不相等。这可以通过检查这两个迭代器中的节点指针是否不同来实现。实现代码如下
// 比较两个迭代器是否不相等
bool operator!(const self s) const
{return _pnode ! s._pnode; // 判断两个节点指针是否不同
}*运算符的重载 当使用解引用操作符*时我们想要获取当前迭代器指向节点的数据。为了支持对数据的修改解引用操作符应返回一个引用。实现代码如下
// 解引用操作符返回节点指针所指节点的数据
Ref operator*()
{return _pnode-_val; // 返回节点指针所指节点的数据
} -运算符的重载 - 运算符 用于通过迭代器访问节点中的数据。 当节点存储的不是内置类型而是自定义类型时。例如日期类我们可能会使用 - 运算符来访问对象的成员。为了实现这一点我们需要重载 - 运算符使其返回节点数据的地址。实现代码如下
// 访问节点数据的地址
Ptr operator-()
{return _pnode-_val; // 返回节点指针所指节点数据的地址
}示例
listDate lt;
Date d1(2024, 8, 12);
Date d2(2002,11, 2);
Date d3(1949, 10, 1);
lt.push_back(d1);
lt.push_back(d2);
lt.push_back(d3);
listDate::iterator pos lt.begin();
cout pos-_year endl; // 输出第一个日期的年份在这个示例中pos-_year 语句实际上涉及两个箭头操作 第一个箭头 pos- 调用重载的 operator-返回 Date* 的指针。第二个箭头 Date*- 访问 Date 对象的成员变量 _year。 解释虽然需要两个箭头操作但为了提高程序的可读性编译器在实现时做了优化使得只有一个箭头操作是可见的。这是因为编译器会自动处理 - 操作的特殊情况简化用户代码中的箭头访问。
list的模拟实现 默认成员函数 构造函数 list 是一个带头双向循环链表。在构造一个 list 对象时我们通常会创建一个头结点并将其前驱指针和后继指针都指向自身。这样可以简化链表的操作避免在插入和删除节点时需要处理空链表的特殊情况。 // 构造函数
list()
{_head new node; // 申请一个头结点_head-_next _head; // 头结点的后继指针指向自己_head-_prev _head; // 头结点的前驱指针指向自己
}拷贝构造函数 拷贝构造函数 用于根据现有 list 容器创建一个新的对象。首先创建一个头结点并将其前驱指针和后继指针都指向自己。然后将原容器中的数据通过遍历方式逐一尾插到新构造的容器中。实现代码如下
// 拷贝构造函数
list(const listT lt)
{_head new node; // 申请一个头结点_head-_next _head; // 头结点的后继指针指向自己_head-_prev _head; // 头结点的前驱指针指向自己// 遍历原容器将数据逐一尾插到新容器中for (const auto e : lt){push_back(e); // 将容器 lt 中的数据一个个尾插到新构造的容器后面}
}赋值运算符重载函数 赋值运算符重载 有两种写法传统写法和现代写法。两者各有优缺点具体如下 传统写法中我们首先清空原容器然后将新容器的数据逐个尾插到当前容器中。实现代码如下 // 传统写法
listT operator(const listT lt)
{if (this ! lt) // 避免自己给自己赋值{clear(); // 清空容器for (const auto e : lt){push_back(e); // 将容器 lt 中的数据一个个尾插到链表后面}}return *this; // 支持连续赋值
}现代写法利用了编译器的拷贝构造函数使用右值参数创建临时对象然后通过 swap 函数交换当前对象和临时对象的内容。实现代码如下 // 现代写法
listT operator(listT lt) // 编译器接收右值时自动调用拷贝构造函数
{swap(lt); // 交换这两个对象return *this; // 支持连续赋值
}总结 传统写法 更为直接但需要额外的清理和插入操作。现代写法 更简洁通过 swap 函数避免了显式的清理操作利用了资源管理的自动化机制。 析构函数 析构函数 在对象销毁时负责清理容器中的数据释放头结点并将头指针置空。实现代码如下
// 析构函数
~list()
{clear(); // 清理容器中的所有数据delete _head; // 释放头结点_head nullptr; // 将头指针置空
}迭代器相关函数 begin和end begin 和 end 函数 的实现用于获取迭代器分别指向容器的第一个有效数据和最后一个有效数据的下一个位置。以下是其实现代码 普通迭代器 begin() 返回指向第一个有效数据的迭代器即头结点后一个结点的地址。end() 返回指向最后一个有效数据的下一个位置的迭代器即头结点的地址。 // 返回指向第一个有效数据的迭代器
iterator begin()
{return iterator(_head-_next); // 使用头结点后一个结点的地址构造普通迭代器
}// 返回指向最后一个有效数据的下一个位置的迭代器
iterator end()
{return iterator(_head); // 使用头结点的地址构造普通迭代器
}常量迭代器 begin() const 返回指向第一个有效数据的常量迭代器即头结点后一个结点的地址。end() const 返回指向最后一个有效数据的下一个位置的常量迭代器即头结点的地址。 // 返回指向第一个有效数据的常量迭代器
const_iterator begin() const
{return const_iterator(_head-_next); // 使用头结点后一个结点的地址构造常量迭代器
}// 返回指向最后一个有效数据的下一个位置的常量迭代器
const_iterator end() const
{return const_iterator(_head); // 使用头结点的地址构造常量迭代器
} 说明 iterator 和 const_iterator 分别用于非 const 和 const 对象。begin 函数返回的是指向第一个实际数据的迭代器end 函数返回的是指向“末尾”的迭代器通常用来表示容器的结束位置。 访问容器相关函数 front和back front 和 back 函数 用于获取链表中第一个有效数据和最后一个有效数据的引用。实现时需要处理普通对象和常量对象的情况。以下是其实现代码 普通对象 front() 返回第一个有效数据的引用。back() 返回最后一个有效数据的引用。 // 返回第一个有效数据的引用
T front()
{return *begin(); // 通过 begin() 获取第一个有效数据的引用
}// 返回最后一个有效数据的引用
T back()
{return *(--end()); // 通过 --end() 获取最后一个有效数据的引用
} 常量对象 front() const 返回第一个有效数据的常量引用。back() const 返回最后一个有效数据的常量引用。 // 返回第一个有效数据的常量引用
const T front() const
{return *begin(); // 通过 begin() 获取第一个有效数据的常量引用
}// 返回最后一个有效数据的常量引用
const T back() const
{return *(--end()); // 通过 --end() 获取最后一个有效数据的常量引用
} 说明 front() 函数返回第一个有效数据的引用或常量引用back() 函数返回最后一个有效数据的引用或常量引用。--end() 操作将 end() 迭代器向前移动一个位置指向最后一个有效数据。 插入、删除函数 insert insert 函数 用于在给定迭代器的位置之前插入一个新结点。 实现步骤包括定位插入位置、调整指针以及插入新结点。以下是 insert 函数的实现代码
// 在给定迭代器位置之前插入一个新结点
void insert(iterator pos, const T x)
{assert(pos._pnode); // 检测 pos 的合法性确保迭代器指向有效的结点node* cur pos._pnode; // 取得迭代器 pos 所指结点的指针node* prev cur-_prev; // 取得 pos 前一个位置的结点指针node* newnode new node(x); // 根据所给数据 x 构造一个新的结点// 建立 newnode 与 cur 之间的双向关系newnode-_next cur;cur-_prev newnode;// 建立 newnode 与 prev 之间的双向关系newnode-_prev prev;prev-_next newnode;
}erase erase 函数 用于删除给定迭代器位置的结点。 实现步骤包括获取当前结点及其相邻结点的指针调整相邻结点的双向关系然后释放当前结点的内存。
// 删除所给迭代器位置的结点
iterator erase(iterator pos)
{assert(pos._pnode); // 检测 pos 的合法性确保它指向一个有效结点assert(pos ! end()); // 删除的结点不能是头结点node* cur pos._pnode; // 取得要删除的结点指针node* prev cur-_prev; // 取得前一个结点指针node* next cur-_next; // 取得后一个结点指针delete cur; // 释放 cur 结点的内存// 建立 prev 与 next 之间的双向关系prev-_next next;next-_prev prev;return iterator(next); // 返回删除结点后的下一个迭代器
}push_back和pop_back push_back 和 pop_back 函数的实现用于 list 的尾插和尾删操作。 在已经实现了 insert 和 erase 函数的情况下可以通过复用这两个函数来实现 push_back 和 pop_back。以下是这两个函数的实现代码及说明
// 尾插函数
void push_back(const T x)
{insert(end(), x); // 在头结点前插入新结点
}// 尾删函数
void pop_back()
{erase(--end()); // 删除头结点的前一个结点
}push_front和pop_front push_front 和 pop_front 函数用于 list 的头插和头删操作。 可以通过复用已经实现的 insert 和 erase 函数来实现这两个功能。以下是这两个函数的实现代码及说明
// 头插函数
void push_front(const T x)
{insert(begin(), x); // 在第一个有效结点前插入新结点
}// 头删函数
void pop_front()
{erase(begin()); // 删除第一个有效结点
}其他函数 size size 函数用于获取当前容器中的有效数据个数。 由于 list 是链表无法直接通过索引访问元素所以需要通过遍历的方式逐个统计有效数据的个数。以下是 size 函数的实现代码及说明
// 获取当前容器中有效数据的个数
size_t size() const
{size_t sz 0; // 用于统计有效数据的个数const_iterator it begin(); // 获取第一个有效数据的迭代器while (it ! end()) // 遍历直到容器的末尾{sz; // 计数器加一it; // 迭代器前移到下一个结点}return sz; // 返回有效数据的个数
}resize resize 函数用于调整 list 容器的大小以适应给定的大小 n。 根据当前容器的大小和目标大小 nresize 的规则如下 若当前容器的大小小于 n 尾部添加元素直到容器大小等于 n。若当前容器的大小大于 n 只保留前 n 个元素删除其余元素。 实现 resize 时避免直接调用 size 函数因为 size 函数会遍历整个容器而我们希望在遍历过程中完成调整大小的操作。以下是 resize 函数的实现代码及说明
// 调整容器的大小为n如果当前大小小于n则尾插若当前大小大于n则删除多余元素
void resize(size_t n, const T val T())
{iterator i begin(); // 获取第一个有效数据的迭代器size_t len 0; // 记录当前遍历的数据个数// 遍历容器直到len达到n或遍历完所有元素while (len n i ! end()){len; // 增加计数器i; // 迭代器前移}if (len n) // 如果当前有效数据个数已达到或超过n{// 删除从第n个元素开始的所有元素while (i ! end()){i erase(i); // 删除当前元素并更新迭代器}}else // 当前有效数据个数小于n{// 尾插元素直到容器大小达到nwhile (len n){push_back(val); // 尾插元素len; // 增加计数器}}
} clear clear 函数会逐个删除所有结点最终只保留头结点。
// 清空容器逐个删除所有结点只保留头结点
void clear()
{iterator it begin(); // 获取第一个有效数据的迭代器while (it ! end()) // 逐个删除结点直到遍历完所有有效数据{it erase(it); // 删除当前结点并更新迭代器}
}empty empty函数用于判断容器是否为空。我们可以通过比较容器的begin函数和end函数返回的迭代器来实现这个判断。如果begin和end返回的迭代器相同那么说明容器中只有一个头结点即容器为空。
// empty函数用于判断容器是否为空
bool empty() const
{return begin() end(); // 判断begin和end返回的迭代器是否是同一个位置的迭代器若相同则说明容器中只有头结点
}swap swap函数用于交换两个容器。在list容器中实际上存储的仅仅是链表的头指针因此我们只需交换两个容器的头指针即可实现交换操作。
// 交换当前容器和指定容器的内容
void swap(listT lt)
{::swap(_head, lt._head); // 交换两个容器的头指针
}注意 在此处调用库中的 swap 函数时需要加上 ::作用域限定符以确保编译器在全局范围内查找 swap 函数避免编译器错误地调用当前类中的 swap 函数。
