AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

C++：关于模拟实现vector和list中迭代器模块的理解

2023-10-13 92
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： C++：关于模拟实现vector和list中迭代器模块的理解

本篇是关于vector和list的模拟实现中，关于迭代器模块的更进一步理解，以及在前文的基础上增加对于反向迭代器的实现和库函数的对比等

本篇是写于前面模拟实现的一段时间后，重新回头看迭代器的实现，尤其是在模板角度对list中迭代器封装的部分进行解析，希望可以对迭代器的封装实现有更深层次的理解，同时将与库内的实现做对比进行优化处理

list和vector的迭代器对比

list和vector的迭代器实现是不一样的，在vector中的迭代器就是一个原生指针，因此在实现的时候也就是用的原生指针即可，但是对于list来说不能这样，list的迭代器中例如++和--这样的操作，是不能和vector中的原生指针一样直接去实现的，而是需要用next或者是prior来模拟这个过程，还有例如*和->这样的访问数据的模式，因此在list的迭代器实现中是使用了封装来进行实现的

STL中有六大组件，其中迭代器算其中一个，那么也就意味着迭代器具有通用的功能，例如下面的代码，在使用构造函数时可以使用迭代器进行构造，而这个构造的过程使用的迭代器对于各种容器来说都是通用的：

#include <iostream>
#include <vector>
#include <list>
using namespace std;
int main()
{
  vector<int> v1{ 1,2,3,4,5,3,2,2 };
  vector<int> v2(v1.begin(), v1.end());
  list<int> l1(v1.begin(), v1.end());
  return 0;
}

那么就意味着，在实现迭代器的过程中也是就可以根据迭代器来进行不同容器间的构造

list的实现过程

首先，在list的实现过程中要有下面几个部分组成：list中包含的节点，list的迭代器访问，list的节点之间的关系

那么首先就是list中节点的定义，用到了模板，现在再对该部分进行解析，其实就是在创建的时候可以根据需要的内容开辟出对应的节点类型

template<class T>
struct list_node
{
  T _data;
  list_node<T>* _next;
  list_node<T>* _prev;
  list_node(const T& x = T())
    :_data(x)
    , _next(nullptr)
    , _prev(nullptr)
  {}
};

有了节点信息，就可以对list做一些基础的操作，例如头插头删，尾插尾删等操作，但对于insert和erase这些操作还不能够实现，因此就要实现迭代器模块的内容

不管是对于vector还是list，迭代器的本质就是用一个原生指针去进行访问等等，但是list和vector不同的是，list的存储地址并不是连续的，因此在访问的过程中就需要对迭代器进行一定程度的封装，例如在++或者--的操作符上可以进行一些体现，因此list迭代器的实现是需要进行单独的封装的

// 定义正向迭代器
template <class T, class Ref, class Ptr>
class __list_iterator
{
public:
  typedef list_node<T> Node;
  typedef __list_iterator<T, T&, T*> self;
  __list_iterator(Node* node)
    :_node(node)
  {}
  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;
  }
  Ref operator*()
  {
    return _node->_data;
  }
  Ptr operator->()
  {
    return &_node->_data;
  }
  bool operator !=(const self& s)
  {
    return _node != s._node;
  }
  bool operator ==(const self& s)
  {
    return _node == s._node;
  }
  Node* _node;
};

上面的片段对list进行了一些封装，实现了它的一些基础功能，从代码中也能看出来，迭代器的本质确确实实就是指针，用指针来进行一系列的操作，对下面这几个片段单独进行解析：

Ptr operator->()
  {
    return &_node->_data;
  }

这是对于迭代器中解引用的运算符重载，这里使用的是&_node->_data的写法，看似很怪，但是实际上这里的函数调用过程应该是这样

也就是说，这里对于->进行运算符重载后，还需要进行解引用，这个运算符重载函数返回的是一个指针，而这个指针还要继续进行解引用才能得到用户想要得到的值，编译器在这里进行了特殊处理，两个->使得可读性下降，因此将两个->进行了一定程度的合并，只需要一个->就可以实现解引用的目的

其次是对模板的使用部分

template <class T, class Ref, class Ptr>
  typedef list_node<T> Node;
  typedef __list_iterator<T, T&, T*> self;

这里在最开始定义的时候，就定义了数据类型，引用和指针三种模板参数，借助这个参数就可以用模板将复杂的内容实现简单化，只需要一份代码，模板就可以直接实例化出用户在调用的时候需要的代码，在进行封装const迭代器的时候，只需要提供的参数改为const版本就可以实现目的，很便捷

