std :: deque или std :: list

я использую push_front() а также push_back() только. Таким образом, я не несу никаких других затрат на использование insert() или же remove(),

Я знаю, что оба контейнера предлагают O(1) сложность для каждой из этих функций, dequeс амортизированным постоянным временем по сравнению с listс постоянным временем.

Но я хочу знать, какое время меньше другого, если оно вообще есть.

5

Решение

Не уверен, как ответить на ваш вопрос. Вы, кажется, хотите, чтобы мы написали тестовую программу, которую вы могли бы написать самостоятельно. Поэтому вместо того, чтобы сделать это, я просто скажу следующее:

  • С listкаждый элемент, который вы нажимаете, будет выделяться из памяти.
  • С deque, большие блоки выделяются сразу.

Учитывая, что распределение памяти обычно медленное, я ожидаю deque превзойти список.

Если вы нажмете или вытолкнете много предметов одновременно, это будет особенно верно, так как локальность кэша вступает в игру.

Конечно, вы можете написать распределитель в списке, чтобы использовать пул памяти. Тогда вы можете получить лучшую производительность.

Итак, имея в виду эти гипотезы, уходи и измерение это, и если вы хотите обсудить результаты, это будет время, чтобы задать вопрос.

7

Другие решения

Всякий раз, когда речь заходит о производительности, плохая идея — «угадать» (или спросить в Интернете, что немного лучше, чем угадать, но только немного), и всегда лучше измерить два варианта — в этом случае просто выполните цикл и push_back или push_front достаточно вещей, чтобы сделать его реалистичным [вы можете захотеть сделать его более реалистичным и выполнять большую часть того, что делает ваш код, и делать это в цикле достаточно времени, чтобы сделать его достаточно продолжительным, чтобы измерить время — часто это больше реалистичнее, чем добавление базилионовых значений к list/deque и затем обнаруживает, что «когда вы должны поменяться, это становится очень медленным!»].

2

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector