Puedo pensar en tres operaciones en C ++ que pueden describirse en cierto sentido como de complejidad 'constante'. He visto un debate (*) sobre lo que esto significa, y me parece que podríamos decir "todas estas operaciones son constantes, pero algunas son más constantes que otras": -)

(Edit 2: Si ya crees que sabes la respuesta, lee parte del debate sobre esta pregunta antes de apresurarte demasiado pronto: ¿Qué estructura de datos, exactamente, son deques en C ++? Muchas personas, con puntajes bastante altos, discuten sobre lo que significa "constante". ¡Mi pregunta no es tan obvia como podría pensar!)

(Edita: No necesito una cartilla sobre lo que significa "complejidad". Quiero una respuesta clara, tal vez con citas del estándar C ++, que nos digaexactament lo que se supone que esconstant. ¿Ticks del procesador, tiempo del mundo real o algo más? En otros hilos, algunas personas han argumentado quehor es totalmente irrelevante para lo que exige el estándar C ++.)

¿Estas garantías de complejidad en el estándar se aplican a tiempo de ejecución de la operación? ¿O simplemente especifican el número (máximo) de copias / movimientos que podrían ocurrir de los objetos contenidos? ¿Y qué significa exactamente 'amortizado'?

1. Dado un (no vacío)vector<int> v, lo siguiente es claramente constante en tiempo de ejecución:

swap(v.front(), v.back());

(¡aunque un pedante podría señalar que depende de si los datos están en el caché o si se intercambian o lo que sea!).

2. Dado unlist<int> l, haciendo unpush_back es sencillo. Se asigna exactamente un nuevo elemento y se barajan algunos punteros en la lista vinculada. Cada push_front implica una asignación, siempre de la misma cantidad de memoria, por lo que es claramente bastante "constante". Pero, por supuesto, el tiempo para hacer la asignación podría ser bastante variable. Es posible que la administración de la memoria tenga que tomar mucho tiempo para encontrar memoria libre adecuada.

3. Pero haciendo unpush_back en unvector<int> es aún más impredecible. La mayoría de las veces, será muy rápido, pero de vez en cuando tendrá que reasignar espacio para todos los datos y copiar cada elemento en una nueva ubicación. Por lo tanto, es menos predecible en términos de tiempo de ejecución que una solalist::push_front, pero todavía se conoce como constante (amortizado). @De medi, agregar muchos datos a un vector tomará una complejidad que es independiente de la cantidad agregada, y es por eso que se llama tiempo 'constante amortizado'. (¿Tengo razón?)

Y finalmente, pregunté sobreint para evitar las complejidades de tener otro tipo. Por ejemplo, unavector< vector<int> > podría ser un poco más complicado de razonar porque cada elemento del vector (de vectores) podría tener un tamaño diferente y, por ejemplo, intercambiar dos elementos no es tan constante como en el caso 1. encima. Pero idealmente, podríamos responder por todosvector<T>, No soloT=int.

(*) Para ver un ejemplo de los debates, vea los comentarios a estas respuestas: ¿Qué estructura de datos, exactamente, son deques en C ++?