【C++】list模拟实现

🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。
🚁 个人主页：不 良
🔥 系列专栏：🛸C++  🛹Linux
📕 学习格言：博观而约取，厚积而薄发
🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同成长！ 🌹

文章目录

  • 定义结点类
  • lis类的成员变量和构造函数
  • list的迭代器
  • list类常用接口模拟实现
    • insert函数
    • erase函数
    • clear函数
    • 构造函数
    • 拷贝构造函数
    • 赋值运算符重载
    • 析构函数
  • 对比vector和list
  • list的反向迭代器

定义结点类

list相当于带头节点的双向链表，我们定义节点时要用类模板参数，同时定义_next、_prev指针和数据_data，使用struct定义类，因为节点类要能够被访问，而struct的默认访问权限就是public；构造函数缺省值要使用匿名对象，保证无论是自定义类型还是内置类型都能够构造成功。

//定义节点
template<class T>
struct list_node {
    list_node<T>* _next;
    list_node<T>* _prev;
    T _data;
    //节点构造函数,缺省值使用匿名对象
    list_node(const T& x = T())
        :_next(nullptr)
        ,_prev(nullptr)
        ,_data(x)
        {
        }
};

lis类的成员变量和构造函数

list是带头节点的双向链表，所以成员变量我们只需要定义一个头结点_head，构造函数就是让头节点指向自己。

注意成员变量类型为类名 + 模板参数。

template<class T>
class list {
    typedef list_node<T> node;
    public:
    list()
    {
        _head = new node;
        _head->_prev = _head;
        _head->_next = _head;
    }
    private:
    node* _head;
};

list的迭代器

vector和string的底层物理空间是连续的，我们可以通过指针的++或–来移动找到对应的元素，然而list的底层物理空间是不连续的，所以模拟实现list迭代器时，如果使用++或 --操作，++或 --的只是一个指针，并不能找到对应的位置。我们可以封装一个list迭代器类，实际上就是对结点指针进行封装，将各种运算符进行重载，使得在list类中能够像vector和string一样能够直接使用迭代器，而不用关心底层实现。

//迭代器类
template<class T>
struct __list_iterator {
    typedef list_node<T> node;
    typedef __list_iterator<T> self;
    node* _node;
    //构造一个迭代器，用结点的指针构造
    __list_iterator(node* n)
        :_node(n)
        {

        }
    T& operator*()
    {
        return _node->_data;
    }
    self& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    //不相等比较的就是结点的指针
    bool operator!=(const self& s)
    {
        return _node != s._node;
    }
};

测试：

