я использую push_front()
а также push_back()
только. Таким образом, я не несу никаких других затрат на использование insert()
или же remove()
,
Я знаю, что оба контейнера предлагают O(1)
сложность для каждой из этих функций, deque
с амортизированным постоянным временем по сравнению с list
с постоянным временем.
Но я хочу знать, какое время меньше другого, если оно вообще есть.
Не уверен, как ответить на ваш вопрос. Вы, кажется, хотите, чтобы мы написали тестовую программу, которую вы могли бы написать самостоятельно. Поэтому вместо того, чтобы сделать это, я просто скажу следующее:
list
каждый элемент, который вы нажимаете, будет выделяться из памяти.deque
, большие блоки выделяются сразу.Учитывая, что распределение памяти обычно медленное, я ожидаю deque
превзойти список.
Если вы нажмете или вытолкнете много предметов одновременно, это будет особенно верно, так как локальность кэша вступает в игру.
Конечно, вы можете написать распределитель в списке, чтобы использовать пул памяти. Тогда вы можете получить лучшую производительность.
Итак, имея в виду эти гипотезы, уходи и измерение это, и если вы хотите обсудить результаты, это будет время, чтобы задать вопрос.
Всякий раз, когда речь заходит о производительности, плохая идея — «угадать» (или спросить в Интернете, что немного лучше, чем угадать, но только немного), и всегда лучше измерить два варианта — в этом случае просто выполните цикл и push_back или push_front достаточно вещей, чтобы сделать его реалистичным [вы можете захотеть сделать его более реалистичным и выполнять большую часть того, что делает ваш код, и делать это в цикле достаточно времени, чтобы сделать его достаточно продолжительным, чтобы измерить время — часто это больше реалистичнее, чем добавление базилионовых значений к list
/deque
и затем обнаруживает, что «когда вы должны поменяться, это становится очень медленным!»].