C++中的list（2）简单复现list中的关键逻辑

C++中的list（2）//简单复现list中的关键逻辑

前言

  1. 这一节的主要内容就是：简单复现list中的关键逻辑。同样的，我们这一节也是先粗略的看一眼源码，结合源码，边理解边复现。源码我已经上传到gitee，网址如下：Murphy/博客存档，我们主要看的就是其中的stl_list.h

  2. 其次就是这一节是有难度的，但是难度很高吗？也不是很高，我尽量捋顺了给大家说清楚。这一节最主要的几个知识点就是：模板、封装、以及数据结构的逻辑。

自我梳理的逻辑

这一部分大家可看可不看，这是我自己梳理的一个逻辑过程，帮助我自己理解list的。大家感兴趣可以看一下，当然也可以直接跳过这部分。

数据结构的逻辑

首先我们知道list容器是一个带头双向循环链表。它和之前的string和vector不一样。链表的底层空间是不连续的，是通过一个一个节点相连形成的。

string类实例化出来的对象实际上是一个字符串或者说字符数组，vector实例化出来的对象实际上就是一个数组，他们空间连续，且可以直接通过new来为数组开辟空间。而且string对象和vector对象中的数组就只是存储目标数据。

而list类实例化出来的对象实际上是一个带头双向循环链表。首先，链表不是数组，链表不能通过new来直接开辟空间。链表是由节点组成的，对链表的管理其实就是对节点的管理。节点的实现是通过结构体来实现的。因为每一个节点中存储的数据不单纯是一个目标数据，还有上一个节点的地址和下一个节点的地址，所以需要用到结构体。上面说过，链表是由节点组成的，对链表的管理其实就是对节点的管理，new无法直接为链表开辟空间，但是new可以为结构体开辟空间。

那么要实现一个list类，它其中的成员变量是什么呢？我们可以先借鉴string和vector，string类我们复现的时候它的成员变量是一个指针（指向数组的指针），一个有效元素个数，一个空间容量大小。因为数组底层空间连续，那么只要知道了首元素的地址（也就是指向数组的那个指针），那么就可以通过对指针进行加减访问到每一个数据。

vector类复现的时候是有三个指针，分别指向数组首元素的地址，有效元素结束位置，数组空间结束位置。同样的，最主要的就是数组首元素地址，因为知道首元素地址之后就可以访问到别的元素。

到了list类，因为我们要实现带头的双向循环链表，那么我们想通过一个简单的成员变量就能找到全部成员，那么我们这里list类的成员变量应该就是：指向头节点的指针。知道头节点的位置之后，我们就可以通过头节点中记录的下一个节点的地址，找到下一个节点，以此类推，找到全部节点。

那么list类中的成员变量需要包含size（有效元素个数）和capacity（容量大小）吗？

那么很明显是不需要的，首先链表的节点是按需开辟，当需要有一个新节点的时候直接创建一个就ok了，它不像数组那样底层空间连续，开辟空间就一整块的开，链表是有一个数据进来的时候开辟一个节点的空间。所以就不涉及到容量大小capacity的问题。size的存在其实主要是与capacity区别开，且方便判断容量占用是否已满，用处其实也不大，因为在链表中，全都是有效元素，它不像vector和string类中的数组，由于空间可能会有冗余，所以才会有有效元素和容量大小的概念。

所以list类是不需要size和capacity这两个成员变量的，而且类里面也会提供size( )函数，所以size更没必要存在了。

带头双向循环链表是一个很不错的数据结构，能极大的方便我们程序员管理数据。

封装&&模板

在list中，我们就可以很明显的感觉到C++的封装和C++借助封装和模板来实现泛型编程的思想。在这一节，你首先得明白list类是什么样的，为什么是这样，也就是上面刚刚说的数据结构的逻辑，然后便是封装思想。封装其实不是什么很高级的东西，但是它就是很有用。

这里的封装主要体现在两个地方，一方面是：类，一方面是：迭代器。list类其实就是对带头双向循环链表的一个封装，并且通过模板来实现存储不同类型的数据。

C++借助类的封装和模板，我们可以发现我们学习的容器在表面上都很相似，用法也十分相似。这其实就是封装和模板的作用。首先我们学习容器的时候，可以发现C++提供的接口都很相似，用法相似，这能极大的帮助我们上手学习C++的容器。其次，当我们真正去实现C++的容器的时候又会发现它们的底层是不一样的，这就带来另一个好处就是，隐藏底层实现细节。

在这一节中，list类对带头双向循环链表的封装是比较容易理解的。但是迭代器对节点指针的封装就比较难理解了。

