2

Добрый день. Имеется структура:

struct part
{
    std::string name;
    unsigned int number;
};

Из неё формируется не пустой вектор:

std::vector<part> arr(n);

Вызывается qsort для сортировки по полю number:

qsort(&arr, arr.size(), sizeof(part), comp);

Используя следующий компаратор:

int comp( const void* a, const void* b )
{
    return ((part*)a)->number - ((part*)b)->number;
}

Как мне подсказал гугл компаратор правильный, но из раза в раз я получаю SIGSEGV. Помогите понять в чём ошибка, мб оно ещё кому поможет. Без сортировки всё работает. При включении в код сортировки в отладчике массив обозначается недоступным после неё.

Полный код:

#include <cstdlib>
#include <string>
#include <vector>

class Rank
{
public:
    static std::string nthRank(const std::string st, std::vector<int> we, int n);
};

struct part
{
    std::string name;
    unsigned int number;
};

int comp( const void* a, const void* b )
{
    return (    ((part*)a)->number - ((part*)b)->number   );
}

std::string Rank::nthRank(const std::string st, std::vector<int> we, int n)
{
    if(st.empty()) return "No participants";
    if(we.size()<(unsigned)n) return "Not enough participants";

    std::vector<part> arr(we.size());
    unsigned int com = 0;

    for(unsigned int i = 0; i < st.size() ; i++)
    {
          if(st[i]!=',')
          {
              arr[com].number +=  std::tolower(st[i])-96 + 1; //1 for length1
              arr[com].name += st[i];
          }
          else
          {
              arr[com].number *= we [com];
              ++com;
          }
    }
    qsort(&arr, arr.size(), sizeof(part), comp);
    return arr[n].name;
}

int main(void)
{
    std::string me("COLIN,AMANDBA,AMANDAB,CAROL,PauL,JOSEPH");
    std::vector<int> arr={1, 4, 4, 5, 2, 1};
    me=Rank::nthRank(me, arr, 4);
}

Класс Rank - часть задания.

3
  • Приведение unsigned к int положения дел тоже не меняет
    – Totem
    25 дек 2017 в 8:42
  • полный компилируемый пример для воспроизведения приведите. + почему qsort, не std::sort?
    – user227465
    25 дек 2017 в 8:58
  • @GreenDragon на второй вопрос: до этого основным языком был Си, от него и осталось
    – Totem
    25 дек 2017 в 9:15

3 ответа 3

5

qsort() — применима только для сортировки Си-массивов (вида strucr part foo [100]). Для сортировки STL-контейнеров, в том числе и векторов используется std::sort(). На практике во всех распространённых реализациях это тот же qsort().

#include <vector>
#include <algorithm>

bool comp( const part & a, const part b )
{
    return a.number < b.number;
}

int main () {
    // ...
    std::vector<part> arr(n);

    // В классическом С++ стиле
    std::sort(arr.begin(), arr.end(), comp);
    // В C++11 стиле с лямдой
    std::sort(v.begin(), v.end(), 
            [](const part &a, const part &b) { return a.number < b.number; });
    // ...
}

Вообще говоря, если элементами вектора являются объекты POD-типа (тривиального типа в терминологии С++11), то для сортировки оного формально можно использовать и qsort(), однако это крайне некрасиво и при последующем внесении изменений в код чревато ошибками.

struct part
{
    //! При замене на std::string с точки зрения стандарта в qsort () будет UB!
    char name[32];
    unsigned number;
};

int comp( const void* a, const void* b )
{
    const unsigned anum=((part*)a)->number, bnum=((part*)b)->number;
    return anum>bnum ? 1 : (anum == bnum ? 0 : -1);
}