void test_list1()
{
    list<int> l1;
    l1.push_back(1);
    l1.push_back(1);
    l1.push_back(1);
    l1.push_back(1);
    list<int>::iterator it = l1.begin();
    while (it != l1.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

在上面的测试代码中list<int>::iterator it = l1.begin();这句话调用了拷贝构造，因为我们没有实现所以调用的就是编译器自动生成的即浅拷贝，这里之所以能够使用浅拷贝是因为迭代器类中没有写析构函数，而且不需要释放结点（结点的指针不属于迭代器，仅仅是使用list结点，没有拥有list结点，没有权利释放list的对象，结点的析构交给链表。迭代器只是一个工具）。

完善一些后置++、后置–之后的代码：

//迭代器类
template<class T>
struct __list_iterator {
    typedef list_node<T> node;
    typedef __list_iterator<T> self;
    node* _node;
    //构造一个迭代器，用结点的指针构造
    __list_iterator(node* n)
        :_node(n)
        {

        }
    //重载解引用操作符*
    T& 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)
    {
        return _node != s._node;
    }
    bool operator==(const self& s)
    {
        return _node == s._node;
    }
};

当我们实现上述代码之后我们就可以在list类中实现begin和end函数：

iterator begin()
{
    return iterator(_head->_next);
}
iterator end()
{
    return iterator(_head);
}

当我们想要接收const对象时就需要先实现const_iterator：如下的代码

void print_list(const list<int>& l1)
{
    list<int>::iterator it = l1.begin();
    while (it != l1.end())
    {
        (*it) *= 2;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

我们在list类中实现下面的代码中编译能够通过：

iterator begin() const
{
    return iterator(_head->_next);
}
iterator end() const
{
    return iterator(_head);
}

但是为什么使用const修饰之后还能构造普通迭代器？这里的const修饰的是*this，也就是this指针指向的内容，但是这里this指针指向的内容还是一个指针，修饰的是指针本身即修饰的_head不能被改变，并不是_head指向的内容，指针本身不能改变，但是可以拷贝给别人，也就是说可以将这个指针传到迭代器类中。

虽然上述代码可以通过编译了，但是并不能达到我们想要的效果，仍然能够改变list中的元素值，为什么呢？因为构造出来的迭代器是普通迭代器，可读可修改。

库中const对象调用的是const函数，返回的是const迭代器。

库中函数声明：

     	iterator begin();
const_iterator begin() const;

const迭代器和普通迭代器的区别是：const迭代器本身可以修改，const迭代器指向的内容不可以被修改。

那我们可不可以用下面这种方式定义const迭代器呢？

typedef __list_iterator<T> iterator;   //T*
typedef const iterator const_iterator;  // T* const，而我们想要的是迭代器内容不能被修改，const T*

不可以，普通迭代器对标的是指针即T*，而const加在iterator前面保护迭代器本身不能被修改相当于保护指针不被修改即 T* const，而我们想要的是迭代器指向的内容不能被修改即const T*。

那我们想实现const迭代器应该怎么实现呢？很简单，只需要将普通迭代器代码稍加修改：

//const迭代器类
template<class T>
struct __list_const_iterator {
    typedef list_node<T> node;
    typedef __list_const_iterator<T> self;
    node* _node;
    //构造一个迭代器，用结点的指针构造
    __list_const_iterator(node* n)
        :_node(n)
        {

        }
    //重载解引用操作符*
    const T& 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)
    {
        return _node != s._node;
    }
    bool operator==(const self& s)
    {
        return _node == s._node;
    }
};

再将list类中的begin函数和end函数重载：

const_iterator begin() const
{
    return const_iterator(_head->_next);
}
const_iterator end() const
{
    return const_iterator(_head);
}

此时我们再将print_list代码修改如下即可实现我们想要的功能：

void print_list(const list<int>& l1)
{
    list<int>::const_iterator it = l1.begin();
    while (it != l1.end())
    {
        //(*it) *= 2;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

观察发现，const迭代器类和普通迭代器类中只有*重载运算符函数的返回值不一样，我们可以通过增加一个模板参数来控制返回值：

//迭代器类
template<class T,class Ref> //增加一个模板参数
struct __list_iterator {
    typedef list_node<T> node;
    typedef __list_iterator<T,Ref> self;
    node* _node;
    //构造一个迭代器，用结点的指针构造
    __list_iterator(node* n)
        :_node(n)
        {
        }
    //重载解引用操作符*
    Ref operator*()
    {
        return _node->_data;
    }
};

然后在list类中通过模板参数控制返回值：

template<class T>
	class list {
		//将节点类型重命名为node
		typedef list_node<T> node;
	public:
		//将迭代器类重命名为iterator
		typedef __list_iterator<T,T&> iterator;
		typedef __list_iterator<T,const T&> const_iterator;
	private:
		node* _head;
	};

image-20230703212948556

模板参数传引用或者传指针都可以，模板参数不同类型也就不同。

库里面的list迭代器类中一共有3个模板参数：

template<class T,class Ref,class Ptr>

我们要知道：

1.迭代器要么就是原生指针；

2.迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为（因为node*本身的++不符合需求，不是连续的空间）。

我们还需要重载一个->，自定义类型的指针要用->，内置类型用解引用*就可以。

如下面的测试代码：一般的类最好都将默认构造加上，并且给上缺省值。

struct AA {
    int _a1;
    int _a2;
    AA(int a1 = 0, int a2 = 0)
        :_a1(a1)
        ,_a2(a2)
        {

        }
}; 
void test_list2()
{
    list<AA> l1;
    l1.push_back(AA(1, 2));
    l1.push_back(AA(1, 2));
    l1.push_back(AA(1, 2));
    list<AA>::iterator it = l1.begin();
    while (it != l1.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

运行结果报错信息如下：

image-20230704160949768

我们可以通过重载流插入<<和流提取>>运算符解决问题，也可以通过下面的方式访问：

struct AA {
    int _a1;
    int _a2;
    AA(int a1 = 0, int a2 = 0)
        :_a1(a1)
        ,_a2(a2)
        {

        }
}; 
void test_list2()
{
    list<AA> l1;
    l1.push_back(AA(1, 2));
    l1.push_back(AA(1, 2));
    l1.push_back(AA(1, 2));
    list<AA>::iterator it = l1.begin();
    while (it != l1.end())
    {
        cout << (*it)._a1 << " " << (*it)._a2 << endl;
        ++it;
    }
    cout << endl;
}

但是这种方法有点麻烦，当我们有一个AA* ptr类型的指针时，我们通常使用->进行解引用：

AA* ptr = new AA(3,4);
cout << ptr->_a1 << " " << ptr->_a2 << endl;

所以迭代器也要去重载->，因为模拟的是指针的行为，所以也要支持使用->解引用。

在迭代器类中实现重载->：

//重载->，这里返回的相当于AA*
T* operator->()
{
    return &_node->_data;
}

然后测试代码就可以使用->：

void test_list2()
{
    list<AA> l1;
    l1.push_back(AA(1, 2));
    l1.push_back(AA(1, 2));
    l1.push_back(AA(1, 2));
    list<AA>::iterator it = l1.begin();
    while (it != l1.end())
    {
        //cout << it.operator->()->_a1  << it.operator->()->_a2 << endl;
        //可优化为下面这样：
        cout << it->_a1 << " " << it->_a2 << endl;
        ++it;
    }
    cout << endl;
}

image-20230704163309760

而当是const迭代器的时候返回值就是const T*，所以我们可以在迭代器类中再加一个模板参数Ptr用来表示->返回值：

//迭代器类
template<class T,class Ref,class Ptr>
struct __list_iterator {
    typedef list_node<T> node;
    typedef __list_iterator<T,Ref,Ptr> self;
    //重载->，这里返回的相当于AA*
    Ptr operator->()
    {
        return &_node->_data;
    }
}

在list类中通过模板参数控制返回值：

template<class T>
class list {
    //将节点类型重命名为node
    typedef list_node<T> node;
    public:
    //将迭代器类重命名为iterator
    typedef __list_iterator<T,T&,T*> iterator;
    typedef __list_iterator<T,const T&,const T*> const_iterator;
}

list类常用接口模拟实现

链表中只要实现了insert和erase，头插头删和尾插尾删都可以实现，所以我们先实现insert和erase函数。

insert函数

在pos位置之前插入一个新结点。

//在pos位置之前插入一个新结点
void insert(iterator pos,const T& val)
{
    node* cur = pos._node;
    node* prev = cur->_prev;
    node* new_node = new node(val);

    prev->_next = new_node;
    new_node->_prev = prev;
    new_node->_next = cur;
    cur->_prev = new_node;
}

list的迭代器不会失效，因为pos的指向不会改变，且它们的位置关系没有改变。

测试代码：迭代器pos的指向都是同一个位置。

void test_list1()
{
    list<int> l1;
    l1.push_back(1);
    list<int>::iterator it = l1.begin();
    while (it != l1.end())
    {
        cout << *it << " ";
        ++it;
    }
    //输出1
    cout << endl;
    list<int>::iterator pos = l1.begin();
    l1.insert(pos, 5);
    l1.insert(pos, 6);
    l1.insert(pos, 7);

    it = l1.begin();
    while (it != l1.end())
    {
        cout << *it << " ";
        ++it;
    }
    //输出5 6 7 1
    cout << endl;
}

有了插入之后头插和尾插就可以复用insert：

//尾插
void push_back(const T& x )
{
    //node* tail = _head->_prev;//这就是尾
    //node* new_node = new node(x);

    //tail->_next = new_node;
    //new_node->_prev = tail;
    //new_node->_next = _head;
    //_head->_prev = new_node;
    insert(end(), x);
}
//头插
void push_front(const T& x)
{
    insert(begin(), x);
}

erase函数

删除pos位置的结点。

void erase(iterator pos)
{
    //头结点不能被删除
    assert(pos != _head);
	//记录pos位置结点的前后结点
    node* prev = pos._node->_prev;
    node* next = pos._node->_next;

    //将pos结点移出list
    prev->_next = next;
    next->_prev = prev;
	
    //释放结点
    delete pos._node;
}

注意erase删除之后迭代器会失效。

迭代器失效是指迭代器所指向的节点失效，list中即节点被删除了，erase函数执行后，it所指向的节点被删除，因此it无效，在下一次使用it时，必须先给it赋值。

复用erase实现头删和尾删：

//尾删
void pop_back()
{
    erase(--end());
}
//头删
void pop_front()
{
    erase(begin());
}

注意引入模板参数之后类名已经不能做类型了，类名加模板参数才是类型。

**迭代器不需要关心模板参数是什么，直接使用就可以。vector的迭代器不一定是原生指针，有可能是被封装的。**我们可以通过typeid().name()函数查看类型。

image-20230704172721950

重载运算符可以由我们自己实现，关于迭代器失效问题具体问题具体对待。

list<int> l1;
//使用迭代器
list<int>::iterator it = l1.begin();
while (it != l1.end())
{
    cout << *it << " ";
    ++it;
}

//直接使用结点来定义
list_node<int>* pnode = l1._head->_next;

上面代码中分别使用迭代器和结点来直接定义，如果没有访问限定符的限制，那么上面两个一样吗？从物理空间上看一样，但是我们不能使用pnode遍历，因为++的结果不一样，*pnode是原生指针的解引用，pnode++只是加了一个指针，因为空间不连续并不一定能找到下一个结点。

既然erase之后迭代器失效，那么就要对erase进行修改，要有返回值：返回当前位置的下一个元素。

iterator erase(iterator pos)
{
    //头结点不能被删除
    assert(pos != _head);
	//记录pos位置结点的前后结点
    node* prev = pos._node->_prev;
    node* next = pos._node->_next;

    //将pos结点移出list
    prev->_next = next;
    next->_prev = prev;
	
    //释放结点
    delete pos._node;
    //返回下一个结点
    return iterator(next);
}

clear函数

清空list

void clear()
{
    iterator it = begin();
    while (it != end())
    {
        //it = erase(it);//erase会返回当前元素的下一个位置。
        erase(it++);
    }
}

我们也可以使用erase(it++)，因为后置++返回的是++之前的值，erase的不是it，是返回的it的拷贝。

迭代器中后置++：

//重载后置++
self operator++(int)
{
    self tmp(*this);
    _node = _node->_next;
    return tmp;
}

构造函数

默认构造函数

要push_back的前提要有哨兵位的头结点，所以要先建立一个头结点。我们可以学库里直接建立一个empty_init函数，用来建立头节点，用来初始化，构造函数调用就可以了。

void empty_init()
{
    _head = new node;
    _head->_next = _head;
    _head->_prev = _head;
}
list()
{
    empty_init();
}

有迭代器区间的构造函数

template<class Iterator>
list(Iterator first, Iterator last)
{
    empty_init();
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

const对象可不可以调用构造函数？

可以，const对象定义的时候没有const属性，如：const int n = 2，否则const对象怎么初始化。

拷贝构造函数

注意也要给定头节点，先进行初始化，调用empty_init函数，再通过尾插将被拷贝list内容拷贝到新容器中。

传统写法：

void empty_init()
{
	_head = new node;
	_head->_next = _head;
	_head->_prev = _head;
}
 
list(const list<T>& lt)
{
	empty_init();
	for ( auto e : lt)
	{
		push_back(e);
	}
}

现代写法：

//先实现交换函数，交换两个链表的头节点
void swap(list<T>& tmp)
{
    std::swap(_head, tmp._head);
}

list(const list<int>& lt)
{
    empty_init();//初始化
    list<T> tmp(lt.begin(), lt.end());//使用迭代器区间构造
    swap(tmp);//调用swap函数交换头节点
}

赋值运算符重载

void swap(list<T>& tmp)
{
    std::swap(_head, tmp._head);
}
//l1 = l2

list<T>& operator=(list<T> lt)
{
    swap(lt);
    return *this;
}

通过传值传参调用拷贝构造函数构造出一个临时对象，然后通过交换头节点实现赋值。不能使用引用，使用引用就相当于将l3和l1的头节点交换，就改变了l3的值，相当于两者交换了并不能正确完成拷贝。

析构函数

~list()
{
    //先将list中数据清空
    clear();
    //再将头结点删除
    delete _head;
    //指向空
    _head = nullptr;
}

对比vector和list

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

vectorlist
底层结构动态顺序表，一段连续的空间带头结点的双向循环链表
随机访问支持随机访问，访问任意元素的效率O(1)不支持随机访问，访问某个元素的效率O(N)
插入和删除任意位置插入和删除效率低，需要移动元素，时间复杂度为O(N)，插入时可能需要增容（开辟新空间，拷贝元素，释放旧空间），导致效率更低任意位置插入和删除效率高，不需要移动元素，时间复杂度为O(1)
空间利用率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点容易造成内存碎片，空间利用率低， 缓存利用率低
迭代器原生态指针对原生态指针(节点指针)进行封装
迭代器失效在插入元素时，要给所有的迭代器重新赋值，因为插入 元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效， 删除元素时，只会导致当前迭代 器失效，其他迭代器不受影响
使用场景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问

list的反向迭代器

正向迭代器的++运算符重载是向后走，即向着_next指针走；而反向迭代器的++运算符重载是沿着_prev方向走，我们可以通过将list迭代器的代码改造一下：修改的地方主要就是将正向迭代器的重载++运算符中改成_prev，重载--运算符中改为_next。

list的反向迭代器代码如下：

//反向迭代器
template<class T, class Ref, class Ptr>
struct __list_reverse_iterator {
    typedef list_node<T> node;
    typedef __list_reverse_iterator<T, Ref, Ptr> self;
    node* _node;

    //构造一个迭代器,用结点的指针构造
    __list_reverse_iterator(node* n)
        :_node(n)
        {

        }
    Ref operator*()
    {
        return _node->_data;
    }
    Ptr operator->()
    {
        return &_node->_data;
    }
    self& operator++()
    {
        _node = _node->_prev;
        return *this;
    }
    //后置++
    self operator++(int)
    {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }

    self& operator--()
    {
        _node = _node->_next;
        return *this;
    }

    self operator--(int)
    {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    //不相等比较的就是结点的指针
    bool operator!=(const self& s)
    {
        return _node != s._node;
    }
    bool operator==(const self& s)
    {
        return _node == s._node;
    }
};

然后在list类中将反向迭代器类重命名以及rbegin和rend函数：

template<class T>
class list {
    //将节点类型重命名为node
    typedef list_node<T> node;
public:
    void empty_init()
    {
        _head = new node;
        _head->_next = _head;
        _head->_prev = _head;
    }

    //将迭代器类重命名为iterator
    typedef __list_iterator<T,T&,T*> iterator;
    typedef __list_iterator<T,const T&,const T*> const_iterator;
    //将反向迭代器类重命名为 reverse_iterator
    typedef __list_reverse_iterator<T, T&, T*> reverse_iterator;
    typedef __list_reverse_iterator<T, const T&, const T*> const_reverse_iterator;
    list()
    {
        empty_init();
    }
    list(const list<T>& lt)
    {
        empty_init();
        for (auto e : lt)
        {
            push_back(e);
        }
    }
    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);
    }
    
    //反向迭代器对应函数
    reverse_iterator rbegin()
    {
        return reverse_iterator(_head->_prev);
    }
    reverse_iterator rend()
    {
        return reverse_iterator(_head);
    }
    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(_head->_prev);
    }
    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(_head); 
    }
private:
    node* _head;
};

测试：

void test_list()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //反向迭代器
    list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
        cout << (*rit) << " ";
        ++rit;
    }
    cout << endl;
}

输出结果：

image-20230704211417861

上面begin和end、rbegin和rend的指向刚开始的位置如下：

image-20230704212756291

但是库中的反向迭代器是通过正向迭代器完成的， 库中这种方法使反向迭代器作为一种正向迭代器的适配器模式，可以生产出任何容器的反向迭代器，只要正向迭代器可以正常工作，那么反向迭代器就能够正常的工作。库中begin和end、rbegin和rend的指向刚开始的位置如下：

image-20230704230641835

如果是上面这样刚开始头结点的位置不能解引用即rbegin位置不能解引用，此时我们如果想要实现倒序遍历就要对*重新进行重载，在重载*函数内让其对上一个位置进行解引用。

重载解引用返回的时候，返回值是个问题，我们可以再定义两个模板参数解决。此时我们就不用再用上面那种反向迭代器实现，可以在新的头文件中定义：

#pragma once
namespace Niu {
	template<class Iterator, class Ref, class Ptr>
    struct ReverseIterator {
        typedef ReverseIterator<Iterator, Ref, Ptr> Self;
        Iterator _cur;

        //我去用正向迭代器去构造一个方向迭代器
        ReverseIterator(Iterator it)
            :_cur(it)
            {

            }
        //重载*
        Ref operator*()
        {
            Iterator tmp = _cur;//拷贝构造
            --tmp;
            return *tmp;//返回上一个结点
        }
        Self& operator++()
        {
            --_cur;
            return *this;
        }
        Self& operator--()
        {
            ++_cur;
            return *this;
        }
        bool operator!=(const Self& s)
        {
            //反向迭代器和正向迭代器都是指针可以直接判断
            return  _cur != s._cur;
        }
    };
}

在类list中定义：

typedef ReverseIterator<iterator, T&,  T*> reverse_iterator;
typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;

此时list类中的rbegin和rend函数也要修改：

reverse_iterator rbegin()
{
    return reverse_iterator(end());
}
reverse_iterator rend()
{
    return reverse_iterator(begin());
}

此时再测试：

void test_list()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //反向迭代器
    list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
        cout << (*rit) << " ";
        ++rit;
    }
    cout << endl;
}

