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

作者：Gausst松鼠会 | 2024-03-06 10:22:14

踩

容器适配器包括哪些

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