// ...
std::vector<part> arr;
// ...
// Не надо так делать! Даже если формально ошибки нет.
qsort(&arr[0], arr.size(), sizeof(part), comp);
10
  • Спасибо, как раз хотел компаратор лямбдой написать, но всё же интересно, почему не работает qsort()?
    – Totem
    25 дек 2017 в 9:16
  • qsort() применима только для сортировки Си-массивов.
    – Fat-Zer
    25 дек 2017 в 9:18
  • 2
    qsort может работать и с плюсовыми классами. Главное, что бы они были POD типами (такими, которые можно безопасно копировать с помощью memcpy). Почему так? просто нужно посмотртеть на сорци (в данном случае это от Эпла, но сути не меняет). Если в структуре есть std::string, то она уже не POD, хотя, из-за SSO, иногда может все работать как ожидается.
    – KoVadim
    25 дек 2017 в 11:22
  • 2
    @KoVadim правда, не могу найти причин, почему для pod'ов в векторе нельзя было бы использовать, но ни как не могу отделаться от ощущения, что как-то это очень грязно....
    – Fat-Zer
    25 дек 2017 в 12:00
  • 1
    @Fat-Zer Этот компаратор по-прежнему не будет работать правильно, если при выполнении вычитания возникнет переполнение. 25 дек 2017 в 21:45
2

Рассмотрим следующий пример (1) кода:

vector<int> vect = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
auto pvect       = &vect;
auto pvect0      = &vect[0];

*pvect0 = 42;
cout << vect[0] << endl;

cout << pvect    << endl;
cout << pvect0   << endl;

cout << sizeof(vect)              << endl;
cout << sizeof(int) * vect.size() << endl;

Одним из возможных выводов данной программы будет следующий:

42
0x7ffc9d7aa3c0
0x5624574c0c20
24
40

Можно заметить, что адрес объекта vect не совпадает с адресом первого элемента вектора vect. Также размер в байтах объекта vect не совпадает с размером в байтах элемента вектора vect, умноженного на количество элементов в векторе vect.

Данные различия обусловлены тем, что элементы вектора vect хранятся отдельно от объекта vect. Обычно внутри объекта vect находится указатель на область памяти, в которой собственно и хранятся его элементы.

Это первая причина, по которой не работает qsort. Здесь:

qsort(&arr, arr.size(), sizeof(part), comp);

вы передаёте qsort вовсе не адрес первого элемента вектора arr, а адрес объекта arr.

Отдельное хранение элементов контейнера свойственно не только для vector но и для string тоже.

Такая архитектура классов vector и string обычно означает, что нельзя просто так взять и побайтово скопировать один экземпляр класса в другой. То есть, в терминах стандарта языка классы vector и string не являются тривиальными типами (trivial types). Подробнее о тривиальных типах: http://en.cppreference.com/w/cpp/concept/TrivialType. Небольшой пример (2).

В стандарте языка явно оговорено (n4659 28.8/3), что поведение программы не определено, если при помощи функции qsort пытаются отсортировать массив, элементы которого не тривиального типа.

The behavior is undefined unless the objects in the array pointed to by base are of trivial type.

2

Как мне подсказал гугл компаратор правильный

В дополнение к вышесказанному можно заметить, что компаратор у вас совершенно НЕ правильный. Так как поле number имеет тип unsigned int, вычитание ((part*)a)->number - ((part*)b)->number; будет проводится в домене беззнакового типа и давать беззнаковый результат. Т.е. никакого компаратора у вас так не получится.

(Последующее запихивание результата такого вычитания в тип int может "спасти" ситуацию, приведя результат к требуемому виду, но, во-первых, языком это не гарантируется и, во-вторых, при достаточно большой разнице между сравниваемыми значениями все равно будет давать белиберду.)

Бросьте дурную манеру писать компараторы через вычитание, что бы вам там ни говорил Гугл. Универсальная идиома для написания типонезависимых "трехзначных" компараторов, если вам такой вдруг понадобится, выглядит так

int comp( const void* a, const void* b )
{
  const part 
    *pa = static_cast<const part *>(a),
    *pb = static_cast<const part *>(b);
  return (pa->number > pb->number) - (pa->number < pb->number);
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.