测试结果：

image-20230704234036262

我们使用模板，只要实现了一个迭代器，所有的迭代器都出来了，但是要求必须是双向迭代器，支持--才能使用，如list和vector。

list可以拷贝一份正向迭代器改造成反向迭代器，但是vector不能解决，因为vector本身就是内置类型。此时我们通过模板给vector的正向迭代器可以得到vector的反向迭代器：

namespace Niu {
	template<class T>
	class vector {
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
		typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}
		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
        ……
    };
}

测试：

void test_vector2()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    //正向遍历
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //反向迭代器
    vector<int>::reverse_iterator rit = v.rbegin();
    while (rit != v.rend())
    {
        cout << (*rit) << " ";
        ++rit;
    }
    cout << endl;
}

测试结果：

image-20230704233816526

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LVS负载均衡集群之LVS-DR部署

LVS负载均衡集群之LVS-DR部署

目录 一、lVS-DR集群概述 二、LVS-DR数据包流向分析 四、LVS-DR特性 五、DR模式 LVS负载均衡群集部 5.0配置虚拟 IP 地址&#xff08;VIP 192.168.14.180&#xff09; 5.1.配置负载调度器(192.168.14.101) 5.2部署共享存储&#xff08;NFS服务器&#xff1a;192.168.14.10…
阅读更多...
6.2Java EE——Spring的入门程序

