Сортировка двух векторов на месте

Question

Есть два вектора std::vector<int>. Как отсортировать их оба так, чтобы результат был такой, как будто бы сортировался один вектор-конкатенация двух? Без использования 3 вектора/линейной памяти.

Пример:

a: 3, 1, 5

b: 2, 9, 3, 1

Результат:

a: 1, 1, 2

b: 3, 3, 5, 9

Answer 1

Организуете доступ по индексу к виртуальному объединению

void put(idx, value)
   if (idx < len1)
       A[idx] = value
   else
       B[idx - len1] = value

int get(idx)
   return  (idx < len1)? A[idx] : B[idx - len1] ;

И применяете сортировку кучей, или вставками (медленно), или быструю (памяти log(n))

Answer 2

Предисловие

Можно создать свой итератор. Не нужно относится серьёзно к тому что получилось. Нормальный итератор лучше сделать шаблоном и конструировать от двух пар итераторов. Или лучше ввести ввести понятия range и view из C++ 20. Для них определена операции views::join и views::concat, которые объединяют диапазоны. Пример такого кода в конце ответа.

Самодельный итератор

Пример будет минимальным, под конкретные типы. Начнём с определения класса итератора, вспомогательных функций и тестового кода. Ещё есть оператор для печати вектора, он опущен:

class Iterator {
public:
    Iterator(std::vector<int> &a1, std::vector<int> &a2, int i);

private:
    std::vector<int> *a1;
    std::vector<int> *a2;
    int i;
};

Iterator::Iterator(std::vector<int> &a1, std::vector<int> &a2, int i)
: a1(&a1), a2(&a2), i(i) {
}

Iterator begin(std::vector<int> &a1, std::vector<int> &a2) {
    return Iterator(a1, a2, 0);
} 

Iterator end(std::vector<int> &a1, std::vector<int> &a2) {
    return Iterator(a1, a2, a1.size() + a2.size());
} 

int main() {
    std::vector<int> a1 = {3, 1, 5};
    std::vector<int> a2 = {2, 9, 3, 1};

    std::cout << a1 << " | " << a2 << '\n';

    std::sort(begin(a1, a2), end(a1, a2));

    std::cout << a1 << " | " << a2 << '\n';
}

Конструктор принимает ссылки на вектора, чтобы не было соблазна передать nullptr. В теле класса хранятся указатели, чтобы итератор можно было копировать. Поле i - номер элемента на который указывает итератор.

Код не компилируется, ошибка указывает на отсутствие operator !=. Добавим его:

class Iterator {
    ...
    friend bool operator !=(const Iterator &it1, const Iterator &it2);
    ...
};

bool operator !=(const Iterator &it1, const Iterator &it2) {
    return it1.i != it2.i;
}

Следующая ошибка - нет operator -. Добавим его и ещё несколько штук:

    friend int operator -(const Iterator &it1, const Iterator &it2);
    friend Iterator operator +(const Iterator &it1, int i);
    friend Iterator operator -(const Iterator &it1, int i);
    friend bool operator ==(const Iterator &it1, const Iterator &it2);
    Iterator &operator ++();

Следующая ошибка интереснее: std::iterator_traits<Iterator> не содержит тип value_type. Читаем документацию по iterator_traits: нужно объявить пять типов в классе итератора:

    using difference_type = int;
    using value_type = int;
    using pointer = int *;
    using reference = int &;
    using iterator_category = std::random_access_iterator_tag;

Ещё ошибки и ещё операторы:

    int &operator *();
    friend bool operator <(const Iterator &it1, const Iterator &it2);
    Iterator &operator --();

operator * единственный интересный:

int &Iterator::operator *() {
    return (i < static_cast<int>(a1->size())) ? (*a1)[i] : (*a2)[i - a1->size()];
}

Готово. Код скомпилировался и отработал:

3, 1, 5 | 2, 9, 3, 1
1, 1, 2 | 3, 3, 5, 9

