面试之快速学习STL-deuqe和list

这篇具有很好参考价值的文章主要介绍了面试之快速学习STL-deuqe和list。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. deque

  1. deque 容器用数组(数组名假设为 map)存储着各个连续空间的首地址。也就是说,map 数组中存储的都是指针
  2. 如果 map 数组满了怎么办?很简单,再申请一块更大的连续空间供 map 数组使用,将原有数据(很多指针)拷贝到新的 map 数组中,然后释放旧的空间

deque容器迭代器的底层实现

template<class T,...>
struct __deque_iterator{
    ...
    T* cur;
    T* first;
    T* last;
    map_pointer node;//map_pointer 等价于 T**
}

cur:指向当前正在遍历的元素;
first:指向当前连续空间的首地址;
last:指向当前连续空间的末尾地址;
node:它是一个二级指针,用于指向 map 数组中存储的指向当前连续空间的指针。

借助这 4 个指针,deque 迭代器对随机访问迭代器支持的各种运算符进行了重载,能够对 deque 分段连续空间中存储的元素进行遍历。例如:

//当迭代器处于当前连续空间边缘的位置时,如果继续遍历,就需要跳跃到其它的连续空间中,该函数可用来实现此功能
void set_node(map_pointer new_node){
    node = new_node;//记录新的连续空间在 map 数组中的位置
    first = *new_node; //更新 first 指针
    //更新 last 指针,difference_type(buffer_size())表示每段连续空间的长度
    last = first + difference_type(buffer_size());
}
//重载 * 运算符
reference operator*() const{return *cur;}
pointer operator->() const{return &(operator *());}
//重载前置 ++ 运算符
self & operator++(){
    ++cur;
    //处理 cur 处于连续空间边缘的特殊情况
    if(cur == last){
        //调用该函数,将迭代器跳跃到下一个连续空间中
        set_node(node+1);
        //对 cur 重新赋值
        cur = first;
    }
    return *this;
}
//重置前置 -- 运算符
self& operator--(){
    //如果 cur 位于连续空间边缘,则先将迭代器跳跃到前一个连续空间中
    if(cur == first){
        set_node(node-1);
        cur == last;
    }
    --cur;
    return *this;
}

deque容器的底层实现

//_Alloc为内存分配器
template<class _Ty,
    class _Alloc = allocator<_Ty>>
class deque{
    ...
protected:
    iterator start;
    iterator finish;
    map_pointer map;
...
}

面试之快速学习STL-deuqe和list,面试之快速学习STL,面试,学习,c++

//begin() 成员函数
iterator begin() {return start;}
//end() 成员函数
iterator end() { return finish;}
//front() 成员函数
reference front(){return *start;}
//back() 成员函数
reference back(){
    iterator tmp = finish;
    --tmp;
    return *tmp;
}
//size() 成员函数
size_type size() const{return finish - start;}//deque迭代器重载了 - 运算符
//enpty() 成员函数
bool empty() const{return finish == start;}

总结

  1. deque并不是真的连续,是通过迭代器的操作符重载实现的所谓序列化容器。
  2. deque是靠两个迭代器和一个指针数组实现的

list

  1. 双向迭代器

list容器的底层实现

1. 双向列表
面试之快速学习STL-deuqe和list,面试之快速学习STL,面试,学习,c++
2. 双向循环列表
面试之快速学习STL-deuqe和list,面试之快速学习STL,面试,学习,c++

  1. node: 可以看到,双向链表的各个节点中存储的不仅仅是元素的值,还应包含 2 个指针,分别指向前一个元素和后一个元素。
template<typename T,...>
struct __List_node{
    //...
    __list_node<T>* prev;
    __list_node<T>* next;
    T myval;
    //...
}

list容器迭代器的底层实现

template<tyepname T,...>
struct __list_iterator{
    __list_node<T>* node;
    //...
    //重载 == 运算符
    bool operator==(const __list_iterator& x){return node == x.node;}
    //重载 != 运算符
    bool operator!=(const __list_iterator& x){return node != x.node;}
    //重载 * 运算符,返回引用类型
    T* operator *() const {return *(node).myval;}
    //重载前置 ++ 运算符
    __list_iterator<T>& operator ++(){
        node = (*node).next;
        return *this;
    }
    //重载后置 ++ 运算符
    __list_iterator<T>& operator ++(int){
        __list_iterator<T> tmp = *this;
        ++(*this);
        return tmp;
    }
    //重载前置 -- 运算符
    __list_iterator<T>& operator--(){
        node = (*node).prev;
        return *this;
    }
    //重载后置 -- 运算符
    __list_iterator<T> operator--(int){
        __list_iterator<T> tmp = *this;
        --(*this);
        return tmp;
    }
    //...
}
  1. 主要是一个node指针

list容器的底层实现

不同版本的 STL 标准库中,list 容器的底层实现并不完全一致,但原理基本相同。这里以 SGI STL 中的 list 容器为例,讲解该容器的具体实现过程。

template <class T,...>
class list
{
    //...
    //指向链表的头节点,并不存放数据
    __list_node<T>* node;
    //...以下还有list 容器的构造函数以及很多操作函数
}
  1. 也是一个node指针
  2. 但是为了更方便的实现 list 模板类提供的函数,该模板类在构建容器时,会刻意在容器链表中添加一个空白节点并作为 list 链表的首个节点(又称头节点)