6.2Java EE——Spring的入门程序

下面通过一个简单的入门程序演示Spring框架的使用&#xff0c;要求在控制台打印“张三&#xff0c;欢迎来到Spring”&#xff0c;实现步骤具体如下。 1、在IDEA中创建名称为chapter06的Maven项目&#xff0c;然后在pom.xml文件中加载需使用到的Spring四个基础包以及Spring依赖…
阅读更多...
etcd的使用

etcd的使用

什么是etcd ETCD是一个分布式、可靠的key-value存储的分布式系统&#xff0c;用于存储分布式系统中的关键数据&#xff1b;当然&#xff0c;它不仅仅用于存储&#xff0c;还提供配置共享及服务发现&#xff1b;基于Go语言实现 。 etcd的特点 完全复制&#xff1a;集群中的每…
阅读更多...
基于springboot+Redis的前后端分离项目之分布式锁（四）-【黑马点评】

基于springboot+Redis的前后端分离项目之分布式锁（四）-【黑马点评】

&#x1f381;&#x1f381;资源文件分享 链接&#xff1a;https://pan.baidu.com/s/1189u6u4icQYHg_9_7ovWmA?pwdeh11 提取码&#xff1a;eh11 分布式锁 分布式锁1 、基本原理和实现方式对比2 、Redis分布式锁的实现核心思路3 、实现分布式锁版本一4 、Redis分布式锁误删情况…
阅读更多...
Linux进程信号