一方面list的迭代器不同于我们前面学的string和vector，我们在学习vector和string的时候可能感觉他们的迭代器实现很简单，不就是指针嘛。但是要知道，它们底层的物理空间是连续的，所以它们的原生指针（没有经过封装的指针）就是天然迭代器。只需要给它们的原生指针改个名字叫迭代器就行了。

那为什么底层物理空间连续的容器，它们的原生指针就能直接做迭代器呢？迭代器，迭代器，顾名思义，迭代，遍历数据用的。这里我们就拿vector来举例，当我们知道了首元素地址，也就是it=begin( )的时候，我们每对it进行一次++，it就会指向下一个元素。对it解引用就是数据本身。

在这里插入图片描述

但是，链表中节点的指针能直接当迭代器吗？假设我们直接使用链表中节点的指针做迭代器。同样是it=begin( )，当我们对it++的时候，it会指向什么地方？指向下一个节点吗？很明显，不一定。因为链表的底层物理空间不是连续的，所以对it++的时候（也就是对节点指针++）是无法准确的找到下一个节点的。

同样，当我们对it解引用的时候，也就是*it，我们可以得到存储的有效数据吗？很明显，也不行，为啥，因为it其实就是结构体指针，解引用之后就是结构体，结构体里面有前后节点的地址以及有效数据，我们无法直接通过对it解引用来获得我们想要的有效数据。

之前我们学习vector和string的时候，都是直接把原生指针改个名，改成iterator直接用。现在不行了。我们直接对结构体指针改个名，无法实现我们想要的结果。

我们想要的是：当我们对迭代器加减的时候能准确的找到前后节点的位置，对迭代器解引用能直接获得有效数据。

那么我们想实现这样的功能，我们目前只能借助函数重载来实现（我也不知道还有什么办法，我也才刚开始学）。

要知道所有的迭代器底层都是指针。我们要通过函数重载，使得迭代器的动作符合我们的要求。更改迭代器动作实质上就是更改结构体指针的动作逻辑，让结构体指针++的时候不是传统意义上的++，而是找到下一个节点的地址。

所以我们要对结构体指针的行为进行运算符重载来达到我们的目的。

但是，运算符重载的一个要求就是该类型是自定义类型，就好比如我们最开始学习的时候的时间类，我们可以使用运算符重载，使得时间类++是什么结果，–是什么结果。

所以，我们要对结构体指针进行封装，封装成一个自定义类型，然后在这个自定义类型里面，重载++和–和解引用等逻辑。

然后我们再对这个自定义类型改个名（iterator），这样我们就得到我们想要的迭代器了。

那么这里其实就有两层封装，一层是对结构体指针进行封装得到一个我们可以操作的自定义类型，一层是对自定义类型进行封装成迭代器。

那么list容器整体的重难点我已经梳理完了，接下来代码的讲解中我也会结合的讲。

源码

这里我也给大家把源码贴出来：

