Daily bit(e) C++. Объединение сортированных списков

Daily bit(e) C++ #16, распространенный вопрос на собеседованиях: объединение отсортированных списков с использованием C++.

Сегодня мы рассмотрим еще один распространенный вопрос на собеседованиях – объединение отсортированных списков.

Однако, поскольку это C++, мы немного усложним задачу и добавим требование избегать ненужных копирований.

Постановка задачи

Даны отсортированные списки в виде std::vector<std::forward_list<>>, создайте объединенный отсортированный std::forward_list<>.

Ваша реализация должна учитывать сложность «большое O» и избегать ненужных копирований.

Для этого входные данные даются по значению и могут быть изменены.

Прежде чем прочесть решение, попробуйте решить задачу самостоятельно: https://compiler-explorer.com/z/5raraWG5f.

Решение

У нас есть два варианта решения этой задачи.

Мы можем либо многократно выбирать список с наименьшим ведущим элементом, что приведет к n (количество элементов) повторений log(k) (выбор наименьшего элемента).

Или мы можем многократно объединять пары списков, что приводит к log(k) (поскольку мы делим количество списков на два на каждой итерации) повторений n операций во время объединения.

Есть несколько мест, где нам следует быть осторожными с копиями. Во-первых, при перемещении списков нам нужно их поменять местами или переместить.

Во-вторых, для первого решения нам понадобится упорядоченная структура данных. Всякий раз, когда мы извлекаем первый элемент из списка, нам нужно извлечь список из структуры данных и только затем изменить его. Это потенциальное место, куда могут быть внедрены копирования, поэтому нам нужно быть осторожными.

Решение А (многократно выбираем список с наименьшим ведущим элементом):

std::forward_list<int> merge(std::vector<std::forward_list<int>> in) 
{
    using fwlst = std::forward_list<int>;

    // Пользовательский компаратор, сравнение по первому элементу
    auto cmp = [](const fwlst& l, const fwlst& r) {
        return l.front() < r.front();
    };
    // Просмотр непустых списков, если фильтровать здесь,
    // то потом не придется проверять.
    auto non_empty = in |
      std::views::filter(std::not_fn(&fwlst::empty)) |
      std::views::common;
    // Забираем входные данные с помощью std::move_iterator,
    // избегая копирования списков.
    std::multiset<fwlst,decltype(cmp)> q(
        std::move_iterator(non_empty.begin()), 
        std::move_iterator(non_empty.end()), 
        cmp);

    fwlst result;
    fwlst::iterator tail = result.before_begin();
    while (!q.empty()) 
    {
        // Извлекаем узел, содержащий элемент, не делая копии.
        auto top = q.extract(q.begin());

        // Соединяем первый элемент списка top с result
        result.splice_after(tail,
                            top.value(), top.value().before_begin());
        ++tail;

        if (!top.value().empty())
           q.insert(std::move(top)); // помещаем назад
    }
    // Каждый элемент является минимальным один раз,
    // поэтому основной цикл будет повторяться O(n) раз,
    // где n — общее количество элементов.
    // Вставка — наша единственная непостоянная операция,
    // а это значит, что в итоге мы получим O(n*logk),
    // где k — количество списков.
    return result;
}

Открыть решение на Compiler Explorer.

Решение Б (многократное объединение пар списков):

std::forward_list<int> merge_binary(
  std::vector<std::forward_list<int>> in) 
{
    auto tail = in.begin();
    auto end = in.end();
    // Пока у нас есть более одного списка
    while (std::distance(in.begin(), end) > 1) 
    {
        auto it = in.begin();
        // Берем пару списков
        while (it != end && std::next(it) != end) 
        {
            // Объединяем
            it->merge(*std::next(it));
            // и перемещаем в начало массива
            tail->swap(*it);
            ++tail;
            std::advance(it, 2);
        }
        // Если у нас нечетное количество списков
        if (it != end) 
        {
            tail->swap(*it);
            ++tail;
        }
        // Новый конец находится за последним перемещенным списком.
        end = tail;
        tail = in.begin();
    }
    // Содержимое основного цикла — O(n),
    // поскольку каждое слияние — O(m),
    // где m — общее количество элементов в обоих списках.
    // Мы повторяем основной цикл O(logk) раз, так как
    // на каждой итерации мы делим количество списков на два.
    // Следовательно, снова O(n*logk).
    return in[0];
}

Открыть решение на Compiler Explorer.

Теги