Linux进程信号

文章目录&#xff1a; 信号入门从生活角度看信号技术应用角度看信号使用 kill -l 命令查看系统定义的信号列表信号处理常见方式概览 产生信号通过终端按键产生信号核心转储&#xff08;core dump&#xff09;的作用调用系统函数向进程发信号由软件条件产生信号硬件异常产生信号…
阅读更多...
0305kali linux配置运行-docker-macos aarm64

0305kali linux配置运行-docker-macos aarm64

文章目录 1 下载运行2 配置2.1 配置系统环境2.2 配置SSH服务2.3 安装工具 3 问题总结结语 1 下载运行 拉取kali linux镜像 docker pull kalilinux/kali-rolling该镜像为“纯净版”系统&#xff0c;没有任何工具&#xff0c;体积小。下面当我们运行起来之后&#xff0c;到容器中…
阅读更多...
Android Java代码与JNI交互 JNI访问Java构造方法(九)

Android Java代码与JNI交互 JNI访问Java构造方法(九)

🔥 Android Studio 版本 🔥 🔥 创建包含JNI的类 JNIConstructorClass.java 🔥 package com.cmake.ndk1.jni;import com.cmake.ndk1.model.Animal;public class JNIConstructorClass {static {System.loadLibrary("constructor-class-lib");}public native…
阅读更多...
Visual studio 2015下载安装以及缺包提示的处理方法

Visual studio 2015下载安装以及缺包提示的处理方法

最近要加入的比赛团队需要用到Visual studio 2015&#xff0c;百度后找到很多资源&#xff0c;自己也转到了百度网盘。中英文都有&#xff0c;需要的可以下载。 链接&#xff1a;https://pan.baidu.com/s/12gpVwXfQxfdkXub-IwhWFw?pwds325 提取码&#xff1a;s325 --来自百…
阅读更多...
为什么需要多语言并行机器翻译？

为什么需要多语言并行机器翻译？

随着全球化的加速和不同语言之间的交流需求不断增长&#xff0c;多语言机器翻译&#xff08;Multilingual Parallel Machine Translation&#xff09;成为一个备受关注的领域。传统上&#xff0c;机器翻译系统主要集中于一对特定语言之间的翻译&#xff0c;但这种单一语言对的模…
阅读更多...
【观察者模式】 ——每天一点小知识

【观察者模式】 ——每天一点小知识

&#x1f4a7; 观察者模式 \color{#FF1493}{观察者模式} 观察者模式&#x1f4a7; &#x1f337; 仰望天空&#xff0c;妳我亦是行人.✨ &#x1f984; 个人主页——微风撞见云的博客&#x1f390; &#x1f433; 《数据结构与算法》专栏的文章图文并茂&#x1f995;…
阅读更多...
uniapp 打包安卓apk (原生App)云打包

uniapp 打包安卓apk (原生App)云打包

uniapp 打包安卓apk (原生App)云打包 hbuilder中操作 项目的一些配置appid DCloud appid 用途/作用/使用说明&#xff1a; https://ask.dcloud.net.cn/article/35907 右键我们项目目录-》发行-》原生APP-云打包 说明&#xff1a; 1. 打包安卓&#xff0c;只选择安卓打包项&…
阅读更多...
基于pyqt和卷积网络CNN的中文汉字识别

基于pyqt和卷积网络CNN的中文汉字识别

直接上效果演示图&#xff1a; 通过点击按钮可以实现在画板上写汉字识别和加载图片识别两个功能。 视频演示和demo仓库地址在b站视频001期&#xff1a; 到此一游7758258的个人空间-到此一游7758258个人主页-哔哩哔哩视频 所有代码展示&#xff1a; 十分的简洁&#xff0c;主…
阅读更多...
jni编程（windows+JDK11+clion）

jni编程（windows+JDK11+clion）

JNI是Java Native Interface的缩写&#xff0c;通过使用 Java本地接口书写程序&#xff0c;可以确保代码在不同的平台上方便移植。 一、java代码 package org.example;public class Main {static {System.load("");}public static void main(String[] args) {Syste…
阅读更多...
医学图像处理——读取和解读NII文件

医学图像处理——读取和解读NII文件

一 预备知识 NII文件的存储格式网上有很多资料&#xff0c;在此只做一点简单的描述。nii是一种文件格式&#xff0c;它存储的是在空间中占有一定体积的小方块的物理位置和该位置对应的像素值。这个小方块我们也称之为体素(voxel)。存储的形式是一个三维数组(3D array)&#xf…
阅读更多...
ESP32连接云服务器【WebSocket】

ESP32连接云服务器【WebSocket】

ESP32连接云服务器【ESP32宝塔面板】 文章目录 ESP32连接云服务器【ESP32宝塔面板】&#x1f468;‍&#x1f3eb;内容1&#xff1a;背景&#x1f468;‍⚖️内容2&#xff1a;服务器配置&#x1f468;‍&#x1f4bb;内容3&#xff1a;ESP32配置 &#x1f468;‍&#x1f3eb;…
阅读更多...
k8s 就绪探针

k8s 就绪探针

【k8s 系列】k8s 学习二十&#xff0c;就绪探针 提起探针&#xff0c;不知兄dei 们是否有印象&#xff0c;之前我们分享过存活探针&#xff0c;分享存活探针是如何确保异常容器自动重启来保持应用程序的正常运行&#xff0c;感兴趣的可以查看文章 k8s 系列k8s 学习十七&#x…
阅读更多...
windows下使用arp 协议

windows下使用arp 协议

/ //自动扫描局域网存活主机 本程序是利用arp协议去获取局域网中的存活主机 arp协议概述 地址解析协议&#xff0c;即ARP&#xff08;Address Resolution Protocol&#xff09;&#xff0c;是根据IP地址获取物理地址的一个TCP/IP协议。主机发送信息时将包含目标IP地址的ARP请…
阅读更多...
音视频——码率、帧率越高越清晰？分辨率、像素、dpi的关系

音视频——码率、帧率越高越清晰？分辨率、像素、dpi的关系

一 前言 本期我介绍一下视频的一些基础概念&#xff0c;如帧率、码率、分辨率、像素、dpi、视频帧、I帧、P帧、gop等。我i初步学习音视频&#xff0c;给这些专业词汇进行扫盲 会解释多少码率是清晰的&#xff0c;是否帧率越高越流畅等问题。 这些概念是比较杂乱的&#xff0c…
阅读更多...
CentOS 7镜像下载 以及 DVD ISO 和 Minimal ISO 等各版本的区别介绍

CentOS 7镜像下载 以及 DVD ISO 和 Minimal ISO 等各版本的区别介绍

1.官网下载 官网下载地址&#xff1a;官网下载链接 点击进入下载页面&#xff0c;随便选择一个下载即可&#xff08;不推荐&#xff0c;推荐阿里云下载&#xff0c;见下文&#xff09; 阿里云下载站点&#xff08;速度非常快推荐&#xff09; 阿里云下载链接&#xff1a; http…
阅读更多...
二叉树（上）——“数据结构与算法”

二叉树（上）——“数据结构与算法”

各位CSDN的uu们好呀&#xff0c;好久没有更新我的数据结构与算法专栏啦&#xff0c;今天&#xff0c;小雅兰继续来更新二叉树的内容&#xff0c;下面&#xff0c;让我们进入链式二叉树的世界吧&#xff01;&#xff01;&#xff01; 二叉树链式结构的实现 二叉树链式结构的实现…
阅读更多...
最新文章

Copyright @ 2022~2023