c++ - queues - ¿Hay una alternativa para insertar y luego ordenar

merge sort algoritmo c++

Question

Si tengo una vector<int> bar vector<int> foo y vector<int> bar ambas ordenadas, y quiero fusionarlas en foo para que el resultado final esté ordenado, ¿el estándar me proporciona un método para hacerlo?

Obviamente puedo hacer:

foo.insert(foo.end(), bar.begin(), bar.end());
sort(foo.begin(), foo.end());

Pero esperaba que hubiera un algoritmo de un paso para lograr esto.

Answer 1

Para profundizar en el comentario de Mat, su código podría verse así usando std::merge :

std::vector<int> result;
std::merge(
    foo.begin(), foo.end(),
    bar.begin(), bar.end(),
    std::back_inserter(result));

foo = result; // if desired

Answer 2

Puede ser más rápido usar std::inplace_merge lugar de std::sort . Si hay memoria adicional disponible, tiene complejidad lineal; de lo contrario, vuelve a caer en NlogN.

auto middle = foo.insert(foo.end(), bar.begin(), bar.end());
std::inplace_merge(foo.begin(), middle, foo.end());

Answer 3

Si necesita este tipo de combinación, ¿por qué no hacer una?

template <class Vector>
void insert_sorted(Vector& where, Vector& what)
{
    typename Container::iterator src = what.begin();
    typename Container::iterator src_end = what.end();

    size_t index = 0;

    while(src != src_end)
    {
        if(*src < where[index])
        {
            where.insert(where.begin() + index, *src);
            ++src;
        }

        ++index;
    }
}

Uso de muestra:

vector<int> foo{ 0, 5, 7, 9, 11, 14 };
vector<int> bar{ 1, 2, 4, 8, 10, 12 };

insert_sorted(foo, bar);

for(vector<int>::iterator i = foo.begin(); i != foo.end(); ++i)
    cout << *i << " ";

Salida:

0 1 2 4 5 7 8 9 10 11 12 14

Muestra en vivo: enlace .

Answer 4

Entonces, después de revisar todos los algoritmos estándar, puedo confirmar que no hay alternativa para insert y sort . Mientras buscaba los algoritmos estándar, noté que todos los algoritmos de copia usan iteradores de entrada e iteradores de salida la única vez que se usan los iteradores de entrada-salida cuando se está operando un solo rango. (Por ejemplo, la sort utiliza iteradores de entrada-salida, pero cualquier copy utiliza iteradores de entrada y un iterador de salida).

Me gustaría dar una ilustración de mi punto. Así que hagamos un ejemplo de cómo se vería un algoritmo de fusión de inserción con un iterador de entrada-salida:

template <class BidirectionalIterator, class InputIterator>
void func(BidirectionalIterator first1, BidirectionalIterator last1, InputIterator first2, InputIterator last2){
    bool is1Empty = first1 == last1;
    bool is2Empty = first2 == last2;
    BidirectionalIterator end = next(last1, distance(first2, last2));

    if (!is1Empty){
        --last1;
    }

    if (!is2Empty){
        --last2;
    }

    while (!is1Empty || !is2Empty){
        --end;
        if (!is1Empty){
            if (!is2Empty && *last2 > *last1){
                *end = *last2;

                if (last2 == first2){
                    is2Empty = true;
                }else{
                    --last2;
                }
            }else{
                *end = *last1;

                if (last1 == first1){
                    is1Empty = true;
                }
                else{
                    --last1;
                }
            }
        }else{
            *end = *last2;

            if (last2 == first2){
                is2Empty = true;
            }
            else{
                --last2;
            }
        }
    }
}

Dos cosas deben tenerse en cuenta sobre este algoritmo func :

1. No respeta last1 se supone que se asigna suficiente espacio más allá de last1 para también contener todos los elementos en el rango de entrada
2. El rango de entrada-salida de func no puede back_inserter con un back_inserter como cualquier otro rango de solo salida en un algoritmo estándar

Debido a esto, incluso func no puede ser un "algoritmo de un paso". Debe ser llamado así:

 foo.resize(foo.size() + bar.size());
 func(foo.begin(), next(foo.begin(), foo.size() - bar.size()), bar.begin(), bar.end());

Tenga en cuenta que la respuesta de Blastfurnace aprovecha el conocimiento de que está fusionando dos rangos ordenados, y como tal tiene una velocidad equivalente a func :

auto middle = foo.insert(foo.end(), bar.begin(), bar.end());
inplace_merge(foo.begin(), middle, foo.end());

El único "algoritmo de un paso" real es convertir la respuesta de Blastfurnace en una función que podría llamar pasando en los contenedores que se fusionarán.