Eu tenho um aplicativo (C ++) que acho que seria bem servido por um STLpriority_queue. A documentação diz:

Priority_queue é um adaptador de contêiner, o que significa que ele é implementado sobre algum tipo de contêiner subjacente. Por padrão, esse tipo subjacente é vetor, mas um tipo diferente pode ser selecionado explicitamente.

e

Filas prioritárias são um conceito padrão e podem ser implementadas de várias maneiras diferentes; essa implementação usa pilhas.

Eu tinha anteriormenteassumido estetop() éO(1), e essapush() seria umO(logn) (as duas razões pelas quais escolhi opriority_queue em primeiro lugar) - mas a documentação não confirma nem nega essa suposição.

Indo mais fundo, os documentos do conceito Sequência dizem:

As complexidades da inserção e eliminação de um único elemento dependem da sequência.

opriority_queue usa umvector (por padrão) como um heap, que:

... suporta acesso aleatório a elementos, inserção e remoção constantes de tempo no final e inserção e remoção linear de tempo no início ou no meio.

Estou deduzindo que, usando o padrãopriority_queue, top() éO(1) epush() éO(n).

Questão 1: Isso está correto? (top() o acesso éO(1) epush() éO(n)?)

Questão 2: Eu seria capaz de alcançarO(logn) eficiência empush() se eu usasse umset (oumultiset) em vez de umvector para a implementação dopriority_queue? Quais seriam as consequências de fazer isso? Que outras operações sofreriam como consequência?

N.B .: Estou preocupado com a eficiência do tempo aqui, não com o espaço.