Есть ли альтернатива для вставки и сортировки

Question

Если у меня есть vector<int> foo а также vector<int> bar оба из которых отсортированы, и я хочу объединить их в foo такой, что окончательный результат отсортирован, стандарт предоставляет мне метод для этого?

Очевидно, я могу сделать:

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

Но я надеялся, что для этого есть один шаг.

Answer 1

Это может быть быстрее использовать std::inplace_merge вместо std::sort, Если имеется дополнительная доступная память, она имеет линейную сложность, в противном случае она возвращается к NlogN.

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

Answer 2

Чтобы уточнить комментарии Мата, ваш код может выглядеть следующим образом: 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 3

Если вам нужно такое слияние, почему бы не сделать его самостоятельно?

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;
    }
}

Пример использования:

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 << " ";

Выход:

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

Живой пример: ссылка.

Answer 4

Поэтому, просмотрев все стандартные алгоритмы, я могу подтвердить, что альтернативы insert а также sort , Когда я искал стандартные алгоритмы, я заметил, что во всех алгоритмах копирования используются входные и выходные итераторы, итераторы ввода-вывода используются только при работе с одним диапазоном. (Например sort использует итераторы ввода-вывода, но любой copy использует входные итераторы и выходной итератор.)

Я хотел бы дать иллюстрацию моей точки зрения. Итак, давайте сделаем пример того, как будет выглядеть алгоритм слияния вставки с итератором ввода-вывода:

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;
            }
        }
    }
}

Об этом следует отметить две вещи func алгоритм:

1. Не уважает last1 предполагается, что за пределами выделено достаточно места last1 также содержать все элементы в диапазоне ввода
2. func Диапазон ввода-вывода нельзя вызвать с помощью back_inserter как и любой другой выходной диапазон в стандартном алгоритме

Из-за этого даже func не может быть "одношаговым алгоритмом". Это должно быть названо так:

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

Обратите внимание, что ответ Blastfurnace использует знание того, что он объединяет два отсортированных диапазона и, следовательно, имеет эквивалентную скорость для func:

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

Единственный фактический "одношаговый алгоритм" - это свернуть ответ этого Blastfurnace в функцию, которую вы могли бы вызвать, передавая контейнеры для объединения.