当前位置:   article > 正文

简述STL中容器适配器的概念_容器适配器包括哪些

容器适配器包括哪些

 

  • STL中提供了三种容器适配器:栈适配器、队列适配器和优先队列适配器。在使用STL时。可以向使用普通的栈stack、队列queue、和优先队列priority_queue那样去操作数据。
  • 栈的特征是后进先出,后入栈的元素先出栈,先入栈的元素后出栈,因此站适配器应该支持从栈顶添加删除元素以及访问元素的操作。容器vector、list和quque都满足栈操作的条件,因此都能作为栈适配器的底层容器,STL中默认使用deque作为栈适配器的底层容器。
  • 队列的特征是先进先出,先入队的元素先出队,后入队的元素后出队,因此队列适配器应该支持从队头删除元素、向队尾添加元素以及访问队头队尾元素的操作。由于容器vector在删除首元素时需要移动所有元素,因此不适合作为队列适配器的底层容器,应该选用list或者deque,STL中默认使用deque作为队列适配器的底层容器。
  • 优先队列在逻辑上与队列相似,一端插入元素和另一端删除元素,但是优先队列在元素中加入了权重的概念。优先队列中的元素并非像队列一样按照插入的顺序依次排列,而是根据元素的权重排列。添加元素时按照元素优先级插入到相应的位置,删除元素时将优先级最高的元素删除。
  • 优先队列中权重相邻的元素在底层容器中并不相邻。实际上优先队列利用底层容器实现了一个队,堆顶的元素优先级最高。堆背后的数据结构是一个二叉树,底层容器中的元素就是二叉树中的结点,二叉树通过顺序容器的下标存储父子结点之间的关系。
  • 优先队列的插入删除元素在底层容器实现的堆上进行操作。在堆的插入删除算法中,需要随机访问元素,因此不能使用list作为优先队列适配器的底层容器,比较而言deque也不太适合,STL中默认使用vector作为优先队列适配器的底层容器。
  • 栈适配器支持删除栈顶元素pop,向栈顶压入元素push,返回栈顶元素top;队列适配器支持删除队首元素pop,向队尾添加元素push,返回队首元素front,返回队尾元素back;优先队列适配器支持删除最高优先级元素pop,添加元素push,返回最高优先级元素top。
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/197907
推荐阅读
相关标签
  

闽ICP备14008679号