手机测评网站,汕头保安公司,数据分析软件哪个最好用,wordpress 修改链接list#xff08;模拟实现#xff09; list模拟实现list_node节点结构定义std::__reverse_iterator逆向迭代器实现list迭代器 __list_iterator定义list类成员定义list成员函数定义1.begin()、end()、rbegin()和rend()2.empty_init()3.构造函数定义4.swap5.析构函数定义6.clear… list模拟实现 list模拟实现list_node节点结构定义std::__reverse_iterator逆向迭代器实现list迭代器 __list_iterator定义list类成员定义list成员函数定义1.begin()、end()、rbegin()和rend()2.empty_init()3.构造函数定义4.swap5.析构函数定义6.clear()7.push_back8.push_front9.insert10.erase11.pop_back()和pop_front()12.empty()、size()、front()和back()13.resize14.赋值运算符重载 list模拟实现全部代码list 和 vector的区别结语 list模拟实现
成员类型表
这个表中列出了C标准库中list容器的一些成员类型定义。这些类型定义是为了使list能够与C标准库的其他组件协同工作并提供一些通用的标准接口。每个成员类型的用处
value_type: 这个成员类型代表list容器中存储的数据类型即模板参数T的类型。
allocator_type: 这个成员类型代表分配器的类型用于为容器的内存分配和管理。默认情况下使用allocatorvalue_type作为分配器。
reference: 这个成员类型表示对元素的引用类型。对于默认分配器它是value_type即对元素的引用。
const_reference: 这个成员类型表示对常量元素的引用类型。对于默认分配器它是const value_type即对常量元素的引用。
pointer: 这个成员类型表示指向元素的指针类型。对于默认分配器它是value_type*即指向元素的指针。
const_pointer: 这个成员类型表示指向常量元素的指针类型。对于默认分配器它是const value_type*即指向常量元素的指针。
iterator: 这个成员类型是一个双向迭代器类型可以用于遍历容器的元素。它可以隐式转换为const_iterator允许在遍历时修改元素。
const_iterator: 这个成员类型也是一个双向迭代器类型用于遍历常量容器的元素不允许修改元素。
reverse_iterator: 这个成员类型是iterator的逆向迭代器可以从容器尾部向头部遍历。
const_reverse_iterator: 这个成员类型是const_iterator的逆向迭代器用于从常量容器的尾部向头部遍历。
difference_type: 这个成员类型表示两个迭代器之间的距离通常使用的是ptrdiff_t与指针的差值类型相同。
size_type: 这个成员类型表示非负整数的类型通常使用的是size_t用于表示容器的大小。
这些成员类型的定义使得list容器能够与其他C标准库的组件以及用户自定义的代码进行交互从而实现更加通用和灵活的功能。
list_node节点结构定义
定义链表的节点结构 list_node用于存储链表中的每个元素。让我们逐一解释每个部分的含义。
templateclass T
struct list_node
{T _data; // 存储节点的数据list_nodeT* _next; // 指向下一个节点的指针list_nodeT* _prev; // 指向前一个节点的指针// 构造函数list_node(const T x T()):_data(x) // 使用参数 x 初始化 _data, _next(nullptr) // 初始化 _next 为 nullptr, _prev(nullptr) // 初始化 _prev 为 nullptr{}
};T _data;存储节点中的数据类型为模板参数 T可以是任意数据类型。
list_nodeT* _next;指向下一个节点的指针用于构建链表结构。初始时设为 nullptr表示当前节点没有后继节点。
list_nodeT* _prev;指向前一个节点的指针同样用于构建链表结构。初始时设为 nullptr表示当前节点没有前驱节点。
构造函数 list_node(const T x T())构造函数可以接收一个参数 x用于初始化节点的数据。如果没有传入参数默认构造一个空节点。
通过这个节点结构你可以创建一个双向链表list将不同类型的数据存储在节点中并连接节点以构建链表的结构。这个节点结构为链表的实现提供了基础。
std::__reverse_iterator逆向迭代器实现
#pragma oncenamespace xzq
{// 复用迭代器适配器templateclass Iterator, class Ref, class Ptrstruct __reverse_iterator{Iterator _cur;typedef __reverse_iteratorIterator, Ref, Ptr RIterator;__reverse_iterator(Iterator it):_cur(it){}RIterator operator(){--_cur;return *this;}RIterator operator--(){_cur;return *this;}Ref operator*(){auto tmp _cur;--tmp;return *tmp;}Ptr operator-(){return (operator*());}bool operator!(const RIterator it){return _cur ! it._cur;}};
}说明 __reverse_iterator 类模板定义了一个逆向迭代器它有三个模板参数Iterator迭代器的类型、Ref引用类型和 Ptr指针类型。 _cur 是一个私有成员变量保存当前迭代器的位置。 构造函数接受一个正向迭代器作为参数并将其存储在 _cur 成员变量中。 operator() 重载了递增操作符让迭代器向前移动一个位置。 operator--() 重载了递减操作符让迭代器向后移动一个位置。 operator*() 重载了解引用操作符返回逆向迭代器指向的元素的引用。 operator-() 重载了成员访问操作符返回逆向迭代器指向的元素的指针。 operator!() 重载了不等于操作符用于判断两个逆向迭代器是否不相等。 这个逆向迭代器可以用于支持从容器的尾部向头部的方向进行迭代。在 C 标准库中std::reverse_iterator 用于实现类似的功能。
这个代码实现了一个迭代器适配器。迭代器适配器是一种在现有迭代器基础上提供不同功能的封装器使得原本的迭代器能够适应新的使用场景。
__reverse_iterator 就是一个逆向迭代器适配器。它封装了一个正向迭代器但通过重载操作符等方式使其可以从容器的尾部向头部进行迭代。这样的适配器能够让原本的正向迭代器在逆向遍历时更加方便。在下面的list模拟实现中的反向迭代器函数需要用到当然它也可以适用于其他容器的模拟实现因场景而定并不是所有容器都可以适用。
list迭代器 __list_iterator定义
迭代器 __list_iterator用于遍历链表中的节点。让我们逐一解释每个部分的含义。
templateclass T, class Ref, class Ptr
struct __list_iterator
{typedef list_nodeT Node; // 定义一个类型别名 Node用于表示 list 节点的类型typedef __list_iteratorT, Ref, Ptr iterator; // 定义一个类型别名 iterator用于表示 list 迭代器的类型typedef bidirectional_iterator_tag iterator_category; // 定义迭代器的分类这里是双向迭代器typedef T value_type; // 定义元素的类型即模板参数 Ttypedef Ptr pointer; // 定义指向元素的指针类型用于迭代器typedef Ref reference; // 定义对元素的引用类型用于迭代器typedef ptrdiff_t difference_type; // 定义表示迭代器之间距离的类型Node* _node; // 指向链表中的节点__list_iterator(Node* node):_node(node) // 初始化迭代器指向给定的节点{}bool operator!(const iterator it) const{return _node ! it._node; // 比较两个迭代器是否不相等}bool operator(const iterator it) const{return _node it._node; // 比较两个迭代器是否相等}Ref operator*(){return _node-_data; // 返回当前节点的数据}Ptr operator-(){ return (operator*()); // 返回当前节点数据的地址}// ititerator operator(){_node _node-_next; // 迭代器自增指向下一个节点return *this;}// ititerator operator(int){iterator tmp(*this); // 创建一个临时迭代器保存当前迭代器_node _node-_next; // 迭代器自增指向下一个节点return tmp; // 返回保存的临时迭代器}// --ititerator operator--(){_node _node-_prev; // 迭代器自减指向前一个节点return *this;}// it--iterator operator--(int){iterator tmp(*this); // 创建一个临时迭代器保存当前迭代器_node _node-_prev; // 迭代器自减指向前一个节点return tmp; // 返回保存的临时迭代器}
};这个迭代器结构为链表提供了遍历节点的能力。它可以用于循环遍历链表的每个元素提供了类似于指针的行为使得遍历链表变得更加方便。
这里提一下迭代器类型的分类
C 标准库中的迭代器分为五种主要类型每种类型提供了不同的功能和支持的操作。这些类型分别是
输入迭代器Input Iterator只允许从容器中读取元素但不能修改容器内的元素。只支持逐个移动、解引用、比较以及比较是否相等等操作。输入迭代器通常用于算法中如 std::find()。
输出迭代器Output Iterator只允许向容器写入元素但不能读取容器内的元素。支持逐个移动和逐个写入元素等操作。
前向迭代器Forward Iterator类似于输入迭代器但支持多次解引用。前向迭代器可以用于一些需要多次迭代的操作如遍历一个单链表。
双向迭代器Bidirectional Iterator在前向迭代器的基础上增加了向前遍历的能力。除了支持输入迭代器的操作外还支持向前移动和逐个向前移动元素等操作。
随机访问迭代器Random Access Iterator是最强大的迭代器类型。除了支持前向迭代器和双向迭代器的所有操作外还支持类似指针的算术操作如加法、减法以及随机访问容器中的元素。随机访问迭代器通常用于数组等支持随机访问的数据结构中。
在上面的代码中typedef bidirectional_iterator_tag iterator_category; 表示这个迭代器是双向迭代器类型因此它应该支持前向和双向迭代器的所有操作包括移动、解引用、比较等。这是为了确保这个迭代器在遍历 list 类的容器元素时能够正常工作。
list类成员定义
下面的代码是C 中双向链表模板类 list 的类定义部分。这个类定义了一些公共的成员类型和私有成员变量来支持链表的操作。让我们逐一解释每个部分的含义。
templateclass T
class list
{typedef list_nodeT Node;
public:// 定义迭代器类型typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;typedef __reverse_iteratoriterator, T, T* reverse_iterator;typedef __reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;private:Node* _head;
};typedef list_nodeT Node;定义一个别名 Node代表链表节点类型 list_nodeT。
typedef __list_iteratorT, T, T* iterator;定义了链表的正向迭代器类型 iterator它使用 __list_iterator 结构模板并指定了相应的参数类型。
typedef __list_iteratorT, const T, const T* const_iterator;定义了链表的常量正向迭代器类型 const_iterator用于在不修改链表元素的情况下遍历链表。
typedef __reverse_iteratoriterator, T, T* reverse_iterator;定义了链表的反向迭代器类型 reverse_iterator这个迭代器从链表末尾向链表开头遍历。
typedef __reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;定义了链表的常量反向迭代器类型 const_reverse_iterator。
Node* _head;链表的私有成员变量指向链表的头节点。
这个部分的代码定义了 list 类的公共成员类型和私有成员变量为实现链表的操作和管理提供了基础。
list成员函数定义
1.begin()、end()、rbegin()和rend()
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);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}这部分代码是关于 list 类的迭代器成员函数的定义。它们用于返回不同类型的迭代器使得用户可以遍历 list 容器的元素。
const_iterator begin() const: 这是一个常量成员函数返回一个常量迭代器它指向容器中的第一个元素节点。由于是常量迭代器所以不允许通过它修改容器内的元素。
const_iterator end() const: 这也是一个常量成员函数返回一个常量迭代器它指向容器末尾的“尾后”位置即不存在的元素位置。常量迭代器不能用于修改元素。
iterator begin(): 这是一个非常量成员函数返回一个非常量迭代器它指向容器中的第一个元素节点。允许通过这个迭代器修改容器内的元素。
iterator end(): 这也是一个非常量成员函数返回一个非常量迭代器它指向容器末尾的“尾后”位置即不存在的元素位置。非常量迭代器可以用于修改元素。
reverse_iterator rbegin(): 这是一个返回反向迭代器的函数它将 end() 的迭代器作为参数传递给 reverse_iterator 构造函数从而返回一个指向容器末尾的反向迭代器。
reverse_iterator rend(): 这是一个返回反向迭代器的函数它将 begin() 的迭代器作为参数传递给 reverse_iterator 构造函数从而返回一个指向容器开始的反向迭代器。
这些函数的目的是为了方便用户在不同情况下遍历容器元素包括正向遍历和反向遍历以及使用常量或非常量迭代器。通过这些迭代器用户可以在 list 容器中轻松访问和操作元素。
2.empty_init()
void empty_init()
{_head new Node; // 创建一个新的节点作为链表头部_head-_next _head; // 将头部节点的下一个指针指向自身表示链表为空_head-_prev _head; // 将头部节点的前一个指针也指向自身表示链表为空
}这是 list 类中的一个私有成员函数 empty_init()它用于初始化一个空的链表。
该函数的目的是在创建一个新的空链表时为头部节点 _head 初始化正确的指针使得链表为空。链表的头部节点 _head 用来标识链表的起始位置和结束位置。
在这个函数中首先通过 new 运算符创建一个新的节点作为链表的头部。然后将头部节点的 _next 指针和 _prev 指针都指向自身表示链表为空。这种情况下链表的头部节点既是首节点也是尾节点形成一个环状的链表结构。
在 list 类的构造函数中通过调用 empty_init() 来创建一个空链表。这在后续的操作中为链表的插入、删除等操作提供了正确的基础。
3.构造函数定义
template class InputIterator
list(InputIterator first, InputIterator last)
{empty_init(); // 初始化一个空链表while (first ! last){push_back(*first); // 将当前迭代器指向的元素添加到链表尾部first; // 移动迭代器到下一个元素}
}list 类的构造函数模板它接受一个范围内的元素并将这些元素添加到链表中。 这个构造函数使用了一个模板参数 InputIterator它表示输入迭代器的类型。这样构造函数可以接受不同类型的迭代器例如普通指针、list 的迭代器等。
在构造函数中首先调用 empty_init() 函数来初始化一个空链表确保链表头部的 _head 节点正确初始化。
然后使用一个循环遍历输入迭代器范围内的元素。在每次循环中通过 push_back() 函数将当前迭代器指向的元素添加到链表的尾部。之后将迭代器向前移动一个位置以便处理下一个元素。
list()
{empty_init(); // 初始化一个空链表
}这是 list 类的无参构造函数它用于创建一个空的链表。
这个构造函数不接受任何参数它只是在对象创建时将 _head 节点初始化为一个空链表。调用 empty_init() 函数会创建一个只包含 _head 节点的链表该节点的 _next 和 _prev 都指向自身表示链表为空。
list(const listT lt)
{empty_init(); // 初始化一个空链表listT tmp(lt.begin(), lt.end()); // 使用迭代器从 lt 创建一个临时链表swap(tmp); // 交换临时链表和当前链表完成拷贝操作
}这是 list 类的拷贝构造函数它用于创建一个新链表该链表与另一个已存在的链表 lt 相同
在这个构造函数中首先通过调用 empty_init() 函数初始化了一个空链表然后创建了一个临时链表 tmp这个临时链表的元素和链表 lt 中的元素相同通过迭代器从 lt 范围内创建。接着通过调用 swap() 函数将当前链表与临时链表 tmp 交换从而实现了链表的拷贝。
这种方式能够实现拷贝构造的效果因为在 swap() 函数中临时链表 tmp 的资源会交给当前链表而临时链表 tmp 会被销毁从而实现了链表内容的拷贝。
4.swap
void swap(listT x)
{std::swap(_head, x._head); // 交换两个链表的头结点指针
}这是 list 类的成员函数 swap它用于交换两个链表的内容。
在这个函数中通过调用标准库函数 std::swap将当前链表的头结点指针 _head 与另一个链表 x 的头结点指针 _head 进行交换。这个操作会导致两个链表的内容被互相交换但是实际上并没有复制链表中的元素只是交换了链表的结构。
这种交换操作通常在需要交换两个对象的内容时使用它可以在不复制数据的情况下实现两个对象之间的内容互换从而提高了效率。
需要注意的是这个函数只是交换了链表的头结点指针而链表中的元素顺序没有改变。
5.析构函数定义
~list()
{clear(); // 清空链表中的所有元素delete _head; // 删除头结点_head nullptr; // 将头结点指针置为空指针
}这是 list 类的析构函数用于销毁链表对象。
在这个析构函数中首先调用了成员函数 clear() 来清空链表中的所有元素确保在删除链表之前释放所有资源。然后使用 delete 关键字释放头结点的内存。最后将头结点指针 _head 置为空指针以避免出现野指针。
这样在链表对象被销毁时它所占用的内存将会被正确地释放从而防止内存泄漏。
6.clear()
void clear()
{iterator it begin(); // 获取链表的起始迭代器while (it ! end()) // 遍历链表{it erase(it); // 使用 erase() 函数删除当前元素并将迭代器指向下一个元素}
}这是 list 类的 clear() 成员函数用于清空链表中的所有元素。
在这个函数中首先获取链表的起始迭代器 begin()然后通过一个循环遍历链表中的所有元素。在循环内部调用了 erase() 函数来删除当前迭代器指向的元素并将迭代器更新为指向被删除元素的下一个元素。这样可以确保链表中的所有元素都被逐个删除。
需要注意的是erase() 函数在删除元素后会返回指向下一个元素的迭代器因此在每次循环迭代时更新迭代器是必要的以便继续正确地遍历链表。
总之这个 clear() 函数用于释放链表中的所有元素并确保链表变为空链表。
7.push_back
void push_back(const T x)
{Node* tail _head-_prev; // 获取当前链表的末尾节点Node* newnode new Node(x); // 创建一个新节点保存新元素 xtail-_next newnode; // 更新末尾节点的下一个指针指向新节点newnode-_prev tail; // 新节点的前一个指针指向原末尾节点newnode-_next _head; // 新节点的下一个指针指向头节点_head-_prev newnode; // 头节点的前一个指针指向新节点完成插入操作
}这是 list 类的 push_back() 成员函数用于在链表的末尾添加一个新元素。
在这个函数中首先获取当前链表的末尾节点尾节点的 _prev 指向链表的最后一个元素然后创建一个新的节点 newnode并将新元素 x 存储在新节点中。接着更新末尾节点的 _next 指针使其指向新节点然后更新新节点的 _prev 指针使其指向原末尾节点。同时将新节点的 _next 指针指向头节点完成循环链表的连接。最后更新头节点的 _prev 指针使其指向新节点确保链表的连接是完整的。
需要注意的是这个函数在链表末尾添加了一个新元素不影响其他元素的相对位置。
8.push_front
void push_front(const T x)
{insert(begin(), x); // 调用 insert 函数在头部插入新元素 x
}这个函数简单地调用了 insert 函数将新元素 x 插入到链表的头部。
9.insert
iterator insert(iterator pos, const T x)
{Node* cur pos._node; // 获取当前位置的节点Node* prev cur-_prev; // 获取当前位置节点的前一个节点Node* newnode new Node(x); // 创建一个新节点保存新元素 xprev-_next newnode; // 更新前一个节点的下一个指针指向新节点newnode-_prev prev; // 新节点的前一个指针指向前一个节点newnode-_next cur; // 新节点的下一个指针指向当前位置节点cur-_prev newnode; // 当前位置节点的前一个指针指向新节点完成插入操作return iterator(newnode); // 返回指向新节点的迭代器
}在 insert 函数中首先获取当前位置节点 pos 和其前一个节点 prev然后创建一个新节点 newnode 并将新元素 x 存储在新节点中。接着更新前一个节点的 _next 指针使其指向新节点然后更新新节点的 _prev 指针使其指向前一个节点。同时将新节点的 _next 指针指向当前位置节点 cur完成插入操作。最后更新当前位置节点的 _prev 指针使其指向新节点确保链表的连接是完整的。最后函数返回一个指向新节点的迭代器表示插入操作完成后的位置。
10.erase
iterator erase(iterator pos)
{assert(pos ! end()); // 断言确保 pos 不等于链表的结束迭代器Node* cur pos._node; // 获取当前位置的节点Node* prev cur-_prev; // 获取当前位置节点的前一个节点Node* next cur-_next; // 获取当前位置节点的后一个节点prev-_next next; // 更新前一个节点的下一个指针指向后一个节点next-_prev prev; // 更新后一个节点的前一个指针指向前一个节点delete cur; // 删除当前位置的节点return iterator(next); // 返回指向后一个节点的迭代器表示删除操作完成后的位置
}这部分代码实现了从链表中删除指定位置元素的功能。
在 erase 函数中首先使用断言来确保删除位置 pos 不是链表的结束迭代器。然后获取当前位置节点 pos、其前一个节点 prev 和后一个节点 next。接着更新前一个节点的 _next 指针使其指向后一个节点同时更新后一个节点的 _prev 指针使其指向前一个节点。这样当前位置节点就从链表中断开了。最后释放当前位置节点的内存空间并返回一个指向后一个节点的迭代器表示删除操作完成后的位置。
11.pop_back()和pop_front()
void pop_back()
{erase(--end()); // 通过 erase 函数删除链表末尾的元素
}pop_back 函数通过将链表的结束迭代器向前移动一个位置然后调用 erase 函数来删除该位置的元素实现了从链表末尾删除一个元素的操作。
void pop_front()
{erase(begin()); // 通过 erase 函数删除链表头部的元素
}pop_front 函数直接调用 erase 函数删除链表头部的元素实现了从链表头部删除一个元素的操作。
这两个函数分别对应于从链表的末尾和头部删除元素的操作通过调用 erase 函数来完成删除操作从而保持了链表的连接性。
12.empty()、size()、front()和back()
bool listT::empty() const
{return begin() end(); // 判断 begin() 是否等于 end() 来确定是否为空
}typename listT::size_t listT::size() const
{size_t count 0;for (const_iterator it begin(); it ! end(); it){count;}return count; // 遍历链表来计算元素个数
}typename listT::reference listT::front()
{assert(!empty()); // 如果链表为空则抛出断言return *begin(); // 返回链表的第一个元素
}typename listT::const_reference listT::front() const
{assert(!empty()); // 如果链表为空则抛出断言return *begin(); // 返回链表的第一个元素
}typename listT::reference listT::back()
{assert(!empty()); // 如果链表为空则抛出断言return *(--end()); // 返回链表的最后一个元素
}typename listT::const_reference listT::back() const
{assert(!empty()); // 如果链表为空则抛出断言return *(--end()); // 返回链表的最后一个元素
}上述代码实现了 empty() 函数用于判断链表是否为空size() 函数用于获取链表元素个数front() 函数用于获取链表第一个元素以及 back() 函数用于获取链表最后一个元素。注意函数中的断言用于确保在链表为空时不执行非法操作。
13.resize
templateclass T
void listT::resize(size_t n, const T val)
{if (n size()) {iterator it begin();std::advance(it, n); // 定位到新的尾部位置while (it ! end()) {it erase(it); // 从尾部截断删除多余的元素}}else if (n size()) {insert(end(), n - size(), val); // 插入足够数量的默认值元素}
}如果 n 小于当前链表的大小size()意味着你想要缩小链表的大小。在这种情况下函数会迭代遍历链表从尾部开始删除多余的元素直到链表的大小等于 n。
首先函数会使用 begin() 获取链表的起始迭代器然后使用 std::advance 函数将迭代器向前移动 n 个位置使其指向新的尾部位置。
接下来函数使用 erase 函数将从新尾部位置到链表末尾的所有元素删除从而使链表的大小减小到 n。
如果 n 大于当前链表的大小表示你想要增大链表的大小。在这种情况下函数会插入足够数量的值为 val 的元素到链表的末尾直到链表的大小等于 n。
函数会使用 insert 函数在链表的末尾插入 n - size() 个值为 val 的元素从而使链表的大小增大到 n。
14.赋值运算符重载
listT operator(listT lt)
{swap(lt); // 交换当前对象和传入对象的内容return *this; // 返回当前对象的引用
}这是一个赋值运算符重载函数它采用了拷贝并交换Copy and Swap的技巧来实现赋值操作。
这是一个成员函数用于将一个 listT 类型的对象赋值给当前的对象。 参数 lt 是通过值传递的所以会调用 listT 的拷贝构造函数创建一个临时副本。 然后通过 swap(lt) 调用 swap 函数来交换当前对象和临时副本的内容。在交换后临时副本的数据会被赋值给当前对象而临时副本会被销毁。由于交换是高效的操作可以避免大量的数据复制。 最后函数返回当前对象的引用以支持连续赋值操作。 这种方式不仅避免了手动管理内存的麻烦还确保了异常安全因为临时副本在函数结束时会被正确销毁。
list模拟实现全部代码
#pragma once#include assert.h
#include iostreamnamespace xzq
{templateclass Tstruct list_node{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr){}};templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, Ref, Ptr iterator;typedef bidirectional_iterator_tag iterator_category;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef ptrdiff_t difference_type;Node* _node;__list_iterator(Node* node):_node(node){}bool operator!(const iterator it) const{return _node ! it._node;}bool operator(const iterator it) const{return _node it._node;}Ref operator*(){return _node-_data;}Ptr operator-(){ return (operator*());}// ititerator operator(){_node _node-_next;return *this;}// ititerator operator(int){iterator tmp(*this);_node _node-_next;return tmp;}// --ititerator operator--(){_node _node-_prev;return *this;}// it--iterator operator--(int){iterator tmp(*this);_node _node-_prev;return tmp;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;typedef __reverse_iteratoriterator, T, T* reverse_iterator;typedef __reverse_iteratorconst_iterator, const T, const T* const_reverse_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);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}template class InputIterator list(InputIterator first, InputIterator last){empty_init();while (first ! last){push_back(*first);first;}}list(){empty_init();}void swap(listT x){std::swap(_head, x._head);}list(const listT lt){empty_init();listT tmp(lt.begin(), lt.end());swap(tmp);}listT operator(listT lt){swap(lt);return *this;}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}void push_back(const T x){Node* tail _head-_prev;Node* newnode new Node(x);tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;//insert(end(), x);}void push_front(const T x){insert(begin(), x);}iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return iterator(newnode);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return iterator(next);}bool listT::empty() const{return begin() end(); // 判断 begin() 是否等于 end() 来确定是否为空}typename listT::size_t listT::size() const{size_t count 0;for (const_iterator it begin(); it ! end(); it){count;}return count; // 遍历链表来计算元素个数}typename listT::reference listT::front(){assert(!empty()); // 如果链表为空则抛出断言return *begin(); // 返回链表的第一个元素}typename listT::const_reference listT::front() const{assert(!empty()); // 如果链表为空则抛出断言return *begin(); // 返回链表的第一个元素}typename listT::reference listT::back(){assert(!empty()); // 如果链表为空则抛出断言return *(--end()); // 返回链表的最后一个元素}typename listT::const_reference listT::back() const{assert(!empty()); // 如果链表为空则抛出断言return *(--end()); // 返回链表的最后一个元素}void resize(size_t n, const T val T()){if (n size()) {iterator it begin();std::advance(it, n);while (it ! end()) {it erase(it); // 从尾部截断删除多余的元素}}else if (n size()) {insert(end(), n - size(), val); // 插入足够数量的默认值元素}}private:Node* _head;};
}list 和 vector的区别
通过模拟实现 list 和 vector你可以更好地理解它们之间的区别和特点。这两者是 C 标准库中的序列式容器但它们在内部实现和使用场景上有很大的区别。
底层实现 list 通常是一个双向链表每个节点都包含了数据和指向前一个和后一个节点的指针。这使得在任何位置进行插入和删除操作都是高效的但随机访问和内存占用可能相对较差。 vector 是一个动态数组元素在内存中是连续存储的。这使得随机访问非常高效但插入和删除操作可能需要移动大量的元素效率较低。 插入和删除操作 在 list 中插入和删除操作是高效的无论是在容器的任何位置还是在开头和结尾。这使得 list 在需要频繁插入和删除操作时非常适用。 在 vector 中插入和删除操作可能需要移动元素特别是在容器的中间或开头。因此当涉及大量插入和删除操作时vector 可能不如 list 效率高。 随机访问 list 不支持随机访问即不能通过索引直接访问元素必须通过迭代器逐个遍历。 vector 支持随机访问可以通过索引快速访问元素具有良好的随机访问性能。 内存占用 由于 list 使用链表存储元素每个节点都需要额外的指针来指向前后节点可能会导致更多的内存占用。 vector 在内存中是连续存储的通常占用的内存较少。 迭代器失效 在 list 中插入和删除操作不会导致迭代器失效因为节点之间的关系不会改变。 在 vector 中插入和删除操作可能导致内存重新分配从而使原来的迭代器失效。 综上所述如果你需要频繁进行插入和删除操作而对于随机访问性能没有特别高的要求那么使用 list 是一个不错的选择。而如果你更注重随机访问性能可以选择使用 vector。当然在实际开发中还需要根据具体情况权衡使用哪种容器。
结语
有兴趣的小伙伴可以关注作者如果觉得内容不错请给个一键三连吧蟹蟹你哟 制作不易如有不正之处敬请指出 感谢大家的来访UU们的观看是我坚持下去的动力 在时间的催化剂下让我们彼此都成为更优秀的人吧 创作128天纪念日暂时还没有想好怎么分享下次再写喽