注意:
使用双向链表实现的 list 容器,其内部通常包含 2 个指针,并分别指向链表中头部的空白节点和尾部的空白节点(也就是说,其包含 2 个空白节点)。

  1. 经常构造空的 list 容器,其用到的构造函数如下所示:
list() { empty_initialize(); }
// 用于空链表的建立
void empty_initialize()
{
    node = get_node();//初始化节点
    node->next = node; // 前置节点指向自己
    node->prev = node; // 后置节点指向自己
}
//故
//begin()成员函数
__list_iterator<T> begin(){return (*node).next;}
//end()成员函数
__list_iterator<T> end(){return node;}
//empty()成员函数
bool empty() const{return (*node).next == node;}
//front()成员函数
T& front() {return *begin();}
//back()成员函数
T& back() {return *(--end();)}

注意end()返回的是node即头节点

4 . 显然,即便是创建空的 list 容器,它也包含有 1 个节点。

  1. 除此之外,list 模板类中还提供有带参的构造函数,它们的实现过程大致分为以下 2 步:
    调用 empty_initialize() 函数,构造带有头节点的空 list 容器链表;
    将各个参数按照次序插入到空的 list 容器链表中

forward_list

forward_list 是 C++ 11 新添加的一类容器,其底层实现和 list 容器一样,采用的也是链表结构,只不过 forward_list 使用的是单链表,而 list 使用的是双向链表(如图 所示)。
面试之快速学习STL-deuqe和list,面试之快速学习STL,面试,学习,c++文章来源地址https://www.toymoban.com/news/detail-652023.html

到了这里,关于面试之快速学习STL-deuqe和list的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 面试之快速学习STL-set

    和 map、multimap 容器不同,使用 set 容器存储的各个键值对,要求键 key 和值 value 必须相等 使用 set 容器存储的各个元素的值必须各不相同 从语法上讲 set 容器并 没有强制对存储元素的类型做 const 修饰, 即 set 容器中存储的元素的值是可以修改的。但是,C++ 标准为了防止用户修

    2024年02月12日
    浏览(30)
  • 【C++】学习STL中的list

            大家好!,今天为大家带来的一篇博客是关于STL中的list,内容主要包括list的介绍使用、list的模拟实现。以及list与vector的对比。         首先,让我们看看list的文档介绍: list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向

    2024年02月10日
    浏览(37)
  • 【C++学习】STL容器——list

    目录 一、list的介绍及使用 1.1 list的介绍  1.2 list的使用 1.2.1 list的构造  1.2.2  list iterator的使用 1.2.3 list capacity 1.2.4 list element access 1.2.5 list modifiers 1.2.6 list 迭代器失效 二、list的模拟实现 2.1 模拟实现list 三、list和vector的对比 一、list的介绍及使用 1.1 list的介绍 list的文档介绍

    2024年02月14日
    浏览(38)
  • 【whale-starry-stl】01天 list学习笔记

    std::bidirectional_iterator_tag 是 C++ 标准库中定义的一个迭代器类型标签,用于标识支持双向遍历的迭代器类型。 在 C++ 中,迭代器是一种泛型指针,用于遍历容器中的元素。迭代器类型标签用于标识迭代器的特性,从而在算法中选择合适的迭代器类型。 std::bidirectional_iterator_tag

    2024年02月09日
    浏览(38)
  • C++ STL list

    ✅1主页:我的代码爱吃辣 📃2知识讲解:C++之 STL list介绍和模拟实现 ☂️3开发环境:Visual Studio 2022 💬4前言:上次我们详细的介绍了vector,今天我们继续来介绍一下TSTL中的另外一个容器list。list在基础的功能和结构上就是一个双向带头的循环链表,实现起来基本不难,但是

    2024年02月13日
    浏览(34)
  • STL——list详解

    1.1 初始化 在C++11之前,std::list容器没有提供初始化列表的构造函数,因此需要使用push_back或push_front函数向列表中添加元素。以下是一些常见的std::list初始化方式: 使用默认构造函数创建空列表 使用列表初始化语法创建列表 使用指定大小和默认值创建列表 使用迭代器创建列

    2024年02月06日
    浏览(38)
  • STL list基本用法

    list的底层实际是双向链表结构 构造函数 说明 list() 无参构造 list (size_type n, const value_type val = value_type()) 构造的list中包含n个值为val的元素 list (const list x) 拷贝构造函数 list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list 构造函数和前面的容器用法相同 赋值

    2024年02月11日
    浏览(40)
  • STL——list用法

    1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 2、list就是一个带头双向循环链表, list通常在任意位置进行插入、移除元素的执行效率更好。 3、 list最大的缺陷是不支持任意位置的随机访问。 有了前面使用string和vector的

    2024年02月12日
    浏览(40)
  • 【C++】STL---list

    list 是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list 的底层是 双向链表 结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 list 与 forward_list 非常相似:最主要的不

    2024年02月11日
    浏览(37)
  • STL之list

    使用库中的list类需要包含头文件 #inlcudelist ,并且使用 std:: 命名空间 list是一个 带头结点的双向循环链表 _head :指向其头结点 1.构造函数 每一个结点,创建时 _data = val,并将 _prev 和 _next 置空(nullptr)。 其中如果没有传val参数,则 使用缺省值T() :T类型的匿名对象(内置类型

    2024年02月09日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包