个人知识库 个人知识库
首页
关于
  • C语言
  • CPlusPlus
  • Linux
  • PHP
  • Nginx
  • MySQL
  • Redis
  • Docker
  • Kubernetes
  • SRS
阅读
常用工具
  • 分类
  • 标签
  • 归档
GitHub

Agnes001

坚持是一件很伟大的事业
首页
关于
  • C语言
  • CPlusPlus
  • Linux
  • PHP
  • Nginx
  • MySQL
  • Redis
  • Docker
  • Kubernetes
  • SRS
阅读
常用工具
  • 分类
  • 标签
  • 归档
GitHub
  • C语言

  • CPlusPlus

    • 基础特性

      • 枚举
      • 字符指针
    • vs2019设置
    • C++11特性

    • 并发编程

    • 引用
    • 类和对象
    • 友元和运算符重载
    • 继承
    • 继承和多态
    • 模板
    • C++基础总结
    • 类型转换
    • 异常
    • 容器
      • 1 string
      • 2 vector
      • 3 deque
      • 4 queue
      • 5 stack
      • 6 list
      • 7 set/multiset
      • 8 map/multimap
      • 顺序容器
      • 容器适配器
    • 算法
    • C++程序设计
    • C++ Primer总结
    • 编程技巧
    • 标准库体系结构与内核分析
    • 设计模式
    • cmake配置C++工程
    • libcurl的使用总结
    • web开发框架--drogon
    • log4cplus使用
    • C++数据类型
    • 函数
    • 线程
    • 进程
    • 文件操作
    • 日常问题记录
    • Cpp案例程序
    • 多线程
    • 侯捷c++11新特性
    • 侯捷stl
  • Lua技术栈

  • edoyun

  • 内存管理

  • 数据结构

  • 网络编程

  • Linux

  • 池化技术

  • 操作系统

  • python

  • 编程技术
  • CPlusPlus
Agnes001
2022-01-06

容器

STL六大组件: 容器、迭代器、算法

容器就是数据结构,用来将数据元素按照一定的规则进行排列,不同的容器拥有不同的排列规则,不同的排列规则可以达到不同的数据操作特点。 算法就是提供对容器数据元素的一些操作。 迭代器就是容器和算法之间的桥梁,粘合剂。

# 1 string

问:string存取字符[]和at的异同? 答:1 相同,[]和at都可以返回第n个字符 2 不同,at访问越界会抛出异常,[]越界会直接程序会挂掉。

# 2 vector

长度动态改变的动态数组,连续的内存空间,随机存取效率高。 vector是单口容器,在队尾插入和删除元素效率高,在指定位置插入会导致数据元素移动,效率低。 问:vector如何实现动态增长? 答: 当vector空间满的时候,再当插入新元素的时候,vector会重新申请一块更大的内存空间,将原空间数据拷贝到新的内存空间,然后释放旧的内存空间,再将新元素插入到新空间中,以此可以看出vector的空间动态增长效率较低。

# 3 deque

deque是双向开口的连续性空间,头尾辆段都可以做元素的插入和删除操作 deque和vector的最大差异? 一在于deque允许常数时间内对头端进行元素插入和删除操作。 二在于deque没有容量的概念,因为它是动态的以分段的连续空间组合而成,随时可以增加一段新的空间并链接起来,换句话说,像vector那样“因旧空间不足而重新分配一块更大的空间,然后再复制元素,释放空间”这样的操作不会发生在deque身上,也因此deque没有必要提供所谓的空间保留功能。

# 4 queue

先进先出的数据结构,不具有遍历行为。 必须从一个口数据元素入队,另一个口数据元素出队。

# 5 stack

先进后出的数据结构,stack不具有遍历行为,没有迭代器。 只有一个出入口

# 6 list

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 问:链表和数组有什么区别? 答:1) 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费。 2) 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据元素。(数组中插入、删除数据项时,需要移动其它数据项)

# 7 set/multiset

数据元素会自动进行排序。set是以RB-tree(红黑树,平衡二叉树的一种)为底层机制,查找效率特别高。 二叉搜索树,是指二叉树中的节点按照一定的规则进行排序,使得对二叉树中元素访问更加高效。二叉搜索树的放置规则是:任何节点的元素值一定大于其左子树中的每一个节点的元素值,并且小于其右子树的值。因此从根节点一直向左走,一直到无路可走,即得到最小值,一直向右走,直至无路可走,可得到最大值。那么在二叉搜索树中找到最大元素和最小元素是非常简单的事情。

# 8 map/multimap

当我们给容器中插入元素的时候,容器内部实施了拷贝动作,将我们要插入的元素再另行拷贝一份放入到容器中,而不是将原数据元素直接放进容器中,也就是说我们提供的元素必须能够被拷贝。 STL容器都是值引用,在向容器中加入元素的时候,实际上是对元数据进行了一份拷贝,将拷贝的数据放入到容器中

# 顺序容器

vector deque list forward_list array string

# 容器适配器

queue stack

编辑此页
#container
异常
算法

← 异常 算法 →

Theme by Vdoing
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式