Не удаётся отсортировать std::vector в C++

Question

Я решал задачу со Степика. Её ТЗ выглядит следующим образом:

Устойчивая сортировка

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

Техническая часть

Вам необходимо реализовать функцию sort_vector со следующей семантикой:

void sort_vector(vector <vector <int> > &vec)

Функция должна устойчиво отсортировать вектор по неубыванию суммы его элементов. Вложенные вектора сортировать не надо. Гарантируется, что размер большого вектора, а также всех вложенных не превосходит 100. Смотрите пример для лучшего понимания условия. В примере первое число n - количество векторов. В следующих n строках описаны сами вектора. Описание каждого вектора начинается с числа k - количества элементов в нем. Следующие k чисел - сами элементы. Вам не требуется считывать из входного потока эти вектора, мы это сделаем за вас.

Sample Input:

4

3 3 2 1

2 1 3

1 5

3 1 2 3

Sample Output:

1 3

5

3 2 1

1 2 3

Я написал следующий код:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int sum(const std::vector<int>& vector) {
    int sum = 0;
    for (const int& x: vector) sum += x;
    return sum;
}
void sort_vector(vector < vector <int> > &vec) {
    sort(vec.begin(), vec.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
        return (sum(a) < sum(b));
    });
}

VS Code говорит, что всё ок:

А Степик выдаёт длиннющую ошибку:

Compilation error
main.cpp:7:14: error: expected unqualified-id before ‘throw’
 #define sort throw 1; sort
              ^
In file included from /usr/include/c++/6/bits/stl_algo.h:60:0,
                 from /usr/include/c++/6/algorithm:62,
                 from main.cpp:10:
/usr/include/c++/6/bits/algorithmfwd.h:803:9: error: expected constructor, destructor, or type conversion before ‘(’ token
     sort(_RAIter, _RAIter);
         ^
main.cpp:7:14: error: expected unqualified-id before ‘throw’
 #define sort throw 1; sort
              ^
In file included from /usr/include/c++/6/bits/stl_algo.h:60:0,
                 from /usr/include/c++/6/algorithm:62,
                 from main.cpp:10:
/usr/include/c++/6/bits/algorithmfwd.h:807:9: error: expected constructor, destructor, or type conversion before ‘(’ token
     sort(_RAIter, _RAIter, _Compare);
         ^
main.cpp:7:14: error: expected unqualified-id before ‘throw’
 #define sort throw 1; sort
              ^
In file included from /usr/include/c++/6/algorithm:62:0,
                 from main.cpp:10:
/usr/include/c++/6/bits/stl_algo.h:4697:9: error: expected constructor, destructor, or type conversion before ‘(’ token
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
         ^
main.cpp:7:14: error: expected unqualified-id before ‘throw’
 #define sort throw 1; sort
              ^
In file included from /usr/include/c++/6/algorithm:62:0,
                 from main.cpp:10:
/usr/include/c++/6/bits/stl_algo.h:4727:9: error: expected constructor, destructor, or type conversion before ‘(’ token
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
         ^
main.cpp: In function ‘void sort_vector(std::vector<std::vector<int> >&)’:
main.cpp:20:6: error: ‘sort’ was not declared in this scope
     });

Как избавиться от этой синтаксической ошибки?

Answer 1

Если стандартные способы использовать нельзя, вы можете написать алгоритм самостоятельно. К счастью, за вас уже все придумали, осталось лишь выбрать нужный, а на википедии для многих из них уже есть примеры готовой реализаии (в т.ч. и на C++)

Например можно использовать сортировку слиянием (merge sort)

Простейший вариант пишется за 10 минут менее чем в 100 строк:


#include <iostream>
#include <vector>

using namespace std;

int sum(const vector<int>& vec) {
    int total = 0;
    for (const int& x : vec) total += x;
    return total;
}

void merge(vector<vector<int>>& vec, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<vector<int>> L(n1);
    vector<vector<int>> R(n2);

    for (int i = 0; i < n1; ++i)
        L[i] = vec[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = vec[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (sum(L[i]) <= sum(R[j])) {
            vec[k] = L[i];
            i++;
        } else {
            vec[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        vec[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        vec[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(vector<vector<int>>& vec, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(vec, left, mid);
        mergeSort(vec, mid + 1, right);

        merge(vec, left, mid, right);
    }
}

void sort_vector(vector<vector<int>>& vec) {
    if (vec.empty()) return;
    mergeSort(vec, 0, vec.size() - 1);
}

int main() {
    vector<vector<int>> vec = {
        {3, 2, 1},
        {1, 3},
        {5},
        {1, 2, 3}
    };

    sort_vector(vec);

    for (const auto& v : vec) {
        for (int num : v) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

При этом данный вид сортировки по умолчанию является устойчивым, так что об этом вам думать не придется (См. Википедию):

Достоинства:

...

Устойчивая - сохраняет порядок равных элементов (принадлежащих одному классу эквивалентности по сравнению).

БЛОГ НА HUSL

Не удаётся отсортировать std::vector в C++

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

Например можно использовать сортировку слиянием (merge sort)