关联容器与顺序容器

  • 关联容器 set，map，multiset,multimap
    关联式容器是非线性的树结构，更准确的说是二叉树结构。关联容器中元素是按关键字来保存和访问的，关联容器支持高效的关键字查找和访问，各元素之间没有严格的物理上的顺序关系。

  • map类型通常被称为关联数组，map以两个元素key-value的形式组织，键key元素在map中担任索引的职位，map内部自建一颗红黑树（一种非严格意义上的平衡二叉树），这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。

  • set类型是简单的关键字集合，可以高效储存和访问不同的关键字，同时set中仅包含一个键，并有效地支持关于某个键是否存在的查询。集合中的元素按一定的顺序排列，并被作为集合中的实例，其中所包含的元素的值是唯一的。

  • 顺序容器 vector,list,deque,stack,queue
    顺序容器是线性的可序群集，在顺序性容器中的每个元素均有固定的位置，除非使用删除或者插入的操作改变这个位置。位置与元素本身无关。

  • vector在C++标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector被认为是一个容器，这是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。

  • stack栈栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。栈是只能在某一端插入和删除的特殊线性表。

  • queue队列是一种特殊的线性表，是一种先进先出（FIFO）的数据结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。