这样就实现了正向迭代器的普通版本，而对于const迭代器的版本也只需要进行不同的模板参数就可以实例化出const版本的迭代器

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

有了迭代器，在实现链表的各种函数功能就更加方便，例如可以实现erase和insert的操作，实现了这两个函数，在进行头插头删，尾插尾删的时候就更加方便，只需要进行原地的调用即可

// Modifiers
  void push_front(const T& val)
  {
    //Node* newnode = new Node;
    //newnode->_data = val;
    //newnode->_next = _head->_next;
    //_head->_next->_prev = newnode;
    //_head->_next = newnode;
    //newnode->_prev = _head;
    //_size++;
    insert(begin(), val);
  }
  void pop_front()
  {
    //Node* delnode = _head->_next;
    //_head->_next = _head->_next->_next;
    //_head->_next->_prev = _head;
    //delete delnode;
    //delnode = nullptr;
    //_size--;
    erase(begin());
  }
  void push_back(const T& val)
  {
    //Node* newnode = new Node;
    //newnode->_data = val;
    //newnode->_prev = _head->_prev;
    //_head->_prev->_next = newnode;
    //newnode->_next = _head;
    //_head->_prev = newnode;
    //_size++;
    insert(end(), val);
  }
  void pop_back()
  {
    //Node* delnode = _head->_prev;
    //delnode->_prev->_next = _head;
    //_head->_prev = delnode->_prev;
    //delete delnode;
    //delnode = nullptr;
    //_size--;
    erase(--end());
  }
  iterator insert(iterator pos, const T& val)
  {
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(val);
    _size++;
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    return iterator(newnode);
  }
  iterator erase(iterator pos)
  {
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    delete cur;
    cur = nullptr;
    _size--;
    prev->_next = next;
    next->_prev = prev;
    return iterator(next);
  }

那么上面是对前面已经有过的内容进行的重新温故，但是上面的代码其实是没有实现反向迭代器的，而在STL的库中，反向迭代器的定义和正向迭代器其实并不相同，它是直接借助正向迭代器对反向迭代器进行适配，有些类似于用vector，list或者deque对栈和队列进行的适配，也体现了封装和代码复用

template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:
  typedef ReverseIterator<Iterator, Ref, Ptr> Self;
  ReverseIterator(Iterator it)
    :_it(it)
  {}
  Self& operator++()
  {
    --_it;
    return *this;
  }
  Ref operator*()
  {
    return *_it;
  }
  Ptr operator->()
  {
    return _it.operator->();
  }
  bool operator!=(const Self& s)
  {
    return _it != s._it;
  }
private:
  Iterator _it;
};

上面的代码就是对于反向迭代器的封装，从中可以看出反向迭代器是使用了正向迭代器的，并且在它的基础上进行的修改，因此这个反向迭代器是可以适配于vector也可以适配于list的

整体来说，对于反向迭代器就是用正向迭代器进行适配出来的，体现了模板的好处

完整代码

