c++ - Diferencia entre std:: merge y std:: inplace_merge?

algorithm c++11

Question

¿Cuál es la diferencia entre std::merge y std::inplace_merge en términos de complejidad y resultado cuando se ejecuta en dos rangos consecutivos con elementos que son todos diferentes? (No soy un hablante nativo de inglés y no estoy seguro de entender claramente lo que significa "in situ")

Answer 1

Observando las referencias de std::merge y std::inplace_merge , verá las siguientes complejidades:
Para std::merge :

Como máximo std :: distance (first1, last1) + std :: distance (first2, last2) - 1 comparaciones.

Y para std::inplace_merge :

Comparaciones exactas de N-1 si hay suficiente memoria adicional disponible; de ​​lo contrario, N · log (N) donde N = std :: distance (first, last).

if enough additional memory is available tiene un significado muy específico, de las notas en esa página:

Esta función intenta asignar un búfer temporal, generalmente llamando std :: get_temporary_buffer. Si la asignación falla, se elige el algoritmo menos eficiente.

std::get_temporary_buffer asigna la memoria dinámicamente (es importante saber si desea usar std::inplace_merge en un bucle cerrado o si tiene requisitos de memoria restringidos).

Por último, las páginas de referencia no mencionan esto ( edit : cppreference se ha actualizado según el comentario a continuación), pero en std::merge no creo que d_first pueda superponerse entre [first1, last1) o [first2, last2) . Esto significa que std::merge debe generar un rango diferente al de cualquiera de los rangos de entrada.
También significa la siguiente llamada (para algunos RandomAccessContainer a ):

    std::inplace_merge(a.begin(), a.begin() + n, a.end());

no es equivalente a:

    std::merge(a.begin(), a.begin() + n,
               a.begin() + n, a.end(), a.begin());

porque no puedes salir en a si estás leyendo de ella. Necesitarías

    decltype(a) b;
    std::merge(a.begin(), a.begin() + n,
               a.begin() + n, a.end(),
               std::back_inserter(b));

por ejemplo.

Curiosamente, esta referencia indica que los rangos no se superpondrán (justo por encima de la sección de valor de retorno), lo que parece más estricto de lo necesario porque significa que los dos rangos de entrada tampoco se superpondrán. Además, en la sección de carreras de datos, se establece claramente que solo se accede a los dos rangos de entrada, por lo que este ejemplo ligeramente artificial (artificial):

    std::merge(a.begin(), a.end(), a.begin(), a.end(), b.begin());

Sería ilegal según eso, pero no estoy convencido. Ninguna de estas referencias es la norma y, desafortunadamente, no tengo una copia de ella como referencia, pero quizás alguien con acceso pueda verificar estos requisitos.

EDITAR :
Con el útil indicador de TemplateRex a un borrador del estándar, ahora puedo decir

N3797 25.4.4 [alg.merge]

2 Requiere : [...] El rango resultante no se superpondrá con ninguno de los rangos originales.

Lo que confirma exactamente lo que estaba diciendo.