在C++中,stack
和queue
默认使用deque
作为底层容器的原因主要有以下几点:
-
操作效率:
deque
(双端队列)支持在头尾两端进行插入和删除操作,且时间复杂度都为O(1),非常高效1。而vector
在增长到一定长度时为了保证完全连续,需要重新申请更长的内存,并把原来的元素全部拷贝过去2。这使得vector
的尾部插入操作在某些情况下的时间复杂度会变为O(n),效率较低2。 -
空间利用率:
deque
并不是真正连续的一段空间,而是由一段段连续的小空间拼接而成1。这使得deque
在空间利用率上相比于list、vector
有优势1。 -
适应性:
deque
的特性使其更能贴合stack
和queue
的需求1。stack
为先进后出结构,所有具有push_back
和pop_back
的容器都可以作为底层默认容器1。queue
为先进先出结构,所有具有push_back
和pop_front
的容器都可以作为底层默认容器1。deque
恰好满足这两种操作的需求1。 -
灵活性:虽然
deque
是stack
和queue
的默认底层容器,但C++标准库允许用户根据自己的需求选择其他容器作为底层容器2。例如,如果能预分配足够的容量,使用vector
作为stack
的底层容器可能会更优2。
总的来说,deque
作为stack
和queue
的默认底层容器,是因为它在操作效率、空间利用率和适应性等方面的综合考虑结果12。