Как отсортировать вектор указатель на структуру

Question

Я пытаюсь отсортировать тип concurrent_vector, где hits_object:

struct hits_object{
        unsigned long int hash;
        int position;
};

Вот код, который я использую:

concurrent_vector<hits_object*> hits;

for(i=0;...){
    hits_object *obj=(hits_object*)malloc(sizeof(hits_object));
    obj->position=i;
    obj->hash=_prevHash[tid];
    hits[i]=obj;
}

Теперь я заполнилвверх concurrent_vector<hits_object*> с именем hits.

Но я хочу отсортировать этот concurrent_vector по свойству position !!!

Вот пример того, что находится внутри типичного объекта попаданий:

0 1106579628979812621
4237 1978650773053442200
512 3993899825106178560
4749 739461489314544830
1024 1629056397321528633
5261 593672691728388007
1536 5320457688954994196
5773 9017584181485751685
2048 4321435111178287982
6285 7119721556722067586
2560 7464213275487369093
6797 5363778283295017380
3072 255404511111217936
7309 5944699400741478979
3584 1069999863423687408
7821 3050974832468442286
4096 5230358938835592022
8333 5235649807131532071

Я хочу отсортировать это по первому столбцу («позиция» типа int).Второй столбец - это «хэш» типа unsigned long int.

. Теперь я попытался сделать следующее:

std::sort(hits.begin(),hits.end(),compareByPosition);

, где определено compareByPositionкак:

int compareByPosition(const void *elem1,const void *elem2 )
{
  return ((hits_object*)elem1)->position > ((hits_object*)elem2)->position? 1 : -1;
}

но я продолжаю получать ошибки сегментации при вводе строки std::sort(hits.begin(),hits.end(),compareByPosition);

Пожалуйста, помогите!

Answer 1

Ваша функция сравнения должна возвращать логическое значение 0 или 1, а не целое число 1 или -1, и она должна иметь строго типизированную подпись:

bool compareByPosition(const hits_object *elem1, const hits_object *elem2 )
{
    return elem1->position < elem2->position;
}

Ошибка, которую вы видели, связана сstd::sort интерпретирует все ненулевые значения, возвращаемые функцией comp, как true, что означает, что левая сторона меньше правой части.

ПРИМЕЧАНИЕ : Этот ответбыл сильно отредактирован в результате разговоров с sbi и Майком Сеймуром.

Answer 2

int (*)(void*, void*) - компаратор для функции C qsort(). В C ++ std::sort() прототип для компаратора:

bool cmp(const hits_object* lhs, const hits_object* rhs)
{
    return lhs->position < rhs->position;
}

std::sort(hits.begin(), hits.end(), &cmp);

С другой стороны, вы можете использовать std::pair struct, которая по умолчанию сравнивает свои первые поля:

typedef std::pair<int position, unsigned long int hash> hits_object;
// ...
std::sort(hits.begin(), hits.end());

Answer 3

Не зная, что такое concurrent_vector, я не могу быть уверен, что является причиной ошибки сегментации.Предполагая, что он похож на std::vector, вам необходимо заполнить его hits.push_back(obj), а не hits[i] = j;вы не можете использовать [] для доступа к элементам за пределами вектора или вообще для доступа к пустому вектору.

Функция сравнения должна быть эквивалентна a < b, возвращая логическое значение;это не функция сравнения в стиле C, возвращающая отрицательный, положительный или ноль.Кроме того, поскольку sort является шаблоном, нет необходимости в аргументах void * в стиле C;все строго типизировано:

bool compareByPosition(hits_object const * elem1, hits_object const * elem2) {
    return elem1->position < elem2->position;
}

Кроме того, вы обычно не хотите использовать new (и, конечно, никогда malloc) для создания объектов для хранения в векторе;самым простым и безопасным контейнером будет vector<hits_object> (и компаратор, который принимает в качестве аргументов ссылки, а не указатели).Если вам действительно нужно хранить указатели (потому что объекты стоят дорого для копирования и не могут быть перемещены, или потому что вам нужен полиморфизм - ни один из которых не применим к вашему примеру), либо используйте умные указатели, такие как std::unique_ptr, либо убедитесь, что вы deleteих, как только вы закончите с ними.

Answer 4

Третий аргумент, который вы передаете std::sort(), должен иметь сигнатуру, аналогичную operator<():

bool is_smaller_position(const hits_object* lhs, const hits_object* rhs)
{
  return lhs->position < rhs->position;
}

Когда вы храните указатели в векторе, вы не можете перегрузить operator<(), потому что меньше, чем фиксировано для всех встроенных типов.

---

На sidenote: Не используйте malloc() в C ++ , вместо этого используйте new.Также мне интересно, почему вы не используете объекты , а не указатели.Наконец, если concurrent_vector - это что-то вроде std::vector, вам нужно явно сделать так, чтобы оно расширялось для размещения новых объектов.Вот как бы выглядел ваш код:

concurrent_vector<hits_object*> hits;

for(i=0;...){
    hits_object obj;
    obj.position=i;
    obj.hash=_prevHash[tid];
    hits.push_back(obj);
}

Answer 5

Это выглядит не так:

for(i=0;...){
    hits_object *obj=(hits_object*)malloc(sizeof(hits_object));
    obj->position=i;
    obj->hash=_prevHash[tid];
    hits[i]=obj;
}

здесь вы уже сортируете массив на основе 'i', потому что вы устанавливаете позицию в i, а также она становится индексом попаданий!

также, почему, используя malloc, вы должны использовать вместо него (/ delete).Затем вы можете создать простой конструктор для структуры, чтобы инициализировать hit_object

например

struct hits_object
{
   int position;
   unsigned int hash;

   hits_object( int p, unsigned int h ) : position(p), hash(h) {;}
};

, а затем написать вместо

hits_object* obj = new hits_object( i, _prevHash[tid] );

или даже

hits.push_back(  new hits_object( i, _prevHash[tid] ) );

Наконец, ваша функция сравнения должна использовать тот же тип данных, что и вектор, для своих аргументов

bool cmp( hits_object* p1, hits_object* p2 )
{
  return p1->position < p2->position;
}