#pragma once
namespace mylist
{
  // 定义节点内容
  template <class T>
  struct list_node
  {
    list_node(const T& x = T())
      :_data(x)
      , _next(nullptr)
      , _prev(nullptr)
    {}
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;
  };
  // 定义正向迭代器
  template <class T, class Ref, class Ptr>
  class __list_iterator
  {
  public:
    typedef list_node<T> Node;
    typedef __list_iterator<T, T&, T*> self;
    __list_iterator(Node* node)
      :_node(node)
    {}
    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;
    }
    Ref operator*()
    {
      return _node->_data;
    }
    Ptr operator->()
    {
      return &_node->_data;
    }
    bool operator !=(const self& s)
    {
      return _node != s._node;
    }
    bool operator ==(const self& s)
    {
      return _node == s._node;
    }
    Node* _node;
  };
  // 定义反向迭代器
  template<class Iterator, class Ref, class Ptr>
  class reverse_iterator
  {
    typedef reverse_iterator<Iterator, Ref, Ptr> self;
  public:
    reverse_iterator(Iterator it)
      :_it(it)
    {}
    self& operator++()
    {
      _it--;
      return *this;
    }
    self& operator++(int)
    {
      self tmp(*this);
      _it--;
      return tmp;
    }
    self& operator--()
    {
      _it++;
      return *this;
    }
    self& operator--(int)
    {
      self tmp(*this);
      _it++;
      return tmp;
    }
    Ref operator*()
    {
      Iterator cur = _it;
      return *(--cur);
    }
    Ptr operator->()
    {
      return &(operator*());
    }
    bool operator !=(const self& s)
    {
      return _it != s._it;
    }
    bool operator ==(const self& s)
    {
      return _it == s._it;
    }
    Iterator _it;
  };
  // 定义链表
  template <class T>
  class list
  {
    typedef list_node<T> Node;
  public:
    typedef __list_iterator<T, T&, T*> iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
    typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
    //typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
    // Constructor
    list()
    {
      empty_init();
    }
    list(const list<T>& lt)
    {
      for (auto x : lt)
      {
        push_back(x);
      }
    }
    list(iterator begin, iterator end)
    {
      empty_init();
      while (begin != end)
      {
        push_back(begin._node->_data);
        begin++;
      }
    }
    //list(reverse_iterator rbegin, reverse_iterator rend)
    //{
    //  empty_init();
    //  while (rbegin != rend)
    //  {
    //    push_back(rbegin._node->_data);
    //    rbegin++;
    //  }
    //}
    // Destructor
    ~list()
    {
      clear();
      delete _head;
      _head = nullptr;
    }
    // Operator=
    list<T>& operator=(const list<T>& lt)
    {
      swap(lt);
      return *this;
    }
    // Iterators
    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(end());
    }
    reverse_iterator rend()
    {
      return reverse_iterator(begin());
    }
    //const_reverse_iterator rbegin() const
    //{
    //  return const_reverse_iterator(end());
    //}
    //const_reverse_iterator rend() const
    //{
    //  return const_reverse_iterator(begin());
    //}
    // Capacity
    bool empty()
    {
      return _size == 0;
    }
    size_t size()
    {
      return _size;
    }
    // Element access
    T& front()
    {
      return begin()._node->_data;
    }
    T& back()
    {
      return (--end())._node->_data;
    }
    // Modifiers
    void push_front(const T& val)
    {
      //Node* newnode = new Node;
      //newnode->_data = val;
      //newnode->_next = _head->_next;
      //_head->_next->_prev = newnode;
      //_head->_next = newnode;
      //newnode->_prev = _head;
      //_size++;
      insert(begin(), val);
    }
    void pop_front()
    {
      //Node* delnode = _head->_next;
      //_head->_next = _head->_next->_next;
      //_head->_next->_prev = _head;
      //delete delnode;
      //delnode = nullptr;
      //_size--;
      erase(begin());
    }
    void push_back(const T& val)
    {
      //Node* newnode = new Node;
      //newnode->_data = val;
      //newnode->_prev = _head->_prev;
      //_head->_prev->_next = newnode;
      //newnode->_next = _head;
      //_head->_prev = newnode;
      //_size++;
      insert(end(), val);
    }
    void pop_back()
    {
      //Node* delnode = _head->_prev;
      //delnode->_prev->_next = _head;
      //_head->_prev = delnode->_prev;
      //delete delnode;
      //delnode = nullptr;
      //_size--;
      erase(--end());
    }
    iterator insert(iterator pos, const T& val)
    {
      Node* cur = pos._node;
      Node* prev = cur->_prev;
      Node* newnode = new Node(val);
      _size++;
      prev->_next = newnode;
      newnode->_prev = prev;
      newnode->_next = cur;
      cur->_prev = newnode;
      return iterator(newnode);
    }
    iterator erase(iterator pos)
    {
      Node* cur = pos._node;
      Node* prev = cur->_prev;
      Node* next = cur->_next;
      delete cur;
      cur = nullptr;
      _size--;
      prev->_next = next;
      next->_prev = prev;
      return iterator(next);
    }
    void swap(const list<T>& lt)
    {
      std::swap(_head, lt._head);
      std::swap(_size, lt._size);
    }
    void clear()
    {
      Node* cur = _head->_next;
      while (cur != _head)
      {
        Node* next = cur->_next;
        delete(cur);
        cur = next;
      }
      _head->_next = _head;
      _head->_prev = _head;
    }
    void empty_init()
    {
      _head = new Node;
      _head->_next = _head;
      _head->_prev = _head;
      _head->_data = T();
      _size = 0;
    }
    void Print()
    {
      Node* cur = _head->_next;
      while (cur != _head)
      {
        cout << cur->_data << "->";
        cur = cur->_next;
      }
      cout << "null" << endl;
    }
  private:
    Node* _head;
    size_t _size;
  };
  void test_iterator()
  {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    cout << "iterator constructor:";
    list<int> lt1(lt.begin(), lt.end());
    lt1.Print();
    cout << "front():" << lt.front() << endl;
    cout << "back():" << lt.back() << endl;
    mylist::__list_iterator<int, int&, int*> it = lt.begin();
    while (it != lt.end())
    {
      std::cout << *it << " ";
      it++;
    }
    cout << endl;
  }
  void test_clear()
  {
    list<int> lt1;
    cout << "push_back:" << endl;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);
    lt1.Print();
    lt1.clear();
    lt1.push_back(5);
    lt1.push_back(6);
    lt1.push_back(7);
    lt1.push_back(8);
    lt1.Print();
  }
  void test_push_pop()
  {
    list<int> lt1;
    cout << "push_back:" << endl;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);
    lt1.Print();
    cout << "pop_back:" << endl;
    lt1.pop_back();
    lt1.Print();
    list<int> lt2;
    cout << "push_front:" << endl;
    lt2.push_front(1);
    lt2.push_front(2);
    lt2.push_front(3);
    lt2.push_front(4);
    lt2.Print();
    cout << "pop_front:" << endl;
    lt2.pop_front();
    lt2.Print();
  }
  void test_reverse_iterator()
  {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    cout << "iterator constructor:";
    //list<int> lt1(lt.rbegin(), lt.rend());
    //lt1.Print();
    cout << "front():" << lt.front() << endl;
    cout << "back():" << lt.back() << endl;
    mylist::list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
      std::cout << *rit << " ";
      rit++;
    }
    cout << endl;
  }
  void test()
  {
    test_reverse_iterator();
    //test_push_pop();
    //test_clear();
  }
}