Программа целиком:

// g++ -pedantic -Wall -Wextra -std=c++17 sort_vectors.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

std::ostream &operator <<(std::ostream &os, const std::vector<int> &a) {
    bool first = true;
    for (int v : a) {
        if (first) {
            first = false;
        } else {
            os << ", ";
        }
        os << v;
    }
    return os;
}

class Iterator {
public:
    using difference_type = int;
    using value_type = int;
    using pointer = int *;
    using reference = int &;
    using iterator_category = std::random_access_iterator_tag;

    Iterator(std::vector<int> &a1, std::vector<int> &a2, int i);

    friend bool operator ==(const Iterator &it1, const Iterator &it2);
    friend bool operator !=(const Iterator &it1, const Iterator &it2);
    friend bool operator <(const Iterator &it1, const Iterator &it2);
    friend int operator -(const Iterator &it1, const Iterator &it2);
    friend Iterator operator +(const Iterator &it1, int i);
    friend Iterator operator -(const Iterator &it1, int i);
    Iterator &operator ++();
    Iterator &operator --();
    int &operator *();

private:
    std::vector<int> *a1;
    std::vector<int> *a2;
    int i;
};

Iterator::Iterator(std::vector<int> &a1, std::vector<int> &a2, int i)
: a1(&a1), a2(&a2), i(i) {
}

bool operator ==(const Iterator &it1, const Iterator &it2) {
    return it1.i == it2.i;
}

bool operator !=(const Iterator &it1, const Iterator &it2) {
    return it1.i != it2.i;
}

bool operator <(const Iterator &it1, const Iterator &it2) {
    return it1.i < it2.i;
}

int operator -(const Iterator &it1, const Iterator &it2) {
    return it1.i - it2.i;
}

Iterator operator +(const Iterator &it, int i) {
    return Iterator(*it.a1, *it.a2, it.i + i);
}

Iterator operator -(const Iterator &it, int i) {
    return Iterator(*it.a1, *it.a2, it.i - i);
}

Iterator &Iterator::operator ++() {
    ++i;
    return *this;
}

Iterator &Iterator::operator --() {
    --i;
    return *this;
}

int &Iterator::operator *() {
    return (i < static_cast<int>(a1->size())) ? (*a1)[i] : (*a2)[i - a1->size()];
}

Iterator begin(std::vector<int> &a1, std::vector<int> &a2) {
    return Iterator(a1, a2, 0);
} 

Iterator end(std::vector<int> &a1, std::vector<int> &a2) {
    return Iterator(a1, a2, a1.size() + a2.size());
} 

int main() {
    std::vector<int> a1 = {3, 1, 5};
    std::vector<int> a2 = {2, 9, 3, 1};

    std::cout << a1 << " | " << a2 << '\n';

    std::sort(begin(a1, a2), end(a1, a2));

    std::cout << a1 << " | " << a2 << '\n';
}

Почти пример кода из C++ 20

Запустить компилятор с поддержкой C++ 20 ranges мне не удалось. Код ниже работает с библиотекой ericniebler/range-v3 которая была прототипом ranges из стандарта. Сортировка вызывается косвенно через ranges::sort:

// g++ -pedantic -Wall -Wextra -std=c++14 -Irange-v3/include ranges.cpp

#include <iostream>
#include <vector>

#include <range/v3/all.hpp>

int main() {
    std::vector<int> a1 = {3, 1, 5};
    std::vector<int> a2 = {2, 9, 3, 1};

    std::cout << ranges::views::all(a1) << ranges::views::all(a2) << '\n';

    ranges::sort(ranges::views::concat(a1, a2));

    std::cout << ranges::views::all(a1) << ranges::views::all(a2) << '\n';
}

БЛОГ НА HUSL

Сортировка двух векторов на месте

Ответы (2 шт):

Предисловие

Самодельный итератор

Почти пример кода из C++ 20