/*** Copyright (c) 1994* Hewlett-Packard Company** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Hewlett-Packard Company makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*** Copyright (c) 1996,1997* Silicon Graphics Computer Systems, Inc.** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Silicon Graphics makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*//* NOTE: This is an internal header file, included by other STL headers.*   You should not attempt to use it directly.*/#ifndef __SGI_STL_INTERNAL_LIST_H
#define __SGI_STL_INTERNAL_LIST_H__STL_BEGIN_NAMESPACE#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#endiftemplate <class T>
struct __list_node {typedef void* void_pointer;void_pointer next;void_pointer prev;T data;
};template<class T, class Ref, class Ptr>
struct __list_iterator {typedef __list_iterator<T, T&, T*>             iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __list_iterator<T, Ref, Ptr>           self;typedef bidirectional_iterator_tag iterator_category;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __list_node<T>* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;link_type node;__list_iterator(link_type x) : node(x) {}__list_iterator() {}__list_iterator(const iterator& x) : node(x.node) {}bool operator==(const self& x) const { return node == x.node; }bool operator!=(const self& x) const { return node != x.node; }reference operator*() const { return (*node).data; }#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */self& operator++() { node = (link_type)((*node).next);return *this;}self operator++(int) { self tmp = *this;++*this;return tmp;}self& operator--() { node = (link_type)((*node).prev);return *this;}self operator--(int) { self tmp = *this;--*this;return tmp;}
};#ifndef __STL_CLASS_PARTIAL_SPECIALIZATIONtemplate <class T, class Ref, class Ptr>
inline bidirectional_iterator_tag
iterator_category(const __list_iterator<T, Ref, Ptr>&) {return bidirectional_iterator_tag();
}template <class T, class Ref, class Ptr>
inline T*
value_type(const __list_iterator<T, Ref, Ptr>&) {return 0;
}template <class T, class Ref, class Ptr>
inline ptrdiff_t*
distance_type(const __list_iterator<T, Ref, Ptr>&) {return 0;
}#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */template <class T, class Alloc = alloc>
class list {
protected:typedef void* void_pointer;typedef __list_node<T> list_node;typedef simple_alloc<list_node, Alloc> list_node_allocator;
public:      typedef T value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference;typedef list_node* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;public:typedef __list_iterator<T, T&, T*>             iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iterator<const_iterator> const_reverse_iterator;typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */typedef reverse_bidirectional_iterator<const_iterator, value_type,const_reference, difference_type>const_reverse_iterator;typedef reverse_bidirectional_iterator<iterator, value_type, reference,difference_type>reverse_iterator; 
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */protected:link_type get_node() { return list_node_allocator::allocate(); }void put_node(link_type p) { list_node_allocator::deallocate(p); }link_type create_node(const T& x) {link_type p = get_node();__STL_TRY {construct(&p->data, x);}__STL_UNWIND(put_node(p));return p;}void destroy_node(link_type p) {destroy(&p->data);put_node(p);}protected:void empty_initialize() { node = get_node();node->next = node;node->prev = node;}void fill_initialize(size_type n, const T& value) {empty_initialize();__STL_TRY {insert(begin(), n, value);}__STL_UNWIND(clear(); put_node(node));}#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void range_initialize(InputIterator first, InputIterator last) {empty_initialize();__STL_TRY {insert(begin(), first, last);}__STL_UNWIND(clear(); put_node(node));}
#else  /* __STL_MEMBER_TEMPLATES */void range_initialize(const T* first, const T* last) {empty_initialize();__STL_TRY {insert(begin(), first, last);}__STL_UNWIND(clear(); put_node(node));}void range_initialize(const_iterator first, const_iterator last) {empty_initialize();__STL_TRY {insert(begin(), first, last);}__STL_UNWIND(clear(); put_node(node));}
#endif /* __STL_MEMBER_TEMPLATES */protected:link_type node;public:list() { empty_initialize(); }iterator begin() { return (link_type)((*node).next); }const_iterator begin() const { return (link_type)((*node).next); }iterator end() { return node; }const_iterator end() const { return node; }reverse_iterator rbegin() { return reverse_iterator(end()); }const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }reverse_iterator rend() { return reverse_iterator(begin()); }const_reverse_iterator rend() const { return const_reverse_iterator(begin());} bool empty() const { return node->next == node; }size_type size() const {size_type result = 0;distance(begin(), end(), result);return result;}size_type max_size() const { return size_type(-1); }reference front() { return *begin(); }const_reference front() const { return *begin(); }reference back() { return *(--end()); }const_reference back() const { return *(--end()); }void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); }iterator insert(iterator position, const T& x) {link_type tmp = create_node(x);tmp->next = position.node;tmp->prev = position.node->prev;(link_type(position.node->prev))->next = tmp;position.node->prev = tmp;return tmp;}iterator insert(iterator position) { return insert(position, T()); }
#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void insert(iterator position, InputIterator first, InputIterator last);
#else /* __STL_MEMBER_TEMPLATES */void insert(iterator position, const T* first, const T* last);void insert(iterator position,const_iterator first, const_iterator last);
#endif /* __STL_MEMBER_TEMPLATES */void insert(iterator pos, size_type n, const T& x);void insert(iterator pos, int n, const T& x) {insert(pos, (size_type)n, x);}void insert(iterator pos, long n, const T& x) {insert(pos, (size_type)n, x);}void push_front(const T& x) { insert(begin(), x); }void push_back(const T& x) { insert(end(), x); }iterator erase(iterator position) {link_type next_node = link_type(position.node->next);link_type prev_node = link_type(position.node->prev);prev_node->next = next_node;next_node->prev = prev_node;destroy_node(position.node);return iterator(next_node);}iterator erase(iterator first, iterator last);void resize(size_type new_size, const T& x);void resize(size_type new_size) { resize(new_size, T()); }void clear();void pop_front() { erase(begin()); }void pop_back() { iterator tmp = end();erase(--tmp);}list(size_type n, const T& value) { fill_initialize(n, value); }list(int n, const T& value) { fill_initialize(n, value); }list(long n, const T& value) { fill_initialize(n, value); }explicit list(size_type n) { fill_initialize(n, T()); }#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>list(InputIterator first, InputIterator last) {range_initialize(first, last);}#else /* __STL_MEMBER_TEMPLATES */list(const T* first, const T* last) { range_initialize(first, last); }list(const_iterator first, const_iterator last) {range_initialize(first, last);}
#endif /* __STL_MEMBER_TEMPLATES */list(const list<T, Alloc>& x) {range_initialize(x.begin(), x.end());}~list() {clear();put_node(node);}list<T, Alloc>& operator=(const list<T, Alloc>& x);protected:void transfer(iterator position, iterator first, iterator last) {if (position != last) {(*(link_type((*last.node).prev))).next = position.node;(*(link_type((*first.node).prev))).next = last.node;(*(link_type((*position.node).prev))).next = first.node;  link_type tmp = link_type((*position.node).prev);(*position.node).prev = (*last.node).prev;(*last.node).prev = (*first.node).prev; (*first.node).prev = tmp;}}public:void splice(iterator position, list& x) {if (!x.empty()) transfer(position, x.begin(), x.end());}void splice(iterator position, list&, iterator i) {iterator j = i;++j;if (position == i || position == j) return;transfer(position, i, j);}void splice(iterator position, list&, iterator first, iterator last) {if (first != last) transfer(position, first, last);}void remove(const T& value);void unique();void merge(list& x);void reverse();void sort();#ifdef __STL_MEMBER_TEMPLATEStemplate <class Predicate> void remove_if(Predicate);template <class BinaryPredicate> void unique(BinaryPredicate);template <class StrictWeakOrdering> void merge(list&, StrictWeakOrdering);template <class StrictWeakOrdering> void sort(StrictWeakOrdering);
#endif /* __STL_MEMBER_TEMPLATES */friend bool operator== __STL_NULL_TMPL_ARGS (const list& x, const list& y);
};template <class T, class Alloc>
inline bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y) {typedef typename list<T,Alloc>::link_type link_type;link_type e1 = x.node;link_type e2 = y.node;link_type n1 = (link_type) e1->next;link_type n2 = (link_type) e2->next;for ( ; n1 != e1 && n2 != e2 ;n1 = (link_type) n1->next, n2 = (link_type) n2->next)if (n1->data != n2->data)return false;return n1 == e1 && n2 == e2;
}template <class T, class Alloc>
inline bool operator<(const list<T, Alloc>& x, const list<T, Alloc>& y) {return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDERtemplate <class T, class Alloc>
inline void swap(list<T, Alloc>& x, list<T, Alloc>& y) {x.swap(y);
}#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */#ifdef __STL_MEMBER_TEMPLATEStemplate <class T, class Alloc> template <class InputIterator>
void list<T, Alloc>::insert(iterator position,InputIterator first, InputIterator last) {for ( ; first != last; ++first)insert(position, *first);
}#else /* __STL_MEMBER_TEMPLATES */template <class T, class Alloc>
void list<T, Alloc>::insert(iterator position, const T* first, const T* last) {for ( ; first != last; ++first)insert(position, *first);
}template <class T, class Alloc>
void list<T, Alloc>::insert(iterator position,const_iterator first, const_iterator last) {for ( ; first != last; ++first)insert(position, *first);
}#endif /* __STL_MEMBER_TEMPLATES */template <class T, class Alloc>
void list<T, Alloc>::insert(iterator position, size_type n, const T& x) {for ( ; n > 0; --n)insert(position, x);
}template <class T, class Alloc>
list<T,Alloc>::iterator list<T, Alloc>::erase(iterator first, iterator last) {while (first != last) erase(first++);return last;
}template <class T, class Alloc>
void list<T, Alloc>::resize(size_type new_size, const T& x)
{iterator i = begin();size_type len = 0;for ( ; i != end() && len < new_size; ++i, ++len);if (len == new_size)erase(i, end());else                          // i == end()insert(end(), new_size - len, x);
}template <class T, class Alloc> 
void list<T, Alloc>::clear()
{link_type cur = (link_type) node->next;while (cur != node) {link_type tmp = cur;cur = (link_type) cur->next;destroy_node(tmp);}node->next = node;node->prev = node;
}template <class T, class Alloc>
list<T, Alloc>& list<T, Alloc>::operator=(const list<T, Alloc>& x) {if (this != &x) {iterator first1 = begin();iterator last1 = end();const_iterator first2 = x.begin();const_iterator last2 = x.end();while (first1 != last1 && first2 != last2) *first1++ = *first2++;if (first2 == last2)erase(first1, last1);elseinsert(last1, first2, last2);}return *this;
}template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {iterator first = begin();iterator last = end();while (first != last) {iterator next = first;++next;if (*first == value) erase(first);first = next;}
}template <class T, class Alloc>
void list<T, Alloc>::unique() {iterator first = begin();iterator last = end();if (first == last) return;iterator next = first;while (++next != last) {if (*first == *next)erase(next);elsefirst = next;next = first;}
}template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {iterator first1 = begin();iterator last1 = end();iterator first2 = x.begin();iterator last2 = x.end();while (first1 != last1 && first2 != last2)if (*first2 < *first1) {iterator next = first2;transfer(first1, first2, ++next);first2 = next;}else++first1;if (first2 != last2) transfer(last1, first2, last2);
}template <class T, class Alloc>
void list<T, Alloc>::reverse() {if (node->next == node || link_type(node->next)->next == node) return;iterator first = begin();++first;while (first != end()) {iterator old = first;++first;transfer(begin(), old, first);}
}    template <class T, class Alloc>
void list<T, Alloc>::sort() {if (node->next == node || link_type(node->next)->next == node) return;list<T, Alloc> carry;list<T, Alloc> counter[64];int fill = 0;while (!empty()) {carry.splice(carry.begin(), *this, begin());int i = 0;while(i < fill && !counter[i].empty()) {counter[i].merge(carry);carry.swap(counter[i++]);}carry.swap(counter[i]);         if (i == fill) ++fill;} for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);swap(counter[fill-1]);
}#ifdef __STL_MEMBER_TEMPLATEStemplate <class T, class Alloc> template <class Predicate>
void list<T, Alloc>::remove_if(Predicate pred) {iterator first = begin();iterator last = end();while (first != last) {iterator next = first;++next;if (pred(*first)) erase(first);first = next;}
}template <class T, class Alloc> template <class BinaryPredicate>
void list<T, Alloc>::unique(BinaryPredicate binary_pred) {iterator first = begin();iterator last = end();if (first == last) return;iterator next = first;while (++next != last) {if (binary_pred(*first, *next))erase(next);elsefirst = next;next = first;}
}template <class T, class Alloc> template <class StrictWeakOrdering>
void list<T, Alloc>::merge(list<T, Alloc>& x, StrictWeakOrdering comp) {iterator first1 = begin();iterator last1 = end();iterator first2 = x.begin();iterator last2 = x.end();while (first1 != last1 && first2 != last2)if (comp(*first2, *first1)) {iterator next = first2;transfer(first1, first2, ++next);first2 = next;}else++first1;if (first2 != last2) transfer(last1, first2, last2);
}template <class T, class Alloc> template <class StrictWeakOrdering>
void list<T, Alloc>::sort(StrictWeakOrdering comp) {if (node->next == node || link_type(node->next)->next == node) return;list<T, Alloc> carry;list<T, Alloc> counter[64];int fill = 0;while (!empty()) {carry.splice(carry.begin(), *this, begin());int i = 0;while(i < fill && !counter[i].empty()) {counter[i].merge(carry, comp);carry.swap(counter[i++]);}carry.swap(counter[i]);         if (i == fill) ++fill;} for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1], comp);swap(counter[fill-1]);
}#endif /* __STL_MEMBER_TEMPLATES */#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif__STL_END_NAMESPACE #endif /* __SGI_STL_INTERNAL_LIST_H */// Local Variables:
// mode:C++
// End:

