c++ - Время работы функции в STL


0

Какое асимптотическое время работы функции q.size() очереди приоритетов?

Источник
  •  96
  •  1
  • 7 янв 2018 2018-01-07 18:11:44
std::priority_queue::size: Complexity - Constant. — 7 янв 20182018-01-07 18:15:55.000000
О(1) вроде бы. Там же куча по сути. — 7 янв 20182018-01-07 18:14:41.000000

1 ответ

0

Для всех стандартных контейнеров size() выполняется за константное время.

  • 19 янв 2018 2018-01-19 18:19:27
@pavel Там четко написано, что начиная с С++11 - константная. Сейчас уже С++17 действующий... Мы разговариваем о современном С++ или о том, который был в прошлом тысячелетии? Это уже пустопоорожний треп и хорошая мина при плохой игре - что если какой-то контейнер оставил линейную... (при том что реально она легко делается константной). Вы же не будете рассказывать, например, что некий дорожный знак в 1970-е годы означал нечто иное, и на этом основании дезавуировать нынешние ПДД? — 19 янв 20182018-01-19 18:26:30.000000
@Mikhailo даже по этой ссылке написано "Constant or linear. (until C++11)". А gcc ради бинарной совместимости оставили линейную и дальше (не точно). — 19 янв 20182018-01-19 18:26:30.000000
@pavel Тут en.cppreference.com/w/cpp/container/list/size четко пишут, что O(1). Я говорю только о стандартных контейнерах, не самопальных. — 19 янв 20182018-01-19 18:26:30.000000
привет из очереди проверок. ответообразное, а вот верность/неверность оценивать не буду. — 19 янв 20182018-01-19 18:26:30.000000
ну спорное утверждение. для списка например. — 19 янв 20182018-01-19 18:26:30.000000