C++ STL中适配器以及deque(双端队列)的基本认识

简介: C++ STL中适配器以及deque(双端队列)的基本认识

一、容器适配器

1、什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。


2、STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque,比如:


3、利用正向迭代器适配反向迭代器

此处我以前面模拟实现的list中的迭代器为例

3.1 list正向迭代器模拟实现

  template<class T, class Ref, class Ptr>
  struct _list_iterator
  {
    typedef list_node<T> Node;
    typedef _list_iterator<T, Ref, Ptr> self;
    Node* _node;
    _list_iterator(Node* node)
      :_node(node)
    {}
    // 析构函数  -- 节点不属于迭代器,不需要迭代器释放
    // 拷贝构造和赋值重载 -- 默认生成的浅拷贝就可以
    Ref operator*()
    {
      return _node->_data;
    }
    Ptr 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& it)
    {
      return _node != it._node;
    }
    bool operator==(const self& it)
    {
      return _node == it._node;
    }
  };

3.2 借助list正向迭代器适配list反向迭代器:

list迭代器图示:

因此对 rbegin 进行 ++ 实际上是对 end 进行 --,而对 rend 进行 – 实际上是对 begin 进行 ++。有了这个结论之后我们就能利用现有的正向迭代器对其进行封装实现反向迭代器。

template<class Iterator, class Ref, class Ptr>
  struct Reverse_iterator
  {
    Iterator _it;
    typedef Reverse_iterator<Iterator, Ref, Ptr> self;
    Reverse_iterator(Iterator it)
      :_it(it)
    {}
    Ref operator*()
    {
      Iterator tmp = _it;
      return *(--tmp);
    }
    Ptr operator->()
    {
      return &(operator*());
    }
    self& operator++()
    {
      --_it;
      return *this;
    }
    self& operator--()
    {
      ++_it;
      return *this;
    }
    bool operator!=(const self& s)
    {
      return _it != s._it;
    }
  };

值得注意的是,这里实现的反向迭代器对于模拟实现STL中的其他容器同样适用。

二、deque的简单了解

1、deque的原理介绍

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。


deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,其底层结构如下图所示:

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:

那deque是如何借助其迭代器维护其假想连续的结构呢?

2、deque的缺陷

  • 与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。
  • 与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。
  • 但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构。

3、为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:


  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。结合了deque的优点,而完美的避开了其缺陷。


目录
相关文章
|
13小时前
|
存储 算法 C语言
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(下)
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)
11 2
|
13小时前
|
缓存 算法 C语言
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(上)
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)
8 0
|
4天前
|
存储 算法 C++
高效利用C++ STL库:标准模板库的使用技巧
本文介绍了C++ STL(标准模板库)的高效使用技巧,包括选择合适的容器类型、使用`emplace_back`而非`push_back`、预分配容器空间和范围for循环遍历容器。此外,还讨论了STL算法的运用,如用算法替代手动循环、使用lambda表达式和进行容器操作。通过这些技巧,开发者可以提升C++代码的性能和可读性。
|
4天前
|
算法 C++
c++算法学习笔记 (21) STL
c++算法学习笔记 (21) STL
|
4天前
|
算法 C++
c++算法学习笔记 (14) 栈与队列
c++算法学习笔记 (14) 栈与队列
|
4天前
|
算法 C++ 容器
黑马c++ STL常用算法 笔记(6) 常用集合算法
黑马c++ STL常用算法 笔记(6) 常用集合算法
|
4天前
|
算法 C++ 容器
黑马c++ STL常用算法 笔记(5) 常用算术生成算法
黑马c++ STL常用算法 笔记(5) 常用算术生成算法
|
1天前
|
存储 编译器 程序员
c++存储类
c++存储类
18 3
|
1天前
|
C++
c++类&对象
c++类&对象
15 3
|
2天前
|
编译器 C++
C++的基类和派生类构造函数
在 C++ 中,类的构造函数不能被继承,但基类的普通成员函数可以在派生类中访问。派生类必须通过其构造函数初始化继承的成员变量,由于私有成员变量无法直接初始化,因此需要在派生类构造函数中调用基类的构造函数来完成。示例代码显示了如何在派生类构造函数中调用基类构造函数,确保正确初始化。构造函数的调用顺序遵循自顶向下、从基类到派生类的规则,且只能调用直接基类的构造函数。如果基类没有默认构造函数,而派生类未指定构造函数调用,会导致编译错误。
17 4