观察源码

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

看到这里，也该到我们自己动手写一个出来了，我先把我的代码贴出来给大家：

复现源码

list.h

#pragma once
#include<cassert>namespace lx
{template <class T>struct ListNode{ListNode<T>* next;ListNode<T>* prev;T data;ListNode(const T& x=T()):next(nullptr),prev(nullptr),data(x){}};template <class T, class Ref, class Ptr>struct __list_iterator{typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __list_iterator<T, T&, T*>             iterator;typedef __list_iterator<T, Ref, Ptr>           Self;typedef ListNode<T>* Node;Node _node;__list_iterator(Node node) : _node(node) {}__list_iterator() {}__list_iterator(const iterator& x) : _node(x._node) {}//重载bool operator==(const Self& x) const{return _node == x._node;}bool operator!=(const Self& x) const{return _node != x._node;}//解引用重载Ref operator*() const{return _node->data;}//箭头重载Ptr operator->(){return &(_node->data);//return &(operator*());}//前置++Self& operator++(){_node = _node->next;return *this;}//后置++Self operator++(int){Self tmp = *this;++ *this;return tmp;}//前置--Self& operator--(){_node = _node->prev;return *this;}//后置--Self operator--(int){Self tmp = *this;-- *this;return tmp;}};template <class T>class list{public:typedef __list_iterator<T, T&, T*>             iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;void empty_init(){_head = new node;_head->next = _head;_head->prev = _head;}list(){empty_init();}~list(){clear();delete _head;_head = nullptr;}list(const list<T>& x){empty_init();/*iterator it = x.begin();while (it != x.end()){push_back(*it);}*/for (const auto& e : x){push_back(e);}}/*list<T>& operator=(const list<T>& x){if (this != &x){clear();for (const auto& e : x){push_back(e);}}return *this;}*/list<T>& operator=(list<T> x){swap(x);return *this;}//iterator begin(){//return iterator(_head->next);return _head->next;}iterator end(){//return iterator(_head);return _head;}const_iterator begin() const{//return iterator(_head->next);return _head->next;}const_iterator end() const{//return iterator(_head);return _head;}//bool empty() const{//return _head->prev == _head;return _head->next == _head;}size_t size() const{size_t count = 0;const_iterator it = begin();while (it != end()){++count;++it;}return count;}//T& front(){return *(begin());}const T& front() const{return *(begin());}T& back(){return *(--end());}const T& back() const{return *(--end());}//void swap(list<T>& x){std::swap(_head, x._head);}iterator insert(iterator position, const T& val){assert(position._node);node* cur = position._node;node* prev = cur->prev;node* newnode = new node(val);prev->next = newnode;newnode->prev = prev;newnode->next = cur;cur->prev = newnode;//return iterator(newnode);return newnode;}iterator erase(iterator position){assert(position._node);assert(!empty());node* cur = position._node;node* next = cur->next;node* prev = cur->prev;delete cur;prev->next = next;next->prev = prev;//return iterator(next);return next;}void push_back(const T& val){node* tail = _head->prev;node* newnode = new node(val);tail->next = newnode;newnode->prev = tail;newnode->next = _head;_head->prev = newnode;}/*void push_back(const T& val){insert(end(), val);}*/void push_front(const T& val){node* cur = begin()._node;node* newnode = new node(val);_head->next = newnode;newnode->prev = _head;newnode->next = cur;cur->prev = newnode;}/*void push_front(const T& val){insert(begin(), val);}*/void pop_back(){assert(!empty());node* cur = _head->prev;node* prev = cur->prev;delete cur;prev->next = _head;_head->prev = prev;}/*void pop_back(){erase(--end());}*/void pop_front(){assert(!empty());node* cur = begin()._node;node* next = cur->next;delete cur;_head->next = next;next->prev = _head;}/*void pop_front(){erase(begin());}*/void resize(size_t n, T val = T()){if (n != size()){if (n > size()){size_t len = n - size();for (size_t i = 0; i < len; i++){push_back(val);}}else{size_t len = size() - n;for (size_t i = 0; i < len; i++){pop_back();}}}	}void clear(){assert(!empty());iterator it = begin();while (it != end()){it=erase(it);}}private:typedef ListNode<T> node;node* _head;};}

test.cpp//测试使用

#include<iostream>
using namespace std;#include"list.h"namespace lx
{void test1(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);auto it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;//////l1.push_front(11);l1.push_front(22);l1.push_front(33);l1.push_front(44);it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;/////l1.pop_front();l1.pop_front();l1.pop_front();l1.pop_front();it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;/////l1.pop_back();l1.pop_back();l1.pop_back();l1.pop_back();it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;l1.resize(7, 99);it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;l1.resize(1);it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;}
}int main()
{lx::test1();return 0;
}

复现代码讲解

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
后续的什么push_back（插入逻辑和insert一样，画画图就能明白）昂和resize呀，clear昂，都很简单了的，看代码完全能看懂的。（注释掉的代码表示的是另一种方法。）

这里简单说一下resize的作用：分为两种，当n大于原来的size()的时候，就是插入n-size()个节点。n小于原来的size()的时候就是删除size()-n个节点，也就是复用push_back和pop_back两个函数。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.tpcf.cn/bicheng/90263.html

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Linux——System V 共享内存 IPC

Linux——System V 共享内存 IPC

文章目录一、共享内存的原理二、信道的建立1.创建共享内存1.key的作用2.key的选取3.shmid的作用4.key和shmid的区别5.内存设定的特性6.shmflg的设定2.绑定共享内存3.代码示例三、利用共享内存通信1.通信2.解除绑定3.销毁共享内存1.命令行销毁2.程序中销毁四、共享内存的生命周期…
阅读更多...
Python 程序设计讲义（9）：Python 的基本数据类型——复数

Python 程序设计讲义（9）：Python 的基本数据类型——复数

Python 程序设计讲义&#xff08;9&#xff09;&#xff1a;Python 的基本数据类型——复数 复数与数学中的复数概念类似。在 Python 中&#xff0c;复数表示为 abj&#xff0c;其中&#xff1a;a为实数部分&#xff0c;b为虚数部分&#xff0c;j称为虚数单位。复数必须包含虚数…
阅读更多...
leetcode_121 买卖股票的最佳时期

leetcode_121 买卖股票的最佳时期

1. 题意 有一个股价变化图&#xff0c;你可以在一天买入&#xff0c;在未来一天卖出。 求通过这样一次操作的最大获利。 2. 题解 2.1 枚举 直接枚举&#xff0c;买入卖出的时间&#xff0c;肯定会超时啦~ 时间复杂度为O(n2)O(n^2)O(n2) 空间复杂度为O(1)O(1)O(1) class …
阅读更多...
ToBToC的定义与区别

ToBToC的定义与区别

B 端和 C 端主要是从产品所面向的用户群体角度来区分的&#xff0c;B 端指的是企业用户&#xff08;Business&#xff09;&#xff0c;C 端指的是个人消费者&#xff08;Consumer&#xff09;&#xff0c;它们在多个方面存在明显区别&#xff0c;具体如下&#xff1a;用户特征B…
阅读更多...
Python 程序设计讲义（8）：Python 的基本数据类型——浮点数

Python 程序设计讲义（8）：Python 的基本数据类型——浮点数

Python 程序设计讲义&#xff08;8&#xff09;&#xff1a;Python 的基本数据类型——浮点数 目录Python 程序设计讲义&#xff08;8&#xff09;&#xff1a;Python 的基本数据类型——浮点数一、浮点数的表示形式1、小数形式2、指数形式二、浮点数的精确度浮点数也称小数&am…
阅读更多...
MCP客户端架构与实施

MCP客户端架构与实施

前言：从模型到生产力 — MCP的战略价值 在过去的一年里，我们团队见证了大型语言模型（LLM）从技术奇迹向企业核心生产力工具的演变。然而，一个孤立的LLM无法解决实际的业务问题。真正的价值释放，源于将模型的认知能力与企业现有的数据、API及工作流进行无缝、安全、可扩展…
阅读更多...
白盒测试核心覆盖率标准详解文档

白盒测试核心覆盖率标准详解文档

白盒测试核心覆盖率标准详解文档 1. 什么是白盒测试与覆盖率&#xff1f; 白盒测试&#xff08;White-box Testing&#xff09;&#xff0c;又称结构测试或逻辑驱动测试&#xff0c;是一种测试方法&#xff0c;测试人员能够访问并了解被测软件的内部结构、代码和实现逻辑。测试…
阅读更多...
顺丰面试提到的一个算法题

顺丰面试提到的一个算法题

顺丰面试提到的一个算法题面试过程中大脑空白&#xff0c;睡了一觉后突然想明白了 原理非常简单就是根据数组中元素的值对值对应的索引进行排序 哎&#xff0c;&#xff0c;&#xff0c;&#xff0c;具体看以下代码吧[使用 Java 17 中 Stream 实现] 最好别用 CSDN 提供的在线运…
阅读更多...
ChatGPT Agent深度解析：告别单纯问答，一个指令搞定复杂任务？

ChatGPT Agent深度解析：告别单纯问答，一个指令搞定复杂任务？

名人说&#xff1a;博观而约取&#xff0c;厚积而薄发。——苏轼《稼说送张琥》 创作者&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 目录一、什么是ChatGPT Agent&#xff1f;从"客服"到"秘书"的华丽转…
阅读更多...
位运算在算法竞赛中的应用（基于C++语言）_位运算优化

位运算在算法竞赛中的应用（基于C++语言）_位运算优化

在C算法竞赛中&#xff0c;位运算优化是一种非常重要的技巧&#xff0c;因为它可以显著提高算法的效率。以下是一些常见的位运算优化方法及其在各种算法中的应用示例&#xff1a; 常见的位运算优化 1&#xff09;位与运算 &&#xff1a; 用途&#xff1a;用于检查某个位是否…
阅读更多...
SpringBoot 使用Rabbitmq

SpringBoot 使用Rabbitmq

1.Springboot默认MQ支持rabbitmq或者kafka maven引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId></dependency>propertis添加配置 # spring.rabbitmq.host192.168…
阅读更多...
C++核心编程学习4--类和对象--封装

C++核心编程学习4--类和对象--封装

C面向对象有三大特性&#xff1a;封装、继承和多态。 封装 将属性和行为作为一个整体。将属性和行为加以权限控制。 例子1&#xff1a;设计一个圆类 #include <iostream> using namespace std;// 设计一个圆类&#xff0c;求圆的周长 // 圆周率&#xff1a;3.14 const do…
阅读更多...
AC身份认证实验之AAA服务器

AC身份认证实验之AAA服务器

一、实验背景某公司需要在企业的公司网络出口使用上网行为管理设备&#xff0c;以审计管理局域网的所有设备&#xff0c;同时&#xff0c;局域网内的所有设备都将上网行为代理上网&#xff0c;但是发生过访客外传一些非法信息&#xff0c;所以需要对外来人员进行实名认证&#…
阅读更多...
数组算法之【数组中第K个最大元素】

数组算法之【数组中第K个最大元素】

目录 LeetCode-215题 LeetCode-215题 给定整数数组nums和整数k&#xff0c;返回数组中第k个最大元素 public class Solution {/*** 这里是基于小顶堆这种数据结构来实现的*/public int findKthLargest(int[] nums, int k) {// 实例化一个小顶堆MinHeap minHeap new MinHeap…
阅读更多...
高亮匹配关键词样式highLightMatchString、replaceHTMLChar

高亮匹配关键词样式highLightMatchString、replaceHTMLChar

replaceHTMLChar: s > s.toString().replace(/</g, <).replace(/>/g, >),// 高亮匹配关键词样式----------------------------------------highLightMatchString(originStr, matchStr, customClass ) {matchStr && (matchStr matchStr.replace(/[.*?…
阅读更多...
HUAWEI Pura80系列机型参数对比

HUAWEI Pura80系列机型参数对比

类别HUAWEI Pura80 UltraHUAWEI Pura80 ProHUAWEI Pura80 ProHUAWEI Pura80建议零售价&#xffe5;9999起&#xffe5;7999起&#xffe5;6499起&#xffe5;4699起颜色鎏光金、鎏光黑釉红、釉青、釉白、釉黑釉金、釉白、釉黑丝绒金、丝绒绿、丝绒白、丝绒黑外观材质设计光芒耀…
阅读更多...
使用 PyTorch 的 torchvision 库加载 CIFAR-10 数据集

使用 PyTorch 的 torchvision 库加载 CIFAR-10 数据集

CIFAR-10是一个更接近普适物体的彩色图像数据集。CIFAR-10 是由Hinton 的学生Alex Krizhevsky 和Ilya Sutskever 整理的一个用于识别普适物体的小型数据集。一共包含10 个类别的RGB 彩色图片&#xff1a;飞机&#xff08; airplane &#xff09;、汽车&#xff08; automobile …
阅读更多...
蓝桥杯51单片机

蓝桥杯51单片机

这是我备考省赛的时候总结的错误点和创新点那个时候是用来提醒自己的&#xff0c;现在分享给你们看^_^一考点二注意点记得初始化&#xff39;&#xff14;&#xff0c;&#xff39;&#xff15;&#xff0c;&#xff39;&#xff16;&#xff0c;&#xff39;&#xff17;&…
阅读更多...
【2025/07/23】GitHub 今日热门项目

【2025/07/23】GitHub 今日热门项目

GitHub 今日热门项目 &#x1f680; 每日精选优质开源项目 | 发现优质开源项目&#xff0c;跟上技术发展趋势 &#x1f4cb; 报告概览 &#x1f4ca; 统计项&#x1f4c8; 数值&#x1f4dd; 说明&#x1f4c5; 报告日期2025-07-23 (周三)GitHub Trending 每日快照&#x1f55…
阅读更多...
【生成式AI導論 2024】第12講：淺談檢定大型語言模型能力的各種方式 学习记录

【生成式AI導論 2024】第12講：淺談檢定大型語言模型能力的各種方式 学习记录

跟标准答案做对比看是否正确 选择题是不是正确 MMLU massive multitask Language Understanding MT-bench 使用语言模型来评分 还有其他任务的对比,也有特别刁钻的问题 阅读长文的能力 grep kamradt 大海捞针
阅读更多...
最新文章

Copyright @ 2022~2023