文章标签：
C++
容器
存储
编译器
关键词：
C++ vector
C++ list
C++模块
C++迭代器
C++ list迭代器
海绵宝宝de派小星
目录
相关文章
hahaha无
|
3月前
|
存储 DataX C语言
vector与list的简单介绍
vector是表示大小可以变化的数组的序列容器。就像数组一样，vector对其元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问其元素，并且与数组中的元素一样高效。但与数组不同的是，它们的大小可以动态变化，它们的存储由容器自动处理。在内部，vector使用动态分配的数组来存储其元素。当插入新元素时，可能需要重新分配此数组才能增大大小，这意味着分配一个新数组并将所有元素移动到该数组。
hahaha无
137 0
vector与list的简单介绍
羑悻的小杀马特
|
7月前
|
算法 编译器 C++
模拟实现c++中的vector模版
模拟实现c++中的vector模版
羑悻的小杀马特
132 28
羑悻的小杀马特
|
7月前
|
算法 C++ 容器
模拟实现c++中的list模版
模拟实现c++中的list模版
羑悻的小杀马特
108 23
ephemerals__
|
9月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现（附源码）
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。 最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。
ephemerals__
182 1
ephemerals__
|
9月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
278 7
蓝易云
|
9月前
|
存储 编译器 C++
C++ initializer_list&&类型推导
在 C++ 中，`initializer_list` 提供了一种方便的方式来初始化容器和传递参数，而右值引用则是实现高效资源管理和移动语义的关键特性。尽管在实际应用中 `initializer_list&&` 并不常见，但理解其类型推导和使用方式有助于深入掌握现代 C++ 的高级特性。
蓝易云
99 4
ephemerals__
|
10月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器，包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组，能够根据需要自动调整大小，提供了丰富的操作接口，如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后，还展示了如何使用`vector`创建字符串数组，体现了`vector`在实际编程中的灵活性和实用性。
ephemerals__
508 4
oioihoii
|
9月前
|
存储 对象存储 C++
C++ 中 std::array＜int, array_size＞ 与 std::vector＜int＞ 的深入对比
本文深入对比了 C++ 标准库中的 `std::array` 和 `std::vector`，从内存管理、性能、功能特性、使用场景等方面详细分析了两者的差异。`std::array` 适合固定大小的数据和高性能需求，而 `std::vector` 则提供了动态调整大小的灵活性，适用于数据量不确定或需要频繁操作的场景。选择合适的容器可以提高代码的效率和可靠性。
oioihoii
390 0
ephemerals__
|
9月前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理，并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表，使用三个迭代器（指针）来维护数组，分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码，帮助读者更好地理解和掌握 `vector` 的实现细节。
ephemerals__
207 0
平凡程序猿~
|
7月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
154 0