Имеет ли std :: deque постоянную вставку времени в начале?

Question

Стандарт гласит:

Deque - это контейнер последовательности, который поддерживает итераторы произвольного доступа (27.2.7). Кроме того, он поддерживает операции вставки и удаления с постоянным временем в начале или в конце; вставка и стирание в середине занимают линейное время.

Однако в том же пункте также говорится:

Все требования к сложности, изложенные в этом пункте, изложены исключительно в условия количества операций над содержащимися объектами. [Пример: конструктор копирования типа vector<vector<int>> имеет линейную сложность, хотя сложность копирования каждого содержащегося vector<int> сама по себе линейна. - конец примера]

Не означает ли это, что вставка в начале, скажем, deque<int> может занимать линейное время до тех пор, пока она не выполняется больше, чем постоянное число операций на int s, которые уже находятся в deque, и новый int объект, который вставляется?

Например, предположим, что мы реализуем deque используя «вектор векторов размера K». Кажется, что каждый раз, когда мы вставляем K раз в начало, новый вектор size-K должен быть добавлен в начале, поэтому все другие векторы size-K должны быть перемещены. Это будет означать, что временная сложность вставки в начале амортизируется O (N / K), где N - общее количество элементов, но K является постоянным, так что это просто O (N). Но кажется, что это разрешено Стандартом, потому что перемещение вектора размера K не перемещает ни один из его элементов, а «требования к сложности» «изложены исключительно с точки зрения количества операций» в содержании int objects.

Действительно ли Стандарт позволяет это? Или мы должны интерпретировать это как наличие более строгого требования: то есть постоянное количество операций над содержащимися объектами плюс постоянное дополнительное время?

Answer 1

Например, предположим, что мы реализуем deque, используя «вектор векторов размера K».

Это не будет правильной реализацией. Вставка в начале vector делает недействительными все указатели / ссылки в контейнере. deque требуется, чтобы не делать недействительными любые указатели / ссылки на переднюю вставку.

Но давайте пока проигнорируем это.

Но, похоже, это разрешено Стандартом, поскольку перемещение вектора размера K не перемещает ни одного из его элементов, а «требования к сложности» «устанавливаются исключительно с точки зрения количества операций» над содержащимися объектами int.

Да, это будет разрешено. Действительно, реальные реализации deque не так уж отличаются от этого (хотя они и не используют std::vector по понятным причинам). Общая схема реализации deque представляет собой массив указателей на блоки (с пространством для роста как спереди, так и сзади), причем каждый блок содержит до X элементов, а также указатели на следующие / предыдущие блоки (на сделать одноэтапную итерацию быстрой).

Если вы вставите достаточно элементов спереди или сзади, то массив указателей блоков должен увеличиться. Это потребует операции, которая представляет собой линейное время относительно количества элементов в deque, но фактически не воздействует на сами элементы, поэтому не учитывается. В спецификации ничего не сказано о сложности этой операции.

Без этого положения я не уверен, что уникальный набор функций deque (быстрая вставка вперед / назад и * 1027) * произвольный доступ) был бы осуществим.

Answer 2

Я думаю, вы немного достигли того, как вы понимаете значение областей сложности. Вы пытаетесь провести различие между «линейным временем» и «линейной сложностью», в чем я не уверен, имеет большой смысл.

Стандарт ясно, что вставка впереди постоянна, и я думаю, мы все согласны с этим. Последний отрывок просто говорит нам, что то, что каждая из этих «постоянных» операций включает внизу, просто не указано или не ограничено стандартом.

И это не является необычным. Любой алгоритм работает на некоторой основе абстракции. Даже если бы мы написали алгоритм, который сводился к отдельным машинным инструкциям, и мы сказали, что когда-либо было N машинных инструкций, сгенерированных нашим алгоритмом, мы бы go не исследовали бы, какого рода сложности каждая сложность имеет внутри процессора и добавить это в наши результаты. Мы бы не сказали, что некоторые операции в конечном итоге делают больше на квантовом молекулярном уровне, и поэтому наш алгоритм O (n) фактически равен O (N × M ³ ) или что-то подобное. Мы решили не учитывать этот уровень абстракции. И, если указанная сложность не зависит от входных данных алгоритма, это вполне нормально.

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

Изменяется ли фактическое время выполнения (которое можно было бы описать в некоторых алгоритмических терминах, если вы так выбрали) в зависимости от содержимого скопированных внутренних векторов? Ну конечно; естественно. Но это не имеет ничего общего с тем, как задача расширения внешнего вектора увеличивается в рабочей нагрузке по мере роста самого внешнего вектора.

Итак, в стандарте говорится, что он не будет копировать N или N ² или даже log N внутренних векторов, когда вы помещаете еще один впереди; это говорит о том, что количество этих операций не будет меняться в масштабе по мере роста вашей deque. Также говорится, что для целей этого правила не имеет значения, что на самом деле включает в себя копирование / перемещение внутренних векторов или насколько они велики.

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